algorithm - 具有 A* JPS(跳跃点搜索)的未探索节点

Question

我正在研究 A* JPS (跳转搜索点) 的实现，尽管我了解它的基础知识，但似乎我仍然遗漏了一点。

这是尝试(见附图)试图找到起始节点(标记为S)和目标节点之间的路径(标记为 G)。带有黑色棋盘格的单元格是已探索的节点，而带有箭头的白色单元格是跳跃点(具有相关方向)。所有单元格的行程成本均为 1，蓝色单元格除外，它们是障碍物。

但是，如您所见，有些区域未被探索，因此尽管路径存在，但它无法找到目标节点。好像是因为在一些跳跃点上没有对角探索造成的，但据我了解，我们应该只考虑当前方向(即跟随图片上的箭头)。

所以我的问题是，这次尝试有什么问题？我是否错过了跳跃点或误解了它的工作方式？

Attached image : A* JPS attempt (还不能嵌入图片 :P)

感谢您的回答。

Linear (both vertical and horizontal, but not diagonals) forced neighbors were missing. C.f. figure 2 of BlueRaja's post

Answer 1

您似乎错过了论文中描述的强制邻居步骤。图片中与箭头相邻的未探索节点应作为强制邻居排队。

参见图 2 和图 3 here .