3D游戏中AI自动寻路机制的算法与优化策略研究

卫　敏

(山西职业技术学院，山西 太原 030006)



3D游戏中AI自动寻路机制的算法与优化策略研究

卫敏

(山西职业技术学院，山西 太原 030006)

摘要：随着3D游戏的日趋流行，在复杂的3D游戏环境中如何能使非玩家控制角色准确实现自动寻路功能成为了3D游戏开发技术中一大研究热点。本文针对3D游戏开发中的AI自动寻路功能的A*算法进行了基于Unity3D游戏开发平台的优化与实现，优化后的A*算法较之传统的路径规划算法，实时性更高、灵活性更强，寻路结果更加接近人工选择的路径结果。

关键词：3D游戏；AI人工智能系统；寻路算法

现今随着手机3D游戏开发技术的日渐成熟，游戏玩家对游戏品质的要求也越来越高。玩家对游戏品质的评价一般主要取决于游戏的操控性是否灵活、游戏的虚拟环境是否逼真以及游戏的运行是否流畅等方面。设计开发3D游戏，怎样在各个性能指标间实现平衡，则属于核心问题。

1AI自动寻路功能概述

在游戏中，AI(即人工智能)系统主要是用于实现游戏角色的某种智能行为，使用户的游戏体验更加逼真，增加游戏的趣味性[1]。例如在射击游戏中敌人的子弹可以自动追踪攻击玩家；在NPC游戏中敌人可以自动的避开障碍物寻找最短路径到达玩家所在目的地对玩家进行攻击，这些智能行为的实现就是通过AI系统中的智能寻路功能来完成的。

在技术实现方面，本文所研究的寻路算法设计主要是基于一种经过变异的贪心算法——A Star算法框架构建的[2]。通过对游戏场景中预先设置的路径节点进行分析计算找出最优路线，实现游戏角色的智能寻路。

23D游戏中AI算法的设计原理

A Star算法简称A*算法，其基本原理是通过创建的开放式列表与封闭式列表对游戏场景中的所有路径节点进行比对和筛选，从而计算出最短的路径，为了节省游戏在这方面的计算开销，该算法采取的是模糊比对，省略了贪心算法中的回溯计算部分。

2.1A*算法的基本原理

如图1所示，将游戏角色的起始位置设为开始节点，要到达的目的地设为目标节点，黑色区域是障碍物标志，白色区域为可通行路径。

图1　路径节点设置示意图

图2　A*算法基本原理

A*算法的基本设计原理如图2所示，首先将所有需要检测的路径节点读入到开放式列表，从起始节点开始中选取距离目的节点最近的节点依次与目标节点进行比对，所得到路径即为最优路径。该算法通过一定的择优策略选择场景中节点进行比对，例如将图1中的路径起始节点设为A，目标节点设为B，当前计算出的最优路径节点为C，在仅考虑节点间的几何距离前提下其节点代价的计算可由公式(1)得出：

(A-C)2+(B-C)2.

(1)

通过计算的各个节点代价，选择代价最小的节点优先进行比对。最坏的情况是遍历了所有的节点才得到结果，因此该算法的计算效率与游戏场景中的节点数量有直接关系，如果游戏场景较为复杂，包含有大量的路径节点信息，会严重增加算法开销，要解决这些问题就需要对A*算法做进一步的优化。

2.2A Star寻路算法的优化

首先，从节点列表的结构优化上着手，改进A*算法的性能。主要是将所有节点按照计算出的节点代价由小到大进行排序并建立相应的结构列表，根据节点的变化动态维护该数据结构，从开放式列表中选择最优节点时可直接通过该数据列表读取到当前的最优节点，该方法适用于复杂的游戏场景寻路，以增加游戏占用的系统存储空间为代价减少寻路算法的系统开销。

其次是在动态场景中对寻路算法进行优化调整。当在游戏中有多个对象同时进行寻路移动时，优化策略可分为以下几步来实现动态的路径调整：

1) 为每个对象建立一个碰撞列表用于记录该对象发生过碰撞的路径信息；

2) 根据各个对象之间的优先级进行排序，当检测到碰撞后，将选择优先级别最高的对象重新进行节点定位和路径选择，同时停止其他对象的移动，直到优先级最高的对象通过再继续原路径的移动；

