游戏地图中寻找路径的改进算法研究  

Research on pathfinding improved algorithm in game map

作　　者：周小镜[1] 

机构地区：[1]西南大学计算机与信息科学学院,重庆400715

出　　处：《信息技术》2010年第12期125-127,共3页Information Technology

摘　　要：随着计算机技术和网络技术的发展,以及人们生活水平的提高,网络游戏已经成为人们休闲娱乐生活不可或缺的一部分。网络游戏中角色按照什么路径行走,直接影响到游戏的质量。然而,由于游戏地图资源庞大和计算机资源等的限制,使得游戏中的寻路成为一个难点。通过分析现有常见的两种游戏地图寻径算法A*算法和单个物体寻径算法的原理及优缺点,提出一种将两种算法结合使用的改进算法,它综合了两种算法的优点,在寻径的速度和找到路径的长度方面都有显著的优势。最后,用C++语言实现了改进的寻路算法,并和原来的算法对比,实验结果显示提出的改进算法的合理性和有效性。With the development of computer technology and network technology,and improvement of living standard,online games have become an integral part of recreational life.The path directly affects the quality of the game.However,the huge game maps resources and the limit computer resources make find its way in games difficultly.By analyzing both A＊algorithm and a single object pathfinding algorithm,including the advantages and disadvantages,and the principles,the paper proposed a combination of the two methods,which combines the advantages of two algorithms in the speed of routing and the length of the path.Finally,it realizes the pathfinding improved algorithm with C＋＋,and comparing the original algorithm.The experimental results show this improved rationality and effectiveness of the algorithm.

关 键 词：地图寻径 A＊算法 单个物体寻径算法 

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