游戏开发中智能路径搜索算法的研究

摘要：在游戏软件中，人工智能是一个重要而又复杂的模块，而寻路算法是人工智能运用于电子游戏中的最基本问题之一。针对游戏中路径搜索的特点，在对一般搜索算法、常见搜索算法和启发式搜索技术进行详细地分析与研究的基础之上，结合实际应用情况，对A*算法进行了一些优化与改进。

关键词：游戏开发；人工智能；A*算法；路径搜索

中图分类号：TP18文献标识码：A文章编号：1009-3044(2008)36-2739-03

Research on Algorithm of AI Pathfinding in Game Development

PAN Jian-sheng

(School of Computer Science & Technology, Nantong University, Nantong 226001, China)

Abstract: In game software,Artificial Intelligence is an important and complicated module.Shortest-Path Search is one of the most basic questions in which artificial intelligence applied to electronic games.The characteristics of the search path in the general search algorithm,commom heuristic search algorithm and technology on the basis of a detailed analysis and study,the combination of practical application,for a number of A* algorithm optimization and improvement.

Key words: game development; artificial intelligence; A* algorithm; pathfinding

1 引言

人工智能（Artificial Inteligence）在电子游戏中运用已经有很多年了，并且在发展中变得越来越完善。如果在游戏中不加入完善的游戏AI控制系统，那么游戏玩家就认为该游戏缺乏可玩性。一个在市场上畅销的成功游戏，必须既要有华丽的画面视觉效果和悦耳的听觉感受，又要有高超逼真的人工智能控制系统。游戏开发者把AI应用在游戏中，就会使广大玩家感到他们所面对的由电脑AI系统控制的敌人（即NPC）跟现实中的敌人一样拥有人类智能，让玩家留下如临实境的体验。在游戏术语中，AI是用来描述游戏角色的行为表现的。如在角色扮演类游戏（RPG）中去模拟人作为某个角色的行为，在即时战略游戏（RTS）中进行路径搜索算法，包括简单的AI找路和群体AI找路，还有策略AI，战术AI，建筑布置，危险估计，地形分析等多方面。一般游戏AI系统都是从搭建最基本的寻路系统开始，一步步修改和完善后而成的。所以本文重点阐述了游戏AI开发中最基本最核心的人工智能寻路算法。

2 主要路径搜索算法

最短路径搜索，就是根据游戏地图中的地形和障碍，寻找一条从起点到终点的最近、最直接的路径的算法。搜索通常有盲目搜索（也称非启发式搜索）和启发式搜索两种不同的方法，盲目搜索的特点是不考虑给定问题所具有的特定知识，系统根据事先确定好的某种固定排序，依次调用规则或随机调用规则，这种搜索具有盲目性，效率不高，一般统称为无信息引导的搜索策略；启发式搜索的特点是在搜索中加入了与问题有关的启发性信息，这些信息可以指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。它是动态地确定规则的排序，并优先调用较合适的规则使用。

2.1 非启发式的Dijkstra算法

Dijkstra算法是最基本的非启发式最短路径搜索，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解。

路径上的开始顶点(出发点)称为源点，路径上的最后一个顶点称为终点，并假定讨论的权值不能为负数。单源点到其他顶点的最短路径是指：给定一个出发点(单源点)和一个有向网G=(V，E)，求出源点到其它各顶点之间的最短路径。迪杰斯特拉算法的基本思想是:设置并逐步扩充一个集合S，存放已求出其最短路径的顶点，则尚未确定最短路径的顶点集合是V-S，其中V为网中所有顶点集合。按最短路径长度递增的顺序逐个以V-S中的顶点加到S中，直到S中包含全部顶点，而V-S为空。具体做法是：设源点为Vl，则S中只包含顶点Vl，令W=V-S，则W中包含除Vl外图中所有顶点，Vl对应的距离值为0，W中顶点对应的距离值是这样规定的：若图中有弧则Vj顶点的距离为此弧权值，否则为∞(一个很大的数)，然后每次从W中的顶点中选一个其距离值为最小的顶点Vm加入到S中，每往S中加入一个顶点Vm，就要对W中的各个顶点的距离值进行一次修改。若加进Vm做中间顶点，使+的值小于值，则用+代替原来Vj的距离，修改后再在W中选距离值最小的顶点加入到S中，如此进行下去，直到S中包含了图中所有顶点为止。

