祁 悦 ，赵 洋 ，杨 帆

（南京理工大学 计算机科学与工程学院,江苏 南京 210094）

一种基于A*算法的分层路径规划在3D游戏中的应用研究

祁 悦1，赵 洋2，杨 帆3

（南京理工大学 计算机科学与工程学院,江苏 南京 210094）

以3D游戏中智能体的路径规划为研究背景，对于如何生成3D游戏的地形网格以及如何进行高速、准确的路径规划进行了研究。提出了一种分层的解决方案，首先通过建立导航网格划分状态空间；接着使用引入地形估价因子的 算法进行网格寻路，并通过拐角点法生成路径，同时对 算法的OPEN表进行了二叉堆的优化；最后介绍了基于射线透射的局部 算法对动态障碍物的处理。实验分析表明该算法的有效性。

导航网格； 算法；地形因子；二叉堆；拐角点法；射线透射

随着游戏产业的快速发展，每年都有很多不同种类的游戏产品推出，形成了一项数十亿美元的产业。尽管游戏的名目众多，但游戏的类型却十分有限。开发者们正在致力于寻找任何可能找到的方式来使他们的游戏受到关注，而游戏人工智能[1]无疑是一个很好的方向。

在游戏人工智能中，路径规划是角色动作选择的一个重要表现。出于对用户体验的考虑，不同游戏对NPC(Non-Player Character,非玩家控制角色)人工智能化程度的设计要求不同，使得不同角色对寻路的要求也不尽相同。对于小型游戏以及对寻路时间要求不高的NPC可以采用基于盲目搜索的路径规划，例如宽度优先搜索便能够保证角色可以到达目标地点，但对于大规模的路径规划，如在需要考虑众多物理因素的3D游戏环境下，启发式搜索可以有效地节约内存资源并且快速达到目标状态。目前，A*算法是应用最为广泛的一种启发式搜索算法。

本文针对3D游戏的物理环境以及特殊性，采用了一种分层次的路径规划解决方案。首先，游戏环境处理层负责根据地形、静态障碍物的规划以及关卡设计信息生成导航网格图；接着，路径规划层负责选择合适的寻路算法对不同角色进行路径规划,本文采用引入地形估价因子的A*算法；最后，动态障碍物规避层则负责处理碰撞检测、局部规避、群体角色寻路优先级等问题。

1 导航网格的生成

在早期的2D游戏中，游戏开发者们多采用栅格法或可见点法[2]划分搜索空间。然而当面对大型的3D游戏，栅格法和可见点法的缺点就显现出来了。它们需要大量细化的栅格或路点来描述多障碍的大地图，内存占用率高，寻路效率低，且在面对动态障碍物以及不同角色的不同寻路参数时表现不尽人意。导航网格[3](NavMesh)是一种越来越受游戏开发商欢迎的方法。它使用凸多边形的网来描述游戏环境中的可访问区域。凸多边形有个很重要的特性，就是它允许从多边形的任一点到网格中的其他点都可以保证畅通无阻。

在游戏环境预处理层，我们可以将三维空间表示成由相互连接的多边形构成的网格，并将多边形数据存储为结点应用于寻路中。导航网格非常接近于三维场景空间，根据地图不同区域的特点，网格可以是三角形或凸多边形。生成导航网格的方法很多，可以选择用中间件生成，例如Xaitment、NavPower、 PathEngine、 Kynapse等[2]。现在很多的集成游戏开发引擎也都包含了生成导航网格的组件。如图1所示，此图是在unity 3D游戏开发引擎中生成的一个导航网格图，在图中可看出在较为宽阔的平地导航网格较稀疏，而在周围静态障碍物的区域，网格密度较稠密。

图1 导航网格图Fig.1 Navmesh implementation

自动生成的导航网格具有一定的局限。在NPC较多或是关卡设计较复杂的状态空间中，关卡设计师需要在某个区域设置更多的网格以便使地图能够处理该区域可能发生的碰撞或者其它动态障碍。例如在FPS（First-Person Shooter Game, 第一人称射击类游戏，简称FPS）游戏或者RTS（Real-Time Strategy,实时策略游戏，简称RTS）游戏中，某个区域会有许多NPC埋伏，此时PC(Player Character,玩家控制角色)需要对该区域进行动态检测，若需要重新进行寻路，该区域则需要较多的网格以确保寻路算法的实现。因此针对关卡设计较复杂的区域，使用手动方式绘制导航网格比较合理。

2 基于导航网格的A⋆算法

传统A*算法可以看作是在Dijkstra算法的基础上加入了启发式搜索，启发信息的确定原理是引入一个估价函数[4]，对状态空间中需要搜索的每个结点进行估价，将估价最小的结点取出并继续向下搜索。A*算法估价函数的基本形式是f(n)=g(n)+h(n)，其中f(n)表示从起始结点经过当前结点并且到达目标结点的估价花费，g(n)表示从初始结点到当前结点的实际花费，h(n)表示当前结点到目标结点的估价花费。当估价花费h(n)越接近真实值，算法的效率就越高[5-6]，越有可能找到最优解。A*算法流程如图2所示。

