遗传算法在游戏路径探索问题中的研究和应用-开题报告

（一）游戏人工智能的发展现状

近年来，游戏产业快速发展，越来越多的人成为游戏玩家，随着技术的进步，玩家对于游戏的可玩性也有了飞跃的提高，于是越来越多的公司，在游戏中采用了人工智 （Artificial Intelligence，简称AI），这也使得人工智能技术飞速的提高。在电子游戏中，玩家操控主要角色，而其他角色的行为逻辑由人工智能操纵，这些角色我们称之为NPC（Non-Player Character，非玩家控制角色）。  

（二）目前AI主要的设计思想

当前游戏中的人工智能设计普遍采用了有限状态设计（缩写为FSM）和模糊状态设计（缩写为FuSM ）两种技术。

1.有限状态设计（FSM）

FSM是包含一组状态集（states）、一个起始状态（start state）、一组输入符号集（alphabet）、一个映射输入符号和当前状态到下一状态的转换函数（transition function）的计算模型。程序员通过FSM可以很清楚地把握NPC的行为，一旦知道NPC当前的状态和输入，就可以准确地做出反应行为。

事实上游戏中的FSM非常复杂，在实际编程中要实现复杂的FSM，通常用C++写一个通用的FSM类，然后根据不同的外部数据决定NPC的不同行为。FSM所建立的是一种确定的行为系统，因此NPC的决策速度比较快，但使用FSM创建的NPC的行为太程式化了，容易让玩家觉得比较“弱智”。在现实中，当不同的人受到攻击时，所做出的反应是不一样的，有的人可能勇敢地反击，有的人会选择逃跑。为了模拟这些不确定的行为，需要一种新的方法。

2.模糊状态设计(FuSM)

FuSM的基本思想就是在FSM的基础上引入了不确定性。在FuSM中，即使知道了输入和NPC的当前状态，也无法确定下一个状态，目标状态的转换是由概率决定的。这样我们可以设计一些简单的FSM，然后通过设定不同的概率，就可以产生行为各异的NPC。NPC行为的改变只要修改概率设定就可以实现了。

3.局限性

应当说FSM和FuSM技术已经很完善，并且易于调试，如果有足够的编程时间，该技术几乎可以适用于所有的场合。但是采用FSM和FuSM开发某些新游戏时，可能会面临游戏中所固有的无数可能的选择，当角色数量或活动空间增加时，相应的逻辑常常会呈指数式增长。以路径探索为例，AI必须估算的选择之多，可能会使开发者难以应对，而且容易出错。如果编程者能够为游戏中的角色设置一个智能系统来进行控制，这个系统能够通过自身不断地学习，逐渐适应复杂的环境，这样编程者就会轻松得多。

寻路问题的算法分析

   在游戏关卡中常常会放置一些怪物（即NPC），这些怪物通常在一个区域内走来走去，这个区域被称为“巡逻区域”；一旦玩家的角色进入怪物的“视野”，怪物就会发现玩家角色，并主动向其所在的位置移动，这个区域称为“警戒区域”；当玩家角色和怪物更加靠近时，会进入到怪物的“攻击区域”，这时怪物会对玩

家角色进行伤害。在某些RPG（Real-Time StrategyGame，即时战略游戏）中，NPC在不利的情况下还会选择主动逃跑。如何模拟这些行为逻辑，便是对当前算法的需要。

  目前比较常用的寻路算法有随机寻路算法、跟踪算法以及闪避算法，这3个算法可以模拟NPC的一些简单的寻路、跟踪和闪避行为，在小游戏中会经常用到。但是，在较大型的游戏中使用这样简单的算法就会大大影响游戏效果了。因此，大型游戏的人工智能算法都较复杂。

 改进优化后的A*算法可以很好地胜任游戏中的路径搜索。由于A*算法是按照寻找最低耗费的路径来设计，A*会找到最短，最直接的路径，当算法具体实现后，得到的这条路径也是唯一的路径，于是，当游戏重来时，玩家会发现NPC总是只有一条路可走，这样就显得不够真实。玩家希望NPC有足够的智力能找到一条适合的路径，也要有不同的选择，如果能够为游戏中的角色设置一个智能系统来进行控制，这个系统能通过自身不断地学习，逐渐适应复杂的环境，自己找到一条“较好”的路径，并且有较高的效率，就会使游戏角色的行为逻辑看上去更真实一些。于是游戏程序员开始尝试使用一些新的方法，如遗传算法。

二、^范文提纲

1.遗传算法

1.1什么是遗传算法

1.2遗传算法的原理

2.遗传算法解决游戏路径探索问题的实例  

2.1迷宫寻路问题

2.2遗传算法的一般步骤及关键代码

2.2.1对待解决问题进行编码；

2.2.2随机初始化群体；

2.2.3计算群体上每个个体的适应度值：

2.2.4评估适度，对当前群体中每个个体计算其适应度：

2.2.5按预定的选择算子产生后代；

2.2.6对后代进行交叉操作；

2.2.7对后代进行变异操作；

2.2.8判断是否满足停止条件，满足转第3步，否则进入9；

2.2.9输出种群中适应度值最优的个体。

遗传算法的时间复杂度

遗传算法的优缺点及发展方向

总结

三、参考文献

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

[2]王小平，曹立明.遗传算法－理论、应用与软件实现[M].西安交通大学出版社,2002. 

[3]张文修.遗传算法的数学基础[M].西安交通大学出版社，2003.5

[4]李敏强，寇纪淞，林丹，李书全.遗传算法的基本理论与应用[M].科学出版社，2002

[5]金朝红等.一种基于自适应遗传算法的神经网络学习算法[J],微型机信息,2005.21(10-1)

[6]张嘉彬.游戏规则设计与数值设定[M],北京汇众益智.2005 

[7]王清,马广富，弥曼.一种基于遗传算法的神经网络控制方法研究[J].系统仿真学报,2006,(4)

[8]倪明田,吴良芝.计算机图形学[M].北京大学出版社，1999.11

[9]周明，孙东栋.遗传算法原理及应用[M].国防工业出版社，2002.05

[10]张铃,张钹.统计遗传算法[J].软件学报,1997,(5)

[11]云庆夏.遗传算法和遗传规划:一种搜索寻优技术[M].冶金工业出版社，1997