実際の3D環境にも適した経路探索アルゴリズムがありますか？実際に複数の階段を持つビルディングなどC++のライブラリやオープンな実装は素晴らしく;-) 私が見た解決策はDjikstraでしたが、もっと最適なものがあるかどうか疑問です。 距離ヒューリスティックがうまく動作しないため、通常のA *はDjikstraよりはうまく動作しません（目的地の1階を上に置く）。 私が現在熟考している別の解決策は、3d環境を2次元グラフにマッピングすることです。したがって、利用可能なC++実装/ライブラリがある場合は、この方法も役立ちます。実際の3D環境（例えば、建物）における経路探索
障害物をナビゲートする機能（つまり、移動が空間内の既知のボリュームを持つエンティティのものであること）を考慮する必要がある場合は、ロボットの動き計画に関する文献を調べることをおすすめします。構成スペースの概念は、障害に対処するために、姿勢の変化を処理することを可能にします。単純なシナリオでジーン・クロード・ラトム
によって古典的な教科書を参照してください、あなたはおそらく、ダイクストラに似ている最初の人のコンピュータゲームで使用される経路計画アルゴリズムと近似アルゴリズムのためにA * (example)
を行うことができます3dを1dカーブに簡単にマッピングして、灰色のコードでオクトリーをトラバースすることができます。こうすることで、各パスを並べ替えることができます。最適解の中にあることが保証されているかどうかは分かりませんが、ヒューリスティックな方が良い方法でなければなりません。
階数が多い場合を除いて、A *は実際にうまくいくことができます。異なるレベルの点のヒューリスティックは、最も近い階段までの距離+垂直距離の合計です。 – biziclop
@biziclop：これは非常に良いアイデアであり、どのグラフ変換よりもはるかに簡単です。私はそれを試してみる – Martin
私は、pathfindingは分裂と征服の影響を受けやすいと信じています。だから、あなたは2dレベルでA *を使って試してみることができますし、Dijkstraのアルゴリズムを使ってそれらを結びつけることもできます。 – comingstorm