计划开发 2D RTS，我试图了解 Astar 的工作原理。确实，我找到了一些文章，解释了如何将 Astar 与二进制堆结合起来进行优化，以及利用路径对称性的算法，如Jump Poin Search 算法。我尝试实现Jump Point Search，它运行良好。我什至用 MovingAI 的地图做了一些基准测试。
然而有一个问题。允许对角线移动时一切正常。禁用时，不返回任何路径...
它可能与我实现它的方式有关，然后我都在问...一般来说，您如何要求算法（JPS）搜索仅涉及直线移动（而不是对角线移动）的路径以达到目标？
跳转点搜索需要启用对角线才能工作。在状态算法中，这是它的局限性之一。此外，您将无法使您的地形可区分（泥浆 = 对运动的惩罚等），因为这会破坏对称性。我建议你坚持 A* 并尝试通过地形呈现（网格、航点）来获得性能。或者也许检查 HPA*。
如果您让它沿着垂直于原始方向的方向发送子搜索（就像对角线移动一样），那么应该可以创建一个仅使用基本方向的 JPS 版本。这样做，它将能够找到给定位置的节点何时会找到更前面的节点。
好吧，从技术上讲，如果不允许对角线移动，那么您的最佳启发式是曼哈顿距离。这意味着 A* 将以最少的动作找到答案。在网格中表示您的地图，每个节点都有一个 onOpen 和 onClosed 布尔值，而不是使用封闭列表，这是一个巨大的优化。另外，如果你使用 std make heap、push_heap 和 pop heap，你可以获得成本 log n (1 to pop + log n to sort = O(logn)) 的最便宜的节点，这比使用向量的伸缩性要好得多。