在真实3D环境（例如建筑物）中寻找路径

Question

是否存在也适用于真实3D环境的寻路算法，例如真正的建筑物与多个楼梯等C++库或开放实施将是精彩;-) 我看到的一个解决方案是Djikstra，但我想知道是否有更优化的东西。 由于距离启发式算法效果不好，所以普通A *不会比Djikstra更好（位于目的地一层以上）。 我目前正在思考的另一个解决方案是3D环境在二维图上的映射。所以如果有这样一些可用的C++实现/库，这也会有所帮助。

Answer 1

如果路径必须考虑到通过障碍物的能力（即运动是具有已知空间体积的某个实体的运动），那么我建议查看关于机器人运动规划的文献。配置空间的概念允许您处理姿势的变化以应对障碍。见吉恩·克劳德·拉姆

对于一些简单场景的经典教材，你也许可以凑合着用第一​​人称的电脑游戏所使用的路径规划算法，类似于Dijkstra算法，A * (example)

Answer 2

对于一个近似算法您可以轻松将3d映射到1d曲线，并用灰色代码遍历八叉树。这样你可以重新排序每条路径。我不知道是否有最佳解决方案的保证，但它必须比任何启发式方法更好。