摘要
在游戏中,寻径算法占有很重要的作用,A*算法广泛应用于游戏寻径,是目前比较流行的启发式搜索算法之一。为了提高A*算法的执行效率,采用并行搜索法对普通A*算法进行优化,即分别从起始节点和目标节点开始路径搜索,直到在中途有相同的临界子节点。将该算法在游戏所使用的网格地图中进行实验,实验结果表明,该算法能够有效地根据系统设定的通行条件寻找出一条最优的实际可行的路径,同时缩短寻路的时间消耗,提高游戏的可玩性。
Path-finding algorithm is the most important issues in the developing of game. A＊ algorithm is one of the most popular heuristic searching,that is the most widely used algorithm in the field of game map path-finding. In order to increase the efficiency A ＊ algorithm,the searching method of parallel search has been used to optimize common A＊ algorithm. Such method may expend the starting node and the goal node at the same time,and if a same adjacency child node was found in the way,the algorithm would be terminated. The experiment in the grid map that used in games proves that this algorithm can effectively find out an optimal practical path,according to the prevailing conditions set by the system. It can raise the search efficiency and reduce the complexity of the planning issue and improve the playability.
出处
《信息技术》
2015年第4期188-191,共4页
Information Technology
关键词
A＊算法
启发式搜索
游戏寻径
并行搜索
网格地图
A＊ algorithm
heuristic searching
game map path-finding
parallel search
grid map
