如何在无网格 2D 平面上使用 A* 寻路算法？
如何在没有节点或单元的无网格 2D 平面上实现 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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
以适合您的问题的任何分辨率创建一个假想网格：尽可能粗粒度以获得良好的性能，但足够细粒度以找到障碍物之间的（所需的）间隙。您的网格也可能与带有障碍物对象的四叉树相关。
在网格上执行 A*。网格甚至可以预先填充有用的信息，例如接近静态障碍物。一旦你有了沿着网格方块的路径，只要路径中有拐点，就可以将该路径后处理为一系列路径点。然后沿着航路点之间的线路行驶。
顺便说一句，您不需要实际距离（参见您提到的毕达哥拉斯定理）：A* 可以很好地处理距离的估计。曼哈顿距离是一个流行的选择：
|dx| + |dy|。如果您的网格游戏允许对角线移动（或者网格是“假的”），那么简单地max(|dx|, |dy|)可能就足够了。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.
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.
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"), simplymax(|dx|, |dy|)is probably sufficient.呃。我首先想到的是，在每个点，您都需要计算梯度或向量，以找出下一步的方向。然后你移动一个小的epsilon并重做。
这基本上为您创建了一个网格，您可以通过选择较小的epsilon来改变单元格大小。通过这样做而不是使用固定网格，即使每个步骤中的度数很小，您也应该能够进行计算 - 与您的 8 点示例相比，小于 45°。
理论上，您也许能够以符号方式求解公式（eps 反对 0），这可能会导致最佳解决方案......只是一个想法。
Uh. The first thing that come to my mind is, that at each point you need to calculate the gradient or vector to find out the direction to go in the next step. Then you move by a small epsilon and redo.
This basically creates a grid for you, you could vary the cell size by choosing a small epsilon. By doing this instead of using a fixed grid you should be able to calculate even with small degrees in each step -- smaller then 45° from your 8-point example.
Theoretically you might be able to solve the formulas symbolically (eps against 0), which could lead to on optimal solution... just a thought.
障碍是如何表示的？它们是多边形吗？然后，您可以使用多边形顶点作为节点。如果障碍物没有表示为多边形，您可以在它们周围生成某种凸包，并使用其顶点进行导航。编辑：我刚刚意识到，你提到你必须绕过相对较多的障碍。对于许多障碍物，使用障碍物顶点可能不可行。
我不知道移动障碍物，我相信 A* 找不到移动障碍物的最佳路径。
你提到你的物体向后移动第四个 - A* 不应该这样做。 A*仅访问每个移动点一次。这可能是动态生成移动点或移动障碍物产生的伪影。
How are the obstacles represented? Are they polygons? You can then use the polygon vertices as nodes. If the obstacles are not represented as polygons, you could generate some sort of convex hull around them, and use its vertices for navigation. EDIT: I just realized, you mentioned that you have to navigate around a relatively high number of obstacles. Using the obstacle vertices might be infeasible with to many obstacles.
I do not know about moving obstacles, I believe A* doesn't find an optimal path with moving obstacles.
You mention that your object moves back and fourth - A* should not do this. A* visits each movement point only once. This could be an artifact of generating movement points on the fly, or from the moving obstacles.
我记得在大学时遇到过这个问题，但我们没有使用 A* 搜索。我不记得数学的具体细节，但我可以告诉你基本的想法。也许其他人可以更详细。
我们将在您的游戏区域外创建一个物体可以跟随的势场。
选取你的比赛场地并倾斜或扭曲它，使起点位于最高点，而目标位于最低点。
在目标中戳一个势井，以强化它是一个目的地。
现在想象你的物体是一个弹珠。如果你把它放在起点，它应该滚下比赛场地，绕过障碍物，然后落入球门。
最困难的部分，即我不记得的数学，是代表这些凹凸和凹坑的方程式。如果你弄清楚了，将它们加在一起以获得最终的场，然后进行一些向量微积分来找到梯度（就像 towi 所说的那样），这就是你在任何步骤中想要走的方向。希望这种方法足够快，以便您可以在每一步重新计算它，因为障碍物会移动。
I remember encountering this problem in college, but we didn't use an A* search. I can't remember the exact details of the math but I can give you the basic idea. Maybe someone else can be more detailed.
We're going to create a potential field out of your playing area that an object can follow.
Take your playing field and tilt or warp it so that the start point is at the highest point, and the goal is at the lowest point.
Poke a potential well down into the goal, to reinforce that it's a destination.
Now imagine your object as a marble. If you placed it at the starting point, it should roll down the playing field, around obstacles, and fall into the goal.
The hard part, the math I don't remember, is the equations that represent each of these bumps and wells. If you figure that out, add them together to get your final field, then do some vector calculus to find the gradient (just like towi said) and that's the direction you want to go at any step. Hopefully this method is fast enough that you can recalculate it at every step, since your obstacles move.
听起来您正在基于 Norvig 和 Russel 在人工智能：现代方法<中对 A* 的讨论来实现 Wumpus 游戏/a>，或非常类似的东西。
如果是这样，您可能需要将障碍物检测作为您的启发式功能的一部分（因此您需要有传感器来提醒您的代理注意障碍物的迹象，如此处）。
为了解决来回问题，您可能需要存储走过的路径，这样您就可以知道您是否已经去过某个位置，并让启发式函数检查过去的 N 次移动（例如 4 次）并将其用作决胜局（即如果我可以从这里向北和向东走，而我最后的4步棋是东、西、东、西，这次向北走）
Sounds like you're implementing The Wumpus game based on Norvig and Russel's discussion of A* in Artifical Intelligence: A Modern Approach, or something very similar.
If so, you'll probably need to incorporate obstacle detection as part of your heuristic function (hence you'll need to have sensors that alert your agent to the signs of obstacles, as seen here).
To solve the back and forth issue, you may need to store the traveled path so you can tell if you've already been to a location and have the heurisitic function examine the past N number of moves (say 4) and use that as a tie-breaker (i.e. if I can go north and east from here, and my last 4 moves have been east, west, east, west, go north this time)