游戏编程中的寻路算法研究
游戏编程中的寻路算法研究
付朝晖1，丁梦2
（1.长沙民政学院，湖南 长沙 410004；2.湖南工业大学，湖南 株洲 410004）
摘 要：本文探讨了当前人工智能（AI）在电子游戏行业中的应用状况和游戏AI设计过程中的主要思路，阐述了游戏AI的传统编程技术及其局限性，针对传统AI技术的存在的问题提出了如何运用遗传算法改进游戏的AI设计，并举例说明了用遗传算法实现路径探索的方法。
关键词：电子游戏；人工智能；有限状态设计；模糊状态设计；遗传算法
AI Techniques and Its Application in Game Programming
Abstract: This essay inquire into the use condition of artificial intelligence in electronic games industry and the main trains of thoughts about the processes of designing AI (artificial intelligence) games, expound the traditional skills of writing programs and the limits of AI games, focusing on the problems exists in the traditional AI skills , bring out the methods about how to wield heredity algorithm to improve the design of AI games ,and set examples to demonstrate the methods how the genetic algorithm realize the methods of route explorations.
Keywords: electronic games; artificial intelligence; Finite State Machine ; Fuzzy State Machine; genetic algorithm
1 引言
游戏中的人工智能（Artificial Intelligence，简称AI），是指用来控制游戏中各种活动对象行为的逻辑。大部分游戏，特别是角色扮演类游戏都需要人工智能，在游戏中玩家是主要人物，而游戏中的其他人物由人工智能操纵。游戏开发领域中的人工智能设计越来越被游戏开发者和玩家重视，因为它能给玩家提供更大的挑战性，从而增加游戏的可玩性，一款游戏的生命力正在于游戏的可玩性。近几年游戏AI发展很快，有统计显示游戏中AI的CPU占用率已经从2000年的15％提高到2005年的35％[5]。所以人工智能在这个领域非常重要。路径探索问题是游戏人工智能研究的一个重要方面，快速，准确的路径探索是游戏开发者追求的目标。计算出让玩家或者角色从游戏地图中的A点到达B点的一条路径，是游戏人工智能的主要研究方向之一。
2 游戏AI设计思路
游戏的可玩性很大程度上与游戏的平衡性相关，玩家的对手通常就是计算机控制的角色，这些角色设计得太容易对付或者太难对付，都容易使玩家失去兴趣。
由于游戏的AI本身与游戏的主体在一起，玩家和游戏AI之间天生处于不平等地位。例如在RTS（Real-Time Strategy Game，即时战略游戏）或FPS（First Person Shooting Game，第一人称射击游戏）中，AI总是占有优势，对手（计算机）可以很容易确定玩家角色在地图中的位置和状况，而玩家却不能完全掌握对手的情况。如果要求游戏AI跟人类一样聪明，完全依靠它的智慧战胜玩家，就会使得AI变得极其复杂，无论是技术上还是商业上都会有很大的风险。假如能够巧妙地利用玩家和游戏AI的不对称地位，通过提高NPC（Non-Player Character，非玩家控制角色）的能力，以弥补AI的不足是最常用的解决办法。程序员通过给NPC提供更多的信息，会使“他们”显得更聪明。另一种办法更简单，就是扩展NPC的能力，扩展NPC的能力相比实现NPC的复杂人工智能要简单很多。例如游戏一开始就给NPC更多的资源，同样可以弥补游戏AI的不足，以保持游戏的平衡性。
电子游戏作为一种商品，在AI上投入太多意味着商业风险增大。因此在游戏开发过程中，游戏业AI设计的思路上不同于学术研究，侧重于实际效果。游戏业往往使用成熟的技术，用最简单的方法，占用最少的资源，给玩家制造假象，让玩家觉得游戏的AI水平高超。
3 有限状态设计和模糊状态设计
当前游戏中的人工智能设计普遍采用了有限状态设计（Finite State Machine ,缩写为FSM）和模糊状态设计（Fuzzy State Machine，缩写为FuSM ）两种技术。
FSM是包含一组状态集（states）、一个起始状态（start state）、一组输入符号集（alphabet）、一个映射输入符号和当前状态到下一状态的转换函数（transition function）的计算模型。程序员通过FSM可以很清楚地把握NPC的行为，一旦知道NPC当前的状态和输入，就可以准确地做出反应行为。
事实上游戏中的FSM非常复杂，在实际编程中要实现复杂的FSM，通常用C++写一个通用的FSM类，然后根据不同的外部数据决定NPC的不同行为。FSM所建立的是一种确定的行为系统，因此NPC的决策速度比较快，但使用FSM创建的NPC的行为太程式化了，容易让玩家觉得比较“弱智”。在现实中，当不同的人受到攻击时，所做出的反应是不一样的，有的人可能勇敢地反击，有的人会选择逃跑。为了模拟这些不确定的行为，需要一种新的方法。
FuSM的基本思想就是在FSM的基础上引入了不确定性。在FuSM中，即使知道了输入和NPC的当前状态，也无法确定下一个状态，目标状态的转换是由概率决定的。这样我们可以设计一些简单的FSM，然后通过设定不同的概率，就可以产生行为各异的NPC。NPC行为的改变只要修改概率设定就可以实现了。
应当说FSM和FuSM技术已经很完善，并且易于调试，如果有足够的编程时间，该技术几乎可以适用于所有的场合。但是采用FSM和FuSM开发某些新游戏时，可能会面临游戏中所固有的无数可能的选择，当角色数量或活动空间增加时，相应的逻辑常常会呈指数式增长。以路径探索为例，AI必须估算的选择之多，可能会使开发者难以应对，而且容易出错。如果编程者能够为游戏中的角色设置一个智能系统来进行控制，这个系统能够通过自身不断地学习，逐渐适应复杂的环境，这样编程者就会轻松得多。
4 遗传算法在游戏AI设计中的应用
4.1 游戏中的路径探索问题
路径探索问题是游戏人工智能研究的一个重要方面，快速，准确的路径探索是游戏开发者追求的目标。计算出让玩家或者角色从游戏地图中的A点到达B点的一条路径，是一件困难的事情。
A*寻路算法一直以来被游戏界认为是最好的寻路算法之一，因而被大量应用。由于A*算法是按照寻找最低耗费的路径来设计，A*会找到最短，最直接的路径。但是对于游戏，寻路太好有时会显得不真实。游戏程序员开始尝试使用一些新的方法，如遗传算法、人工神经网络计算等技术被引入到游戏AI设计中来。下面以迷宫探索为例，探讨一下如何运用遗传算法去解决游戏场景中的路径探索问题。
4.2 路径探索的遗传算法实现
遗传算法是模拟生物进化的步骤，将繁殖、杂交、变异、竞争和选择等概念引入到算法中，通过维持一组可行解，并通过对可行解的重新组合，改进可行解在多维空间内的移动轨迹或趋向，最终走向最优解。它克服了传统优化方法容易陷入局部极值的缺点，是一种全局优化算法。
遗传算法的步骤如下：（1）对待解决问题进行编码；（2）随机初始化群体X(0)=(x1, x2, … xn)；（3）对当前群体X(t)中每个个体xi计算其适应度F(xi)，适应度表示了该个体的性能好坏；（4）从当前群体选出2个成员，选出的概率正比于染色体的适应性，适应分愈高，被选中的概率也愈大。（5）按照预先设定的杂交率（crossover rate），从每个选中染色体的一个随机确定的点上进行杂交。（6）按照预定的变异率（mutation rate），通过对被选染色体的位的循环，把相应的位实行翻转。（7）如果不满足终止条件继续(3)。
在这个路径探索例子中首先创建一个地图，它有一个入口，还有一个出口，地图中放置着一些障碍物，在入口处放置一个NPC。地图可以用一个二维整数数组Map[][]来表示，其中用0来表示可以通行的空间，1代表墙壁或障碍物，8为入口，9为出口。接下来要使它能找到出口，并避免与所有障碍物相碰撞。这种地图设计方法被封装在一个称为CNpcMap的类中，只需要以常量的形式来保存地图数组以及起点和终点就行了。除了存储地图，这个CNpcMap类中需要一个数组NpcPath[ ][ ]，用来记录NPC在地图中行走的路径。可以用一个由1（UP）、2（DOWN）、3（LEFT）、4（RIGHT）所组成的动作方向序列来检测NPC走了多远，并计算出NPC能到达的最远位置，然后返回一个适应性分数，它正比于NPC最终位置离出口的距离。NPC所到达的位置与出口越近，给NPC的适应性分数就越高。如果NPC实际已到达了出口，将得到满分１，这时循环就会自动结束。这时得到一个解。
根据遗传算法的步骤，第一步为染色体编码，染色体把NPC的每一个动作方向编入代码中。NPC有上、下、左、右四个动作方向，编码后的染色体是代表这4个动作方向的一个数组DirAction[ ]。首先通过程序生成由1234组成的整型随机数数组，就能根据它得到NPC行动时的方向。例如染色体{3,2,1,2,4,3,2,1……}。
第二步要做的就是将NPC置于地图得入口，然后指示NPC根据DirAction[ ]数组中所列的动作方向一步步地走。如果有一个方向使NPC碰到了墙壁或障碍物，则忽略该指令并继续按下一条指令去走就行了。这样不断走下去，直到用完所有方向或NPC到达出口为止。程序产生的大量随机染色体中，某些个体就可能为NPC指出一条到达出口的路径（问题的一个解）。遗传算法以整型随机数数组作为初始群体，测试它们每一个能让NPC走到离出口有多么近，然后让其中最好的那些作为种子产生后代，期望它们的“子孙”中能有走得离出口更近一点。这样继续下去，直到找出一个解。因此需要定义一种结构，其中包含一个染色体，以及一个与该染色体相联系的适应性分数。这个结构的定义如下：
struct Chromosome
{
int DirAction[ ];
double FitnessScore;
Chromosome ():FitnessScore(0){}
Chromosome( int num):FitnessScore(0)
{
for (int i=0; i
{
//创造随机字符数组
}
}
}
在创建Chromosome对象时把一个整型数作为参数传递给构造函数，则它就会自动创建一个以此整数为长度的随机数字数组，并将其适应性分数初始化为零，完成对基因组的设置。
第三步，也是遗传算法类中最为关键的一步，就是测试染色体群中每一个体的适应性分数，数。函数CalFitSco()根据代表上、下、左、右4个方向的数组DirAction[ ]，计算出NPC离开出口的最终距离，返回一个适应性分数。计算适应性分数程序如下：
int Dist_X = abs(Npc_X – End_X);
int Dist_Y = abs(Npc_Y – End_Y);
return 1/(Dist_X+Dist_Y+1); //加1避免分子为0
这里的Dist_X 和Dist_Y就是NPC所在的位置相对于地图出口的水平和垂直偏离值。如果NPC到达出口，则Dist_X + Dist_Y = 0。CalFitSco()保持对每一代中适应性分数最高的基因组以及与所有基因组相关的适应性分数的跟踪。每当一个新的基因组群被创建出来时，需要将它们保存下来。
第四步，从当前群体选出2个个体以备杂交。赌轮选择是常用的一种方法，被选中的几率和它们的适应性分数成比例，适应性分数愈高的染色体，被选中的概率也愈大。但这并不说明适应性分数最高的成员一定能选入下一代，它只是有最大的概率被选中。
while ( Parents< V_Num)
{
//用赌轮法选择
Chromosome Parent1 = RSele();
Chromosome Parent2 = RSele();
在每次迭代过程中，需要选择两个染色体作为“后代”染色体的“父辈”，一个染色体的适应性分数越高，其被赌轮方法选择作为“父辈”的概率就越大。
//第五步杂交
Chromosome Cbaby1, Cbaby2;
Hybridize (Parent1.DirAction,Parent2.DirAction,Cbaby1.DirAction,Cbaby2.DirAction);
创建两个新的染色体，它们与所选的父辈一起传递给杂交函数Hybridize()。这一函数执行了杂交，并把新的染色体的二进制位串存放到Cbaby1和Cbaby2中。
//第六步变异
Differentiation(Cbaby1.DirAction);
Differentiation(Cbaby2.DirAction);
……
}
以上这两步实现对染色体后代杂交变异，完成后把两个后代染色体加入新的群体，这样就完成了一次迭代过程。该过程不断重复，原有的那个群体由新生一代所组成的群体来代替，直到染色体收敛到了一个解。程序运行中可能不是总能找到一条通往出口的路径，NPC有时会在一个角落不确定地走来走去，原因是群体太快地收敛到一个特殊类型的染色体，由于群体中的成员变得相似，Hybridize算子的优势这时实际上已经不能发挥作用，只有很少的变异操作在起作用。但变异率设置得很低，当染色体类型的差异消失后，仅仅依靠变异本身已不能去发现一个解。选择适当的参数可以改善这个问题，但是目前还没有一个有效的规则，用户只能通过自己的实践选取合适的值。
三、遗传算法的优缺点
与其他优化算法相比 ,遗传算法具有如下优点 :
(1). 将搜索过程作用在编码后的字符串上 ,不直接作用在优化问题的具体变量上 ,在搜索中用到的是随机的变换规则 ,而不是确定的规则。它在搜索时采用启发式的搜索 ,而不是盲目的穷举 ,因而具有更高所搜索效率。
(2). 现行的大多数优化算法都是基于线性、凸性、可微性等要求 ,而遗传算法只需要适合度信息 ,不需要导数等其他辅助信息 ,对问题的依赖性较小 ,因而具有高度的非线性 ,适用范围更广。此外还可以写出一个通用算法 ,以求解许多不同的优化问题。
(3). 遗传算法从一组初始点开始搜索 ,而不是从某一个单一的初始点开始搜索。而且给出的是一组优化解 ,而不是一个优化解 ,这样可以给设计者更大的选择余地。它能在解空间内充分搜索 ,具有全局优化能力。
(4). 遗传算法具有很强的易修改性。即使对原问题进行很小的改动 ( 比如目标函数的改进 ),现行的大多数算法就有可能完全不能使用 ,而遗传算法则只需作很小的修改就完全可以适应新的问题。
(5). 遗传算法具有很强的可并行性 ,可通过并行计算来提高计算速度 ,因而更适用于大规模复杂问题的优化。
正是基于以上优点 ,遗传算法对优化工作者来说充满了吸引力。
但是由于遗传算法是一种较新的算法 ,在实际中的运用中也还有许多地方有待进一步地深入和改进 ,主要集中在以下几个方面 :
(1). 遗传算法的理论研究比较滞后。由于遗传算法本身也是一种仿生的思想 ,尽管实践效果很好 ,但理论证明比较困难。而且这种算法提出来的时间还不是很长 ,因此其理论和实践的研究几乎是平行进行的。
(2). GA 算法本身的参数还缺乏定量的标准 ,目前采用的都是经验数值 ,而且不同的编码、不同的遗传技术都会影响到遗传参数的选取 ,因而会影响到算法的通用性。
(3). GA 对处理约束化问题还缺乏有效的手段 ,传统的罚函数法中对惩罚因子的选取还是一个比较困难的技术问题。
5 小结：
在过去的10年里，游戏的AI发展很快，各种AI技术被引入到游戏中，如遗传算法、人工神经网络计算、地形分析技术、团队寻径算法、A*算法等，这些技术出色地解决了游戏中一些基本问题。我们有理由相信未来游戏的AI将会给玩家带来更多的惊喜。
【参考文献】
[1] 何国辉，陈家琪.游戏开发中智能路径搜索的算法研究[J].计算机工程与设计,2006,27(13):2334-2337
[2] 王小平，曹立明.遗传算法－理论、应用与软件实现[M].西安交通大学出版社,2002.
[3] 阎平凡，张长水 人工神经网络与模拟进化计算[M],清华大学出版社.2000.
[4] 金朝红等.一种基于自适应遗传算法的神经网络学习算法[J],微型机信息,2005.21(10-1):49-51
[5] 张嘉彬.游戏规则设计与数值设定[M],北京汇众益智.2005
[6] 王清，马广富，弥曼.一种基于遗传算法的神经网络控制方法研究[J].系统仿真学报,2006,18(4):1070-1077
作者简介：
付朝晖(1972－)，男，湖南常德人，讲师，硕士研究生，主要研究方向：计算机网络技术、游戏软件；
游戏编程中的寻路算法研究.doc
