A＊算法在地图寻径中的实用性优化  

The Practicality Optimization of A ＊ Algorithm in Game Map Seeking Route

作　　者：王敬东[1] 李佳[1] 

机构地区：[1]东北电力大学信息工程学院,吉林市132012

出　　处：《电脑开发与应用》2007年第7期24-25,共2页Computer Development & Applications

基　　金：吉林省基金项目(电力规程网络游戏培训系统应用改进后的A*算法)

摘　　要：为了提高A*算法在地图寻径中的执行效率,首先深入分析了A*算法在游戏地图中搜索最优路径时影响速度的原因,然后从数据结构方面入手通过引入最小化堆的方法遍历开启列表,引入链表对节点数据结构进行改进等手段给出了A*算法的优化方案并对该方案进行了理论分析,最后通过500个大小不同的游戏地图对改进后的算法进行了测试和评估,实验结果表明改进后的A*算法有效地提高了路径搜索速度,切实可行。To raise the efficiency of A ＊ algorithm in game map seeking route, the paper first analyses the result that the algorithm of A ＊ influences the reason of speed in game map when searching for optimum route, then it gives the optimization scheme of A ＊ algorithm by restricting the size of close queue to reduce the scale of route searching and using the list from data structural aspect. At the same time, the optimization scheme of the algorithm of A ＊ has carried out theoretical analysis for this scheme,. At last, the scheme is tested and evaluated by 500 big and small differences game map. Experiment result shows It has effectively raised route-searching speed of A ＊ algorithm and the scheme is practical and feasible.

关 键 词：A＊算法 开启队列 关闭队列 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]