最简单的寻路算法，寻路算法java

作者：runzhiwang，腾讯TEG后端开发工程师

本文介绍了跳跃搜索算法JPS及其四种优化算法。其最快寻路速度比A*算法快273倍。本文中的JPS-Bit和JPS-BitPrune都支持动态阻塞。

1.首先

寻路算法可用于多种应用，包括游戏和地图。尽管A*算法众所周知，其优化也层出不穷，但其性能却没有取得任何突破。本文介绍JPS 的效率、多线程、内存和路径优化算法。为了测试搜索算法的优化性能，实验中设置了游戏场景，起点和终点相距200格，需要寻路10000次。

结果显示，A*的总路径搜索时间约为2.6074×1011纳秒（1秒为109纳秒），JPS基本版本的总路径搜索时间为1.7037×1010纳秒。位操作优化的总时间为3.2364×109纳秒，使用位操作和剪枝优化的JPS（以下简称JPS-BitPrune）的总路径搜索时间为2.3703×109纳秒。时间为2.0043×109纳秒，使用位操作、剪枝和预处理三个优化的JPS（JPS-BitPrunePre）总寻路时间为9.5434×108纳秒。

有些文章将预处理称为JPS+。本文中的JPS-Bit和JPS-BitPrune都支持动态阻塞。本文解决了大多数开源JPS 中存在的一个潜在错误：遍历块。在图2.2.1 中，当从H 步行到K 时，您穿过H 右侧的街区。

上述结果表明，JPS 的5 个版本在200 个网格中寻找路径的平均时间分别为1.7 ms、0.32 ms、0.23 ms、0.02 ms 和0.095 ms。路径搜索速度比A*快15倍。该算法显着优于A*算法81倍、110倍、130倍和273倍，表明寻路不是性能瓶颈。

事实上，在2012 年至2014 年举办的三场基于网格的路径规划竞赛（GPPC）中（迄今为止仅三场），JPS 被证明是基于最快的路径查找算法，而无需进行预处理。

本文接着介绍了JPS的基础版本和四种优化算法，然后解读了GPPC2014大赛，介绍了GPPC大赛的地图数据，并分析了寻路时间、路径长度、内存消耗和失败率，并对22个参赛寻路进行了比较。算法的角度：的优点和缺点。

2.JPS算法

2.1 算法概述JPS，又称Jump Point Search，是由两位澳大利亚教授于2011年提出的一种基于网格点阵的寻路算法。 JPS算法保持了A*算法的框架，同时进一步优化了A*算法寻找后继节点的操作。为了说明JPS基于A*的具体优化策略，图2.1.1给出了A*和JPS的算法流程图对比。从图2.1.1可以看出，JPS算法与A*算法的主要区别在于，后续这是一种节点扩展策略。 JPS通过点击当前节点来展开后续节点，采用基于当前节点展开并按照“两个定义、三个规则”寻找跳转点的策略。

定义1，强制邻接：节点n是x的邻居，节点n的邻居被阻塞（不可行走的网格），并且从父节点(x),x,n开始的路径长度为例如从(x如果Parent(x) 是路径中x 之前的点，并且n 是x 的强制邻域，x 是n 的跳跃点，则) 到n 而不经过x 是短的。在图2.2.1中，注意K是从S到E的路径上I的强制邻居（I是K的跳跃点）。这里从H到K似乎是不可能的，因为对角线上有障碍物（这个与论文不符，但确实符合代码。从H直接到达K 根据论文，开源代码相信可以从H直接到达K，所以如果需要从H到K，就会出现穿越街区的情况。如果K，则K是H的强制邻域（H是K的跳跃点）。

定义2、跳跃点： (1) 若y点为起点或目标点，则y为跳跃点。例如图2.2.1中，S既是起点又是跳跃点，E是跳跃点。目标点和跳跃点。

(2) 如果y 有强制邻居，则y 是跳跃点。例如，I是一个跳跃点。请注意，从强制邻居定义中，n 是强制邻居，x 是关联。例如，在图2.2.1中，M也是K的邻居，但K不是跳跃点。不是M 的强制邻居。

