c++ - A *ジャンプポイント検索-剪定は実際にどのように機能しますか？

Question

私はジャンプポイント検索に出くわしました、そしてそれは私にはかなり甘いようです。ただし、それらの剪定ルールが実際にどのように機能するかはわかりません。より具体的には、図1には、次のように記載されています。

ノードxを経由せずに、xの親から最適に到達できるため、すべての灰色の隣接ノードをすぐに削除できます。

ただし、これはやや対立しているようです。x2番目の画像では、最初にノード7を通過し、対称パスを完全にスキップすることでノード5に到達できます。つまり、に対称で6 -> x -> 5あるように見え6 -> 7 -> 5ます。xこれは、最初の画像を通過せずにノード3に到達する方法と同じです。そのため、これら2つの画像が完全に同等ではなく、互いに回転したバージョンだけではないことを理解していません。

次に、このアルゴリズムを3次元検索ボリュームに一般化する方法を理解したいと思います。

Answer 1

2番目の画像が正しく表示されません。付随するテキストを見ると、「どちらの場合も、ノードxを経由せずに、xの親から最適に到達できるため、すべての灰色の隣接ノードをすぐに削除できます。」

「両方の場合」に重点を置きます。

この概念を3次元空間（または、n次元空間でさえ）に適用するという点では、このアルゴリズムは、ノードと接続の単なるメッシュであるという点でA*と同じです。次元は完全にあなたの裁量にあります。

Answer 2

私はこれが優先事項についてであることを理解しています。各非対称パスを列挙するには、すべてのノードを列挙する必要がありますが、対称であるため、どのパスを選択してもかまいません。そのため、作成者は対角線を優先することにしました。つまり、対角線の動きは常に、パス内の直線の動きの前に表示されます。これが、ストレートがより多くのノードを剪定する理由です。これは、すべての対角線が考慮された後に発生する必要があるためです。

Answer 3

はい、JPSは優れていますが、特定の制約があるマップに限定されています。

1. マップはグリッドを表す必要があります。
2. グリッド内のすべてのアクセス可能なセルは、同じトラバーサルコストを持っている必要があります。
3. 移動エージェントは、4つの基本方向と4つの対角線の8つの可能な移動方向を持っている必要があります。

アルゴリズムの鍵は、これらの制約がいくつかの重要な仮定を可能にすることです。

1. （障害物がない場合の）2点間の最短の幾何学的ルートも、最小コストのルートです。
2. （障害物がない場合の）2つのポイント間の最小コストのパスでは、方向を複数回変更する必要はありません。

これらの仮定により、アルゴリズムは対称パスオプションを無視し、次のように動作します。

1. 基本的な方向に移動するときは、ペーパーに示されている位置の1つで障害物に遭遇したときの方向の変更のみを考慮する必要があります。方向転換が考慮されるこれらのポイントは、「ジャンプポイント」です。
2. 斜めに移動する場合は、2つのブラケットの「前向き」基本方向のいずれかでジャンプポイントが「見える」場合にのみ、方向の変更を考慮する必要があります。これも論文に示されています。