江苏龙网

  1. 主页 > 生活百科 > >

最快速的寻路算法 Jump Point Search( 三 )

寻路算法


表 2.2.1 所示为 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 。
3.JPS 优化3.1 JPS 算法的五个效率优化算法3.1.1 JPS 效率优化之一 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 倍左右 。

最快速的寻路算法 Jump Point Search

文章插图
 
图3.1.1
3.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)步到达的点） 。


推荐阅读


上一篇：webpack教程：如何从头开始设置 webpack 5

下一篇：白茶茶汤的颜色,天目湖白茶泡水颜色