如何在没有节点或单元的无网格 2D 平面上实现 A* 算法？我需要对象在目标途中绕过相对较多的静态和移动障碍物。我当前的实现是在对象周围创建八个点，并将它们视为可能是对象潜在位置的虚构相邻正方形的中心。然后我计算每个启发式函数并选择最好的。起点和运动点之间的距离，以及运动点和目标之间的距离我用勾股定理计算正常的方式。问题是这样的对象经常忽略所有的障碍物，甚至更经常地被卡在两个位置之间来回移动。我意识到 mu 问题可能看起来多么愚蠢，但感谢您提供任何帮助。
问问题
4661 次
5 回答
5
以适合您的问题的任何分辨率创建一个虚构的网格：尽可能粗粒度以获得良好的性能，但细粒度足以找到障碍物之间的（理想的）间隙。您的网格也可能与带有障碍物的四叉树相关。
在网格上执行 A*。网格甚至可以预先填充有用的信息，例如接近静态障碍物。一旦你有一条沿着网格方块的路径，将该路径后处理为一系列路径点，只要路径中有拐点。然后沿着航点之间的线行驶。
顺便说一句，您不需要实际距离（参见您提到的勾股定理）：A* 可以很好地估计距离。曼哈顿距离是一个流行的选择：|dx| + |dy|。如果您的网格游戏允许对角线移动（或网格是“假的”），那么简单max(|dx|, |dy|)可能就足够了。
于 2010-10-29T18:38:22.803 回答
1
呃。我想到的第一件事是，在每一点你都需要计算梯度或向量来找出下一步的方向。然后你移动一个小ε并重做。
这基本上为您创建了一个网格，您可以通过选择一个小的epsilon来改变单元格大小。通过这样做而不是使用固定网格，您应该能够在每一步中计算小角度 - 比您的 8 点示例小 45°。
从理论上讲，您可能能够象征性地求解公式（eps 对 0），这可能会导致最佳解决方案......只是一个想法。
于 2010-10-29T18:28:57.147 回答
1
障碍是如何表示的？它们是多边形吗？然后，您可以将多边形顶点用作节点。如果障碍物不表示为多边形，您可以在它们周围生成某种凸包，并使用其顶点进行导航。编辑：我刚刚意识到，您提到您必须绕过相对较多的障碍物。对于许多障碍物，使用障碍物顶点可能是不可行的。
我不知道移动障碍物，我相信 A* 没有找到移动障碍物的最佳路径。
您提到您的对象向后移动和第四次移动 - A* 不应该这样做。A* 只访问每个运动点一次。这可能是在飞行中或从移动的障碍物生成运动点的伪影。
于 2010-10-29T18:38:04.960 回答
1
我记得在大学时遇到过这个问题，但我们没有使用 A* 搜索。我不记得数学的确切细节，但我可以给你基本的想法。也许其他人可以更详细。
我们将在您的游戏区域之外创建一个物体可以跟随的势场。
把你的比赛场地倾斜或扭曲，使起点在最高点，目标在最低点。
将潜在的井戳入目标，以强调它是一个目的地。
- 对于每一个障碍，创造一个潜在的小山。对于您的非点障碍物，势场可以在障碍物的边缘逐渐增加。
现在将您的对象想象成大理石。如果你把它放在起点，它应该滚下比赛场地，绕过障碍物，落入球门。
困难的部分，我不记得的数学，是代表每个凹凸和凹坑的方程式。如果你弄清楚了，把它们加在一起得到你的最终场，然后做一些向量演算来找到梯度（就像 towi 说的那样），这就是你在任何一步都要走的方向。希望这个方法足够快，你可以在每一步重新计算它，因为你的障碍物会移动。
于 2010-10-29T18:39:13.167 回答