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