c++ - A* JPS を使用した 3D 検索

Question

Jump Point 検索を 3D 検索ボリュームに一般化するにはどうすればよいですか?

ここまでで、直線 (0,0,1)、一次対角線 (0,1,1)、二次 (1,1,1) の 3 つの動きのそれぞれを含む 3D 立方体の枝刈り規則を定義しました。 .

私が最も関心を持っているのは、論文で定義されている最適な転換点です。それらがどのように導出されたかを正確に確認することができなかったため、3 次元について自分自身を導出する方法.

これを行う方法について何か提案はありますか?

Answer 1

転換点を導き出そうとするのではなく、2D のアルゴリズムを直感的に理解することが役立ちます。

2 地点間の最短距離は直線であるため、1次元で2歩に相当するため、斜めに移動するのが最速であることがわかります。3D では、これは対角線が3 つのステップに相当することを意味します。(実際には、これらの値はsqrt(2)とsqrt(3)です)。これにより、できるだけ多くの軸を横切って移動することによって最適化することを選択します... 2D 軸に沿って移動するために回転することは、3D 軸に沿って移動するために回転するよりも悪いです。同様に、1D (直線) に沿った移動は、2D 移動よりもさらに悪いです。これは、ジャンプポイントが作成するコア仮定です。

カリング アルゴリズムでは、最適ではない軸 (1D) でジャンプしている場合、軸上に平行な壁ができるまで、より高い軸次数 (2D 軸に変わる) の最適な回転はないという仮定があります。同軸順。たとえば、図 2(d)を見てください。コードは 1D で平行な壁を認識し、2D の動きをリストに追加します。

ヒューリスティックとして

1 つのスペースが開いたままになるまで前方に評価し (壁が 2 スペース離れている)、このポイントをジャンプリストに追加します。ジャンプリストの任意のポイントで、新しい方向にジャンプします。目標 > 前方への 2D の動き > 前方への 1D の動き > 後方への 1D の動き > 後方への 2D の動き。このヒューリスティックを任意の n 次元に一般化できます...

次の方向を評価すると、+ は目標に向かって、n はインクリメントされた次元の量であり、次の方程式が得られます... + n D > + n-1 D > ... +1D > 0D > -1D > .. . > - n-1 D > - n D

3D での最高→最悪のターニング ポイントの順序

1. 3D+ = [1, 1, 1]
2. 2D+ = [1, 1, 0], [1, 0, 1], [0, 1, 1]
3. 1D+ = [1, 0, 0], [0, 1, 0], [0, 0, 1], [-1, 1, 1], [1, -1, 1], [1, 1, - 1]

(以下の準最適; [0, 0, 0] は役に立たないので含めませんでした)

4. 0D = [1, -1, 0], [1, 0, -1], [-1, 1, 0], [-1, 0, 1], [0, -1, 1], [0, 1、-1]
5. 1D- = [-1, 0, 0], [0, -1, 0], [0, 0, -1], [-1, -1, 1], [1, -1, -1], [-1、1、-1]
6. 2D- = [-1, -1, 0], [-1, 0, -1], [0, -1, -1]
7. 3D- = [-1、-1、-1]

タイピングは面倒でしたが、問題は解決するはずです。

「ジャンプ」するときは、ジャンプしている軸の順序を追跡することを覚えておいてください。同じ軸で平行な壁を見つける必要があります。したがって、方向 [1, 0, 1] に移動し、[1, 1, 0] および [0, 1, 1] にある壁を見つけて、[ 1、1、1]。

同じ論理で、1D [1, 0, 0] に移動する場合、壁の [0, 1, 0] にチェックを入れて、[0, 1, 1] と [1, 1, 0] を追加します。[1, 0, 1] と [0, 1, 1] をジャンプ ポイントとして追加するには、[0, 0, 1] もチェックします。

視覚化して計算するのは非常に難しいため、私の言いたいことが理解できることを願っていますが、数学が理解できれば簡単に把握できます。

結論

A* ヒューリスティックを使用...

• ダイクストラ = スタートからの距離
• Greedy First = ゴールまでの距離

次に、新しいヒューリスティックを追加します。

• + n D > + n-1 D > ... +1D > -1D > ... > - n-1 D > - n D
• ポイントn D に平行な障害物がある場合、開いているn+1 D 方向ごとにジャンプ ポイントを追加できます。

編集: コードの「並列」の定義

• 進行方向と同じ順序の任意の点
• その方向の次のポイントではありません
• 次のポイントと同じ量の正と負の次元の移動があります (たとえば、[1, 1, -1] は [1, -1, 1] および [-1, 1, 1] に平行ですが、[ には平行ではありません) 。 1、0、0]