[译]寻路优化

看到一篇关于寻路优化的文章,简单翻译了一下,原文在这里

• 译文并未照搬原文翻译,多处是意译
• 原文图片已经失效,不过其他转载网址仍有图片,我对应着补了一下

寻路对很多游戏来讲都是不可或缺的元素,在一般的游戏中,使用一些基本的寻路算法(譬如 BFS, Dijkstra 或者 A* 等等)就可以很好的解决寻路问题,但是在另一些游戏中,尤其是在游戏地图比较庞大的情况下,这些基本寻路算法需要耗费大量的时间进行寻路,进而造成游戏卡顿,这使得寻路优化变得非常重要.

在这篇文章中,我会简单介绍一下 A* 算法以及该算法的一些改进点,我也会讲解一些常用的 A* 衍生算法以及 HPA 算法的一些实现要点.

重温 A* 算法

A* 算法用于寻找从开始点至目标点之间的一条可达路径.A* 算法在寻路过程中会使用一种简单的方法来评估当前节点与目标点之间的距离.通过将已经经过的路径距离和预估的路径距离相加,算法会首先扩展搜索那些最有"前途"(与目标点距离最短)的节点.A* 算法的寻路方式保证其一定可以找到最优路径.

在这里插入图片描述

从上图中我们可以看出,从白色的开始点出发,A* 算法搜索了开始点附近的所有节点并沿着离目标点最近的节点找到了一条可达路径.当 A* 算法找到目标点后,他就通过回溯父节点的方式来重建路径.

以下是我们实现 A* 算法的方式:

1. 将开始点放入开放列表(open list)中
2. 当开放列表不为空时我们重复执行以下操作:
3. 从开放列表中取出 F 值最小的节点并将他放入关闭列表中(我们后续不会再考虑关闭列表中的节点)
4. 对于该节点每一个不在关闭列表中的相邻节点:
5. 将该节点设置为当前相邻节点的父节点(主要用于后面的节点回溯)
6. 计算当前相邻节点的 G 值(从开始点到当前相邻点的距离)并将其加入到开放列表中
7. 计算当前相邻节点的 F 值(通过将当前相邻节点的 H 值(当前相邻节点到目标点的预估距离)与当前相邻节点的 G 值相加)

基本优化

存在很多调整方法可以优化 A* 算法,这些方法能让 A* 算法执行的更快(但是加速程度不如一些对 A* 进行算法层面优化的方法),另外的,这些方法在某些情况下也并不一定能得到最优的寻路结果,但是对于较空旷(不包含大量阻挡)的游戏地图,这些方法的寻路结果也已经足够好了.如果你想加速 A* 算法但是又不想对其实现进行大幅改动的话,你可以参考以下的几点建议:

• 使用有序列表. A* 算法的每一次搜索都需要找到具有最低 F 值的节点,通过使用有序列表,我们就可以在列表的头部位置方便的找到该节点(译注:原文中的意思是使用无序列表,疑有误或者有其他指代意义,译文改为有序列表)
• 使用 字典(或者说优先级队列) 或者 堆 来替代 列表 也可以加速 A* 算法.在这些数据结构中遍历元素非常之快,这会非常有助于你在其中搜索某一节点,同样的,在有序字典或者最小堆中,我们也能很方便的找到具有最低 F 值的节点.
• 分帧寻路.如果你的游戏并不需要在一帧中就获取完整的寻路结果,那么我们就可以使用分帧寻路来优化 A* 算法.我们可以设置一个循环上限,如果 A* 算法在该循环限制内没能完成寻路,我们便暂停当前寻路,并在下一帧继续.(译注:原文的意思应该是分段寻路,方法是如果在设置的循环限制内不能完成寻路的话,下一帧就从最后一个搜索节点开始重新寻路,这种方法并不一定能正确得到寻路结果,译文调整为分帧寻路)
• 节点中保存 is_open 或者 is_close 变量.你可以在节点中保存一个变量,用以表示节点是否在开放列表中或者关闭列表中.通过这种方式,当你需要搜索一个列表中的节点时,你就可以不用在整个列表中搜索节点,而是直接检查对应的变量值即可.这种方法可以大幅减少检查节点是否在列表中的开销.
• 在开始实际寻路之前先进行一次低层级的寻路.你可以在原游戏地图的基础上预先构建一张由部分节点构成的地图,然后在实际真实寻路之前,先在这张低层级地图上进行寻路,这样你就可以获取到一条由部分节点构成的寻路路径,之后你就可以分帧来搜寻这些(部分)节点之间的路径,与上述的分帧寻路不同的是,你不用限制循环上限,而是一帧一帧的来寻找(部分)节点之间的路径.

