游戏AI中的路径搜索算法的研究与应用

发布时间：2017-05-04 14:02

  本文关键词：游戏AI中的路径搜索算法的研究与应用，由笔耕文化传播整理发布。

【摘要】：路径搜索是游戏AI(人工智能)的重要组成部分,在大型的商业游戏中,路径搜索经常受限于存储空间以及CPU处理能力,且路径搜索的性能直接决定用户对游戏的满意程度。论文通过对传统路径搜索算法的深入研究与分析,提出了几种改进与优化策略,并通过实验对比,分析了算法改进的效果。论文首先探讨了课题的研究背景与意义,分析了国内外研究现状。路径搜索是影响游戏整体效果的因素之一,因为路径搜索赋予NPC感知周围环境的能力,在一定程度上标志着NPC智能水平的高低并直接影响游戏角色的行为。接着,论文对比研究了传统的各种路径搜索算法,描述了搜索空间表示方法。传统的Dijkstra算法、A*算法时间复杂度高,难以满足大规模地图中路径搜索的要求;HPA*等分层寻路算法对地图进行均匀分区,未考虑地图中地形的分布信息,适应能力差。针对以上问题,论文在三方面进行了改进与优化:(1)提出了一种对A*算法Open表优化的方法。利用Multiset关联容器作为A*算法Open表的数据结构。深入分析了顺序容器和关联容器的性质,以及RB-Tree(红黑树)的增加、删除以及查找操作。经实验对比,Open表优化的A*算法在搜索效率方面优于标准A*算法、索引数组优化的A*算法以及盲目式搜索算法。(2)提出一种基于地图影响因子的MF-A*路径搜索算法。首先,根据地形分布信息,定义三种地图影响因子,进而得出单个地图区域的权值,同时设计MF-A*算法的启发函数;然后,利用Floyd平滑处理方法筛选路径上的结点,并利用Catmull-Rom算法对路径进行平滑处理。实验证明,MF-A*算法99%以上的搜索结果优于A*算法,且改善了路径出现锯齿状的现象,MF-A*算法能够达到预期的效果。(3)提出了一种基于地图聚类的分层路径搜索算法K-HPA*。首先对地图进行预处理,其中包括筛选障碍物区域、最大距离法寻找初始聚类中心、利用K-Means算法对地图进行聚类;然后,定义关键结点并构建虚拟地图,在障碍物区域采用MF-A*搜索算法,在非障碍物区域采用Bresenham处理方法。经实验对比,K-HPA*算法搜索效率高于MF-A*算法,且扩展结点数目少于MF-A*算法。论文最后结合实际,对论文研究工作进行了总结与展望。
【关键词】：游戏AI A*算法 红黑树 影响因子 分层搜索
【学位授予单位】：杭州电子科技大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP18
【目录】：

