跳点搜索算法JPS及其优化

引言

寻路算法用途众多，例如在游戏和地图中。A*算法已经众所周知，对于其优化也是层出不穷，然而性能并没有取得突破性进展。本文介绍一种跳点搜索算法JPS以及其四个优化算法，其中三个优化是加速跳点的寻找，第四个优化是加速寻路失败情况的判断。为了测试搜索算法的优化性能，实验中设置游戏场景使得起点和终点差距200个格子，需要寻路10000次。结果发现，A*寻路总时间约2.6074x1011纳秒（一秒为109纳秒）；基础版JPS寻路总时间1.7037x1010纳秒；利用位运算优化的JPS（下文称JPS-Bit）寻路总时间3.2364x109纳秒；利用位运算和剪枝优化的JPS（下文称JPS-BitPrune）寻路总时间2.3703x109纳秒；利用位运算和预处理的JPS（下文称JPS-BitPre）寻路总时间2.0043x109纳秒；利用位运算、剪枝和预处理三个优化的JPS（下文称JPS-BitPrunePre）寻路总时间9.5434x108纳秒。其中的预处理在一些文章被称为JPS+。本文的JPS-Bit和JPS-BitPrune都支持动态阻挡。本文解决了绝大部分开源JPS存在的潜在BUG：穿越阻挡，在图2中，从H走到K时，穿越H右边阻挡。

上述结果表明，寻路200个格子的路径，JPS的五个版本，平均消耗时间分别为1.7毫秒、0.32毫秒、0.23毫秒、0.02毫秒、0.095毫秒，寻路速度分别为A*算法的15倍、81倍、110倍、130倍、273倍，大幅度超越A*算法，标志着寻路已经不会成为性能的瓶颈。

事实上，在2012到2014年举办的三届（目前为止只有三届）基于Grid网格寻路的比赛GPPC（The Grid-Based Path Planning Competition）中，JPS已经被证明是基于无权重格子，在没有预处理的情况下寻路最快的算法。本文接下来介绍JPS基础版本以及四个优化算法；然后解读GPPC2014的比赛，介绍GPPC的比赛地图数据，并从寻路时间、路径长度、消耗内存、失败率等方面比较22个参赛寻路算法的优劣

JPS算法

2.1 算法介绍

JPS又名跳点搜索算法（Jump Point Search），是由澳大利亚两位教授于2011年提出的基于Grid格子的寻路算法。A*算法整体流程如表一所示，JPS算法在保留A*算法的框架的同时，进一步优化了A*算法寻找后继节点的操作。为了说明JPS在A*基础上的具体优化策略，我们在图1中给出A*和JPS的算法流程图对比。由图1看出，JPS与A*算法主要区别在后继节点拓展策略上，不同于A*算法中直接获取当前节点所有非关闭的可达邻居节点来进行拓展的策略，JPS根据当前结点current的方向、并基于跳点的策略来扩展后继节点，遵循“两个定义、三个规则”（见表二，两个定义确定强迫邻居、跳点，三个规则确定节点的拓展原则），具体流程如下：

一，若current当前方向是直线方向：（1）如果current左后方不可走且左方可走（即左方是强迫邻居），则沿current左前方和左方寻找不在closedset的跳点；（2）如果current当前方向可走，则沿current当前方向寻找不在closed集合的跳点；（3）如果current右后方不可走且右方可走（右方是强迫邻居），则沿current右前方和右方寻找不在closedset的跳点；

二，若current当前方向为对角线方向：（1）如果current当前方向的水平分量可走（例如current当前为东北方向，则水平分量为东），则沿current当前方向的水平分量寻找不在closedset的跳点；（2）如果current当前方向可走，则沿current当前方向寻找不在closedset的跳点；（3）如果current当前方向的垂直分量可走（例如current当前为东北方向，则垂直分量为北），则沿current当前方向的垂直分量寻找不在closedset的跳点。JPS寻找跳点的过程有三种优化：一，位运算；二；预处理；三；剪枝中间跳点。

图1 A*和JPS的算法流程图对比

