Q&A
すみません、回答した後に思ったのですが、
斜め方向は本質的には不要な気がしました。ポイントは「格子を少し細かくする」点だと思います。
フリーグリッドのルート探査について助言が欲しいです。
既にライブラリやアルゴリズムについて書かれている物がある場合は教えて欲しいです。
初期位置と最終到達座標が与えられます。
半径(r)のある物体が移動します。(1)
位置は実数(浮動小数)で表されます。
マップ上には厚みのない壁があり、整数座標の位置にP(座標)とV(ベクトル)で表されます。(2)(3)
壁の端は半径rの分だけ離れて通過します。(4)(5)
計算量や計算の難易度により、多少めり込んでも構いません。(4')
最悪壁から離れなくても構いません。(4'')
手作業でおおよその目標ルートを(4)(4')と(5)で書いてみました。
最終的にこの赤点を辿る順番で得られたらいいと思っています。
マップのサイズは可変でここでは単純に小さく示していますが、とても広いマップを想定しています。
・単純な上下左右移動による検索
アルゴリズムとして確立した物があるので、この検索自体は出来るのですが問題があります。
上側を通るルートは(0,0)(1,0)(1,1)(2,1)(2,0)...
となりますが、最終的に得られたステップ数と移動ルートの長さが(3)の壁を回り込む様な場合に正しく得られない事です。
最短を得たい場合に全てのルートを取得した上で、赤点を算出して全てのルートの長さを得なければなりません。
また、(2)壁の下の2x2の様な同じコストのルートがある場合など、赤点を正しく作る方法が思いつきません。
この方法は、到達できるかの判定用には使えるのですが、もう少しエレガントな方法でルートを見つけられないかなと思っています。
・壁とベクトルの衝突判定
始めにスタート地点から目標地点までの直通ベクトルに対して全ての壁との衝突判定をして、ヒットしていたら分割して行くという方法も考えたのですが、
(4,3)(7,4)(8,5)の壁がまずヒットし...と仮の中間点を追加して行きつつそれらを結ぼうと思っても、(7,4)の壁から座標(7,3)辺りに中間点を置くとした場合に、上のルートにならない状況が考えられてしまったりしてどうしたものかと思っています。
(2018/06/07)追記
重要なのは壁の端というのは分かっていたのですが、「どの壁の端か」を特定する為に、ベクトルの衝突(交差)という方法を用いようとしました。
追加した中継点が必要か不必要かの判定も必要で、「端点か角」の中継点が有用であるのも直感的に理解は出来ます。
「上下移動による検索」のルート探査を行った上で、中継点がどの領域と接しているかによってどっちのルートの中継点になるかを判別可能である、というのは上の文章を書いてから気がつきました。(下図)
灰色はルート1とルート2の共有ルートです。
色(ルート)に属していない中継点は検索の対象から外せます。
ルートであるのに色の付いていない所は、同じコストの別ルートがある場合。(だけど、条件としてはこれでは駄目で、route2と書かれた右上の白い場所が壁で囲まれていた場合、この条件では破綻します)
色の上であるのに端点としては使えないものがあるが、条件が分からない。(灰色に青い点が付いた中継点)
ベクトルの衝突判定は、端点を出す為ではなく、中継点を接続した時に有効かどうかを判定する為に使えそう。
まだ整理が付いていないですが、まだまだ自分の理解が浅いというのを痛感しています。
時間もなく、考える頭の許容量も目一杯で、分不相応な課題に取り組んでいる事も痛感しています。
議論の場として機能してほしいのですが、ベストアンサーを付けて終了しなければならないのかとも思っていて不安です。もう少し考える時間がほしいと思っています。私のわがままなのですがすいません。
回答3件
0
可能な経路を考える場合、トポロジーを利用すると問題が単純化（見えやすく）できます。
図１と図２は形の異なる壁ですが、壁に沿ってSからGに進めるという性質は同じなので、図１の壁と図２の壁は同相(topological に同じ)です。
可能な経路は、経路を構成する要素を同相な図形で取り換えても変わりません（topologicalな意味で変わらなという事で、経路の距離が同じという事ではありません）。
質問の図（図３）の構成要素(外側の壁、中央の障害物)を同相な図形で取り換えてみたのが図４です。
可能な経路は、中央の障害物を右側から避けるルートと、左側から避けるルートの２つしか無いことが判ります。
障害物の数が増えると可能な経路が指数的に増加しますが、既に見つかっている経路うちの最短距離を超えたところで探索を止める事ができるので、極端な計算量爆発は起きないと思います。
最短経路については、Computational Geometry のスライドが参考になると思います。
経路を（可能な範囲で短くなろうとする）ゴムバンドと考えるのは直観的ですし、実用的です。
投稿2018/06/07 02:55
総合スコア6915
0
質問者さんが真に望んでおられる最適解（幾何的な最適解）ではない「ナンチャッテ」な方法なのですが、アルゴリズムが単純なので一例としてコメントしてみます。
ご質問にある
単純な上下左右移動による検索
これは格子上にある隣接したセルに「出発点からの上下左右での移動回数」を記録していき最短経路を大まかに求める手法だと思います。そこに次のような工夫をちょこっと追加してみます。
- 格子の分割を少し細かくする
- 斜め方向の移動も可能とする
上下左右の移動距離を1と見做しますが斜め方向は2の平方根としておきます。
- セルの値（距離）の決定方法を若干変更する
オリジナルのアルゴリズムでは「隣接したセルがまだ未探索なら、そのセルの値を現在のセルの値＋１と定める」という具合に未探索のセルの値を決めますが、斜め方向の移動を導入するにあたり、「隣接したセルが既に探索済みであっても、より短い距離と見做せるときは値を書き換える」ようにしてみます。
このような方針で単純探索すると以下のような経路が求まります。
グレーは壁から一定距離のセルを「通過不能」と記録していることを表します。淡い色がスタート地点からゴールに向けて計算した距離を表します。
この結果は本当に求めたい「真の幾何的最短距離」ではありませんが、「最短距離のルートに概ね近い経路」を表しているとは言えると思います。
このようにして仮の経路を決定した後、ゴールからスタートに向けて
p1, p2, p3, ...
という経路上の各点を吟味し、p1->p2の幾何的な距離よりp1->p3の距離が近く、かつp1->p3に障壁がない場合はp2を削除する・・・と言った方針で途中の経路点のうち「真の最短経路から外れている点」を取り除いてみてはどうでしょう？
投稿2018/06/06 04:10
総合スコア18394
回答ありがとうございます。
半分のサイズは考えたのですが、更に細かくすることで近似値は出せるみたいですね。
大変参考になりました。すいませんがもう少し様子を見させてください。
この問題は色々なアプリ―チがある気がします。自分の回答は分割のため大きなマップだとマップを埋める手数が増えてしまう点が問題になると思います。最低限１マスを３分割しないといけないのですがそうすると全体の探索ステップは約９倍になります。３分割で充分「本当の最短経路が特定できるか」という問題もあるかも知れません。（自分には難しすぎてYES/NOがわかりません）
なお、質問者さんが挙げておられるように「分割せずに可能な経路を求めその経路各々に対して幾何的な最短距離を求めそれを最終経路として比較する」のも悪くない方法であると思いました。大きなマップの場合、計算量的には有利な気がするのです・・・
0
自己解決
(2018/06/13)自己解決
上下左右の検索は、今回のこの例のような格子状に壁がある限定的な条件の場合には使えるかもしれないが、汎用的な検索ではない。
壁の端点は検索対象として使え、壁の末端と角を考えるのが良い。
中継点が決まれば、スタートからゴールまでの間に中継点を経由し、経路が壁に遮られず、同じ中継点を二度通過しない条件で組み合わせを作り、その内の最短経路を探せば目的の経路が得られる。
という所で計算をさせてみました
中継点19個で40程度の経路が10秒ほど掛かって検索できた。その内の求めていたふたつの経路を表示してある
角と端点を計算対象にして、実際に有効な点(水色)以外にも使わない点(桃色)もあって、計算効率はあまり良くない
経路の壁との衝突判定が今ひとつしっくりこない為、端点から端点までが同じ座標の場合に経路が結べない不具合がある(右側の赤点同士の経路が出来ない)
経路を結ぶ場合は、端点の場合はrだけ離れた位置、角の場合はXとY共にrだけ離れた位置、を結ぶようにしてある(下側の赤線が経路)
壁にめり込んでしまう為、経路点の微調整が必要だけどとりあえずの目標は達成できました。
完璧に理想形にするにはまだまだ錬らなければならず、頭の整理と条件の精査が必要のようです。
中継点が少し増えただけで計算回数が増大する為、無闇に中継点を増やせない
半径rがゼロの場合に壁と接近しすぎていて経路が見つからない
最短ステップが必ずしも最短経路ではない為、経路の長さをチェックしながら、最短で見つかった物より長い経路を排除して短い経路の物だけを残して計算する必要がある
投稿2018/06/12 19:02
総合スコア422
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2018/06/07 11:50