人工智能寻路算法及其在游戏中的应用研究

李志豪 张毅 黄健宇

摘要：近年来，大型网络游戏逐渐开发，游戏开发中所用到的技术大部分为智能化、自动化技术。其中基于人工智能的寻路算法在游戏开发中比较突出，A*搜索算法是寻路算法中反映速度最快的一种，能够在短时间内遍历诸多地点，并找寻出最短的路径。基于此，本文将对游戏中的人工智能寻路算法中的A*搜索算法进行分析，研究其实际算法的改进，并将改进后的智能算法应用到实际游戏开发中。

前言：随着游戏的开发与应用，人工智能A*搜索算法占据了游戏设计是重要部分。其中A*搜索算法是一种被广泛应用的最短路径搜索算法之一，在广度优先搜索模式的启发之下，进行路径搜索，其搜索函数所针对的对象是对当前搜索位置。在实际的路径遍历中，A*搜索算法经常会走弯路，为了提升路径搜索效率，需要对A*搜索算法进行改进，并保障A*搜索算法下所搜索的路径为最优。

1.人工智能寻路算法概述

1.1人工智能

人工智能的简称为AI，是一种的应用于模拟场景开发、延伸以及拓展等的智能理论，是目前比较时尚的技术科学。人工智能所包含的内容比较多，其中主要包括思维过程模拟，以及智能型我的模拟。总体来说，人工智能所研究的对象是使得计算机能够运用专业知识去解决实际问题，模拟人类的部分智能行为。基于人工智能寻路算法在游戏中的应用，推动了游戏的开发[1]。

1.2 A*搜索算法

A*搜索算法实际上是一种启发式的算法，在很多领域中得以应用。A*搜索算法能够在地图上的两点间找到一条路径，这条路径是两点间的最短路径。在搜索路径之前，该算法首先需要判断，所要计算的两点间是否存在着路径。除了A*搜索算法还有很多搜索路径的计算方式，但是A*搜索算法对于路径的计算以及搜索速度是最快的，且其算法比较灵活多变。A*搜索算法在路径搜索环节中不会盲目，有时也能进行回溯尝试。A*搜索算法的搜索过程，主要是通过在地图中创建与位置相对应的节点，并在地图上以移动的方式来实现。这些节点有不同的属性，g代表着起始节点到该节点的代价，h代表着该节点到目标节点的估计代价，f代表着是经过该节点的路径估计值[2]。

2.A*搜索算法改进

2.1减少AI角色之间的碰撞

在大型的网络游戏中，AI角色之间不允许碰撞，如果不同的AI角色之间出现了碰撞，将会出现节点怪异。但是在进行A*搜索算法搜索路径环节中，不能忽视游戏中不同的AI角色之间的相互干扰，如果不能对以上情况进行避免将会出现不同的寻路者之间的穿越。为了避免不同角色之间的碰撞，需要对靠近一个正在运动的AI角色时，需要系统对其各自路径上的节点进行惩罚，并对另辟蹊径的AI寻路着进行奖励，在这样的模式下就能够避免AI角色之间的碰撞。在 游戏开发时，为了避免不同角色之间发生碰撞，需要在后台编写一段代码，当角色之间发生碰撞时，一个AI寻路者需要找到新路径，如果一个被碰撞的AI角色处于移动的状态时，则原AI寻路者需要等待，待其离开之后，在就行移动[3]。

2.2未知区域探索

在实际的游戏中，A*搜索算法的应用能够帮助AI角色进行未知区域的路径探索。而形成这样的功能实际上需要游戏系统中为游戏中的每一个角色创建一个"KnownWalkability"数组，在该数组中能够对角色所探索的路径进行记忆，避免AI角色在路的死端进行徘徊，并导致路径选择上出现问题。在游戏中，一旦地图的未知区域被其他玩家所探索过了，那么AI角色在进行寻路的环节中就会很容易找到未知[4]。

2.3非方形区域的搜索

