面向大型三维场景的优化分层A*寻路算法研究

朱昌龙 刘黎志

摘 要：针对大型三维场景中A*寻路算法存在搜索节点过多、寻路效率低的问题，提出了一种面向三维场景网格的改进分层A*算法。首先将三维场景进行体素划分，根据三维体素的属性生成可行走域的导航网格，并利用多级K划分对导航网格进行抽象分层，形成抽象分层路径，然后使用双向搜索策略对A*算法进行优化。建立了大型三维场景环境下寻路仿真实验平台，将传统A*算法与改进分层A*算法进行性能对比，实验证明改进分层A*算法搜索效率明显高于传统A*算法。

关键词：A*算法；体素化；分层路径；导航网格；双向搜索

DOI：10. 11907/rjdk. 182335

中图分类号：TP312 文献标识码：A 文章编号：1672-7800（2019）005-0013-04

Abstract： Regarding the shortcoming of A-star algorithm's excessive searching nodes of path and inefficiency of searching in large 3D scenes， an improved hierarchical A-star algorithm for 3D scene mesh is presented. Firstly， the voxel is divided into three-dimensional scenes， and the navigation mesh of the walkable domain is generated according to the attributes of the three-dimensional voxel， and the navigation mesh is abstractly divided by Multilevel K-way Partitioning to form an abstract hierarchical path. Secondly， the A-star algorithm is optimized using a bidirectional search strategy. Finally， a pathfinding simulation experiment platform in a large three-dimensional scene environment is established. The performance difference between the traditional A-star algorithm and the hierarchical A-star algorithm is analyzed and compared. The experiment proves that the improved hierarchical A-star algorithm has higher search efficiency than the traditional A-star algorithm.

Key Words： A* algorithm； voxelization； hierarchical path； navigation mesh； bidirectional search

0 引言

玩家喜愛拥有大型三维场景的游戏。如何提高游戏路径搜索性能是游戏人工智能的研究热点 [1-4]，路径搜索过程分为地图预处理和寻路算法两方面。

地图预处理常用的方法是栅格法[5-7]，它将地图划分为等面积大小方格，根据障碍物占栅格的百分比判断栅格属性。栅格法是一种较简单的地图划分方法，但针对大型三维场景地图，寻路算法搜索的网格节点过多，从而导致搜索效率过低。导航网格法[8-11]是将可行走域的地图以多边形或三角形数组进行划分的方法，在大面积地图区域中可减少大量的搜索节点。

寻路算法目前应用最多的是A*算法[12-14]，它是一种最基本的启发式全局路径搜索，通过启发式函数估计从当前节点到达邻居节点到目标点的成本进行路径搜索。A*算法近年来得到了很多改进 [15-17]，如为降低基于网格的地图路径查找复杂性，Adi Botea等[18]提出了基于网格的分层A*方法，该技术将地图根据四叉树算法等距离划分为相互连接的本地集群，在本地级别预先计算并缓存跨越每个群集的最佳距离，在全局层面路径搜索直接跨越集群而不是移动到相邻的节点位置。但是这种分层路径方法可能导致不平衡的抽象路径集群，所得到的更高级别层次结构在节点之间具有不均匀的边缘数量。基于导航网格的分层寻路算法，利用多级K划分方法进行分层，采用双向搜索策略进行优化，可极大减少节点数量，提高寻路搜索效率[19-21]。

1 三维场景导航网格

导航网格是一组用来划分地图信息的多边形数组集合。三维导航网格与二维导航网格区别在于：三维场景中允许有不同高度上的重叠移动区域，导航网格可行走的区域划分取决于游戏设定的人物可行走坡度。

三维导航生成步骤：①体素化输入三维地图模型，生成体素集合。体素是三维空间的划分单位，每个体素单位包含地图的属性信息，如图1（a）所示为地图模型体素化；②根据三维场景的配置信息（如可行走的坡度等），过滤障碍物以及角色无法行走的区域，生成可行走的区域体素集合。如图1（b）所示，蓝色为可行走区域，当坡度不满足设置要求时则为不可通过区域；③使用分水岭算法进行多边形划分，将可行走域划分为多个凸多边形的形式，如图1（c）划分了多个凸多边形；④对凸多边形继续使用三角剖分算法细分为三角网格，如图1（d）所示。

