即时战略游戏的智能流场寻路算法设计与实现  

Design and implementation of intelligent flow field pathfinding algorithm for real-time strategy game

作　　者：李恬 张树美 赵俊莉 LI Tian;ZHANG Shumei;ZHAO Junli(College of Data Science and Software Engineering,Qingdao University,Qingdao Shandong 266071,China)

机构地区：[1]青岛大学数据科学与软件工程学院

出　　处：《计算机应用》2020年第2期602-607,共6页journal of Computer Applications

基　　金：国家自然科学基金资助项目(61702293);中国博士后科学基金资助项目(2017M622137);教育部虚拟现实应用工程研究中心基金资助项目(MEOBNUEVRA201601)~~

摘　　要：针对即时战略游戏中多智能体寻路时间长和移动碰撞阻塞的问题,提出一种基于组合式改进的流场寻路算法。首先,采用红黑树存储数据,提高数据的存取速度;其次,采用惩罚函数将非线性的偏微分方程问题转化为线性的无约束问题,简化完整代价值的计算方式;最后,引入前置邻接点关联节点,生成流场方向。该算法与改进前的流场寻路算法相比,路径计算时间减少20%,平均移动时间稳定在20 s。实验结果表明,在即时战略游戏中采用改进后的流场寻路算法能够有效缩短寻路时间,提高智能体移动速度,提升游戏人工智能水平。To solve the problems of too long time of pathfinding and collision and blocking during movement in real-time strategy games,a combined improved flow field pathfinding algorithm was proposed.Firstly,the red-black tree was used to store data to improve the speed of data access.Secondly,by using the penalty function,the calculation of the integration field cost was simplified through transforming the nonlinear partial differential equation problem into a linear unconstrained problem.Finally,a pre-adjacency node was introduced to generate the flow direction.Compared with the flow field pathfinding algorithm without improvement,the improved algorithm has the path calculation time reduced by 20%,and the average moving time is stable at 20 s.Experimental results show that the improved flow field pathfinding algorithm can effectively shorten the pathfinding time,increase the moving speed of Agents and improve the level of game artificial intelligence in real-time strategy games.

关 键 词：路径搜索 即时战略游戏 人工智能 多智能体模拟 流场 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]