基于改进A*算法的地图游戏寻径研究

摘要

随着科技的进步，电子游戏经历了跨越式发展,游戏业的快速发展离不开游戏开发技术的研究，基于 A*算法游戏寻路是游戏开发技术的一个热门研究课题。A*搜索算法虽然高效，但也有一些不足之处。首先，在节点扩展过程中，会对OPEN表反复遍历，在大规模游戏中，严重影响搜索效率。其次，在寻找最优节点时会对相同 F值节点逐一考查比较，但是远离目标的节点不是最优节点，这样就产生了大量对无用节点的考察量。
　　本文的研究工作是基于A*算法的地图游戏寻径所展开，利用改进的A*算法来提高地图游戏寻径的效率，并进行了仿真实验，验证了改进后的A*算法的有效性。本文的主要工作：
　　（1）针对A*寻路算法对OPEN表反复遍历问题，本文使用混合数据结构优化OPEN表操作。选用最小二叉堆存储OPEN表节点，可有效的提高取最小F值节点的效率。同时使用索引数组来对OPEN表中节点进行标记，可使 OPEN成员的隶属判断的时间复杂度减至O（1）。
　　（2）针对A*寻路算法中产生大量无用节点的考察量问题，本文使用余弦函数对启发函数进行改进，改进后的启发函数可有效减少无用节点的访问量。
　　（3）本文为了验证改进后的A*算法的有效性和可行性，通过仿真实验对改进前后的 A*算法进行了对比实验分析，分别统计出改进前后算法寻路所花费的时间毫秒数以及总的搜索节点数。通过耗时和搜索节点总数这两个值的对比分析来评估改进后算法的有效性。

目录

封面

中文摘要

英文摘要

目录

1 绪论

1.1研究背景及其意义

1.2国内外研究现状

1.3本文研究内容

1.4本文组织结构

2 游戏地图寻径概论

2.1 相关术语

2.2 寻径搜索原理

2.3 常用寻径算法

2.4 寻径算法的选择

2.5 本章小结

3A*算法理论

3.1 A*（A-Star)算法的定义

3.2 A*算法的估价函数

3.3 A*算法原理

3.4 A*算法性质

3.5 A*算法实现

3.6 A*算法优缺点

3.7 本章小结

4A*算法改进与优化

4.1优化OPEN表存储结构

4.2 优化OPEN表成员隶属判断

4.3 改进启发函数

4.4 本章小结

5 基于A*算法的游戏地图寻径仿真实验及对比分析

5.1 仿真实验设计

5.2 标准A*算法实验数据

5.3 最小二叉堆存储OPEN表对比实验分析

5.4 加入索引数组前后对比分析

5.5 改进启发函数前后对比分析

5.6 综合改进后的A*算法性能分析

5.7 本章小结

6 总结和展望

6.1 结论

6.2 展望

参考文献

附录A：作者攻读硕士学位期间发表论文及科研情况

致谢

声明