前言

JPS 算法是一个基于 Grid 的寻路算法，其在保留 A 算法基本框架的基础上，优化了寻找后继结点的逻辑。A 当中是通过获取当前节点所有非关闭的可达邻居来拓展后续节点，而 JPS 是通过根据当前节点的方向，基于跳点搜索的策略来拓展后续节点。

JPS 主要遵循 两个定义，三个规则

定义

forced neighbour

  • 结点 n 是 x 的邻居
  • 节点 n 的邻居有阻挡（即不可行走的格子）
  • (parent(x) -> x -> n) 的路径长度 < 任何 (parent(x) -> n 且不经过 x) 的路径长度

此处 parent(x) 为路径当中 x 前一个点。

此时可以称 n 为 x 的强迫邻居，x 为 n 的跳点。

图1.1.1

如图 1.1.1，寻找 S 到 E 的路径，其中 K 为 I 的强迫邻居，I 为 K 的跳点。如果 H 右边没有阻挡，那么 K 将为 H 的强迫邻居（H 为 K 的跳点）

jump point

  • 如果点 y 是起点或者目标点，那么其就是跳点。如图 1.1.1 当中，S 和 E 都是跳点。
  • 如果 y 有强迫邻居则 y 是跳点，例如 I 就是一个跳点。跳点和强迫邻居是一个伴生的关系。比如 K 的邻居只有 I 是一个跳点，M 虽然也是 I 的邻居，但其不是跳点。
  • 如果 parent(x) 到 y 是对角线移动，并且 y 经过水平或者垂直方向也可以到达跳点，则 y 是跳点。例如 parent(G) 也就是 S 到 G 是对角线移动，而 G 到 I 为垂直移动，I 是跳点因此 G 也是跳点。

规则

为了和对角线作区分，下文的直线都表示为水平方向和垂直方向。

规则一

搜索跳点的过程当中，如果直线方向和对角线方向都能移动，则优先搜索直线方向。

规则二

  • 如果从 parent(x) 到 x 是直线移动，n 是 x 的邻居。如果有从 parent(x) 到 n 的路径不经过 x 且路径长度小于或者等于从 parent(x) 经过 x 到 n 的路径，则走到 x 后下一个点不会走到 n。
  • 如果从 parent(x) 到 x 是对角线移动，n 是 x 的邻居。如果有从 parent(x) 到 n 的路径不经过 x 且路径长度小于从 parent(x) 经过 x 到 n 的路径，则走到 x 后下一个点不会走到 n。

规则三

只有跳点才会被加入 openset，因为跳点会改变行走方向，而非跳点不会。

寻路流程

若当前为直线方向

  • 如果 current 左后方不可走且左方可走（即左边是强迫邻居），则沿着 current 左前方和左方寻找不在 closedset 当中的跳点。
  • 如果 current 当前方向可走，则沿着 current 当前方向寻找不在 closedset 的跳点。
  • 如果 current 右后方不可走且右方可走（右方是强迫邻居），则沿着 current 右前方和右方寻找不在 closedset 当中的跳点。

若当前为对角线方向

  • 如果 current 的水平分量（例如东北方向的水平分量为东）可走，则沿着 current 当前方向的水平分量寻找不在 closedset 当中的跳点。
  • 如果 current 当前方向可走，则沿着 current 当前方向寻找不在 closedset 当中的跳点。
  • 如果 current 当前的垂直分量能走，则沿着 current 当前方向的垂直分量寻找不在 closedset 当中的跳点。