3) 将上一步碰撞检测到的路径信息记录到碰撞列表中，每次检测到碰撞后，都先在碰撞列表中进行查询。如果路径信息是重复的则要更新路径选择策略，如果路径信息无重复则要对碰撞列表进行更新。这主要是为了避免对象的路径重复，反复与同一对象发生碰撞。

33D游戏开发中AI寻路算法的具体实现

本文采用了目前在移动平台上较为流行的一款游戏开发引擎——Unity3D来进行AI寻路算法的设计。

3.13D游戏开发软件——Unity3D游戏引擎中AI系统的设计框架

Unity3D游戏引擎本身就提供有AI寻路系统，主要采用的是路径节点(WayPoint)算法进行路径选择。WayPoint算法是基于A*算法框架由Unity3D引擎自行开发的寻路策略，其设计框架可以简述为：

首先通过调用Unity3D游戏引擎中的Navigation路径导航系统对场景中的地形进行分析计算，建立节点信息列表；

其次进行寻路者的设置，为寻路者添加AI寻路组件(Nav Mesh Agent)计算寻路者的节点位置、运动速度、旋转速度等信息；

初始化节点信息，通过WayPoint算法在游戏场景中标记出所有的路径节点，并在各个节点间建立连接路径，在确定了的起始节点与目的节点之间每次任取两个分别与起始节点和目的节点临近的节点计算路径代价，并优先选择其中代价最小者来获取最短路径；

编写寻路控制脚本用于实现寻路者的动态寻路控制，当目的节点发生改变，通过寻路脚本控制可动态更新追踪目的节点并进行路径的调整控制。

3.2三维游戏场景中AI寻路功能的实现与控制

Unity3D游戏引擎主要支持C#、Java及boo三种脚本的编程开发，这里对自动寻路的控制实现编程采用的是C#脚本，其核心代码示例如下：

Public class NavMA:MonoBehaviour{

Transformm_object;//定义寻路者对象组件变量

Player m_MyPlay;//定义玩家变量

NavMeshAgentm_MeshA;//定义寻路组件变量

voidStart(){

m_object=this.transform;//将寻路者对象实例化

m_MyPlay=GameObject.FindGameObjectWithTag(“Player”).GetComponent();//实例化玩家对象，通过m_MyPlay的位置属性可锁定动态目标节点

m_MeshA=GetComponent();//导入游戏地形的节点计算信息

m_MeshA.SetDestination(m_MyPlay. m_object.position);//实时锁定寻路的目标节点位置为玩家所在位置}

void Update(){

MoveCon();//调用控制函数}

voidMoveCon(){

m_MeshA.Move(m_object.TransformDirection((new Vector3(0.0f,0.0f,0.3f))));//控制寻路者动态追踪玩家坐标节点，计算最短路径，并按照设置的速度进行寻路移动}}

4结论

本文针对目前3D游戏开发中的研究热点——AI寻路功能的优化进行了一些研究和尝试。通过对A Star寻路算法的应用分析，再进一步优化了算法，并通过Unity3D平台进行了实现。但为了兼顾游戏的运行效率，算法设计中未能提高现有寻路机制的精确性，在一些特殊情况下会影响到用户的游戏体验，在这一方面还有待进行更加深入的研究。

参考文献

[1]梁毅，周刚.基于定位点和路径复用的大型多人在线游戏寻路算法[D].成都：四川大学，2013.

[2]杨科选.人工智能寻路算法及其在游戏中的应用研究[D].长沙：中南大学，2013.

收稿日期：2015-12-31

作者简介：卫敏(1979- )，女，山西太原人，助讲，大学本科，研究方向：计算机应用。

文章编号：1674- 4578(2016)02- 0091- 02

中图分类号：TP391.41

文献标识码：A

3D Games AI Algorithms Automatically Find Its Way Mechanism and Strategy Research

Wei Min

(DepartmentofComputerScience,ShanxiVocationalandTechnicalCollege,TaiyuanShanxi030006,China)

Abstract:With the increasingly popular spreading of 3D game, how to make non-player to control characters and exactly realize the automatic pathfinding function becomes one major research focus in the 3D game development technology under the complex 3D game environment. Aiming at the A* algorithm of AI automatic pathfinding function, this paper makes optimization and realization for it based on Unity 3D game development platform. Compared to the traditional algorithm of route planning, the optimized A* algorithm is more real-time and flexible, and its pathfinding result is closer to that of artificial selection.

Key words:D games; AI artificial intelligence system; pathfinding algorithm