(3) 如果parent(y)相对于y沿对角线移动并且y水平或垂直移动到达跳跃点，则y为跳跃点。例如图2.2.1中的G就是跳跃点。 ）为S，从S到G的运动为对角运动，从G到跳跃点I的运动为垂直运动。由于I是跳跃点，所以G也是跳跃点。

规则1：在JPS寻找跳跃点的过程中，下面的所有直线都是可以水平（纵向和水平）和对角线移动的，所以先在直线上寻找跳跃点，然后在对角线上寻找跳跃点方向。规则2： (1) 如果从父项(x) 到x 的运动是一条直线，则如果存在从父项(x) 到n 不经过x 和length 的路径，则n 是x 的邻居。该路径小于或等于从父级(x) 开始的路径。在从x到n的路径中，到达x后的下一个点不会到达n。

(2) 如果存在从父级(x) 到x 的对角线移动，则如果从父级(x) 到x 的路径长度小于x，则n 是x 的邻域。从父节点(x)经过x路径到n的路径，到达x后的下一个点不会继续到n（相关证明参见论文）。

规则3：只有跳跃点才添加到开放组中。这是因为跳跃点会改变行走方向，但非跳跃点不会改变行走方向，并且最终找到的路径点也是跳跃点。路径搜索的具体过程如下。

1. 如果水流方向是直线： (1) 如果水流的左、后侧不可步行，但左侧可步行（即左侧强制相邻），则求跳跃点。 (2)如果沿当前方向不在闭集内，则搜索沿当前方向不在闭集内的跳跃点。不能向右走和向后走，可以向右走（右侧强制相邻）。然后沿着当前的前方和右侧行驶。查找不在闭集中的跳跃点。

那么，如果当前方向是对角线： (1)如果当前方向的水平分量是可步行的（例如，当前方向是东北，水平分量是东，垂直分量是北），则沿着前进。当前方向水平分量查找不在封闭集中的跳跃点。 (2)如果可以在当前方向上行走，则沿着当前方向寻找不在闭集中的跳跃点。可以沿着当前方向的垂直分量（比如当前方向是东北，那么水平分量是东，垂直分量是北）走，沿着垂直分量找到不在闭集中的跳跃点。当前方向。 JPS查找跳转点的过程有三处优化。 1. 位操作2. 预处理3. 去除中间跳转点。

图2.1.1 A*与JPS算法流程图对比

2.2 JPS算法示例表2.2.1 A*与JPS的路径搜索成本比较

下面的例子展示了JPS的具体寻路过程。示例如图2.2.1 所示。 5*5的网格，黑色代表区块区域，S为起点，E为终点。

为了找到从S到E的最短路径，JPS首先初始化一个起点S并将其添加到开集。从开集中获取F值最小的点S，将其从开集中移除，如果S的当前方向为空，则沿着下图8个方向找到跳跃点。只有三个点：S，下，右，右下，但是你可以朝方向移动，但是如果探索到D，你会遇到边界，如果你向右探索F，你会遇到障碍，所以你将无法找到跳转点。接下来，在右下方向寻找跳跃点。在G点，根据上面第(3)条中的第二个定义，parent(G)是S，praent(G)向S斜线移动，G可以到达它。我们通过垂直（向下）移动来跳转到点I，所以G 就是跳转点。

将G 添加到开集。从开集中取出F值最小的点G，将其从开集中移除，并将其添加到闭集中。 G当前的方向是对角线的（从S到G），所以它在右边。查找三个方向（垂直分量）的跳跃点：（当前方向的水平分量）、向下（当前方向）和右下（当前方向）。在这个图中，从G开始，只能向下移动。根据上面定义2的(2)找到跳跃点并将I添加到开集中。从开集中取出F值最小的点I，将其从开集中移除，并将其添加到闭集中。由于I当前的方向是一条直线（从G到I），在I点，我不能向左和I后面走，但我可以向左和向前走，所以我沿着左、左前和前创建跳跃点。我寻找，但左前和前都陷入了边界，我只找到了跳跃点Q。 （根据上面定义2的（2））），Q被添加到开集。

从开集中取出F值最小的点Q，将其从开集中移除，并将其添加到闭集中。由于Q当前的方向是直线，所以不可能走到Q的左后和左前。可以行走，所以它沿着left、left-front、forward点寻找跳跃，但是left-front和forward都遇到了边界，只在左侧找到了跳跃点E（根据（1）和） 。由于上面的定义2))，E 被添加到开集。从开集中获取F 值最小的点E。由于E是目标点，路径搜索结束，路径变为S、G、I、Q、E。