2.2 JPS算法举例

图2 寻路问题示例场景（5*5的网格）

下面举例说明JPS具体的寻路流程。问题示例如图2所示，5*5的网格，黑色代表阻挡区，S为起点，E为终点。JPS要寻找从S到E的最短路径，首先初始化将S加入openset。从openset取出F值最小的点S，并从openset删除，加入closedset，S的当前方向为空，则沿八个方向寻找跳点，在该图中只有下、右、右下三个方向可走，但向下遇到边界，向右遇到阻挡，因此都没有找到跳点，然后沿右下方向寻找跳点，在G点，根据上文定义二的第（3）条，parent(G)为S，praent(G)到S为对角线移动，并且G经过垂直方向移动（向下移动）可以到达跳点I，因此G为跳点 ，将G加入openset。从openset取出F值最小的点G，并从openset删除，加入closedset，因为G当前方向为对角线方向（从S到G的方向），因此在右、下、右下三个方向寻找跳点，在该图中只有向下可走，因此向下寻找跳点，根据上文定义二的第（2）条找到跳点I，将I加入openset。从openset取出F值最小的点I，并从openset删除，加入closedset，因为I的当前方向为直线方向（从G到I的方向），在I点时I的左后方不可走且左方可走，因此沿下、左、左下寻找跳点，但向下、左下都遇到边界，只有向左寻找到跳点Q（根据上文定义二的第（2）条）），因此将Q加入openset。从openset取出F值最小的点Q，并从openset删除，加入closedset，因为Q的当前方向为直线方向，Q的左后方不可走且左方可走，因此沿右、左、左上寻找跳点，但向右、左上都遇到边界，只有向左寻找到跳点E（根据上文定义二的第（1）条）），因此将E加入openset。从openset取出F值最小的点E，因为E是目标点，因此寻路结束，路径是S、G、I、Q、E。注意，本文不考虑从H能走到K的情况，因为对角线有阻挡（这点和论文不一致，但和代码一致，因为如果H到K能直接到达，会走进H右边的阻挡区，大部分的JPS开源代码根据论文都认为H到K能直接到达，所以存在穿越阻挡的情况），如果需要H到K能走，则路径是S、G、H、K、M、P、E，修改跳点的计算方法即可。

表三 A*和JPS的寻路消耗对比

上述的JPS寻路效率是明显快于A*的，原因在于：在从S到A沿垂直方向寻路时，在A点，如果是A*算法，会将F、G、B、H都加入openset，但是在JPS中这四个点都不会加入openset。对F、G、H三点而言，因为从S、A、F的路径长度比S、F长，所以从S到F的最短路径不是S、A、F路径，同理S、A、G也不是最短路径，根据上文规则二的第（1）条，走到A后不会走到F、G，所以F、G不会加入openset，虽然S、A、H是S到H的最短路径，但因为存在S、G、H的最短路径且不经过A，据上文规则二的第（1）条，从S走到A后，下一个走的点不会是H，因此H也不会加入openset；对B点而言，根据上文规则三，B不是跳点，也不会加入openset，直接走到C即可。表三所示为A*和JPS在寻路消耗中的对比，D. Age: Origins、D. Age 2、StarCraft为三个游戏龙腾世纪：起源、、龙腾世纪2、星际争霸的场景图集合，M.Time表示操作openset和closedset的时间，G.Time表示搜索后继节点的时间。可见A*大约有58%的时间在操作openset和closedset，42%时间在搜索后继节点；而JPS大约14%时间在操作openset和closedset，86%时间在搜索后继节点。避免在openset中加入太多点，从而避免过多的维护最小堆是JPS比A*快的原因（（最小堆插入新元素时间复杂度log(n)，删除最小元素后调整堆，时间复杂度也为log(n)）），实际上在从S到E的寻路过程中，进入openset的只有S、G、I、Q、E。

JPS算法的四个优化算法

3.1 JPS优化之一JPS-Bit：位运算优化

