游戏地图中的分层动态路径搜索算法  

Hierarchical Dynamic Path Finding Algorithm in Game Maps

作　　者：李艳[1] 陈彩[1] 李铁松[1] 苏兰明[1] 

机构地区：[1]河北大学数学与计算机学院机器学习与计算智能重点实验室,河北保定071002

出　　处：《计算机工程》2012年第2期288-289,共2页Computer Engineering

基　　金：国家自然科学基金资助项目(60903088);河北省自然科学基金资助项目(F2009000227;A2010000188);河北省第二批百名优秀人才支持计划基金资助项目(CPRC002)

摘　　要：在大型游戏地图环境中,玩家必须对动态地形做出即时反应,而动态寻路算法对改变节点的位置非常敏感。为此,结合增量路径搜索(LPA*)算法和分层路径搜索(HPA*)算法,提出一种分层动态路径搜索(HPLPA*)算法。对地图分层形成抽象图,并在动态环境中及时更新,采用LPA*搜索,找到抽象路径再细化,以此形成本地路径。实验结果证明,与LPA*和HPA*相比,该算法更有效。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.

关 键 词：路径搜索 分层动态地形 HPLPA＊算法 重规划 

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