heuristics - 如何在无网格的二维平面上使用 A* 寻路算法？

Question

如何在没有节点或单元的无网格二维平面上实现 A* 算法？我需要物体绕过目标途中相对较多的静态和移动障碍物。
我当前的实现是在对象周围创建八个点，并将它们视为可能是对象潜在位置的假想相邻正方形的中心。然后我为每个计算启发式函数并选择最好的。起点和运动点之间的距离，运动点和目标之间的距离我用勾股定理计算的正常方式。问题是这样的对象通常会忽略所有障碍物，并且更经常在两个位置之间来回移动被卡住。
我意识到 mu 问题可能看起来多么愚蠢，但任何帮助表示赞赏。

Answer 1

以适合您的问题的任何分辨率创建一个假想网格:尽可能粗粒度以获得良好性能，但足够细粒度以找到障碍之间的(理想的)间隙。您的网格也可能与带有障碍物的四叉树相关。

在网格上执行 A*。网格甚至可以预先填充有用的信息，例如接近静态障碍物。一旦沿着网格方块有了一条路径，就将该路径后处理成一系列路径点，只要路径中有拐点。然后沿着航路点之间的线行进。

顺便说一句，您不需要实际距离(参见您提到的勾股定理):A* 可以很好地估计距离。曼哈顿距离是一个受欢迎的选择:|dx| + |dy| .如果您的网格游戏允许对角移动(或网格是“假的”)，只需 max(|dx|, |dy|)可能就足够了。