江苏龙网

  1. 主页 > 生活百科 > >

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

寻路算法


最快速的寻路算法 Jump Point Search

文章插图
 
图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 指针数组大小为 2k


推荐阅读


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

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