注意，本文没有考虑因为对角线被遮挡而可以从H走到K的情况。如果我们需要从H 直接到达K，则路径将为S、G、H、K、M、P。 E.修改跳跃点计算方法已经足够了，但是在游戏中，如果你能从H直接到达K，你就会穿过H右侧的障碍物。

图2.2.1

上面提到的JPS寻路效率明显快于A*。原因是A*算法在A点进行从S到A的垂直寻路时，会执行F、G、B、H。添加了一个开集，但JPS 并没有将这四个点添加到一个开集。对于三点F、G、H，从S 到F 的最短路径不是S、A、F 的路径，因为从S、A、F 的路径长度比S 和F 长。根据上面规则2(1)，步行到A后，没有步行到F或G，因此F和G不加入开集。 S、A、H是从S到H的最短路径。然而，由于S、G、H之间存在一条不经过A的最短路径，根据上面的规则2(1)，从S走完之后，如果A，下一个要移动到的点不是H， H也没有参加公开赛。对于B点，根据上面的规则3，B不是跳跃点，因此不参与开集。 C 直接。

表2.2.1显示了A*和JPS寻路消耗的比较。 D. Age: Origins、D. Age 2、StarCraft 是来自三款游戏的场景地图的集合：《龙腾世纪：起源》、《龙腾世纪2》和《星际争霸》。 M.Time表示开集和闭集的运行时间，G.Time表示后续节点的搜索时间。 A* 大约58% 的时间用于开集和闭集操作，42% 的时间用于搜索后继节点，而JPS 大约14% 的时间用于开集和闭集操作，可以看到我花费了86%。我在这上面的时间。寻找后继节点。避免向开集添加太多点，从而避免过度维护最小堆，这就是JPS 比A* 更快的原因（插入新元素时最小堆较低），时间复杂度为log(n) 且堆在移除最小元素后进行调整，时间复杂度也是log(n))。事实上，在从S到E的寻路过程中，只有S、G、I、Q、E进入开集。

3.JPS优化

3.1 JPS算法的五种效率优化算法3.1.1 JPS效率优化之一JPS-Bit：位运算优化JPS-Bit使用位运算优化的主要优化思想是为了优化使用JPS部署的Node的效率。下面介绍的JPS-Bit和JPS-BitPrune在发生动态阻塞时将网格标记为阻塞，而在动态阻塞占用k个网格时将网格标记为非阻塞。阶数为O(k)。下面，我们使用图3.1.1.1中的示例场景来说明如何将位操作合并到JPS算法中。假设你当前的位置是I（蓝色位置）并且你当前的方向是正确的。在按位运算中，1表示不可能，0表示可能。在这种情况下，I 的当前B 行的8 位可以用00000100 和前一行的B- 的8 位表示。 I可以用8位来表示：00000000，I

在下面

B+行的8位可以用8位00110000来表示。要查找当前行中块的位置，可以使用CPU 指令__builtin_clz(B) （它返回前导零的数量）。即当前块位于第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，因此跳转点为第四个位置M（从0 开始）。本文使用_builtin_ffs(((B-1) !B-) ||((B+1) !B+))，其中__builtin_ffs(x)是x的最后一位（从后到前为1）返回。例如，7368 (1110011001000) 返回4。这是因为本文使用小端模式进行网格位编码，而这里我们使用网格位端模式。

JPS-Bit采用了更高效的位运算和CPU指令运算来优化原有JPS节点扩展过程中的遍历操作，因此在实际测量中，JPS-Bit的算法效率比原来要高，而路径探索时间要高。 JPS 的。 JPS-Bit 的JPS 大约短5 倍。

图3.1.1

3.1.2 JPS效率优化2 JPS-BitPrune：位运算和剪枝优化JPS-BitPrune利用位运算和剪枝优化，在JPS-Bit的基础上进一步进行剪枝优化，削减不必要的中间跳数（定义2（3））。定义2，中间跳数在节点扩展过程中只起到简单的“继承”作用，将中间跳数放入开放集中，JPS-BitPrune会随着数量的增加而删除所有中间跳数。并将中间跳后续跳中非中间跳的父跳修改为中间跳的父跳。这样有效避免了冗余的节点扩容操作。

