Kir*_*ril 4 heuristics path-finding
如何在没有节点或单元格的无网格2D平面上实现A*算法？我需要物体以目标的方式围绕相对大量的静态和移动障碍物进行操纵.我目前的实现是在对象周围创建八个点,并将它们视为可能是对象的潜在位置的虚构相邻正方形的中心.然后我计算每个的启发函数并选择最佳.起点和运动点之间的距离,以及运动点和目标之间的距离我用毕达哥拉斯定理计算正常方式.问题在于,通过这种方式,物体通常会忽略所有障碍物,甚至更常被卡在两个位置之间来回移动.我意识到看起来多么愚蠢的问题,但任何帮助都表示赞赏.
以适合您的问题的任何分辨率创建一个虚构的网格:尽可能粗粒度以获得良好的性能,但细粒度足以在障碍物之间找到(理想的)间隙.您的网格也可能与障碍物体的四叉树相关.
在网格上执行A*.网格甚至可以预先填充有用信息,例如接近静态障碍物.一旦沿着网格方格有一条路径,就可以将该路径后处理到一系列路点中,无论路径中存在拐点.然后沿着航点之间的线路行进.
顺便说一下,你不需要实际的距离(参见你提到的毕达哥拉斯定理):A*可以很好地估算距离.曼哈顿距离是一个受欢迎的选择:|dx| + |dy|.如果您的网格游戏允许对角线移动(或网格是"假的"),那么就max(|dx|, |dy|)足够了.