生成三维场景导航流程如图2所示，已生成的导航网格以三角形网格集合形式呈现。为使三角网格同样适用于A*算法寻路，需要对A*算法的网格代价重新定义，定义三角网格之间的耗费代价为三角网格中心之间的距离。

2 多层K路划分分层

三维导航网格是大小不同的三角形网格，不能采用基于栅格地图的均匀四叉树方法划分。为使导航网格分层的各区域更加平衡，采用多级K路划分算法进行抽象分层。

粗化阶段的主要目的是降低原始图的复杂性，方便构建图的层次结构。在粗化过程中，从原始图G0=（V0，E0）创建出一系列较小的Gi=（Vi，Ei），并满足 |Vi | < |Vi-1|。由Gi创建下一层级图Gi+1的方法是：通过找到Gi的最大匹配Mi？Ei，并将在相匹配的每个边的相关联顶点折叠在一起，不相关联顶点保留。如果没有发现相关联的顶点则称为最大匹配，不需要继续分层。为保持粗化后的图能保持原始图的一致性及保留连接信息，将粗化后的图的顶点和边的权重分别设置为上一层图的顶点和边的权重之和。

初始化阶段分区使用多级二分算法，以保证每个分区的节点权重之和大致等于原始图|V0|/K的節点权重。划分方法使用Kernighan-Lin算法，该算法本质是迭代的。首先将节点划分为两个不相交的子集，并使两个不相交的子集最小化，再从每个子集中找到一个顶点继续划分。

在细化阶段，将粗化图的分区（Gm，Gm-1，…G1）投影回原始图中。在每个投影步骤之后，使用动态方法来细化分区，在分区之间迭代地移动节点，从而改善分区质量。当所有分区投影至原始图时，细化阶段结束。

3 优化A*算法

A*寻路算法是基本的启发式路径搜索算法，根据估价函数对当前节点周围的邻居节点进行评估，选择代价最小的节点作为下一路径点。常规的A*算法是从起始点开始依次循环遍历直到搜索到目标点为止，采用双向搜索策略可极大提高搜索效率。

3.1 A*算法优化

A*寻路算法是基本的启发式路径搜索算法，根据估价函数对当前节点周围的邻居节点进行评估，选择代价最小的节点作为下一路径点。常规的A*算法是从起始点开始依次循环遍历，直到搜索到目标点为止。A*算法对节点数据操作采用两个优先队列表，一个是Open列表，用来存储待考察的节点，另一个是Close列表，用来存储已考察的节点。每进行一次寻路过程，都需要更新Open列表和Close列表。当地图规模很大时会产生大量节点，导致搜索效率过慢，因此采取双向搜索策略。

双向搜索算法同时运行两个搜索方法：一个从起始点正向搜索，另一个从目标点反向搜索，当各个方向搜索出相同最优路径点则停止搜索并连接。A*算法的双向搜索策略需要建立4个优先队列表：正向的Fopen列表、Fclose列表以及反向的Bopen列表和Bclose列表，用于存储搜索节点。A*寻路算法性能很大程度上取决于启发式函数和估价函数。

搜索路径过程分为4个阶段：

（1）确定起始点S与目标点G。预先确定起始点S和目标点G的层次分区并连接分区的边界。对于已经确定的起始点S和目标点G，依次递归地从L0层查找至最高层，存储所在的层次。

（2）在抽象图中插入起始点S和目标点G。将起始S和目标G位置插入最低层次L0的图中，然后递归地查找最高层次的相应节点层次结构，将起始点S、目标点G作为临时节点Nts和Ntg插入更高层次级别的抽象图中。分别连接至所在抽象分区的邻接边缘，由最底层分区至最高层分区，分别计算并存储起始点S到分区的每个邻接边缘的最短路径。如图5（a）所示为起始点连接分区边缘。

（3）在最高层次抽象图中搜索起始点S至目标点G的最短路径。当最高层次抽象图中确定了起始点S和目标点G的临时节点，就可在最高层次抽象图中使用A*寻路算法。

（4）连接完整路径。A*寻路算法给出了在抽象图中各个层次的最短路径，路径搜索从最高层次抽象图搜索至最低层次结束，连接各个层次的临时节点获得完整路径，见图5（b），得到S到G的最短路径，最后再删除临时节点释放内存。

4 实验仿真及评估