获取拐点：JPS-BitPrune 去掉了中间跳转点，因此JPS-BitPrune 搜索到完整路径后，必须使用特定策略将中间拐点添加到最终路径中，请特别注意。这允许每两条相邻路径从垂直、水平和对角线方向到达节点。对此，JPS-BitPrune采用的具体方法是：

假设当前正在搜索的路径是start(jp1)、jp2、jp3.jpk.end(jpn)。对于每两个相邻跳，jpi、jpi+1、1、jpi、jpi+1 将是x 坐标或y。坐标相等。如果jpi和jpi+1的x坐标相等，说明两个跳跃点水平或垂直方向相同，可以直线到达，不需要在第二个跳跃点之间添加拐点。当y坐标不相等时（1）当x坐标差dx（即jpi的x坐标减去jpi+1的x坐标）和y坐标差的绝对值时dy 相等。如果相等，则两个跳跃点在对角处，也可以直线到达，无需在两个跳跃点之间添加拐点。 (2)差值dx的绝对值；如果x坐标差值dy和y坐标差值dy不相等，则说明两个跳跃点不在直线的两侧，可以无法通过直线到达（由于跳跃点附近有障碍物）。现在，只需在jpi 到jpi+1 的对角线上添加一个位于jpi 和jpi+1 之间的点即可（jpi ， jpi+1 无法水平、垂直或对角到达；也就是说， jpi 和jpi 一定是中间跳转点+1之间的拐点只需要在jpi+1上加上最近的中间跳跃点即可作为拐点（沿对角线方向取dx，dy到达的点）。

图3.1.2.1 JPS-BitPrune剪枝优化示例

下面，我们以图3.1.2.1中的问题场景为例，说明JPS-BitPrune在剪枝过程中如何进行寻路。起点为S（坐标为(1,1)，或S(1,1)），节点1、4、6均为中间跳跃点。这是因为节点2和3是满足定义的跳转点。因此，节点1是到达节点2和3的中间跳，同样节点4和6也是中间跳。在修剪中间跳之前，中间跳后继节点的父节点必须与中间跳的父节点对齐。例如，在图3.1.2.1中，节点1的后继跳为节点2、3、4，其中节点4也是中间跳，如果去掉中间跳节点1，则节点2和节点2的父跳为2 会的。 3、节点1改为节点S。删除中间跳节点4 后，节点4 的后继跳5 的父跳从节点4 变为节点S（节点4 的父跳为节点1，但由于节点1 被删除，节点6 被删除），在中间节点删除节点6 后hop，节点6的后继跳7的父跳从节点6变为节点S（节点6的父跳为节点4，但节点4被移除），并且节点4的父跳节点1也被移除，因此返回。到节点S。

上述过程是逻辑上的简化，实际操作方法是从节点S开始寻找跳转点。首先找到中间跳跃点节点1，然后找到并连接水平和垂直跳跃点节点2、3。设置节点S的父跳转点。到达节点4后，沿水平和垂直方向找到跳跃点，并设置节点S的父跳跃点。继续从节点5 到节点S 对角搜索跳跃点。到达节点6后，沿水平和垂直方向寻找跳跃点7。将跳转点7的父跳转点设置为节点S。因此JPS-BitPrune 得到路径S(1,1)，节点7(4,6)。由于路径中的S(1,1)无法垂直、水平或对角走到节点7(4,6)，按照上述拐点添加策略，dx为3，dy为中间拐点，需要添加点。您需要从S 沿对角线走三步。即节点6(4,4)可以作为中间分支点。因此，在图3.1.2.1的例子中，最终的路径将是JPS构建的完整路径。 -BitPrune 为S(1,1)，节点6(4,4)，节点7(4,6)。

3.1.2.1 剪枝的优化效率我们通过比较剪枝前后的JPS节点扩展来说明剪枝操作的优化效率。

场景1（不剪枝） 如果不剪枝中间跳，则从节点S到节点7的路径将经历以下过程。 (1) 从节点S开始搜索跳数，找到跳数节点1。开放集只有节点。 1;

