寻路:跳跃点搜索 - 直线移动与对角线移动

Question

计划在2D RTS上工作，我试图了解Astar是如何工作的。事实上，我找到了一些文章，解释了如何优化 Astar 与二进制堆的耦合，以及利用路径对称性的算法，如跳跃点搜索算法。我尝试实现跳点搜索，它运行良好。我甚至用MovingAI的地图做了一些基准测试。

然而，有一个问题。当允许对角线移动时，一切正常。禁用后，不会返回任何路径...

它可能与我实现它的方式有关，然后我都在问......一般来说，您将如何强制算法（JPS）搜索仅涉及直线移动（而不是对角线移动）的路径以达到目标？

Answer 1

跳转点搜索需要启用对角线才能工作。在状态算法中，这是它的局限性之一。此外，您将无法区分地形（泥浆=移动的惩罚等），因为这会破坏对称性。我建议您坚持使用A*，并尝试通过地形表示（网格，航点）来获得性能。或者检查HPA*。

Answer 2

如果您让 JPS 沿垂直于原始方向的方向发送子搜索（就像对角线移动一样），应该可以创建一个仅使用基本方向的版本。这样做，它将能够找到给定位置的节点何时会找到更前面的节点。

Answer 3

好吧，从技术上讲，如果不允许对角线移动，那么您的最佳启发式方法是曼哈顿距离。这意味着 A* 将以最少的动作找到答案。在网格中表示您的地图，每个节点都有一个 onOpen 和 onClosed 布尔值，而不是使用封闭列表，这是一个巨大的优化。此外，如果你使用 std make heap、push_heap 和 pop heap，你可以得到成本 log n 的最便宜的节点（1 到 pop + log n to sort = O（logn）），它的扩展性比使用向量要好得多。