c++ - 真实 3D 环境中的寻路（例如建筑物）

Question

是否有一种寻路算法也适用于真实的 3D 环境，例如具有多个楼梯的真实建筑物等。C++ 库或开放式实现会很棒;-) 我看到的一个解决方案是 Djikstra，但我想知道是否有更优化的解决方案。普通 A* 不会比 Djikstra 工作得更好，因为距离启发式不能很好地工作（位于目的地上方一层）。我目前正在考虑的另一个解决方案是将 3d 环境映射到 2d 图形上。因此，如果有一些可用的 C++ 实现/库以这种方式运行，那也会很有帮助。

Answer 1

如果路径必须考虑通过障碍物导航的能力（即运动是空间中已知体积的某个实体的运动），那么我建议查看有关机器人运动规划的文献。配置空间的概念允许您处理姿势的变化以处理障碍物。参见让-克劳德·拉通贝 (Jean-Claude Latombe) 的经典教科书

对于更简单的场景，您可以使用第一人称计算机游戏中使用的路径规划算法，类似于 Dijkstra，A* （示例）

Answer 2

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