(2) 从开集中选取F值最小的节点1，并搜索节点1的后续跳数。在水平和垂直方向上找到跳跃节点2和3，在对角线方向上找到跳跃节点4。目前，开放集有节点2、3 和4。

(3) 从开集中选取F值最小的节点4，并搜索节点4的下一跳。水平和垂直找到跳跃节点5，对角找到跳跃点6。开集现在有节点2 和3。

(4) 从开集中取出F值最小的跳跃点6，找到垂直跳跃点7。开集现在有节点2、3、5 和7。

(5)将开集中F值最小的跳节点7设置为目的点，搜索结束。因此，完整路径是节点S(1,1)、节点1(2,2)、节点4。 (3,3)、节点6(4,4)、节点7(4,6)。在JPS 到达目的节点7 之前，中间跳1、4、6 必须不断扩展。

场景2（中间跳剪枝） 经过中间跳剪枝后，从节点S到节点7的寻路过程得到了极大的简化。

（1）从节点S寻找跳跃点，首先找到中间跳跃点节点1，然后找到水平和垂直跳跃点节点2和3，并将节点2和3的父跳跃点设置为节点。 S; 找到对角线的跳跃点。导航到节点4后，将节点5的父跳转点设置为节点S。对角到达节点6后，沿水平和垂直方向搜索跳跃点7，将跳跃点7的父跳跃点设置为节点S，沿对角方向搜索跳跃点。如果有障碍物，则搜索结束。开集有节点2、3、5 和7。

(2) 目的点是开集中F值最小的跳节点7，结果路径是S(1,1)和节点7(4,6)。与不进行剪枝的JPS需要扩展中间跳1、4、6不同，JPS-BitPrune将节点1、4、6全部剪枝为中间跳，有效扩展了冗余节点，大大提高了路径搜索的效率。

3.1.3 JPS效率优化三JPS-BitPres：位运算和预处理这种优化预处理在有些文章中称为JPS+。 JPS-BitPre 和JPS-BitPrunePre 都不支持动态阻塞。这是因为当动态阻塞发生时，八个方向上可以执行的最大步数发生变化，使得预处理结果不准确。使用位运算和预处理JPS-BitPre 继续使用JPS-Bit 的位运算，预处理是存储每个点8 个方向的最大步数。此步骤值影响JPS 部署顺序。节点和扩展的“跨度”提高了路径探索的效率。

步长值由跳跃点、障碍物、边界等决定。如果遇到跳跃点，则step是到达跳跃点的步数，否则step是到达障碍物或边界的步数。例如，对于图3.1.3.1 中的N 点，向北可走的最大步数是节点8，即2 步。您可以向南移动的最大步数是节点4，即4 步。向西最多可以走的步数是节点6，即3步，向东最多可以走的步数是节点2（节点2是它的跳跃点）。它满足定义2(2))，即5步。西北最多可以移动2 步到节点1（节点1 已在上面定义）。第2(3))条定义的点是1步，西南可以3步向上移动到节点5（节点3就是上面2 3）定义的跳跃点）），即3步。

图3.1.3.1 JPS-BitPre路径搜索场景示例

以图3.1.3.1场景为例，JPS-BitPre查找从节点N到节点T的路径的寻路过程如下。

(1) 从开集中取出节点N，并从N沿8个方向找到跳跃点。根据预处理得到的每个方向上最远可达方向的步长值，可以快速确定8个方向中最远可达的节点。如图3.1.3.1所示，方向{1,2,3,4,5,6,7,8}中，节点1、2、3都是满足定义2的跳跃点。这些都是直接添加的。对于节点4、5 和6、7、8，首先确定它们是否位于N 周围的南、西南、西、西北或北，因为终点T 位于西南。从方向上看，只有节点5位于西南方向，所以直接跳过节点4、6、7、8。在从N到5的方向上，N可以走三步，得到x坐标dx的绝对值。 N和T的差值为1，y坐标dy的差值的绝对值为2，所以我们从节点N到节点5。向节点11 执行min(dx,dy) 步骤。并参加公开组。

(2) 从开集中取出F值最小的节点11，找到垂直跳跃点T，将其加入到开集中。

