三维构形空间中的星型算法

Question

我对A*算法和其他基于图形的算法做了一些研究，但是大部分的教程和实现都是用2D网格和两个参数(x，y坐标)来完成的。

是否有人在不同的配置空间中有良好的示例教程(C++或Java)或关于A*的链接。如三维环境或非网格，有x，y，z坐标或x，y，方位或其他任何东西.

谢谢

Answer 1

一般的A*算法不包括网格和维数。它是一种加权图的最短路径算法.这个图的节点和边是完全特定于场景的.

在二维网格的情况下，节点是网格单元，边指定邻接。一个类似的图表可以建立在一个三维网格。如果您不想将自己限制在网格上，您可以构建任意连通性的任何图。

节点不一定需要对应位置，权重不一定需要与距离相对应。例如，皮诺曹系统使用A*来增长骨架嵌入。这里的距离是嵌入质量/能量(虽然能量不是沿着路径积累的)。节点对应于部分嵌入。