利用位运算优化的JPS-Bit的关键优化思路在于利用位运算来优化JPS中节点拓展的效率。JPS-Bit和下文介绍的JPS-BitPrune支持动态阻挡，当动态阻挡出现时，将格子标记为阻挡，当动态阻挡消失时，将格子标记为非阻挡，如果动态阻挡占据k个格子，则时间复杂度为O(k)。下面以图3中的场景示例说明如何将位运算融合于JPS算法中，其中黑色部分为阻挡，假设当前位置为I（标蓝位置），当前方向为右，位运算中使用1代表不可走，0代表可走，则I当前行B的八位可以用八个bit：00000100表示，I上一行B-的八位可以用八个bit：00000000表示，I的下一行B+的八位可以用八个bit：00110000表示。在当前行寻找阻挡的位置可以用CPU的指令__builtin_clz(B)（返回前导0的个数），即当前阻挡在第5个位置（从0开始）。寻找当前行的跳点可以用__builtin_clz(((B->>1) && !B-) ||((B+>>1) && !B+)) 寻找，例如本例中(B+>>1) && !B+为：(00110000 >> 1) && 11001111，即00001000，而(B->>1) &&!B为00000000，所以__builtin_clz(((B->>1) && !B-) ||((B+>>1) && !B+))为__builtin_clz(00001000)为4，所以跳点为第4个位置M（从0开始）。注意论文中使用_builtin_ffs(((B-<<1) && !B-) ||((B+<<1) && !B+))，__builtin_ffs(x)返回x的最后一位1是从后向前第几位，比如7368（1110011001000）返回4，因为论文对格子的bit编码采用小端模式，而这里对格子的bit编码采用大端模式。

由于JPS-Bit使用运算效率更高的位运算和CPU指令运算来优化原始JPS节点扩展过程中的遍历操作，JPS-Bit的算法效率高于原始的JPS，实测中JPS-Bit的寻路时间比JPS缩短5倍左右。

图3寻路问题示例场景（3*8的网格）

3.2 JPS优化之二JPS-BitPrune：位运算与剪枝优化

利用位运算和剪枝优化的JPS-BitPrune在JPS-Bit的基础上进一步进行剪枝优化，剪掉不必要的中间跳点（见表二，定义二第(3)条定义），根据定义二，中间跳点在节点拓展过程中只具有简单的“承接”作用，不具备拓展价值，将中间跳点放入openset会增大扩展的次数，因此JPS-BitPrune将中间跳点全部删除，将中间跳点后继跳点中的非中间跳点的父跳点改为中间跳点的父跳点，可以有效避免冗余的节点拓展运算。

拐点获取：值得一提的是，JPS-BitPrune由于删除了中间跳点，因此JPS-BitPrune需要在搜索到完整的路径之后以一定的策略在最后寻得的路径中加入中间拐点，使得每两个相邻的路径节点之间都是垂直、水平、对角线方向可达的。对此，JPS-BitPrune采用的具体方法如下：

假设目前搜索到的路径为start(jp1)、jp2、jp3...jpk..end(jpn)，对每两个相邻的跳点jpi、jpi+1，一，如果jpi、jpi+1的x坐标或者y坐标相等，说明这两个跳点在同一个水平方向或垂直方向，可以直线到达，无需在这两个跳点之间加入拐点；二，如果jpi、jpi+1的x坐标和y坐标都不相等，（1）如果x坐标的差dx（即jpi的x坐标减去jpi+1的x坐标）和y坐标的差dy的绝对值相等，说明这两个跳点在对角线方向，也可以直线到达，无需在这两个跳点之间加入拐点；（2）如果x坐标的差dx和y坐标的差dy的绝对值不相等，说明这两个跳点不在对角线方向，并且有可能不能直线到达（因为跳点附近有阻挡），此时jpi、jpi+1之间只需要加入一个从jpi出发离jpi+1最近的对角线上的点即可（jpi、jpi+1不能水平、垂直、对角线到达，说明jpi、jpi+1之间一定存在被剪枝的中间跳点，只需要补上离jpi+1最近的一个中间跳点充当拐点即可，该拐点即为jpi沿对角线方向走min(dx,dy)步到达的点）。

