复合寻路策略在手机游戏中的应用研究  

STUDY ON APPLICATION OF COMPOSITE PATHFINDING STRATEGY IN MOBILE PHONE GAME

作　　者：胡文艺[1] 邓威[1] 阚瑷珂[2,3] 姜雪娇[1] 

机构地区：[1]成都理工大学信息科学与技术学院,四川成都610059 [2]成都理工大学地球物理学院,四川成都610059 [3]西藏自治区科技信息研究所,西藏拉萨850001

出　　处：《计算机应用与软件》2014年第5期136-140,共5页Computer Applications and Software

基　　金：国家科技支撑计划课题(2012BAH33F01)

摘　　要：复合寻路算法成功应用于手机游戏CrazyWar。该寻路算法包含三个寻路模块:直线寻路模块、A*寻路模块、航点寻路模块。提出的复合寻路算法先通过航点算法得到一个总体的大致路径,再在寻路精细方面由直线寻路模块和A*寻路模块处理,从而解决了A*寻路模块中随搜索地图增长而资源消耗也呈几何增长、大范围搜索耗时过长以及提高估值因子所带来的路径准确度降低的缺点。通过理论分析和实际应用表明:复合寻路算法在寻路速度、资源消耗、寻路效果上均优于单一寻路算法,具有很好的推广性与实用价值。The composite pathfinding algorithm is successfully applied in the mobile phone game Crazywar. This pathfinding algorithm contains three pathfinding modules： the linear pathfinding module,the A＊pathfinding module and the waypoint pathfinding module. The composite pathfinding algorithm put forward in this paper gets a general rough path through waypoint algorithm at first,then the fine aspect of pathfinding is dealt with by linear pathfinding module and A＊pathfinding module,which solves the disadvantages in A＊pathfinding module that resource consumption increases geometrically as map searching increases,long time consuming when searching range is wide,and path veracity decreases when estimation value of factor is improved. It is indicated through theoretical analysis and practical application that the composite pathfinding algorithm has good popularisation and practical value since it outperforms the single pathfinding algorithm in pathfinding speed,resource consumption and pathfinding effect.

关 键 词：复合寻路 BRESENHAM算法 A＊算法 航点算法 手机游戏 

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