最快速的寻路算法JumpPointSearch

善心如水

作者：runzhiwang，腾讯TEG后台开发工程师本文介绍一种跳点搜索算法JPS以及其四个优化算法，其寻路速度最快可是A*算法的273倍。文中的JPS-Bit和JPS-BitPrune都支持动态阻挡。1.引言寻路算法用途众多，例如在游戏和地图中。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.2.1中，从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（TheGrid-BasedPathPlanningCompetition）中，JPS已经被证明是基于无权重格子，在没有预处理的情况下寻路最快的算法。本文接下来介绍JPS基础版本以及四个优化算法；然后解读GPPC2014的比赛，介绍GPPC的比赛地图数据，并从寻路时间、路径长度、消耗内存、失败率等方面比较22个参赛寻路算法的优劣。2.JPS算法2.1算法介绍JPS又名跳点搜索算法（JumpPointSearch），是由澳大利亚两位教授于2011年提出的基于Grid格子的寻路算法。JPS算法在保留A*算法的框架的同时，进一步优化了A*算法寻找后继节点的操作。为了说明JPS在A*基础上的具体优化策略，我们在图2.1.1中给出A*和JPS的算法流程图对比。由图2.1.1看出，JPS与A*算法主要区别在后继节点拓展策略上，不同于A*算法中直接获取当前节点所有非关闭的可达邻居节点来进行拓展的策略，JPS根据当前结点current的方向、并基于搜索跳点的策略来扩展后继节点，遵循“两个定义、三个规则”。定义一，强迫邻居（forcedneighbour）：如果节点n是x的邻居，并且节点n的邻居有阻挡（不可行走的格子），并且从parent(x)、x、n的路径长度比其他任何从parent(x)到n且不经过x的路径短，其中parent(x)为路径中x的前一个点，则n为x的强迫邻居，x为n的跳点，例如图2.2.1中，寻找从S到E的路径时，K为I的强迫邻居（I为K的跳点）。这里不认为从H到K能走，因为对角线有阻挡（这点和论文不一致，但和代码一致，因为如果H到K能直接到达，会走进H右边的阻挡区，大部分的JPS开源代码根据论文都认为H到K能直接到达，所以存在穿越阻挡的情况），如果需要H到K可走，则K为H的强迫邻居（H为K的跳点）。定义二，跳点（jumppoint）：（1）如果点y是起点或目标点，则y是跳点，例如图2.2.1中，S是起点也是跳点，E是目标点也是跳点；（2）如果y有强迫邻居则y是跳点，例如I是跳点，请注意此类跳点和强迫邻居是伴生关系，从定义一强迫邻居的定义来看n是强迫邻居，x是跳点，二者的关系是伴生的，例如图2.2.1中K的邻居只有I是跳点，M虽然也是K的邻居，但M不是跳点，因为K不是M的强迫邻居；（3）如果parent(y)到y是对角线移动，并且y经过水平或垂直方向移动可以到达跳点，则y是跳点，例如图2.2.1中G是跳点，因为parent(G)为S，S到G为对角线移动，从G到跳点I为垂直方向移动，I是跳点，所以G也是跳点。规则一：JPS搜索跳点的过程中，如果直线方向（为了和对角线区分，直线方向代表水平方向和垂直方向，且不包括对角线等斜线方向，下文所说的直线均为水平方向和垂直方向）、对角线方向都可以移动，则首先在直线方向搜索跳点，再在对角线方向搜索跳点。规则二：（1）如果从parent(x)到x是直线移动，n是x的邻居，若有从parent(x)到n的路径不经过x且路径长度小于或等于从parent(x)经过x到n的路径，则走到x后下一个点不会走到n；（2）如果从parent(x)到x是对角线移动，n是x的邻居，若有从parent(x)到n的路径不经过x且路径长度小于从parent(x)经过x到n的路径，则走到x后下一个点不会走到n（相关证明见论文）。规则三：只有跳点才会加入openset，因为跳点会改变行走方向，而非跳点不会改变行走方向，最后寻找出来的路径点也都是跳点。寻路具体流程如下：一，若current当前方向是直线方向：（1）如果current左后方不可走且左方可走（即左方是强迫邻居），则沿current左前方和左方寻找不在closedset的跳点；（2）如果current当前方向可走，则沿current当前方向寻找不在closedset的跳点；（3）如果current右后方不可走且右方可走（右方是强迫邻居），则沿current右前方和右方寻找不在closedset的跳点；二，若current当前方向为对角线方向：（1）如果current当前方向的水平分量可走（例如current当前为东北方向，则水平分量为东，垂直分量为北），则沿current当前方向的水平分量寻找不在closedset的跳点；（2）如果current当前方向可走，则沿current当前方向寻找不在closedset的跳点；（3）如果current当前方向的垂直分量可走（例如current当前为东北方向，则水平分量为东，垂直分量为北），则沿current当前方向的垂直分量寻找不在closedset的跳点。JPS寻找跳点的过程有三种优化：一，位运算；二；预处理；三；剪枝中间跳点。图2.1.1A*和JPS的算法流程图对比2.2JPS算法举例表2.2.1A*和JPS的寻路消耗对比下面举例说明JPS具体的寻路流程。示例如图2.2.1所示，5*5的网格，黑色代表阻挡区，S为起点，E为终点。JPS要寻找从S到E的最短路径，首先初始化将起点S加入openset。从openset取出F值最小的点S，并从openset删除，加入closedset，S的当前方向为空，则沿八个方向寻找跳点，在该图中从S出发只有下、右、右下三个方向可走，但向下搜索到D遇到边界，向右搜索到F遇到阻挡，因此都没有找到跳点，然后沿右下方向寻找跳点，在G点，根据上文定义二的第（3）条，parent(G)为S，praent(G)到S为对角线移动，并且G经过垂直方向移动（向下移动）可以到达跳点I，因此G为跳点。将G加入openset。从openset取出F值最小的点G，并从openset删除，加入closedset，因为G当前方向为对角线方向（从S到G的方向），因此在右（当前方向水平分量）、下（当前方向垂直分量）、右下（当前方向）三个方向寻找跳点，在该图中从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能直接到达，则路径是S、G、H、K、M、P、E，修改跳点的计算方法即可，但在游戏中如果H到K能直接到达，则会穿越H右边的阻挡。图2.2.1上述的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即可。表2.2.1所示为A*和JPS在寻路消耗中的对比，D.Age:Origins、D.Age2、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。3.JPS优化3.1JPS算法的五个效率优化算法3.1.1JPS效率优化之一JPS-Bit：位运算优化利用位运算优化的JPS-Bit的关键优化思路在于利用位运算来优化JPS中节点拓展的效率。JPS-Bit和下文介绍的JPS-BitPrune支持动态阻挡，当动态阻挡出现时，将格子标记为阻挡，当动态阻挡消失时，将格子标记为非阻挡，如果动态阻挡占据k个格子，则时间复杂度为O(k)。下面以图3.1.1.1中的场景示例说明如何将位运算融合于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.1.13.1.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)步到达的点）。图3.1.2.1 JPS-BitPrune的剪枝优化示例下面以图 3.1.2.1 的问题场景示例 JPS-BitPrune 如何在剪枝的同时进行寻路。起点为 S（坐标为(1,1)，即 S(1,1)），节点 1、4、6 均为中间跳点：因为节点 2、3 是满足定义二第(2)条的跳点，所以节点 1 是为了到达节点 2、3 的中间跳点，同理节点 4、6 也为中间跳点。在剪枝中间跳点之前，要将中间跳点的后继节点的父节点调整为该中间跳点的父节点。例如图 3.1.2.1 中，节点 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)可作为中间拐点，因此，在图 3.1.2.1 的示例中，JPS-BitPrune 最后构建的完整路径为 S(1,1) 、节点 6(4,4) 、节点 7(4,6)。3.1.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.1.3 JPS 效率优化之三 JPS-BitPre：位运算与预处理本优化中的预处理在一些文章被称为 JPS+。JPS-BitPre 和 JPS-BitPrunePre 都不支持动态阻挡，因为动态阻挡的出现会导致八个方向最多能走的步数发生变化，从而导致预处理的结果不再准确。利用位运算和预处理的 JPS-BitPre 依旧采用 JPS-Bit 中的位运算，而其中的预处理则是对每个点存储八个方向最多能走的步数 step，这个 step 值将影响 JPS 中节点的拓展顺序和拓展“跨度”，加快寻路效率。step 值由跳点、阻挡、边界等决定，如果遇到跳点，则 step 为走到跳点的步数；否则 step 为走到阻挡或边界的步数。例如对图 3.1.3.1 中的 N 点，向北最多走到节点 8，即 2 步；向南最多走到节点 4，即 4 步；向西最多走到节点 6，即 3 步；向东最多走到节点 2（节点 2 是满足定义二第（2）条的跳点），即 5 步；西北最多走到节点 7，即 2 步；东北最多走到节点 1（节点为 1 是上文定义二第（3）条定义的跳点），即 1 步；西南最多走到节点 5，即 3 步；东南最多走到节点 3（节点 3 是上文定义二第（3）条定义的跳点），即 3 步。图3.1.3.1 JPS-BitPre寻路的场景示例以图 3.1.3.1 中的场景为例，要寻找从节点 N 到节点 T 的路径，JPS-BitPre 的寻路流程如下：(1)从 openset 取出节点 N， 从 N 沿八个方向寻找跳点，根据预处理得到的各方向最远可走的 step 值，可以快速确定八个方向最远能到达的节点{1，2，3，4，5，6，7，8}，如图 3.1.3.1 所示，其中，节点 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；(3)从 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.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 指针数组大小为 2k2k4byte 即为 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，则寻路区域面积是 40m40m，格子数 8080 即 6400，经统计跳点数目占所有格子数目的比例不到 1/10， 即跳点数目少于 640，因此 800 个跳点足够使用，800 个跳点共占内存 800byte*12，即为 9.6k，忽略不计；二，secLayerMatrix 指向的 100*100*4byte 的内存池，因为每次寻路都需要至少一个 secLayerMatrix，如果每次寻路都重新申请，寻路完后再释放，会造成开销，因此 secLayerMatrix 指向的 1001004byte 的空间也在内存池中，申请时，从内存池拿出，释放时，放回内存池即可，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.14.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 Agerigins（龙腾世纪：起源），三个游戏分别提供地图 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 Agerigins（龙腾世纪：起源），最大的地图来自 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 帕累托最优。欢迎关注我们的视频号：腾讯程序员最新视频：鹅厂程序员用代码画企鹅