图4 JPS-BitPrune的剪枝优化示例

下面以图4的问题场景示例JPS-BitPrune如何在剪枝的同时进行寻路。起点为S（坐标为(1,1)，即S(1,1)），节点1、4、6均为中间跳点：因为节点2、3是满足定义二第(2)条的跳点，所以节点1是为了到达节点2、3的中间跳点，同理节点4、6也为中间跳点。在剪枝中间跳点之前，要将中间跳点的后继节点的父节点调整为该中间跳点的父节点。例如图4中，节点1的后继跳点为节点2、3、4，其中节点4也为中间跳点，删掉中间跳点中的节点1后，节点2、3的父跳点由节点1改为节点S，删除中间跳点中的节点4后，节点4的后继跳点5的父跳点由节点4改为节点S（节点4的父跳点为节点1，但节点1已经被删掉，因此回溯到节点S），删除中间跳点中的节点6后，节点6的后继跳点7的父跳点由节点6改为节点S（节点6的父跳点为节点4，但节点4被删，节点4的父跳点节点1也被删，因此回溯到节点S）。上述过程是简化的逻辑描述，实际运行中的做法是从节点S寻找跳点，首先找到中间跳点节点1，然后在水平方向和垂直方向寻找到跳点节点2、3，将节点2、3的父跳点设为节点S；继续沿对角线方向寻找跳点，走到节点4后，沿水平方向和垂直方向寻找到跳点节点5，将节点5的父跳点设为节点S；继续沿对角线方向寻找跳点，走到节点6后，沿水平方向和垂直方向寻找到跳点7，将跳点7的父跳点设为节点S。因此JPS-BitPrune获得路径S(1,1) 、节点7(4,6)。因为路径中S(1,1)无法垂直、水平、对角线方向走到节点7(4,6)，需要加入中间拐点，根据上述的拐点添加策略，有dx为3，dy为5，需要从S沿对角线走3步，即节点6(4,4)可作为中间拐点，因此，在图4的示例中，JPS-BitPrune最后构建的完整路径为S(1,1) 、节点6(4,4) 、节点7(4,6)。

3.2.1 剪枝的优化效率

下面通过对比剪枝前后的JPS节点拓展的情况来说明剪枝操作的优化效率：

场景一（无剪枝） 如果不对中间跳点进行剪枝，那么从节点S寻路到节点7将经历如下过程：

(1)从节点S搜索跳点，找到跳点节点1，openset此时只有节点1；

(2)从openset取出F值最小跳点节点1，并搜索节点1的后继跳点，水平方向和垂直方向找到跳点节点2、3，对角线方向找到跳点节点4，此时openset有节点2、3、4；

(3)从openset取出F值最小跳点节点4，并搜索节点4的后继跳点，水平和垂直方向找到跳点节点5，对角线方向找到跳点6，此时openset有节点2、3、5、6；

(4)从openset取出F值最小跳点节点6，垂直方向找到跳点7，此时openset有节点2、3、5、7；

(5)从openset取出F值最小的跳点节点7，为目的点，搜索结束，因此完整路径为节点S(1,1)、节点1(2,2) 、节点4(3,3) 、节点6(4,4) 、节点7(4,6)。JPS在到达目的节点7之前，需要接连拓展中间跳点1，4，6。

场景二（剪枝中间跳点） 在剪枝中间跳点之后，从节点S寻路到节点7的流程得到了明显简化：

(1)从节点S寻找跳点，首先找到中间跳点节点1，然后在水平方向和垂直方向寻找到跳点节点2、3，将节点2、3的父跳点设为节点S；继续沿对角线方向寻找跳点，走到节点4后，沿水平方向和垂直方向寻找到跳点节点5，将节点5的父跳点设为节点S；继续沿对角线方向寻找跳点，走到节点6后，沿水平方向和垂直方向寻找到跳点7，将跳点7的父跳点设为节点S；继续沿对角线方向寻找跳点，遇到阻挡，搜索终止，此时openset有节点2、3、5、7；

