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

《游戏ai中的路径搜索算法的研究与应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文题目:游戏AI中的路径搜索算法的研究与应用研究生张加一专业计算机技术指导教师冯建文副教授完成日期2016年3月杭州电子科技大学硕士学位论文游戏AI中的路径搜索算法的研究与应用研究生：张加一指导教师：冯建文副教授2016年3月DissertationSubmittedtoHangzhouDianziUniversityfortheDegreeofMasterTheresearchandapplicationofPathFindingAlgorithmsinGameArtificialIntelligenceCandidate:Ji

2、ayiZhangSupervisor:JianwenFengMarch,2016杭州电子科技大学学位论文原创性声明和使用授权说明原创性声明：本人郑重声明所呈交的学位论文，是本人在导师的指导下，独立进行研。究工作所取得的成果除文中己经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写过的作品或成果。对本文的研究做出重要贡献的个人和集１体，均已在文中＾｜明确方式标明。申请学位论文与资料若有不实么处一，本人承担切相关责任。论文作者签名：日期：年月日学位论文使用授权说明本人完全了解杭州电子科技

3、大学关于保留和使用学位论文的规定，目Ｐ；研究生在校攻读学位期间论文工作的知识产权单位属杭州电子科技大学。本人保证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为杭州电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可Ｗ公布论文的全部或部分内容，可Ｗ允许采用影印、缩印或其它复制手段保存论文。（保密论文在解密后遵守此规定）论文作者签名：曰期：＞４年＾月／耗指导教师签名：日期：＞〇年月日日（／乙＾摘要路径搜索是游戏AI（人工智能）的重要组成部分，在大型的商业游戏中，路径搜索经常受限于存储空间

4、以及CPU处理能力，且路径搜索的性能直接决定用户对游戏的满意程度。论文通过对传统路径搜索算法的深入研究与分析，提出了几种改进与优化策略，并通过实验对比，分析了算法改进的效果。论文首先探讨了课题的研究背景与意义，分析了国内外研究现状。路径搜索是影响游戏整体效果的因素之一，因为路径搜索赋予NPC感知周围环境的能力，在一定程度上标志着NPC智能水平的高低并直接影响游戏角色的行为。接着，论文对比研究了传统的各种路径搜索算法，描述了搜索空间表示方法。传统的Dijkstra算法、A*算法时间复杂度高，难以满足大规模地图中路径搜索的要求；HPA*等分层寻

5、路算法对地图进行均匀分区，未考虑地图中地形的分布信息，适应能力差。针对以上问题，论文在三方面进行了改进与优化：（1）提出了一种对A*算法Open表优化的方法。利用Multiset关联容器作为A*算法Open表的数据结构。深入分析了顺序容器和关联容器的性质，以及RB-Tree（红黑树）的增加、删除以及查找操作。经实验对比，Open表优化的A*算法在搜索效率方面优于标准A*算法、索引数组优化的A*算法以及盲目式搜索算法。（2）提出一种基于地图影响因子的MF-A*路径搜索算法。首先，根据地形分布信息，定义三种地图影响因子，进而得出单个地图区域的权

6、值，同时设计MF-A*算法的启发函数；然后，利用Floyd平滑处理方法筛选路径上的结点，并利用Catmull-Rom算法对路径进行平滑处理。实验证明，MF-A*算法99%以上的搜索结果优于A*算法，且改善了路径出现锯齿状的现象，MF-A*算法能够达到预期的效果。（3）提出了一种基于地图聚类的分层路径搜索算法K-HPA*。首先对地图进行预处理，其中包括筛选障碍物区域、最大距离法寻找初始聚类中心、利用K-Means算法对地图进行聚类；然后，定义关键结点并构建虚拟地图，在障碍物区域采用MF-A*搜索算法，在非障碍物区域采用Bresenham处理方

7、法。经实验对比，K-HPA*算法搜索效率高于MF-A*算法，且扩展结点数目少于MF-A*算法。论文最后结合实际，对论文研究工作进行了总结与展望。关键词：游戏AI，A*算法，红黑树，影响因子，分层搜索IABSTRACTPathsearchisanimportantpartofgameartificialintelligence.Inlargecommercialgames,pathsearchisoftenlimitedbystoragespaceandCPUprocessingpower.Pathsearchperformancedirec

8、tlydeterminestheuser'ssatisfactionwiththegame.Byanalyzingthetraditionalpathfindingalgorit