A*搜索算法在以前的图形搜索中，一般使用的2D环境的方形图，但是随着游戏技术的不断开发，可以对非规则形状的图形区域进行探索。例如在《英雄联盟》、《梦三国》等游戏中，游戏开发可以设计出与角色路径探索相关的寻路关卡。首先需要设计者在地形图中确立一个路径点系统，该路径点一般是道路的转折点，在地形图中如果两个点之间没有障碍，就视为两个点是相邻的，在以上竞技类的游戏中，需要相邻位置安排在表格中，并记录地图上两个点之间的直线距离，进而实现非方形的区域搜索。

3.改进后的A*搜索算法应用

3.1盲目搜索

将改进了的A*搜索算法在实际游戏中的应用，能够实现地图的盲目搜索，盲目搜素实际上需要是在准确搜索的基础上，确定AI角色的大致位置，在实际游戏中的应用效果比较明显。盲目搜索是在一个图的搜索之下，对相关边的全部关系进行遍历。同时该种搜索模式能够针对不区域内部的节点和边进行分析，能够及时发现已经遍历过的目标节点，并迅速的将其排除在外。盲目搜索与其他种搜索模式相比，存在着很多差异，也有很多优势，一方面在搜索环节中所需要的信息都比较小，另一方面所搜索的深度和广度都比较大。

3.2 cost的图搜索

在很多游戏图搜索环节中，要想搜索一条路径，都需要具有一个开销，开销实际上就是权--cost。在游戏者想要寻找到两点之间的最短路径，首先需要考虑开销，在开销理念中，沿着两条比较短路径进行遍历，会比两条长边进行遍历便捷的多。基于A*搜索算法就属于开销中的一种。将A*搜索算法进行改进，能够对两个节点之间的距离进行判断，一方面提升了A*搜索算法实际效率，另一方面也对开销进行充分利用[5]。

3.3以游戏Gauntlet为例分析A*搜索算法的实际应用

Gauntlet游戏是在欧洲开发，以奇幻世界为游戏背景的角色扮演类游戏。在实际游戏中有以下四个角色，分别为英雄、女神、魔法师以及精灵。在该游戏中包含了五大实体模块，分别为行动、行为、感知、代理、视觉等。在 A*搜索算法下，该游戏的AI寻路过程如下：首先将游戏启动，在游戏登陆者按键之后进入到游戏环节中，游戏背景启动。然后游戏主程序进行AI角色遍历，在角色遍历环节中，所消耗的时间比较长。因此基于这样的背景，游戏开发者为了减少游戏启动的时间，在游戏人物遍历环节中，改变帧速。一般情况下普遍采用每帧只允许一个AI人物进行寻路的模式，对整体帧速进行控制。这样的设计能够使得整体的游戏画面能够更加的流畅。当AI角色进入时，角色大脑需要对问题进行思考，找到游戏中需要考虑的问题。然后开始正式的对游戏世界进行探索，对游戏中不同的带来进行合理调用。最先需要调用的就是感知类--AIPerception：：Perceive（），然后感知类的函数将搜索信息传递到行动类中，调用行动类的表现--AIBehavior：：Behave（），在行动类的驱使下，对游戏中具体的人物行为进行控制，然后进行游戏路径探索，调用函数--AINodeManager：：DoPathFinding（），函数调用之后，系统后台自动计算出路径距离，驱动AI人物开始寻路表现。

结论：

综上所述，在本文中对人工智能寻路算法进行介绍，着重分析了A*搜索算法的实际应用。为了提升游戏中寻路效率，对当前的A*搜索算法进行改进，首先需要避免AI角色之间的碰撞，提升算法对未知区域的探索，并优化A*搜索算法对非方形区域的搜索。将改进了的A*搜索算法在实际游戏中应用，通过实际的游戏进行路径寻路分析。

参考文献：

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

[2]何文雅.3D游戏场景中虚拟角色的智能寻径应用研究[D].华中师范大学，2009.

[3]沈健.FPS游戏寻路算法的研究与实现[D].华南理工大学，2012.

[4]胡俊.游戏开发中的人工智能研究与应用[D].电子科技大学，2007.

[5]荆东星.人工神经网络在游戏寻路中的应用研究[D].长沙理工大学，2010.