为验证基于导航网格分层优化A*算法的性能，实验仿真地图采用某大型城市游戏三维地图，如图6（a）所示。首先将游戏地图导出为模型文件，利用建模工具3DMax剔除障碍物，只保留可行走的域模型并生成导航网格，以导航图的形式保存下来。最后利用Unity3D游戏引擎搭建实验平台，导入导航图，划分三层抽象图，利用优化分层A*算法找到最优路径，如图6（b）所示。

对三维大型地图经过实验对比分析，在测试50次的标准下取平均值，测试结果见表1。虽然导航网格预处理地图的时间高于传统方格地图，但在搜索时间上明显小于基于方格A*算法。综合实验分析，基于导航网格分层优化A*算法搜索速度明显高于传统A*算法。

5 结语

本文基于静态大型地图进行全局寻路并给出了一种高效的寻路算法。首先将地图预处理为导航网格并将地图进行分层处理，利用双向搜索策略进行改进，利用Unity3D引擎搭建实验平台，实验证明该算法在寻路效率上有明显提升。但在动态地图和局部动态寻路方面，分层划分和双向搜索算法有一定的局限性，动态寻路问题是下一步研究重点。

参考文献：

[1] 何国辉，陈家琪. 游戏开发中智能路径搜索算法的研究[J]. 计算机工程与设计，2006，27（13）：2334-2337.

[2] 詹海波. 人工智能寻路算法在电子游戏中的研究和应用[D]. 武汉：华中科技大学，2006.

[3] 李井颂. 游戏中的智能路径搜索算法及其应用[D]. 昆明：昆明理工大学，2017.

[4] 周振华. 游戏场景中分层寻路算法及地图复杂性度量研究[D]. 保定：河北大学，2014.

[5] 于红斌，李孝安. 基于栅格法的机器人快速路径规划[J]. 微电子学与计算机，2005，22（6）：98-100.

[6] 王卫红，顾国民，秦绪佳，等. 基于栅格法的矢量路径规划算法[J]. 计算机应用研究，2006，23（3）：57-59.

[7] 夏梁盛. 基于栅格法移动机器人运动规划研究[J]. 计算机仿真，2012，29（12）：229-233.

[8] 朱庆，王烨萍，张骏骁，等. 综合导航网格模型及其在智慧旅游寻径中的应用[J]. 西南交通大学学报，2017，52（1）：195-201.

[9] 王烨萍. 基于综合导航网格的智慧旅游动态寻径方法[D]. 成都：西南交通大学，2017.

[10] 陈娜，黄明和，刘清华. 基于DAF算法的地图寻径研究[J]. 科学技术与工程，2010，10（30）：7536-7540.

[11] 林巍凌. 引入导航网格的室内路径规划算法[J]. 测绘科学， 2016，41（2）：39-43.

[12] 陈和平，张前哨. A*算法在游戏地图寻径中的应用与实现[J]. 计算机应用与软件，2005， 22（12）：118-120.

[13] 刘浩，鲍远律. A*算法在矢量地图最优路径搜索中的应用[J]. 计算机仿真， 2008（4）：253-257.

[14] 熊伟，张仁平，刘奇韬，等. A*算法及其在地理信息系统中的应用[J]. 计算机系统应用，2007，16（4）：14-17.

[15] HARABOR D， GRASTIEN A. Online graph pruning for pathfinding on grid maps[C]. California：AAAI Conference on Artificial Intelligence，2011.

[16] DEKIM H，YU K，KIM J. Reducing the search space for pathfinding in navigation meshes by using visibility tests[J]. Journal of Electrical Engineering & Technology，2011，6（6）：867-873.

[17] 陈刚，付少锋，周利华. A*算法在游戏地图寻径中的几种改进策略研究[J]. 科学技术与工程，2007，7（15）：3731-3736.

[18] BOTEA A， MüLLER M， SCHAEFFER J. Near optimal hierarchical path-finding[J]. Journal of Game Development，2004， 1（7）：7-28.

[19] 郑丽丽. 带权图的k划分算法研究[D]. 天津：天津工业大学，2013.

[20] KARYPIS G，KUMAR V. Parallel multilevel k-way partitioning scheme for irregular graphs[J]. Siam Review，1999，41（2）：278-300.

[21] 高松，陆锋，段滢滢. 一种基于双向搜索的K则最优路径算法[J]. 武汉大学学报：信息科学版，2008，33（4）：418-421.

（责任编輯：杜能钢）