摘要： 在大型游戏地图环境中，玩家必须对动态地形做出即时反应，而动态寻路算法对改变节点的位置非常敏感。为此，结合增量路径搜索(LPA*)算法和分层路径搜索(HPA*)算法，提出一种分层动态路径搜索(HPLPA*)算法。对地图分层形成抽象图，并在动态环境中及时更新，采用LPA*搜索，找到抽象路径再细化，以此形成本地路径。实验结果证明，与LPA*和HPA*相比，该算法更有效。
关键词:
路径搜索,
分层动态地形,
HPLPA*算法,
重规划
Abstract: Game agents must respond quickly to the changes of dynamical topography in large environments. The efficiency of Lifelong Planning A*(LPA*) algorithm is sensitive to the location of the updated nodes. This paper proposes a Hierarchical Path Finding and Lifelong Planning A*(HPLPA*) algorithm, where LPA* is combined with HPA* algorithm. Based on HPA*, an abstract graph is generated and updated in time. LPA* is used on the abstract graph to generate an abstract path. The abstract path is refined to a local path. Experimental results are conducted to compare LPA*, HPA* and HPLPA*, which show that HPLPA* is more effective.
Key words:
path finding,
hierarchical dynamic topography,
Hierarchical Path Finding and Lifelong Planning A*(HPLPA*) algorithm,
replanning
中图分类号:
李艳, 陈彩, 李铁松, 苏兰明. 游戏地图中的分层动态路径搜索算法[J]. 计算机工程, 2012, 38(2): 288-289.
LI Yan, CHEN Cai, LI Tie-Song, SU Lan-Meng. Hierarchical Dynamic Path Finding Algorithm in Game Maps[J]. Computer Engineering, 2012, 38(2): 288-289.