在游戏开发中用于寻路的A*算法根据导航网格密度、网格边数以及跨越网格边界的权值不同，估价花费f(n)的选取也不同。因此，首先对导航网格内每一个多边形结点的定义如下：

图2 A*算法流程Fig.2 A*algorithm processes

其中，point_array表示网格顶点位置信息，edge_array表示边的信息，factor表示当前网格的地形因子，f和g分别代表启发函数中的f(n)和g(n)。两个布尔变量inOpen和inClose分别表示当前网格结点是否存在于 算法中的OPEN表或者CLOSED表中。

其次需要研究的就是如何确定一个合适的估价函数。简单地图多采用欧几里德距离法[7]、曼哈顿距离法[8]或者对角线距离法定义估价函数，但这些方法仅仅考虑了距离而忽略了地形代价，在多障碍的大型复杂地图中往往不太适用。这里我们引入一个地形因子factor，针对不同代价的地形因子可以更准确地反映角色寻路的花费。对于估价函数中的代价g值，这里定义为网格结点穿入边和穿出边中点的曼哈顿距离；估价花费h值取该三角形的中心点（三顶点的中值）到路径终点B的x和y方向的曼哈顿距离，化简后的公式为：

其中g0表示起始结点到第一条穿出边的g值花费，gn为第n个结点网格的g值花费，s.x, s.y为起始结点的二维坐标值；p[1].x, p[1].y为第一条穿出边的中点二维坐标值；p[n].x, p[n].y为第n条穿入边的中点二维坐标值；p[m].x, p[m].y为n所在网格穿出边中点的二维坐标值；hn表示网格结点n到终点的估计花费； m[n].x, m[n].y表示第n个多边形网格结点中点的二维坐标值；fn则表示为n结点的总花费；最后factor表示地形因子。地形因子的影响因素有很多，因素如地形坡度、粗糙度等，这些因素不能直接作为路径规划的信息，需要对其进行一定的转化。这里简单的以坡度α和粗糙度β作为因素提出一种地形因子的解决方案，公式如下：

估价函数确定后，就可以根据A*算法的算法流程，找到最优网格路径。考虑到算法引入了地形估价因子，对算法的效率产生了一定的影响，这里可以对OPEN表进行一个二叉堆[7]的优化处理。二叉堆是一棵排序树，它的父亲结点总是小于或大于 它所有的孩子结点，但各个孩子结点之间是无序的，因为它并不是完全有序的树，但在算法中我们仅需将OPEN表中最小的一个结点取出即可，即只需将二叉堆的顶点取出放入CLOSED表。因此，使用二叉堆可以减少比较次数和排序的时间。在此我们在Inter Core i3 2.93 GHz/ Windows 7 32 bit/Visual C++ 2008环境下对二叉堆优化OPEN表的A*算法和传统A*算法对运行时间进行简单对比试验，地形因子factor值取1，即在光滑的二维平面进行，h(n)取十倍的曼哈顿距离，对比结果如表1所示。结果表明使用二叉堆存放OPEN表是可以提高算法效率的。

表1 算法的对比结果Tab.1 Test result of the algorithm

最后进行网格内路径点的生成。如图3左边网格点图所示，5个相邻的多边形为A*算法求出的最优网格路径。其中S表示起点，P表示终点，其余C到G各点为网格公共边的交点。本文定义多边形顶点的存储均为顺时针顺序，如图可以看出每条公共边均为起点穿出该多边形区域的边，故以下称该边为穿出边。首先，将起点S所在穿出边的两个交点A、B分别设为左点和右点。如图3右边网格线图所示，由起点S分别连接A和B并延长，定义线段SA和SB为左线和右线，查找下一条穿出边的两个端点C和D，若C点在左线和右线之间，记C点为新的左点，并且更新SC为新的左线；同理，若顶点D在新的左线SC和右线SB之间，则更新D点为右点，且记新的右线为SD。

图3 网格点与网格线图Fig.3 Maps with navmesh points and navmesh lines

继续查找，如图4左边拐点图所示，若下一条穿出边的顶点E不在左线和右线之间，则不更新左点和左线，而F点则在左线SC和右线SD之间，则更新F点为右点，SF为右线。若下一条穿出边的两个顶点均不在当前左线和右线之间，如图H点和G点均在右线SF之外，则当前的右点为右线的终点，记该右点为路径的一个拐点。拐点确定后，将其视为新的起点，循环以上步骤，当终点出现在左线和右线之间时，从起点开始，连接所有的拐点和终点，则找到了一条完整的路径。如图4右边最终路径图所示，连接SF和FP，即生成了从起点到终点的路径。

图4 拐点与最终路径图Fig.4 Maps with corner points and final path

3 动态障碍物处理