算法优化

所谓算法优化,是指那些会改变算法搜寻节点方式的优化.每一个对于算法搜寻节点方式(基于地图分布方式或者角色移动方式)的微小改变都可能极大的改善寻路算法的效率.值得一提的是,根据游戏地图的动态程度不同,算法优化的效果也不尽相同.目前有很多关于 A* 的算法优化方式,我们这里只会谈论其中的两种: HPA 和 JPS.

HPA

分层寻路会将原始地图预处理成一张更低层级的地图,其中原始地图会被分为多个簇(块),这些簇之间的距离和最优路径会被预先计算并缓存起来.实际寻路时,首先在更低层级的地图上(即簇之间)进行寻路,然后,我们根据之前预先计算缓存的(簇之间的)最优路径来获得一条到达目标点的路径.

在这里插入图片描述

正如我们在上图中所看到的,各个网格(节点)都按簇的方式进行划分,并且在这些簇上有用于连接相邻簇的出口,一旦我们将簇的出口(也是网格,或者说节点)进行相连,我们就可以得到簇从一条边(出口)到另一条边(出口)的距离,这些可以预计算的距离对于我们后面搜索路径非常有帮助.

在这里插入图片描述

现在,我们来看个例子,我们想寻找一条从 S 到 G 的路径,我们首先在低层级地图上(各个簇之间)进行一次 A* 寻路,然后,我们可以根据预计算数据(簇之间的连通数据)快速的得到一条完整的路径.

记住一点:你可以自定义网格和簇的创建方式,这听起来似乎很当然,但是这意味着你可以根据你游戏地图的分布方式来创建网格(和簇).通过自定义网格(和簇),你可以使一些簇变得更大,以使这些簇可以适应整个房间或者其他一些地图区域.

算法利弊:

每一种优化都有适合的使用情境,如果使用不当,优化效果就会大打折扣. 譬如在动态地图中, HPA 便 需要不时的重新计算簇之间的距离和路径,这会消耗很多的时间. 类似的, HPA 也并不是在空旷地图中寻路的最佳选择,不过这并不是说 HPA 在空旷地图上的寻路表现糟糕,而是说另一些寻路算法(譬如 JPS)更适用于这种情况.

JPS

JPS 算法的基本思路就是持续"扩展"节点直到到达无法继续"扩展"的区域为止.如果你仔细想一想就会发现, JPS 算法的内涵思想其实挺简单的:如果我们可以通过其他节点以更短的距离达到某一节点,那么我们完全可以不在(开放)列表中添加这个节点(因为这个节点在扩展其他节点时会被评估是否要加到开放列表中).

和 HPA 不同的是, JPS 不需要预计算任何数据,他的优势在于遍历开放列表和关闭列表的开销很小.需要注意的是, JPS 只支持规则网格(节点)的寻路,即使你的游戏地图包含不同寻路成本(距离)的网格或者区域, JPS 也只会把他们当做统一成本(距离)的网格或者区域.不过也正因为只支持规则网格的关系,JPS 才能够跳过网格的某些扩展方向,️而相对应的, A* 算法则需要扩展网格的所有可能方向.在 JPS 中,算法仅需要扩展被其称为 跳跃点(jump point) 的节点,接下来我会解释 JPS 是如何找到这些跳跃点的.

在讲解 JPS 算法的细节之前,我们先聊聊 JPS 的算法基础: 邻点裁剪(neighbour pruning)

在这里插入图片描述

假设节点 x 正在通过其父节点进行扩展,上图中我们用箭头来表示这个"父子"关系.如图所示,对于其中各个灰色节点而言,我们都可以不经过 x 节点,而是通过 x 的父节点(即 4 号节点)来进行访问(译注:意思是这些节点如果经过 x 节点来访问,其成本(距离)将小于或等于仅经过 x 父节点(4 号节点)来访问,所以在扩展 x 节点时,我们可以直接忽略这些节点而不进行扩展).现在我们来说下什么是强制邻点(forced neighbour):

在这里插入图片描述

强制邻点是指无法从 x 节点扩展到的节点,如上图所示,如果沿着灰色网格的箭头方向,我们无法到达红圈中的节点(译注:这里说的有些笼统,我们可以简单这么理解,由于阻挡的存在,我们已经不能直接经 x 父节点访问到红圈节点),这些节点便称为强制邻点.记住,如果正在扩展的节点旁边有阻挡的话,阻挡"后面"的节点便是强制邻点.