在Dijkstra算法中，求一条最短路径所花费的时间：从V-S中选取具有最小距离的顶点Vk花费时间O(n)；修改V-S中顶点的距离花费时间O(n)；输出最短路径花费时间O(n)。因此求出n-1条最短路径的时间复杂度为O(n2)。顶点对之间的最短路径是指：对于给定的有向网G=(V,E)，要对G中任意一对顶点有序对V、W(V≠W)，找出V到W的最短距离和W到V的最短距离。解决此问题的一个有效方法是:轮流以每一个顶点为源点，重复执行Dijkstra算法n次，即可求得每一对顶点之间的最短路径，总的时间复杂度为O(n3)。但由于Dijkstra算法遍历计算的节点很多，所以效率较低。非启发式路径搜索实际上是一种穷举法，通过固定顺序依次搜索寻路者周围的路点，直到找到目的路点为止。搜索点在计算机模拟图象上呈现的是一个不断扩大的矩形。如此穷举直接导致搜索速度过慢且不符合人类一般的寻路逻辑。

2.2 启发式的A*算法

启发式搜索的核心是估价函数f(n)，所谓的估价函数就是用来估计节点重要性的函数。函数f(n)被定义为从初始节点A出发，约束经过节点n到达目标节点B的所有路径中最小路径代价的估计值。即f(n)的值由两部分组成，一部分是从起始节点A到该结点的代价，用函数g(n)表示。一般而言，g(n)的值计算是让父结点的该值和从父结点到本身的代价和相加而得，所以它的值是能够确定的；另外一部分则是从该结点到目标结点的估计代价，用函数h(n)表示。对h(n)的值一般需要根据问题自身的特性来确定，它体现的是自身的启发性信息，因此也称为启发函数。对一般的地图寻路问题，h(n)的值通过水平和垂直位置的差距结合而算出的效果比较好。例如:设B(dx，dy)是终点，n(sx，sy)是当前点，则:h(n)=|dx-sx|+|dy-sy|那么函数f(n)则可以表示为:f(n)=g(n)+h(n)

A*算法是一种典型的启发式搜索算法，它除了利用上述的启发函数来对搜索过程中的每一个节点进行评估，另外它还保持着两个表:Open表和Close表.Open表由未考察的结点组成，而Close表由已考察的结点组成。当算法已经检查过与某个结点相连的所有子结点，计算出这些子结点的g(n)，h(n)和f(n)值，并把它们放入Open表以待考察，那么该点就是已考察的结点，通常都是放在 Close表里面。因为在A*算法计算的过程中，会经常从Open表或者Close表中取出一个最小值的元素，所以这两个表所用的数据结构通常要便于排序，常见的是使用堆数据结构，该结构每次都能够把最小值的元素放到最上面。A*算法就是利用估价函数对地图中的每个结点进行评估，并结合Open表和Close表的操作来完成路径的搜索。假设起始结点为A，终止结点为B，下面代码是A*算法实现过程的伪代码描述，其中n是每次被考察的结点，临时结点m代表n的每个有效子结点，所谓有效子结点就是指在地图中能够到达的结点。当n等于B时那么该次搜索也就完成了。

A*算法伪代码:

计算A的g，h和f值，并把A放入Open表中；

wh1le(Open表非空)

{

取Open表里f值最小的元素n，将其放入Close表里；

if(n等于B)

搜索完成，返回；

for(n的每个有效子结点m)

{

计算m的g，h和f值；

if(m未被访问过)//说明不在Open表和Close表里

将其放入Open表里；

e1seif(m在Open表里)

{if(m该次计算的f值比上次更小)

重新设置m的g，h和f值为该次计算的值；

}}}

根据中间的搜索标记求出路径；

A* 算法具备很多优点。首先，如果起点和终点之间存在有效路径，A* 就一定能够找到。其次，只要h ( n)是可纳的，它就一定能找到一条最短路径。第三，A* 算法是启发式搜索算法中搜索状态最少的一种算法，它使启发式函数得到了最有效的应用。A*算法是一个利用某个估价函数可以找出最短路径的最好优先算法。我们选取的估价函数越好，则路径搜索时排除的节点就越多，这个A*算法就越好越有效率。但在实际游戏开发中由于实时性的问题，估价函数中的启发信息越多，它的计算量就越大，耗费的时间就越多。所以又要适当的减少h(n)启发信息，即减小约束条件，可是算法的准确性就差了，这就是个全局平衡取舍的问题了。