在游戏中，如果PC遇到障碍物，游戏操作者本身可以通过观察和操作对障碍物进行规避，而对于没有学习能力的NPC，当遇到游戏场景动态的变化，例如一个较大的爆炸碎片堵住了寻得的路线上的某结点或是一群NPC突然出现在了某个需要通过的结点，此时如果重新进行路径规划是十分不明智的。因此，在路径规划的最后引入动态障碍物规避层，该层主要负责处理碰撞检测[9]、局部规避、群体角色寻路优先级[10]等问题。

游戏世界众多的NPC都是具有物理属性的，即可能发生碰撞，那么就需要一个碰撞检测子系统能够监听到此类情况的发生。在3D场景里，碰撞检测可以通过射线透射实现。射线是以智能NPC自身所在坐标为起点向前进方向发射的一条或多条无终点的线，一旦检测出射线存在终点坐标，则可判断其将遇到障碍物。此时，可以向游戏状态获取障碍物详细信息，即可以判断其是否将发生碰撞。如若角色在移动过程中接收到的碰撞子系统的决策告知下一个或是多个结点将发生碰撞，则将其标记为阻塞结点，此时需要改变寻路策略。对此可以引入一种基于射线投射的局部A*寻路方法。

定义从阻塞结点的前一个结点开始到阻塞结点后一个结点进行局部寻路，然后将新的路径覆盖阻塞的部分。这么做的好处是，原先A*算法已经求得的路径花费可以重用，提高寻路的效率。对于NPC群体寻路，可以采取设置优先级的方法，若高优先级的角色和其他角色发生碰撞，可以默认将其他角色视为静态障碍物，等待高优先级的角色走过后再进行寻路。通常优先级的确定是与角色的移动力和反应速度等因素相关的。

4 结束语

文中针对3D游戏中的路径规划问题，提出了分层次的解决方案。首先采用导航网格对大地图的状态空间进行划分，避免了存储大量的路点，节约了内存空间。接着使用基于导航网格的A*算法实现了最优网格路径并对A*算法的OPEN表进行了二叉堆的优化，实验分析表明该方案能够提高算法的工作效率。接着采用拐角点法生成了网格内部的路径，完成角色的路径搜索。最后，给出了一种基于局部A*算法的智能NPC的障碍物规避算法。本文介绍的层次化路径规划解决方案正用于3D游戏运动模型系统的研发，初步效果令人满意。

[1]方约翰, 李睿凡, 郭燕慧, 等. 游戏人工智能: 计算机游戏中的人工智能[M]. 北京邮电大学出版社, 2007.

[2]Buckland M. 游戏人工智能编程案例精粹[M].罗岱,译. 人民邮电出版社, 2008.

[3]Sturtevant N R,Buro M. Improving Collaborative Pathfinding Using Map Abstraction[C]//AIIDE. 2006: 80-85.

[4]Leigh R, Louis S J, Miles C. Using a genetic algorithm to explore A*-like pathfinding algorithms [C]//Computational Intelligence and Games, 2007. CIG 2007. IEEE Symposium on. IEEE, 2007:72-79.

[5]Graham R, McCabe H, Sheridan S. Pathfinding in computer games[J]. ITB Journal, 2003,8:57-81.

[6]Björnsson Y, Enzenberger M, Holte R C, et al. Fringe search:beating at path-finding on game maps[J]. CIG, 2005, 5: 125-132.

[7] Ballinger C, Louis S. Comparing heuristic search methods for finding effective real-time strategy game plans[C]//2013 IEEE Symposium Series on Computational Intelligence. 2013:122-128.

[8]徐翔, 黄敏. 一种改进的群体智能寻路算法[J]. 计算机应用与软件, 2012, 29(5): 139-142.

XU Xiang，HUANG Ming.An improved group intelligence pathfinding algorithm[J]. Computer Applications and Software,2012,29(5):139-142.

[9] Bakkes S C J, Spronck P H M, van Lankveld G. Player behavioural modelling for video games[J]. Entertainment Computing, 2012,3(3): 71-79.

Application of a A* algorithm-based hierarchical path planning in 3D games

QI Yue1, ZHAO Yang2, YANG Fan3
（College of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing 210094, China）

This paper focuses on how to generate a 3D navmesh and implement high-speed path-finding for autonomous characters in 3D games. We proposed a hierarchical solution to meet the requirement. Firstly, a navmesh is used to divide the state space. Then we used the A* algorithm to find the path of the navmesh with making use of binary heaps to optimize the OPEN table. We also proposed a method of corner points to find the final path. At last, we used ray transmission to detect the dynamic obstacles. The initial experimentation shows that our solution is able to be used in some 3D games.

navmesh; A* Algorithm; terrain factor; binary heaps; corner points; ray transmission

TN919.32

A

1674-6236(2014)11-0037-03

2013-10-24 稿件编号：201310166

祁 悦(1989 —），女，江苏扬州人，硕士。研究方向：游戏人工智能。