3D 配置中的星形算法 space

Question

我对 A* 算法和其他基于图的算法进行了一些研究，但大多数教程和实现都是使用 2D 网格和 2 个参数（x、y 坐标）制作的。

是否有人有很好的示例教程（C++ 或 Java）或关于不同配置的 A* 的链接 space。例如 3D 环境或非网格，具有 x、y、z 坐标或 x、y、方向或任何其他...

谢谢

Answer 1

一般的 A* 算法不包括网格和维度。它是加权图的最短路径算法。该图的节点和边是什么，完全是特定于场景的。

在二维网格的情况下，节点是网格单元，边缘指定邻接。可以从 3D 网格构建类似的图形。如果您不想局限于网格，您可以构建具有任意连通性的任何图形。

节点不一定要对应位置，权重也不一定要对应距离。例如，Pinocchio System 使用 A* 来生成骨架嵌入。这里的距离是嵌入质量/能量（尽管能量不是沿着路径累积的）。节点对应于部分嵌入。