算法流程

暂略(译注:原文在这里通过示例描述了 JPS 算法在 水平方向 与 对角方向 搜索节点的流程,但是描述的比较简略,也存在一些错误,在此暂时省略翻译,有兴趣的朋友可以阅读这篇文章来了解 JPS 的算法流程)

算法利弊

正如之前所说,JPS 不能用于非规则网格地图的寻路;对于其适用的规则网格地图,地图的空旷程度越高,JPS 的效率也会越高.另外, JPS 也不需要预处理任何数据,并且支持动态地图.

如果你发现自己仍然不太理解 JPS 的算法步骤,你可以在这个网站上直观的查看 A*, Djikstra, JPS 等寻路算法的运行方式.

优化实现

现在,我们来看一个简单的寻路优化的实现方式,基本思想就是避免开放列表和关闭列表的遍历.我们首先需要创建一个节点数组.

在这里插入图片描述

通过这个节点数组,我们就可以通过网格的位置(索引)直接访问节点数据,这对于节点遍历非常有用.一旦我们有了节点数据,我们就可以执行 A* 算法了,我们要做的第一步就是在该数组中填充原始节点,我们使用的填充函数是 std::fill(first item, last item, Node).

在这里插入图片描述

注意,size 的大小为 width * height.我们接下来需要为开放列表创建优先级队列.正如我们之前所说,优先级队列可以让具有最低 F 值的节点位于队列头部,这样我们就不需要去遍历搜索该节点了.

在这里插入图片描述

如果你不知道上述代码里模板参数中的 compare 是什么,你可以简单理解是一种定义了如何比较节点的简单数据结构.

在这里插入图片描述

下一步就是创建 firstNode 节点指针,并将其加入开放列表中.我使用了 DistanceTo 函数来计算节点的启发式距离(到目标点的评估距离,即节点的 H 值).

在这里插入图片描述

其中 GetPathNode 函数用于通过给定节点位置(索引)获取对应的节点指针.

在这里插入图片描述

代码写到这里,我们就已经准备好进行 while 循环了,我们会使用节点指针来进行循环操作并检查这些节点指针是否已经在开放列表或者关闭列表中.

在这里插入图片描述

我们将当前节点的分值设置为最低,并且将其 on_close 变量设置为 true,正常来说,我们应该将节点放置于关闭列表中,但是设置节点变量数据是效率更高的一种方式.OK,现在是时候扩展相邻节点了,扩展之前我们需要检查相邻节点是否已经处于关闭列表中.

在这里插入图片描述

循环中我们创建了一个指向当前评估节点的指针 temp,然后我们检查他的 on_close 和 on_open 变量以获知其是否在关闭列表中或是在开放列表中.使用这种方法我们就避免了在传统 A* 算法中最大的一个性能问题:遍历列表以检查某一节点是否存在.代码的其他部分和一般的 A* 算法没有什么区别,值得一提的一点是,如果我们找到了一条到某一节点更短的路径,我们需要重新设置该节点的父节点.

在这里插入图片描述

CalculateFopt 是一个用来计算节点 G 值 和 H 值 的函数,方法上主要是检查了节点间是对角距离还是水平(或垂直)距离.我们需要做的最后一件事是,当我们搜索到目标点后,如何回溯节点直到返回开始点:

我们可以首先保存当前节点,然后一直回溯节点的父节点直到父节点为空.至此,我们仅通过节点数组便完成了所有的寻路操作(而没有使用节点列表)!

优化总结

我尝试在 120x120 的地图上进行最"困难"的路径搜索,结果显示,使用优化过的 A* 算法寻路,时间花费最多是在 20ms 左右,而普通的 A* 算法则需要 200 ~ 600 ms.

你可以在 github 上下载工程文件并自己尝试下~

参考

• http://zerowidth.com/2013/05/05/jump-point-search-explained.html
• http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter17_Pathfinding_Architecture_Optimizations.pdf
• http://www.intelligence.tuc.gr/~robots/ARCHIVE/2015w/Projects/LAB51326924/jps.html
• https://gamedevelopment.tutsplus.com/tutorials/how-to-speed-up-a-pathfinding-with-the-jump-point-search-algorithm–gamedev-5818
• http://aigamedev.com/open/review/near-optimal-hierarchical-pathfinding/
• https://qiao.github.io/PathFinding.js/visual/