通过该算法伪代码可以看出，一次搜索任务是通过两个循环计算来完成的。另外当一次路径搜索正在计算的过程中，是不能够被外界中断的。但是如果当搜索规模很大时，则通常一次计算会耗费大量的时间，而此时主程序的其它模块就不得不等待该次计算的完成。这种同步寻路算法所导致的结果在某些需要实时响应的系统中可能会是致命的。对于游戏的特殊要求，A* 还有几个不得不改进的缺点：标准A* 搜索比较费时，当多个单位同时应用算法进行寻径时，其耗时会令游戏玩家无法忍受；直接利用算法得到的路径虽然是最短路径，但往往曲曲折折，过于机械化。因此，还要对它进行平滑处理；除此以外，游戏地图中的特殊地形、目标节点可达不可达的判断、地图中障碍物位置的动态改变，以及当某一狭窄路径交通堵塞时，如何改变寻路策略，都是需要考虑的问题。针对这些问题，本文下面将对该算法进行优化和改进。

3 A*算法的改进、优化策略

3.1 避免AI角色之间的碰撞

在前述的A*算法描述中，完全忽略了其他AI角色对寻路的干扰。这种的情况下AI寻路者之间表现出来的是可以相互穿越。这种现象在大多数的实际游戏中是不允许的。如果希望AI角色之间能互相绕开，则对于相互靠近的运动着的AI角色，可以通过惩罚它们各自路径上的节点，来鼓励这些AI角色找到各自不同的路径.如果选择了把其他正在移动并且远离当前寻路者的那些AI角色也考虑在内，将需要实现一种方法及时预测在何时何地碰撞可能会发生，以便恰当的避免，否则极有可能得到一条怪异的路径，单位突然转弯试图避免和一个已经不存在的单位发生碰撞。当然我们也需要写一段碰撞检测的代码，因为无论计算的时候路径有多完美，它也会因时间而改变。当碰撞发生时，一个AI寻路者必须寻找一条新路径，或者，如果将要碰撞到的另一个AI角色正在移动，则原AI寻路者等待那个AI角色离开后再继续沿当前路径前进。

3.2 各种地形的不同损耗

在前述的A*算法描述中，地形分为可通过的和不可通过的两种。但在实际游戏设计中，我们会遇到一些不同种类的可通过的地形。他们的移动耗费各异如沼泽，山坡，沙漠，楼梯等等，这些都是可通过但比平坦的自然道路移动耗费更高的地形。同样我们也需要比自然道路移动耗费更低的地形，如平滑的下坡道等等。对这个问题，我们只要在计算任何地形G值的时候增加或减少地形损耗就可以了。由于A*搜索算法已经按照寻找最低耗费的路径来设计，所以很容易处理这种情况。

3.3 平滑搜索路径

尽管A*算法提供了最短、最低代价的路径，但这条路径常常看起来AI角色走起来显得比较突兀，不是很平滑。有两种方法可以解决这个问题。当计算路径的时候可以对改变方向的格子施加不利影响，即对G值增加额外的数值。也可换另一种方法，可以在路径计算完之后沿着它跑一遍，找出那些会让路径看起来更平滑的相邻格替换原先路径上的格子。

3.4 预计算最短路径

利用Dijkstra算法计算最短路径树，将其存储在一个最短路径查找表中。在游戏运行时，不再执行路径查找算法，而是查表。

3.5 分层次寻路

利用不同细致级别的搜索空间图，首先计算一个较粗糙的路径，在到达具体的区域时再使用更细致的搜索空间（可以是该区域的局部搜索空间）来计算更精确的路径。

4 结束语

A*算法作为一种计算最短路径的算法，它结合了启发式方法和形式化方法，为许多即时战略游戏所用到. 通过对A*算法的优化改进后，A* 算法可以很好地胜任游戏中的路径搜索，提高了原算法的执行效率，并使路径的选择更加人性化.但在减少搜索时间的同时也增加了空间的消耗.随着A *算法在游戏的设计开发领域广泛应用，电脑游戏中人工智能A *的算法会发展得越来越完善。

参考文献：

[1] Rabin S.人工智能游戏编程真言[M].庄越挺,吴飞,译.北京:清华大学出版社,2005.

[2] 严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,1997.

[3] 何国辉,陈家琪.游戏开发中智能路径搜索的算法研究[J].计算机工程与设计,2006,27(13).

[4] 朱福喜,汤怡群,傅建明.人工智能原理[M].武汉:武汉大学出版社,2002.

[5] 陈刚,付少锋,周利华.A*算法在游戏地图寻径中的几种改进策略研究[J].科学技术与工程,2007,7(15).