基于人物状态自动机的实时动态寻径算法优化  

Realtime and dynamic path-finding algorithm and optimization based on figures state automachine

作　　者：袁文杰[1] 郭爽[2] 

机构地区：[1]东北电力大学输变电技术学院,吉林吉林132012 [2]东北电力大学信息工程学院,吉林吉林132012

出　　处：《计算机工程与设计》2009年第10期2599-2600,F0003,共3页Computer Engineering and Design

摘　　要：路径搜索是实现游戏中的角色逼真行走的关键技术之一。针对游戏动态路网中寻径极易陷入陷阱且寻径效率不高的问题,将人物状态自动机和加权的LRTA*算法相结合,提出了基于人物状态自动机的实时动态寻径算法。通过改变估价函数值更新规则与解时间和解质量相结合,加快算法收敛速度,并引入人工搜索标志,完成对LRTA*算法的优化。测试结果表明,该算法有效提高了路径搜索的速度,并使搜索得到的路径平滑自然。Path-finding is one of the key technology to implement intelligent move of the character in game. To solve the problem of games path-finding in dynamic network easily falled into the trap and low efficiency, realtime and dynamic path-finding algorithm based on figures state automachine is presented by combining the figures state automachine with the weighted LRTA＊ algorithm. To speed up the algorithm convergence, the updated rules of valuation function are changed, the time and quality of the solution are compromised relatively. To complete the optimization of LRTA＊ algorithm, the artificial searching mark is introduced. Test results show that the new algorithm can enhance the speed of the path-finding greatly, and smooth the path to be natural.

关 键 词：动态路网 人工智能 人物状态自动机 人工搜索标志 寻径算法 

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