游戏中的智能路径搜索算法及其应用

发布时间：2019-10-18 09:05

【摘要】：游戏地图路径搜索是指在尽可能短的时间内,为游戏中的虚拟角色计算出一条从当前位置到目标位置的最短无碰撞路径,被称为游戏人工智能的一块神圣基石。游戏中的智能路径搜索算法主要包括A*算法与遗传算法两种,但两种算法在该领域应用中的设计与实现均有不足,造成算法运行速度不够快,影响游戏的实时性,且搜索到最短路径的概率不够高,影响游戏NPC的智能性。有鉴于此,本文对它们进行了适当改进与重新设计。因为A*算法已经非常成熟,且学术界又有多位学者对其进行了改进研究,故本只提出了一种简单A*算法的启发式的改进方案。改进后的启发式可根据地图中障碍物的多少调节简单A*算法的搜索行为,使之兼顾搜索成功率与运行时间。遗传算法相对A*算法较不成熟,本文将其作为研究重点,对其进行的改进与重新设计如下:1)设计了一种以地图图块坐标为基因的染色体编码方式,以方便进行平滑路径等后续优化操作;2)设计了一种不产生断路与环路的染色体生成方式,提高了初代群体的整体质量;3)提出了一种即可保留优胜个体又可增加种群的多样性的变异算子,减小了算法陷入局部最优解的概率;4)提出了一种基于启发式深度优先搜索的变异操作,又将交叉操作的执行顺序调整于其后,加快了种群的进化速度;5)提出了一种以指定迭代次数为算法终止条件时,兼顾搜索能力与计算速度的最佳种群规模的选取方案。最后通过实验分析了上述改进的有效性,并与传统遗传算法及其他学者的改进算法进行了对比实验。
【图文】：

实现路径搜索是实现游戏ＮＰＣ智能化的首要任务，被称为游戏人工智能的一逡逑块“神圣基石”。所谓游戏ＮＰＣ路径规划，就是在尽可能短的时间内，为游戏ＮＰＣ逡逑计算出一条从起点到终点的无碰撞的最短路径（图１．１）。现如今依赖地图的游戏逡逑越来越多，比如最近非常受欢迎的魔兽争霸、英雄联盟、王者荣耀、皇室战争等逡逑游戏，就存在大量的游戏ＮＰＣ，需要为他们计算出一条这样的路径。逡逑１逡逑Ｉ逡逑

２．１二维游戏地图逡逑二维游戏地图是由多个图层叠加而成，而图层又由多个图块拼接而成，看起逡逑来与栅格化的移动机器人工作空间类似，如图２．１所示。逡逑：ＣｒａｔｘＳ＾ｐ．邋ｔ？ｓ邋Ｘ邋！■逦窈邋Ｓｔ；逡逑灥！逡逑１１１＇逡逑图２．１邋２Ｄ游戏地图逡逑那么何为图层，何为图块呢？下面就对二维游戏地图中的这两个重要概念作逡逑一下简要说明：逡逑（１）图层逡逑与Ｐｈｏｔｏｓｈｏｐ中的ｐｓｄ分成文件类似，游戏地图也是分层的，最上层是对象逡逑层，也就是与玩家角色交互的层。中间可以是地图层，用来表示地图的各种地形。逡逑而最下层往往作为碰撞检测层，用于进行碰撞检测，并对玩家隐藏。这样就可以逡逑使碰撞检测和地图图块所代表的具体地形分开，，方便游戏开发。逡逑７逡逑
【学位授予单位】：昆明理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18

【参考文献】

相关期刊论文 前10条

1 卢月品;赵阳;孟跃强;刘佳;;基于改进遗传算法的狭窄空间路径规划[J];计算机应用研究;2015年02期

2 刘大瑞;冯镍;;基于多目标遗传算法的游戏路径规划研究[J];软件导刊;2014年01期

3 黎忠文;覃志东;王全宇;倪仲余;;游戏引擎最短路径搜索优化遗传算法设计[J];计算机应用研究;2014年01期

4 马超;;遗传算法和Dijkstra算法在动态权值系统中的比较[J];计算机技术与发展;2012年09期

5 沈畅;乐天;;遗传算法中的变异算子的述评[J];科技视界;2012年23期

6 雷文杰;;基于遗传算法的游戏地图寻径问题[J];电脑知识与技术;2012年16期

7 肖晓明;陈志兴;高平安;;动态确定基因数的遗传算法路径规划[J];计算机应用研究;2009年07期

8 康晓军;王茂才;;基于遗传算法的最短路径问题求解[J];计算机工程与应用;2008年23期

9 李擎;冯金玲;柳延领;周洲;尹怡欣;;自适应遗传算法在移动机器人路径规划中的应用[J];北京科技大学学报;2008年03期

10 付朝晖;丁梦;喻昕;;游戏编程中的寻路算法研究[J];湖南工业大学学报;2007年04期

相关硕士学位论文 前9条

1 唐崇;基于加速A*算法的游戏网格地图寻径研究[D];江西师范大学;2015年

2 陈汉伟;基于人工智能的虚拟角色行为决策能力的研究[D];浙江理工大学;2015年

3 周振华;游戏场景中分层寻路算法及地图复杂性度量研究[D];河北大学;2014年

4 韩玮;游戏地图寻路及其真实性研究[D];西南大学;2013年

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

6 秦思涵;Virtools三维游戏最优路径的遗传算法研究[D];四川师范大学;2012年

7 杨科选;人工智能寻路算法及其在游戏中的应用研究[D];中南大学;2009年

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

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

本文编号：2551011