c++ - 実際の 3D 環境 (建物など) でのパスファインディング

Question

実際の 3D 環境、たとえば複数の階段がある実際の建物などにも適したパスファインディング アルゴリズムはありますか? C++ ライブラリまたはオープンな実装は素晴らしいでしょう ;-) 距離ヒューリスティックがうまく機能しないため、通常の A* は Djikstra よりもうまく機能しません (目的地の 1 階上の位置)。私が現在考えているもう 1 つの解決策は、3D 環境を 2D グラフにマッピングすることです。したがって、この方法で利用可能な C++ 実装/ライブラリがあれば、それも役に立ちます。

Answer 1

パスが障害物を通り抜ける能力を考慮に入れる必要がある場合 (つまり、動きが空間内の既知のボリュームを持つエンティティの動きである場合)、ロボットの動作計画に関する文献を調べることをお勧めします。構成空間の概念により、障害物に対処するためにポーズの変更を処理できます。Jean-Claude Latombe の古典的な教科書を見る

より単純なシナリオでは、Dijkstra、A* (例)に似た、一人称コンピューター ゲームで使用されるパス プランニング アルゴリズムでおそらく間に合わせることができます。

Answer 2

近似アルゴリズムの場合、3d を 1d 曲線に簡単にマップし、グレイ コードで octree をトラバースできます。そうすれば、各パスを並べ替えることができます。最適解の範囲内にあるという保証があるかどうかはわかりませんが、ヒューリスティックな方法よりも優れているに違いありません。