(3) 将开集中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.1.4 JPS 效率优化之五：空间换时间openset 采用最小堆实现，最小堆的底层数据结构是一个数组，从最小堆中插入、删除时间复杂度为 O(logn)。除了删除还需要查找操作，每次找到一个跳点，都需要判断在最小堆中是否有，如果有，则判断是否更新 G 值、F 值、父跳点等，如果没有，则加入 openset。在最小堆的中查找操作时间复杂度 O(n)，因此需要优化。closedset 存的是已经从 openset 中弹出的跳点，实际只需要对每个跳点加个标记即可，如果跳点打上标记，则表示是 closedset 中跳点，否则不是。
综合上述需求，针对 1km*1km 的地图，构建 2k*2k 的二维数组 matrix，数组每个元素 pnode 均为一个指针，指针的对象类型包括节点 id、是否扩展过 expanded(即是否在 closedset 中)、G 值、F 值、父跳点指针 parent、在最小堆中的索引 index 等 12 个 byte。
如果地图(x,y)处是搜索到的跳点，首先检查在二维数组 matrix 对应的(x,y)处指针 pnode 是否为空，如果为空，表示该跳点之前未搜索过，从内存池 new 出一个跳点，将指针加到最小堆 openset 中，并在执行 shift up、shift down 操作之后，记录在最小堆中的索引 index；如果不为空，则表示该跳点之前搜索过，首先检查 expand 标记，如果为真，则表示在 closedset 中，直接跳过该跳点；否则表示在 openset 中，通过 matrix(x,y)记录的在 openset 中的索引 index 找到对应的指针，检查 matrix(x,y)和 openset(index)的指针是否相等进行二次确认，然后检查判断是否需要更新 G 值、F 值、父跳点等，采用空间换时间的方法可以将 openset 和 closedset 中查找操作降为 O(1)。游戏中有很多场景，无需为每个场景构建一个 matrix，以最大的场景的大小构建一个 matrix 即可。
3.2 多线程支持游戏服务器普遍采用单进程多线程架构，多线程下，不能对 JPS 寻路加锁，否则寻路串行化，失去了多线程的优势，为了支持多线程 JPS 寻路，需要将一些变量声明为线程独有 thread_local，例如上文提到的为了优化 openset 和 closedset 的查找速度，构建的二维跳点指针数组 matrix。该数组必须为线程独有，否则，不同线程在寻路时，都修改 matrix 元素指向的跳点数据，例如 A 线程在扩展完跳点后，将 expanded 标记为真，B 线程再试图扩展该跳点时，发现已经扩展过，就直接跳过，导致寻路错误。
3.3 JPS 内存优化3.3.1 分层JPS 的地图格子粒度如果采用 0.5m*0.5m，每个格子占 1bit，则 1km*1km 的地图占用内存 2k*2k/8 个 byte，即 0.5M；为了向上、向下也能通过取 32 位数获得向上、向下的 32 个格子阻挡信息，需要存将地图旋转 90 度后的阻挡信息；上文 JPS 优化之四：不可达两点提前判断，需要存连通信息，假设连通区数目最多 15 个，则需内存 2k*2k/2 个 byte，即 2m，则内存为：原地图阻挡信息 0.5m、旋转地图阻挡信息 0.5m、连通区信息 2m，即 3m。另外，上文提到用空间换时间的方法，为了优化 openset 和 closedset 的查找速度，构建二维跳点指针数组 matrix。1km*1km 的地图，格子粒度为 0.5m*0.5m，构建出的 matrix 指针数组大小为 2k
2k
4byte 即为 8m，为了支持多线程，该 matrix 数组必须为 thread_local，即线程独有，16 个线程共需内存 16*8m 即为 128m，内存空间太大，因此需要优化这部分内存。
首先将 2k*2k 分成 100*100
的块
，即 20*20 个块，20*20 个块为第一层数组 firLayerMatrix，100*100 为第二层数组 secLayerMatrix，firLayerMatrix 的 400 个元素为 400 个指针，每个指针初始化为空，当遍历到的跳点属于 firLayerMatrix 中(x,y)的块时，则从内存池 new 出 100*100*4byte 的 secLayerMatrix，secLayerMatrix 每个元素也是一个指针，指向一个从内存池 new 出来的跳点。例如，搜索 2k*2k 的地图时，在(231,671)位置找到一个跳点，首先检查 firLayerMatrix 的(2,6)位置指针是否为空，如果为空，则 new 出 100*100*4byte 的 secLayerMatrix，继续在 secLayerMatrix 查找(31,71)位置检查跳点的指针是否为空，如果为空，则从内存池 new 出来跳点，加入 openset，否则检查跳点的 expanded 标记，如果标记为真，表示在 closedset 中，直接跳过该点，否则表示在 openset 中，判断是否更新 G 值、F 值、父节点等。
因为游戏中 NPC 寻路均为短距离寻路，JPS 寻路区域最大为 80*80，一个 secLayerMatrix 是 100*100，因此只需要一个 secLayerMatrix，则两层 matrix 大小为：20*20*4byte+100*100*4byte 即为 0.04m。所以 16 个线程下，总内存为：原地图阻挡信息 0.5m、旋转地图阻挡信息 0.5m、连通区信息 2m、两层 matrix0.04m*16，共 3.64M，游戏中场景最多不到 20 个，所有场景 JPS 总内存为 72.8M。
3.3.2 内存池在搜索过程中，每次将一个跳点加入 openset，都需要 new 出对应的节点对象，节点对象中存节点 id、父节点、寻路消耗等共 12 个 byte，为了减少内存碎片，以及频繁 new 的时间消耗，需要自行管理内存池，每次 new 节点对象时，均从内存池中申请，为了防止内存池增长过大，需要限制搜索步数。
内存池是在真正使用内存之前，先申请分配一定数量的、大小相等(一般情况下)的内存块留作备用。当有新的内存需求时，就从内存池中分出一部分内存块，若内存块不够再继续申请新的内存。
本文的内存池共有两个：一，跳点的内存池，初始大小为 800 个跳点，当 new 的跳点数目超出 800 个，即停止寻路，因为服务器用 JPS 进行 NPC 的寻路，NPC 不会进行长距离寻路，假设 NPC 寻路上限距离是 20m，则寻路区域面积是 40m
40m，格子数 80
80 即 6400，经统计跳点数目占所有格子数目的比例不到 1/10， 即跳点数目少于 640，因此 800 个跳点足够使用，800 个跳点共占内存 800byte*12，即为 9.6k，忽略不计；二，secLayerMatrix 指向的 100*100*4byte 的内存池，因为每次寻路都需要至少一个 secLayerMatrix，如果每次寻路都重新申请，寻路完后再释放，会造成开销，因此 secLayerMatrix 指向的 100
100
4byte 的空间也在内存池中，申请时，从内存池拿出，释放时，放回内存池即可，secLayerMatrix 内存池占内存 0.04m。
3.4 路径优化如图 3.4.1 所示，绿色格子为起点，红色格子为终点，灰色格子为跳点，蓝线为 JPS 搜出来的路径，灰色虚线为搜索过程。可以看出，从绿色格子到红色格子可以直线到达，而 JPS 搜索出来的路径却需要转折一次，在游戏表现上，会显得比较奇怪。因此在 JPS 搜索出来路径后，需要对路径进行后处理。
比如 JPS 搜出来的路径有 A、B、C、D、E、F、G、H 八个点，走到 A 时，需要采样检查 A、C 是否直线可达，如果 A、C 直线可达，再检查 A、D 是否直线可达，如果 A、D 直线可达，继续检查 A、E，如果 A、E 直线不可达，则路径优化为 A、D、E、F、G、H，走到 D 时，再检查 D、F 是否直线可达，如果 D、F 直线可达，继续检查 D、G，如果 D、G 直线不可达，则路径优化为 A、D、F、G、H。依此类推，直到走到 H。因为采样检查的速度很快，大约占 JPS 寻路时间的 1/5，而且只有当走到一个路点后，才采样检查该路点之后的路点是否可以合并，将采样的消耗平摊在行走的过程中，因此采样的消耗可以忽略。
图3.4.1
4.GPPC 竞赛解读
4.1 GPPC 竞赛与地图数据集基于格子的寻路一直是被广泛研究的热点问题，也有很多已经发表的算法，但是这些算法没有相互比较过，因此也难辨优劣，使用者如何选择算法也有很大的困难。为了解决这个问题，美国丹佛大学的 Nathan R. Sturtevant 教授创办了基于 Grid 格子的寻路比赛：The Grid-Based Path Planning Competition，简称 GPPC，目前已经在 2012、2013、2014 举办过三次，下文主要讨论 GPPC2014。
GPPC 比赛用的地图集如表 4.1.1 所示，地图数据主要分为游戏场景图和人造地图。其中来自游戏场景图的数据有三类：Starcraft（星际争霸）、Dragon Age2（龙腾世纪 2）、Dragon Age:origins（龙腾世纪：起源），三个游戏分别提供地图 11、57、27 张，提供寻路问题 29970、54360、44414 个。来自人造地图有三类：迷宫、随机、房间，三类数据分别提供地图 18、18、18 张，提供寻路问题 145976、32228、27130 个。六类数据共提供地图 132 张，寻路问题 347868 个。图 4.1.1 中给出三个游戏的场景图示例，图 4.1.2 中给出三类人造地图示例，其中黑色代表阻挡区，白色代表可行走区。地图大小从 100*100 到 1550*1550，六个地图集的大小分布如图 4.1.3 所示，横坐标是格子数，纵坐标是地图数目，最小的地图来自 Dragon Age:origins（龙腾世纪：起源），最大的地图来自 Starcraft（星际争霸）和人造数据。
表4.1.1 GPPC比赛用的地图集
图4.1.1 GPPC的三类游戏场景地图示例
图4.1.2 GPPC的三类人造场景地图示例
图4.1.3 GPPC的六类地图大小分布
4.2 GPPC 的评价体系GPPC 在相同的配置下运行参赛算法，其中 CPU 的配置是 Xeon E5620，四核处理器、2.4Ghz 主频，12G 内存。为了消除误差，GPPC 要求对每个参赛的寻路方法在 34868 个寻路问题上运行 5 遍，共寻路 34868*5，即 174340 次，所以下文介绍的总运行时间等指标都是寻路 174340 次的结果汇总。其中运行时间包括：加载预处理数据和寻路时间，而预处理时间并不计算在运行时间内。
GPPC 定义如下 13 个指标来评价寻路算法（其中，路径表示从起点到终点的完整路径）：
Total (秒)：寻路 174340 次所花费的总时间。
Avg(毫秒)：寻路 174340 次的平均时间。
20 Step(毫秒)：寻找到路径的前 20 步所花费的平均时间。该指标衡量最快多久可以跟随路径，在实时交互例如游戏中，该指标很重要。
Max Segment(毫秒)：每条路径最长段的寻路平均时间。该指标衡量在实时交互中，寻路方法最差情况下的表现。
Avg Len：路径的平均长度。如果 A 寻路算法在长路径上表现好，在短路径上表现不好；B 寻路算法在长路径上表现不好，在短路径上表现好，则 A 的该指标优于 B 的指标，因为 Avg Len 的增加主要来自长路径。该指标偏向于在长路径上表现好的寻路方法。
Avg Sub-Opt：寻到的路径长度/最优路径长度 的平均值。如果 A 寻路方法在长路径上表现好，在短路径上表现不好；B 路径寻路方法在长路径上表现不好，在短路径上表现好，则 B 的该指标优于 A 的指标，因为 174340 次寻路大多数的路径都是短路径。该指标偏向于在短路径上表现好的寻路方法。
Num Solved：在 174340 次寻路中，成功的数目。
Num Invalid：在 174340 次寻路中，返回错误路径的数目。错误路径：路径的相邻路点无法直线到达。
Num UnSolved：在 174340 次寻路中，没有寻找到路径的数目。
RAM(before)(兆)：寻路算法在加载预处理数据后，寻路之前占用的内存。
RAM(after)(兆)：寻路 174340 次后占用的内存，包括所有寻路结果占用的内存。
Storage：预处理的数据占用的硬盘大小。
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)。
表 4.3.1 给出参加 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 种算法没有严格的优劣关系，只是在不同指标下的表现各有侧重，算法的使用者可基于对不同指标的具体需求来选择自己适用的算法。
表4.3.1 GPPC2014的比赛结果
下面给出所有在 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 帕累托最优。