JPS 寻路算法

发表于 | 分类于
字数统计: 1.6k | 阅读时长 ≈ 5
JPS（Jump Point Search）算法是一种针对 A* 算法的优化，专为网格路径搜索设计。它通过识别路径改变方向的关键点，即跳点，来减少需要评估的节点数量。JPS 算法引入了"强迫邻居"的概念，确保搜索过程不会错过任何可能的路径选择。算法流程包括初始化 OpenList，搜索跳点，并将找到的跳点加入 OpenList，直到目标点被找到或 OpenList 为空。JPS 算法的优势在于提高搜索效率，降低内存使用，尤其适用于大规模地图的路径搜索，因为它能快速跳过可行走区域，而无需逐节点评估。

概述

JPS（Jump Point Search，跳点搜索）算法是对 A* 算法的一种优化。在 A* 算法中，当前节点周围的所有可搜索邻居都会被加入到 OpenList 中。JPS 算法则在保持 A* 算法基本框架的基础上，采用了一种更为高效的策略来确定哪些点需要被加入到 OpenList 中。这种方法能够显著减少需要评估的节点数量，从而提高路径搜索的效率。

强迫邻居

为了减少需要评估的节点数量，JPS 算法引入了强迫邻居的概念。强迫邻居指的是在路径搜索过程中，某些节点的直接邻居是必须被考虑的，因为它们是达到更远距离节点的必经之路。在 JPS 算法中，强迫邻居用于确保搜索过程不会错过任何可能的路径选择。

强迫邻居的定义：当节点 x 的 8 个邻居中存在障碍，且节点 x 的父节点 p 经过节点 x 到达节点 n 的距离代价，总是小于不经过节点 x 到达节点 n 的任意路径的距离代价，则称节点 n 是节点 x 的强迫邻居。

简单来讲，节点 x 是从节点 p 到节点 n 的最短路径的必经节点。

情况一：父子节点是直线关系

情况一
  • 黑色节点：障碍
  • 4：父节点
  • x：子节点
  • 从 4 到 3 的最短路径为：4 → x → 3，因此 3 是节点 x 的强迫邻居

情况二：父子节点是斜线关系

情况二
  • 黑色节点：障碍
  • 6：父节点
  • x：子节点
  • 从 6 到 1 的最短路径为：6 → x → 1，因此 1 是节点 x 的强迫邻居

邻居修剪规则

上面部分没看懂没关系，先对 JSP 算法中的强迫邻居有个大致的印象。接下来，将从邻居修剪开始，让你对强迫邻居的求解有个更直观的感受。

我们先作一些定义：考虑节点 x 的邻居，节点 x 的父节点记为 ，记经过 x 到达 n 的路径为 path1，不经过 x 到达 n 的路径为 path2

情况一：父子节点是直线关系

父子节点是直线关系

如果父子节点之间是直线关系，即父节点经过一次斜线运动可以直接到达子节点，我们不需要考虑存在 path2 小于等于 path1 的邻居。

先考虑图（a）的情况，我们修剪除 n = 5 之外的所有邻居。以 n = 3 为例：

  • path1 = 4 → x → 3：路径长度为
  • path2 = 4 → 2 → 3：路径长度为

这里path1 == path2，需要将该邻居修剪（拒绝加入 OpenList）

因此，对于图（a），x 的下一步应该继续往 5 走，但是不将 5 加入 OpenList。

再考虑图（b）带黑色障碍的情况。相比图（a），我们多了个 n = 3 的邻居无法被修剪。

情况二：父子节点是斜线关系

父子节点是斜线关系

当父子节点是斜线关系时，邻居的修剪规则和直线关系的情况类似，唯一的区别是，此时只修剪存在 path2 严格小于 path1 的邻居。因此，按照此规则，n = 2 和 n = 5 的情况不会被修剪。

再考虑图（d）带黑色障碍的情况。相比图（c），我们多了个 n = 1 的邻居无法被修剪。

得到强迫邻居

图（a）和图（c）不包含任何障碍，我们将应用直线或对角线修剪后的剩余节点（白色格子）称为 x 的自然节点。灰色格子则是 x 的非自然节点。而对于图（b）和图（d），包含障碍之后，各自有一个非自然节点（分别为 n = 3 和 n = 1）无法被修剪，这两个节点则被称为 x 的强迫邻居。

跳点

跳点的要求

当节点 x 满足以下三个条件之一，则称节点 x 为跳点：

  1. 节点 x 是起始点或目标点
  2. 节点 x 至少有一个强迫邻居
  3. 如果节点 x 的父节点 到节点 x 是对角线移动，且 x 可以通过水平或垂直方向的移动到达另一个跳点，则节点 x 也是跳点。

识别跳点的例子

从 x 开始，水平和垂直方向都没有遇到跳点，因此沿着对角线行进。继续重复水平、垂直、对角线。直到到达节点 y。

从节点 y 开始，水平移动 2 格，到达节点 z。节点 z 是跳点，且根据条件 3，节点 y 也是跳点。

算法流程

有了跳点的概念之后，接下来我们就可以介绍 JPS 算法的具体流程。

初始化：将起点加入到 OpenList 中。

搜索跳点：

  • 从 OpenList 中取出具有最小 值的节点作为当前节点（这部分和 A* 算法一样），并将其加入到 CloseList 中
  • 从当前节点开始，沿水平或垂直方向搜索跳点。搜索过程中，如果遇到跳点，则将该跳点加入到 OpenList 中，并停止当前方向的搜索。
  • 接下来，从当前节点开始往对角线方向搜索跳点。对角线方向的搜索优先考虑水平分量，然后是垂直分量。如果找到跳点，则将该跳点加入到 OpenList 中，并停止当前方向的搜索。
  • 若所有方向（8 个方向）已完成搜索，则认为当前节点搜索完毕。

重复搜索：重复执行搜索跳点步骤，直到找到目标点或 OpenList 为空。

JPS 相比 A* 算法的优势

  1. 效率提升：JPS算法通过只扩展关键的跳点（即路径改变方向的点），而不是每个可能的节点，从而显著减少了 OpenList 中节点的数量，提高了搜索效率。
  2. 内存使用降低：由于 OpenList 中节点数量的减少，JPS算法在内存使用上也更加高效。
  3. 适用于大规模地图：JPS 算法在大规模地图上的表现尤为出色，因为它能够快速地跳过大片可行走区域，而不需要逐个节点地进行评估。

参考文献

0%