(2)从openset取出F值最小的跳点节点7，为目的点，搜索结束，此时获得的路径为S(1,1) 、节点7(4,6)。不同于无剪枝的JPS需要拓展中间跳点1、4、6，在JPS-BitPrune中，节点1、4、6作为中间跳点均被剪枝，有效避免了冗余的节点拓展，寻路效率得到大大提升。

3.3 JPS优化之三JPS-BitPre：位运算与预处理

图5 JPS-BitPre寻路的场景示例

本优化中的预处理在一些文章被称为JPS+。JPS-BitPre和JPS-BitPrunePre都不支持动态阻挡，因为动态阻挡的出现会导致八个方向最多能走的步数发生变化，从而导致预处理的结果不再准确。利用位运算和预处理的JPS-BitPre依旧采用JPS-Bit中的位运算，而其中的预处理则是对每个点存储八个方向最多能走的步数step，这个step值将影响JPS中节点的拓展顺序和拓展“跨度”，加快寻路效率。由于预处理版本的JPS需要存储八个方向最多能走多少步，如果地图大小是N*N，每个方向最多能走的步数用16位数表示，则需要存储空间N*N*8*16bit，如果N为1024，则大概需要存储空间为16M，存储空间占用较大，使用该版本JPS时需要权衡是否以空间换时间，另外预处理的时间对小于1024*1024个格子的图可以在1秒内处理完，但对于2048*2048个格子的图需要一小时左右处理完。

其中，step值由跳点、阻挡、边界等决定，如果遇到跳点，则step为走到跳点的步数；否则step为走到阻挡或边界的步数。例如对图5中的N点，向北最多走到节点8，即2步；向南最多走到节点4，即4步；向西最多走到节点6，即3步；向东最多走到节点2（节点2是满足定义二第（2）条的跳点），即5步；西北最多走到节点7，即2步；东北最多走到节点1（节点为1是上文定义二第（3）条定义的跳点），即1步；西南最多走到节点5，即3步；东南最多走到节点3（节点3是上文定义二第（3）条定义的跳点），即3步。

以图5中的场景为例，要寻找从节点N到节点T的路径，JPS-BitPre的寻路流程如下：

(1)从openset取出节点N， 从N沿八个方向寻找跳点，根据预处理得到的各方向最远可走的step值，可以快速确定八个方向最远能到达的节点{1，2，3，4，5，6，7，8}，如图5所示，其中，节点1、2、3均为满足定义二的跳点，直接加入openset，对于节点4、5、6、7、8，首先判断终点T位于以N为中心的南、西南、西、西北、北的哪部分，因为T位于西南方向，只有节点5位于西南方向，因此节点4、6、7、8直接略过，在从N到5的方向上，N可走3步，而N和T的x坐标差绝对值dx为1，y坐标差绝对值dy为2，因此将从节点N到节点5方向上走min(dx,dy)步即节点11，加入openset；

(2)从openset取出F值最小节点11，垂直方向找到跳点T，加入openset；三，从openset取出F值最小节点T，为目的点，搜索结束，此时获得的路径为N(4,5)、节点11(3,4) 、节点T(3,3)。

为了说明JPS-BitPre寻路的准确性与高效率，这里给出原始JPS-Bit从N到T的寻路流程作为对比：

(1)从openset取出节点N后，需要沿八个方向寻找跳点，节点1、3、11为上文定义二第（3）条定义的跳点，加入openset，节点2为上文定义二的第（2）条定义的跳点，加入openset；

(2)从openset取出F值最小节点11，垂直方向找到跳点T，加入openset；

(3)从openset取出F值最小跳点T，为目的点，搜索结束，此时获得的路径也为N(4,5)、节点11(3,4) 、节点T(3,3)。

对比发现，经过预处理的JPS-BitPre和只使用位运算的JPS-Bit最后寻得的路径是一样的，然而，由于JPS-BitPre无需在每一步节点拓展过程中沿各方向寻找跳点，其可以根据预处理得到的step值快速确定openset的备选节点，从而大大提升寻路效率。

