円形障害物における経路探索 (2017)
Circular Obstacle Pathfinding (2017) (redblobgames.github.io)
要約
この記事は、A*アルゴリズムを用いて円形の障害物がある環境での経路探索を行う方法を解説しています。円形障害物間の接線(ビットージェント)を利用してグラフを構築し、A*アルゴリズムを適用する手順を詳細に説明しています。
全文翻訳
円形障害物経路探索
円形障害物の周りのナビゲーション
Mar 2017
森の中のナビゲーション
A経路探索アルゴリズムは、最適なパスを迅速に生成するための強力な手法です。通常、Aはグリッドベースのマップでのナビゲーションを示すために使われますが、Aはグリッドアルゴリズムだけではありません!あらゆるグラフで機能します。この丸い障害物の世界を通過するパスを見つけるためにAを使用できます。
同じアルゴリズムが両方の問題をどのように解決するのでしょうか?まず、A*の仕組みを復習することから始めましょう。
A*アルゴリズム
Aアルゴリズムは、障害物を避けながら、開始点から終了点までの最適なパスを見つけます。これは、部分パスのセットを段階的に拡張することによって行われます。各部分パスは、開始点からゴールまでの途中にある中間点までのステップのシリーズです。Aが進むにつれて、部分パスはゴールポイントにどんどん近づいていきます。アルゴリズムは、残りの可能性よりも優れていると証明できる完全なパスを見つけた時点で終了します。
アルゴリズムの各ステップで、Aは部分パスのセットを評価し、セットの中で最も有望なパスを拡張することによって新しいパスを生成します。これを行うために、Aは部分パスを推定距離でソートされた優先度付きキューに保持します。これは、これまでのパスの実際の測定距離に、ゴールまでの残りの距離の推測を加えたものです。この推測は過小評価でなければなりません。つまり、推測は実際の距離よりも短くても構いませんが、長くすることはできません。ほとんどの経路探索問題では、良い過小評価は、部分パスの終点からゴールまでの幾何学的な直線距離です。部分パスの終点からゴールまでの実際の最適なパスは、この直線距離よりも長くなる可能性がありますが、短くなることはありません。
Aが開始すると、優先度付きキューには1つの部分パス、つまり開始点のみが含まれます。アルゴリズムは、推定距離が最も小さいパス、つまり最も有望なパスを優先度付きキューから繰り返し削除することによって機能します。このパスがゴールポイントで終わる場合、アルゴリズムは完了です。優先度付きキューにより、他のどのパスもそれより良くならないことが保証されます。そうでない場合、キューから削除された部分パスの終点から開始して、Aはあらゆる可能な方向に1ステップずつ進むことによって新しいパスを生成します。これらの新しいパスを優先度付きキューに戻し、プロセスを再度開始します。
グラフ
Aはグラフで動作します。これはノードのコレクションで、エッジ*で接続されています。グリッドベースの世界では、各ノードは個々のグリッド位置を表し、各エッジは北、南、東、または西の隣接位置への接続を表します。
円形の障害物の森でA*を実行できるようになる前に、それをグラフに変換する必要があります。森を通過するすべてのパスは、線分と円弧セクションが交互に並んだものです。これらはパスグラフのエッジです。これらのエッジの端点がノードになります。グラフを通過するパスは、エッジで接続されたノードのシリーズです。
セグメントとアークの両方がグラフのエッジとして機能します。セグメントをサーフィンエッジと呼びます。パスが障害物の間をサーフィンするために使用するためです。アークをハギングエッジと呼びます。パスでの目的は障害物の側面に沿って進むためです。
次に、障害物の森をグラフに変換する簡単な方法を探ります。可能なすべてのサーフィンエッジとハギングエッジを生成します。
これは接線可視性グラフと呼ばれます。
サーフィンエッジの生成
2つの円間のサーフィンエッジは、両方の円にわずかに接する線分です。これらの線分は共通接線として知られており、各円のペアに対して4つあります。円の間を横切る共通接線は内共通接線であり、外側を沿って伸びるものは外共通接線です。
内共通接線
歴史的に、内共通接線は、異なるサイズのプーリーを横切るベルトの長さを計算するために重要でした。そのため、内共通接線を構築する問題はベルト問題として知られています。内共通接線を見つけるには、以下の図の角度(\theta)を計算します。
重なり合う円には共通接線はありません
円の中心が点(A)と(B)にあり、半径が(r_A)と(r_B)で、中心間の距離が(d)であるとすると、次のようになります。
[\theta = \arccos{{r_A+r_B}\over{d}}]. (\theta)がわかると、点(C)、(D)、(E)、(F)を簡単に見つけることができます。
外共通接線
外共通接線、つまりプーリー問題の構築は、同様の技術を使用します。
小さい円が大きな円に完全に含まれている
外共通接線の場合、(\theta)は次のように見つけることができます。
[\theta = \arccos{{\lvert r_A - r_B \rvert} \over d}]. 円Aまたは円Bのどちらが大きいかは関係ありませんが、図に示すように、(\theta)はAからBへの側に見えますが、Bから離れる側に見えます。
直線視線
これらをまとめると、2つの円間の内共通接線と外共通接線は、円間のサーフィンエッジを構成します。しかし、3番目の円が1つ以上のサーフィンエッジをブロックしている場合はどうでしょうか?
円が視線をブロックしている AとBは互いに見える
サーフィンエッジが別の円によってブロックされている場合、そのエッジを削除する必要があります。このケースを検出するために、単純な点線距離計算を使用します。サーフィンエッジから障害物の中心までの距離が障害物の半径より小さい場合、その障害物はサーフィンエッジをブロックしているため、エッジを削除する必要があります。
点(C)から線分(\overline{AB})までの距離を計算するには、次の方法を使用します。
まず、垂直な垂線が点(C)に当たる線分(\overline{AB})に沿った距離の割合である(u)を計算します。
([ u = {(C - A) \cdot (B-A) \over (B-A)\cdot(B-A)} ]]
次に、(\overline{AB})上の位置(E)を計算します。
([ E = A + \mathrm{clamp}(u, 0, 1) * (B - A) ]]
0 1 u={{Math.round(100 extit{(C.x-A.x)/(B.x-A.x)})/100}} d r
(C)から線分(\overline{AB})までの距離(d)は、(C)から(E)までの距離です。
([d = |E - C|]]
(d < r)の場合、円は(A)から(B)への視線をブロックしており、エッジは削除する必要があります。(d \ge r)の場合、(A)から(B)への視線があり、エッジは保持する必要があります。円を移動して(d \ge r)および(d < r)のケースを確認してください。
ハギングエッジの生成
グラフノードは、サーフィンエッジとハギングエッジを接続します。前のセクションでサーフィンエッジを生成しました。ハギングエッジを生成するには、サーフィンエッジの終点から開始し、円周に沿って移動し、別のサーフィンエッジの終点で終了します。
円のハギングエッジのセットを見つけるには、まず円に触れるすべてのサーフィンエッジを見つけます。次に、円上のすべてのサーフィンエッジの終点間にハギングエッジを作成します。
まとめ
サーフィンエッジ、ハギングエッジ、ノードの生成、およびブロックされたサーフィンエッジの除外により、グラフを作成し、A*アルゴリズムを使用して経路探索を実行できます。
拡張機能
ここで説明したグラフ生成手順は、アルゴリズムを説明するには十分ですが、改善できる点はたくさんあります。これらの拡張機能により、アルゴリズムはCPUとメモリの使用量を削減し、より多くのケースを処理できるようになります。いくつか見てみましょう。
接触する障害物
おそらく気づいたかもしれませんが、これまでの例の円形障害物は、重なったり接触したりしていませんでした。円が接触することを許可すると、経路探索問題は少し、しかしそれほど難しくはありません。
共通接線
共通接線は、内共通接線の場合にこの式で求められることを思い出してください。
([\theta = \arccos{{r_A+r_B}\over{d}}]]
外共通接線の場合にはこの式です。
([\theta = \arccos{{\lvert r_A - r_B \rvert} \over d}]]
2つの円が接触または重なっている場合、それらの間に内共通接線はありません。この場合、({r_A+r_B}\over d)は1より大きくなります。アークコサインは([-1, 1])のドメイン外の入力に対して未定義であるため、アークコサインを実行する前に円の重なりを確認することが重要です。
同様に、一方の円がもう一方の円を完全に囲んでいる場合、それらの間に外共通接線はありません。この場合、({r_A - r_B} \over d)は([-1, 1])の範囲外であり、アークコサインを持ちません。
円は重ならない:外側と内側の両方の共通接線 円は重なる:外側の共通接線のみ 小さい円が大きな円に囲まれている:共通接線なし
サーフィンエッジの直線視線
障害物が接触または重なることを許可すると、サーフィンエッジの直線視線の計算で新しいケースが発生します。サーフィンエッジ上の距離の割合である(u)の計算を思い出してください。垂直な垂線がエッジに当たる点です。円が互いに接触しない場合、(u)が([0,1])の外にある値は、円がエッジに触れることができないことを意味します。なぜなら、そうするにはエッジのいずれかの終点に触れる必要があるからです。これは、エッジの終点がすでに他の円に接線(したがって接触)しているため不可能です。
しかし、円が重なることを許可する場合、(u)が([0,1])の外にある値は直線視線をブロックする可能性があります。これは、円がサーフィンエッジの端を過ぎているが、終点を覆っているか接触しているケースに対応します。これらのケースを数学的に捉えるために、(u)を([0,1])の範囲にクランプします。
([E = A + clamp(u, 0, 1) * (B - A))]
ハギングエッジの直線視線
障害物が接触または重なることを許可する場合、ハギングエッジはサーフィンエッジと同様に障害物によってブロックされる可能性があります。以下の図のハギングエッジを考えてみてください。別の障害物がハギングエッジに接触している場合、それはブロックされており、削除する必要があります。
ハギングエッジがブロックされている ハギングエッジは有効
ハギングエッジが別の障害物によってブロックされているかどうかを判断するには、次の方法を使用して、2つの円が交差する点を決定します。点(A)と(B)を中心とする半径(r_A)と(r_B)の円があり、(d)が(A)と(B)の間の距離である場合、最初にチェックすべきいくつかのケースがあります。円が接触していない場合(つまり、(d > r_A + r_B))、一方の円がもう一方の内側にある場合((d < |r_A - r_B|))、または円が一致している場合((d = 0)かつ(r_A = r_B))、円は互いのハギングエッジに干渉できません。
これらのケースのいずれも当てはまらない場合、円は2つの点で交差します。円が互いに接している場合、これらの2つの点は一致します。交差点を結ぶ線に垂直な根軸を考えます。これは、(A)と(B)を結ぶ線上の点(C)で直角になります。(A)から(C)までの距離(a)は次のように計算できます。
([a = {r_A^2 - r_B^2 + d^2 \over 2d } ]]
(a)を見つけたら、角度(\theta)を見つけることができます。
([\theta = \arccos {a \over r_A} ]]
(\theta)がゼロの場合、円は(C)で接しています。それ以外の場合、正と負の(\theta)に対応する2つの交点があります。
大きい円が小さい円を囲んでいる 円は重ならない
次に、交点のいずれかがハギングエッジの開始点と終了点の間に位置するかどうかを判断します。この場合、障害物はハギングエッジをブロックしているため、エッジを破棄する必要があります。ハギングエッジが障害物内に完全に含まれているケースについては、サーフィンエッジの直線視線による除外ですでに破棄されているため、心配する必要はありません。
共通接線の計算とサーフィンエッジおよびハギングエッジの直線視線の変更を行った後、すべてがうまく機能します。
可変アクター半径(ミンコフスキー和による)
円形障害物の世界を円形オブジェクトでナビゲートする場合、問題を単純化できるいくつかの観察を行うことができます。まず、半径rの円を円形障害物の森で移動することは、ポイントを同じ森で移動することと同一であることに気づくことで、物事を容易にすることができます。ただし、1つの変更点があります。各障害物の半径がrだけ増加します。これはミンコフスキー和の非常に単純な応用です。半径がゼロより大きい場合、開始前に障害物のサイズを大きくします。
遅延エッジ生成
一般に、(n)個の障害物の森のグラフには(O(n^2))個のサーフィンエッジが含まれていますが、これらのそれぞれは(n)個の障害物に対して直線視線を確認する必要があるため、グラフを生成する総時間は(O(n^3))になります。さらに、サーフィンエッジのペアがハギングエッジを生成する可能性があり、これらのそれぞれは直線視線のためにすべての障害物に対して確認する必要があります。しかし、A*アルゴリズムは非常に効率的であるため、通常は最適なパスを生成するためにこの大きなグラフのごく一部しか調べません。
すべてを事前に実行するのではなく、Aアルゴリズムを進めながらグラフの小さな部分をオンザフライで生成することで時間を節約できます。Aが迅速にパスを見つけた場合、グラフの小さな部分のみを生成します。これは、エッジ生成をneighbors()関数に移動することによって行います。
いくつかのケースがあります。アルゴリズムの開始時には、開始点の隣接ノードが必要です。これらは、開始点から各障害物の左端と右端へのサーフィンエッジです。
次のケースは、A*が障害物(C)の端にある点(p)にサーフィンエッジに沿って到着したばかりの場合です。neighbors()は、(p)から始まるハギングエッジを返す必要があります。これを行うには、(C)と他のすべての障害物との間の共通接線を計算し、直線視線を持たないものをすべて除外することによって、障害物から出るサーフィンエッジを決定します。次に、(p)をこれらのサーフィンエッジに接続するすべてのハギングエッジを見つけ、他の障害物によってブロックされているものを除外します。これらのハギングエッジすべてを返し、サーフィンエッジは後続のneighbors()呼び出しで返すために保存します。
最後のケースは、A*が障害物(C)に沿ってハギングエッジを通過し、(C)をサーフィンエッジ経由で離れる必要がある場合です。前のステップで計算および保存されたすべてのサーフィンエッジがあるため、正しいエッジセットを検索して返すことができます。
尖ったハギングエッジの除外
ハギングエッジは同じ円に触れるサーフィンエッジを接続しますが、これらのハギングエッジの多くは、最適なパスで使用する資格がないことが判明します。これらを除外することで、アルゴリズムを高速化できます。
障害物の森を通過する最適なパスは、常にサーフィンエッジとハギングエッジが交互に並んだものです。ノード(A)に入り、出口を決定しようとしているとします。
(A)から入るということは、時計回り(\circlearrowright)に進むことを意味します。時計回り(\circlearrowright)を維持するノードから出る必要があります。したがって、ノード(B)または(D)からのみ出口を見つけることができます。(C)から出口を見つけると、パスに尖り(\curlywedge)が作成され、最適になることはありません。これらの尖ったエッジをフィルタリングする必要があります。
まず、A*はすでに各無向エッジ(P \longleftrightarrow Q)を2つの有向エッジ、(P \longrightarrow Q)と(Q \longrightarrow P)として扱っていることに注意してください。これを利用するために、エッジとノードに方向を注釈付けます。
- ノード(P)は、時計回り(P\circlearrowright)または反時計回り(P\circlearrowleft)のいずれかの方向を持つノードになります。
- 無向サーフィンエッジ(P \longleftrightarrow Q)は、有向エッジ(P,p \longrightarrow Q,\hat{q})および(Q,q \longrightarrow P,\hat{p})になります。ここで、(p)と(q)は方向であり、(\hat{x})は(x)の反対方向を意味します。
- 無向ハギングエッジ(P \longleftrightarrow Q)は、有向エッジ(P\circlearrowright \longrightarrow Q\circlearrowright)および(P\circlearrowleft \longrightarrow Q\circlearrowleft)になります。ここでフィルタリングが発生します。方向を変更すると尖り(\curlywedge)が生成されるため、(P\circlearrowright \longrightarrow Q\circlearrowleft)および(P\circlearrowleft \longrightarrow Q\circlearrowright)は含めません。
私たちの図では、ノード(A)は2つのノード、(A\circlearrowright)と(A\circlearrowleft)になり、(\longrightarrow A\circlearrowright)という入力サーフィンエッジと、(A\circlearrowleft \longrightarrow)という出力サーフィンエッジを持ちます。パスが(A\circlearrowright)から入った場合、(\circlearrowright)ノードから出る必要があります。これは、(A\circlearrowright \longrightarrow B\circlearrowright)ハギングエッジ((A\circlearrowright \longrightarrow B\circlearrowright)ハギングエッジ経由)または(D\circlearrowright \longrightarrow)サーフィンエッジ((A\circlearrowright \longrightarrow D\circlearrowright)ハギングエッジ経由)のいずれかになります。(A\circlearrowright \longrightarrow C\circlearrowleft)ハギングエッジを除外しているため、回転方向を変更する(C\circlearrowleft \longrightarrow)から出ることはできません。
これらの尖ったハギングエッジをグラフから除外することで、アルゴリズムをより効率的にします。
交差エッジの除外
最後のサーフィンエッジが最後から2番目のサーフィンエッジと交差する部分パスを除外します。
多角形障害物
Game Programming Gems 2の第3.10章、「Optimizing Points-of-Visibility Pathfinding」(Thomas Young著)を参照してください。これはノードの除外を扱っていますが、円ではなく多角形の場合です。