質問: フリーグリッドのルート探査について助言が欲しいです。 既にライブラリやアルゴリズムについて書かれている物がある場合は教えて欲しいです。 ![イメージ説明](https://teratail.storage.googleapis.com/uploads/contributed_images/c7a3628e28d06625ebdc2207b621a7fa.png) 初期位置と最終到達座標が与えられます。 半径(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)追記 重要なのは壁の端というのは分かっていたのですが、「どの壁の端か」を特定する為に、ベクトルの衝突(交差)という方法を用いようとしました。 追加した中継点が必要か不必要かの判定も必要で、「端点か角」の中継点が有用であるのも直感的に理解は出来ます。 「上下移動による検索」のルート探査を行った上で、中継点がどの領域と接しているかによってどっちのルートの中継点になるかを判別可能である、というのは上の文章を書いてから気がつきました。(下図) ![イメージ説明](https://teratail.storage.googleapis.com/uploads/contributed_images/0ab53d260983c565e4e23d62e81b417f.png) 灰色はルート1とルート2の共有ルートです。 色(ルート)に属していない中継点は検索の対象から外せます。 ルートであるのに色の付いていない所は、同じコストの別ルートがある場合。(だけど、条件としてはこれでは駄目で、route2と書かれた右上の白い場所が壁で囲まれていた場合、この条件では破綻します) 色の上であるのに端点としては使えないものがあるが、条件が分からない。(灰色に青い点が付いた中継点) ベクトルの衝突判定は、端点を出す為ではなく、中継点を接続した時に有効かどうかを判定する為に使えそう。 まだ整理が付いていないですが、まだまだ自分の理解が浅いというのを痛感しています。 時間もなく、考える頭の許容量も目一杯で、分不相応な課題に取り組んでいる事も痛感しています。 議論の場として機能してほしいのですが、ベストアンサーを付けて終了しなければならないのかとも思っていて不安です。もう少し考える時間がほしいと思っています。私のわがままなのですがすいません。
回答: (2018/06/13)自己解決 上下左右の検索は、今回のこの例のような格子状に壁がある限定的な条件の場合には使えるかもしれないが、汎用的な検索ではない。 壁の端点は検索対象として使え、壁の末端と角を考えるのが良い。 中継点が決まれば、スタートからゴールまでの間に中継点を経由し、経路が壁に遮られず、同じ中継点を二度通過しない条件で組み合わせを作り、その内の最短経路を探せば目的の経路が得られる。 という所で計算をさせてみました !ルート検索と条件と不具合 中継点19個で40程度の経路が10秒ほど掛かって検索できた。その内の求めていたふたつの経路を表示してある 角と端点を計算対象にして、実際に有効な点(水色)以外にも使わない点(桃色)もあって、計算効率はあまり良くない 経路の壁との衝突判定が今ひとつしっくりこない為、端点から端点までが同じ座標の場合に経路が結べない不具合がある(右側の赤点同士の経路が出来ない) 経路を結ぶ場合は、端点の場合はrだけ離れた位置、角の場合はXとY共にrだけ離れた位置、を結ぶようにしてある(下側の赤線が経路) 壁にめり込んでしまう為、経路点の微調整が必要だけどとりあえずの目標は達成できました。 完璧に理想形にするにはまだまだ錬らなければならず、頭の整理と条件の精査が必要のようです。 中継点が少し増えただけで計算回数が増大する為、無闇に中継点を増やせない 半径rがゼロの場合に壁と接近しすぎていて経路が見つからない 最短ステップが必ずしも最短経路ではない為、経路の長さをチェックしながら、最短で見つかった物より長い経路を排除して短い経路の物だけを残して計算する必要がある