3.4 JPS优化之四：不可达两点提前判断

如图6所示，起点S不可到达终点E，然而寻路算法仍然会花费时间去寻找S、E之间的路径，而且失败情况下寻路花费的时间远大于成功情况下寻路花费的时间，因为失败情况下需要遍历所有的路径，才能确定两点不可达。因此为了避免这种情况，在每次寻路之前，判断起点和终点是否可达：如果起点和终点在同一连通区域，则起点和终点可达，否则不可达。只有起点和终点可达，才需要去寻路。

首先计算Grid网格的连通区域，算法如表三所示，算法只能采用宽度优先搜索，深度优先搜索的递归层次太深，会导致栈溢出。按照表三的算法，图6的点S、1、2的连通区域编号均为1，点3、4、E的连通区域编号均为2，S、E连通区域编号不同，因此S、E不在同一连通区域，不需要寻找路径。表三的算法在程序启动时计算一次即可，算法复杂度为O(N)，N为Grid网格数目，运行时只需要查询两点是否在同一连通区域，算法复杂度为O(1)。

图6 不可达的两点 S 、E

Chapter 4

GPPC竞赛解读

4.1 GPPC竞赛与地图数据集

基于格子的寻路一直是被广泛研究的热点问题，也有很多已经发表的算法，但是这些算法没有相互比较过，因此也难辨优劣，使用者如何选择算法也有很大的困难。为了解决这个问题，美国丹佛大学的Nathan R. Sturtevant教授创办了基于Grid格子的寻路比赛：The Grid-Based Path Planning Competition，简称GPPC，目前已经在2012、2013、2014举办过三次，下文主要讨论GPPC2014。

GPPC比赛用的地图集如表四所示，地图数据主要分为游戏场景图和人造地图。其中来自游戏场景图的数据有三类：Starcraft（星际争霸）、Dragon Age2（龙腾世纪2）、Dragon Age:origins（龙腾世纪：起源），三个游戏分别提供地图11、57、27张，提供寻路问题29970、54360、44414个。来自人造地图有三类：迷宫、随机、房间，三类数据分别提供地图18、18、18张，提供寻路问题145976、32228、27130个。六类数据共提供地图132张，寻路问题347868个。图6中给出三个游戏的场景图示例，图7中给出三类人造地图示例，其中黑色代表阻挡区，白色代表可行走区。地图大小从100*100到1550*1550，六个地图集的大小分布如图8所示，横坐标是格子数，纵坐标是地图数目，最小的地图来自Dragon Age:origins（龙腾世纪：起源），最大的地图来自Starcraft（星际争霸）和人造数据。

表四 GPPC比赛用的地图集

图6 GPPC的三类游戏场景地图示例

图7 GPPC的三类人造场景地图示例

图8 GPPC的六类地图大小分布

4.2 GPPC的评价体系

GPPC在相同的配置下运行参赛算法，其中CPU的配置是Xeon E5620，四核处理器、2.4Ghz主频，12G内存。为了消除误差，GPPC要求对每个参赛的寻路方法在34868个寻路问题上运行5遍，共寻路34868*5，即174340次，所以下文介绍的总运行时间等指标都是寻路174340次的结果汇总。其中运行时间包括：加载预处理数据和寻路时间，而预处理时间并不计算在运行时间内。GPPC定义如下13个指标来评价寻路算法（其中，路径表示从起点到终点的完整路径）：

1. Total (秒)：寻路174340次所花费的总时间。

2. Avg(毫秒)：寻路174340次的平均时间。

3. 20 Step(毫秒)：寻找到路径的前20步所花费的平均时间。该指标衡量最快多久可以跟随路径，在实时交互例如游戏中，该指标很重要。

4. Max Segment(毫秒)：每条路径最长段的寻路平均时间。该指标衡量在实时交互中，寻路方法最差情况下的表现。