• 摘要5-6
• ABSTRACT6-11
• 第一章 绪论11-15
• 1.1 研究背景与意义11-12
• 1.2 国内外研究现状12-13
• 1.3 本文的主要研究内容与结构13-15
• 第二章 路径搜索算法概述15-25
• 2.1 路径搜索算法15-19
• 2.1.1 盲目式搜索算法15-16
• 2.1.2 启发式搜索算法16-18
• 2.1.3 分层路径搜索算法18-19
• 2.2 搜索空间表示19-23
• 2.2.1 导航网格法19-22
• 2.2.2 可见点法22
• 2.2.3 栅格法22-23
• 2.3 Cocos2d-x简介23-24
• 2.4 本章小结24-25
• 第三章 基于Open表优化的A*算法25-40
• 3.1 引言25-26
• 3.2 Multiset数据结构简介26-30
• 3.2.1 关联容器简介26-27
• 3.2.2 Multiset数据结构27-30
• 3.3 Open表数据操作30-37
• 3.3.1 Insertion插入节点30-33
• 3.3.2 Erasure删除节点33-37
• 3.4 实验设计与分析37-39
• 3.4.1 实验设计37-38
• 3.4.2 实验数据分析38-39
• 3.5 本章小结39-40
• 第四章 MF-A*路径搜索算法40-56
• 4.1 MF-A*算法的提出40
• 4.2 MF-A*算法思想40-41
• 4.3 地图预处理41-46
• 4.3.1 地图空间划分41-43
• 4.3.2 设计地图影响因子43-46
• 4.3.2.1 通过性影响因子43-44
• 4.3.2.2 坡度影响因子44-45
• 4.3.2.3 实时性影响因子45-46
• 4.4 MF-A*路径搜索46-49
• 4.4.1 标准估价函数46-47
• 4.4.2 MF-A*算法估价函数47-49
• 4.5 路径平滑处理49-51
• 4.6 实验数据分析51-55
• 4.6.1 实验设计51-52
• 4.6.2 实验数据分析52-55
• 4.6.2.1 MF-A*算法与标准A*算法实验分析52-53
• 4.6.2.2 MF-A*算法平滑处理实验分析53-55
• 4.7 本章小结55-56
• 第五章：K-HPA*路径搜索算法56-68
• 5.1 K-HPA*算法的提出56
• 5.2 K-HPA*算法思想56-58
• 5.3 地图预处理58-60
• 5.3.1 筛选障碍物区域58
• 5.3.2 地图分类58-60
• 5.3.2.1 选取K-Means聚类中心59-60
• 5.3.2.2 K-Means地图聚类60
• 5.4 K-HPA*路径搜索60-64
• 5.5 实验数据分析64-66
• 5.5.1 实验设计64
• 5.5.2 实验数据分析64-66
• 5.6 本章小结66-68
• 第六章 总结与展望68-70
• 6.1 总结68-69
• 6.2 展望69-70
• 致谢70-71
• 参考文献71-74
• 详细摘要74-78

【相似文献】

中国期刊全文数据库 前10条

1 冯玉翔,唐韶华;利用证书路径搜索实现交叉认证[J];计算机工程与应用;2003年36期

2 李得伟;韩宝明;韩宇;;一种逆向改进型A*路径搜索算法[J];系统仿真学报;2007年22期

3 李艳军;李智勇;陈思远;;一种面向3D场景的实时自动路径搜索方法[J];计算机应用;2010年01期

4 王天顺;张莉;;一种基于导航网格的路径搜索技术[J];电脑知识与技术;2010年12期

5 柯健;李帅;郝沅君;张倩倩;;虚拟场景中路径搜索技术的研究[J];苏州市职业大学学报;2012年02期

6 符光梅;王红;;基于节点可达度的公交多路径搜索算法[J];计算机应用研究;2012年12期

7 缪成;吴启迪;许维胜;;突发灾害下可靠路径搜索模型与算法[J];计算机工程与应用;2007年28期

8 夏云龙;王正武;王杰;;考虑可靠性的降级路网最优路径搜索方法[J];交通科学与工程;2013年04期

9 何国辉;陈家琪;;游戏开发中智能路径搜索算法的研究[J];计算机工程与设计;2006年13期

10 陆悠;华泽;张妮;;基于二维有向集合扩散的公交网路径搜索算法研究[J];计算机与现代化;2009年12期

中国重要会议论文全文数据库 前2条

1 陈思远;史广顺;李刚;;实时3D游戏中的智能体路径搜索与动作控制[A];中国计算机图形学进展2008--第七届中国计算机图形学大会论文集[C];2008年

2 文聪;徐红兵;邓罡;;任意多边形排样和最短切割路径搜索的算法及实现[A];2006中国控制与决策学术年会论文集[C];2006年

中国博士学位论文全文数据库 前1条

1 马尧;在线社会网络的信任网络发现与信任融合研究[D];华中科技大学;2014年

中国硕士学位论文全文数据库 前10条

1 沈良;考虑出行时间相关性的最优路径搜索算法及应用[D];中国矿业大学;2016年

2 阎立忠;室内多目的地导航路径搜索系统的研究[D];哈尔滨工业大学;2015年

3 张加一;游戏AI中的路径搜索算法的研究与应用[D];杭州电子科技大学;2016年

4 陈彩;游戏地图中的分层和动态路径搜索[D];河北大学;2012年

5 李文亮;基于决策树划分的分层路径搜索[D];河北大学;2011年

6 左振华;基于ArcGIS API for Flex的人性化路径搜索算法研究及实现[D];内蒙古师范大学;2010年

7 徐菲云;3D游戏场景中路径搜索的研究与实现[D];电子科技大学;2007年

8 武s，

本文编号：345177