基于地图非均匀划分的Android游戏智能体寻径算法  

Routing Algorithm for Android Game Agents Based on Non-uniform Partition of Map

作　　者：李红波[1] 赵宽[1] 吴渝[1] 

机构地区：[1]重庆邮电大学计算机学院网络智能研究所,重庆400065

出　　处：《计算机科学》2013年第11期316-318,F0003,共4页Computer Science

基　　金：教育部新世纪优秀人才支持计划项目(教技司[2008]274号);重庆市原创动漫技术及软件(工具)技术研发团队(国科发高[2009]593号)资助

摘　　要：针对当前Android手机CPU频率较低、内存较小等手机资源不足的问题,在分层寻径算法的基础上提出了基于地图非均匀划分的智能体寻径优化算法。该优化算法在预处理阶段对游戏地图进行非均匀划分,生成抽象地图,在线搜索阶段首先在抽象地图的关键点中进行寻径,再在每个子图中进行路径搜索,最终到达目标节点。实验结果表明,与HPA*Enhancements算法和KM-A*算法相比,提出的算法搜索时间更短,遍历点数更少,能够取得更好的效果。最后,在算法中考虑了地形因素,加入了地形因子,让算法更能适应Android手机游戏的需要。For Android phones there are problems of insufficient mobile phone resources like the lower CPU frequency and smaller memory. To solve these problems, on the basis of the hierarchical routing algorithm, a routing algorithm for Android game agents based on non-uniform partition of map was presented. In this algorithm, the game map is non-uni- formly partitioned to generate the abstract map in preprocessing phase. And in online searching phase, it first finds paths in key points of the abstract map, then searches paths in each sub-map until the destination node is found. The ex- periment results indicate that compared with the HPA~ Enhancements and KM-A＊ , the algorithm has the advantages of shorter searching time, fewer traverse points and better results. Finally, a topographical factor is taken into considera- tion in order to adapt this algorithm to the need of the Android phone games.

关 键 词：ANDROID手机 分层寻径算法 非均匀划分 地形因子 

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