5. Avg Len：路径的平均长度。如果A寻路算法在长路径上表现好，在短路径上表现不好；B寻路算法在长路径上表现不好，在短路径上表现好，则A的该指标优于B的指标，因为Avg Len的增加主要来自长路径。该指标偏向于在长路径上表现好的寻路方法。

6. Avg Sub-Opt：寻到的路径长度/最优路径长度 的平均值。如果A寻路方法在长路径上表现好，在短路径上表现不好；B路径寻路方法在长路径上表现不好，在短路径上表现好，则B的该指标优于A的指标，因为174340次寻路大多数的路径都是短路径。该指标偏向于在短路径上表现好的寻路方法。

7. Num Solved：在174340次寻路中，成功的数目。

8. Num Invalid：在174340次寻路中，返回错误路径的数目。错误路径：路径的相邻路点无法直线到达。

9. Num UnSolved：在174340次寻路中，没有寻找到路径的数目。

10. RAM(before)(兆)：寻路算法在加载预处理数据后，寻路之前占用的内存。

11. RAM(after)(兆)：寻路174340次后占用的内存，包括所有寻路结果占用的内存。

12. Storage：预处理的数据占用的硬盘大小。

13. Pre-cmpt(分钟)：预处理数据花费的时间，表3中该列数字之前的“+”表示采用并行计算进行预处理。

4.3 GPPC参赛算法及其比较

目前为止参加GPPC竞赛的算法共有22个，其中参加GPPC2014的有14个，可大致分为如下4类：一，对A*的改进，例如Relaxed A*(RA*)和A* Bucket；二，利用格子特点的算法，例如Jump Point Search(JPS)和SubGoal Graphs；三，预先生成任意两点第一个路点的

压缩数据库，例如SRC；四，基于节点优先级的算法，例如Contraction Hierarchy(CH)。

表五给出参加GPPC2012、2013、2014的共22个算法的结果对比，其中前14个为参与GPPC2014的算法。其中第一列（Entry列）为算法名，其后13列给出每个算法在13个指标下的表现。第一列被黑体加粗的算法表示该算法在某些指标（帕累托最优的指标）达到帕累托最优，该算法所在的行被加粗的指标，表示帕累托最优的指标。帕累托最优表示：没有其他算法在帕累托最优的指标上均优于当前算法。例如JPS(2012)帕累托最优的指标：第6个指标Avg Sub-Opt和第12个指标Storage，达到帕累托最优，表示没有其他算法在6个指标Avg Sub-Opt和第12个指标Storage上均优于JPS(2012)。22种算法没有严格的优劣关系，只是在不同指标下的表现各有侧重，算法的使用者可基于对不同指标的具体需求来选择自己适用的算法。下面给出所有在GPPC中获得帕累托最优的算法，本文介绍的JPS算法位列其中。

1.RA*(2014)：第10个指标RAM(before)和第12个指标Storage帕累托最优。

2.BLJPS(2014)：第2个指标Avg、第6个指标Avg Sub-Opt和第12个指标Storage帕累托最优。

3.BLJPS2(2014)：第2个指标Avg、第6个指标Avg Sub-Opt和第12个指标Storage帕累托最优。

4.RA-Subgoal(2014)：第2个指标Avg和第12个指标Storage帕累托最优。

5.NSubgoal(2014)：第2个指标Avg、第6个指标Avg Sub-Opt和第12个指标Storage帕累托最优。

6.CH(2014)：第2个指标Avg、第6个指标Avg Sub-Opt和第12个指标Storage帕累托最优。

7.SRC-dfs-i(2014)：第3个指标20 Step和第4个指标Max Segment帕累托最优。

8.SRC-dfs(2014)：第2个指标Avg和第6个指标Avg Sub-Opt帕累托最优。

9.JPS(2012)：第6个指标Avg Sub-Opt和第12个指标Storage帕累托最优。本文的主角JPS在未使用预处理的算法中Avg Sub-Opt表现最优。

10.PDH(2012)：第3个指标20 Step和第12个指标Storage帕累托最优。

11.Tree(2013)：第2个指标Avg帕累托最优。