A *ジャンプポイント検索 - プルーニングは実際にどのように機能しますか？

Question

私はJump Point Searchに出くわしました。それは私にとってかなり甘いようです。しかし、私は自分の枝刈りルールが実際にどのように機能するかは不明です。具体的には、図1に、これらはしかし、これはそう、これまでノードX

を経由せずに、xの親から最適に到達することができるよう、我々はすぐにすべての灰色の隣人を剪定することができます

と述べていますややオッズである。第2の画像では、ノード5を最初に通過し、xを完全に対称的な経路でスキップすることによってノード5に到達することができます。つまり、6 -> x -> 5は6 -> 7 -> 5と対称に見えます。これは、最初のイメージでxを経由せずにノード3に到達する方法と同じになります。このように、私はこれらの2つのイメージが完全に同等ではなく、互いに回転したバージョンではないことを理解していません。

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

Answer 1

私はこのことを優先事項として理解しています。それぞれの非対称パスを列挙するためには、すべてのノードを列挙しなければなりませんが、対称的なので、どのパスを選択しても問題ありません。そこで、著者は対角線方向に進むことに決めました。つまり、対角線方向の移動は常に、パス内の直線移動の前に現れます。そのため、ストレートにはより多くのノードが整理されます。なぜなら、すべての対角線が考慮された後でなければならないからです。

Answer 2

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

「両方のケース」を強調します。

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

Answer 3

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

1. マップは、グリッドを表している必要があります。
2. グリッド内のすべてのアクセス可能なセルは、同じトラバーサルコストを持たなければなりません。
3. 移動エージェントには8つの可能な移動方向、4つの基本方向と4つの対角線が必要です。
   1. （障害物の非存在下で）二点間の最短の幾何学的経路はまた、A最小コスト経路である：

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

4. 2つのポイント間の最小コストのパス（障害物がない場合）は、複数の方向の変更を必要としません。

これらの仮定は、アルゴリズムが対称パスオプションを無視して、次のように動作することを可能にする：

1. あなたが唯一の障害は、のいずれかに遭遇したときに方向の変更を検討する必要がある基本的方向に移動するとき論文に描かれている位置。方向の変化が考慮されるこれらの点は「ジャンプ点」である。
2. 対角線上を移動するときは、やはり紙に描かれているように、2つのブラケティング「前方を向いている」枢機卿の方向のうちの1つでジャンプポイントを「見る」ことができるときに、方向の変更だけを考慮する必要があります。