江苏龙网

  1. 主页 > 生活百科 > >

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

寻路算法


最快速的寻路算法 Jump Point Search

文章插图
 
图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 步 。


推荐阅读


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

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