改进A*算法在游戏地图路径搜索中的应用研究  

Research on improved A* algorithm of path finding in game map

作　　者：钟瑛[1] 陈凌峰[1] 朱顺痣[1] 

机构地区：[1]厦门理工学院计算机与信息工程学院,福建361024

出　　处：《网络安全技术与应用》2013年第8期54-56,共3页Network Security Technology & Application

基　　金：福建省教育厅A类科技项目(JA11241);厦门市科技计划高校创新项目(3502Z20123037)

摘　　要：路径搜索是许多游戏的核心组成部分,路径搜索的算法有很多,不同的搜索算法有其不同的搜索策略、时间效率、空间消耗与应用场合。本文通过对A*算法的分析与研究,找出不足并进行优化和改进。使用最小二叉堆来优化A*算法对OPEN表的遍历,提高计算速度;通过引入以向量夹角余弦作为新启发式信息,减少计算过程中产生的无用节点,提高算法效率。最后通过仿真实验对标准A*算法、Dijkstra算法、改进A*算法进行数据分析比较,有效表明了本文所提算法的准确性和高效性。The path-finding technique is one of the core techniques in many games. There are many path-finding algorithms, which have different search strategies, time efficiency and space efficiency. So they have different application situations. In this paper, we identify deficiencies and improve the algorithm based on A ＊ algorithm analysis and research. In order to improve computing speed, the minimum binary heap is used to optimize A ＊ algorithm and traverse the OPEN table. Meanwhile, to improve efficiency of the algorithm, the cosine of vectors as the new heuristic information are introduced. Thus the unwanted nodes are reduced during the calculation process. Finally, simulation experiments of the standard A ＊ algorithm, Dijkstra algorithm, the improved A ＊ algorithm for data analysis and comparison, the proposed method effectively demonstrates the accuracy and efficiency.

关 键 词：A＊算法 路径搜索 启发式信息 向量夹角余弦 

分 类 号：TP391.3[自动化与计算机技术—计算机应用技术]