如何在无网格的二维平面上使用 A* 寻路算法? [英] How to use the A* path finding algorithm on a grid less 2D plane?

问题描述

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

How can I implement the A* algorithm on a gridless 2D plane with no nodes or cells? I need the object to maneuver around a relatively high number of static and moving obstacles in the way of the goal. My current implementation is to create eight points around the object and treat them as the centers of imaginary adjacent squares that might be a potential position for the object. Then I calculate the heuristic function for each and select the best. The distances between the starting point and the movement point, and between the movement point and the goal I calculate the normal way with the Pythagorean theorem. The problem is that this way the object often ignores all obstacle and even more often gets stuck moving back and forth between two positions. I realize how silly mu question might seem, but any help is appreciated.

推荐答案

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

Create an imaginary grid at whatever resolution is suitable for your problem: As coarse grained as possible for good performance but fine-grained enough to find (desirable) gaps between obstacles. Your grid might relate to a quadtree with your obstacle objects as well.

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

Execute A* over the grid. The grid may even be pre-populated with useful information like proximity to static obstacles. Once you have a path along the grid squares, post-process that path into a sequence of waypoints wherever there's an inflection in the path. Then travel along the lines between the waypoints.

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

By the way, you do not need the actual distance (c.f. your mention of Pythagorean theorem): A* works fine with an estimate of the distance. Manhattan distance is a popular choice: |dx| + |dy|. If your grid game allows diagonal movement (or the grid is "fake"), simply max(|dx|, |dy|) is probably sufficient.

这篇关于如何在无网格的二维平面上使用 A* 寻路算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！