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

Research of Path-finding in Game Maps Based on Improved A~* Algorithm

作　　者：陈素琼[1] 王惠来[1] 向天雨[1] 

机构地区：[1]重庆医科大学附属大学城医院信息中心,重庆401331

出　　处：《重庆师范大学学报（自然科学版）》2017年第4期75-78,共4页Journal of Chongqing Normal University:Natural Science

基　　金：重庆市渝中区科委科技攻关项目(No.20110205)

摘　　要：【目的】对A~*算法进行研究和改进优化,以提高基于A~*算法的地图游戏寻径效率。【方法】使用最小二叉堆和标记数组两种混合数据结构优化OPEN表的存储和遍历,用夹角余弦值作为新的启发信息,减少搜索过程中对非最有节点的考察量,通过仿真实验对标准A~*算法、改进A~*算法地图寻径进行数据对比分析。【结果】综合地提高了路径搜索的效率。【结论】通过对A~*算法进行改进优化,有效提高了基于A~*算法的地图游戏寻径效率。[Purposes]The A＊ algorithm is studied and improved to improve the efficiency of map game routing based on A＊ algorithm. [Methods]Use the smallest binary heap and the index array to optimize the storage and traversal of the OPEN table for the mixed data structure. The cosine function is used as the new heuristic information to reduce the useless nodes in the search process through the simulation experiment, the standard A＊ algorithm and improved A＊ algorithm are compared and analyzed. [Findings]The efficiency of path search is improved synthetically. [Conclusions]By improving the A＊ algorithm, the efficiency of map game search based on A＊ algorithm is improved.

关 键 词：A＊算法 索引数组 余弦函数 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]