Journal of Computer Applications ›› 2020, Vol. 40 ›› Issue (2): 602-607.DOI: 10.11772/j.issn.1001-9081.2019071158

• Frontier & interdisciplinary applications • Previous Articles     Next Articles

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

Tian LI, Shumei ZHANG(), Junli ZHAO   

  1. College of Data Science and Software Engineering,Qingdao University,Qingdao Shandong 266071,China
  • Received:2019-07-04 Revised:2019-08-22 Accepted:2019-08-30 Online:2019-09-19 Published:2020-02-10
  • Contact: Shumei ZHANG
  • About author:LI Tian, born in 1995, M. S. candidate. Her research interests include artificial intelligence, path planning.
    ZHAO Junli, born in 1977, Ph. D., associate professor. Her research interests include computer vision, computer graphics, virtual reality.
  • Supported by:
    the National Natural Science Foundation of China(61702293);the China Postdoctoral Science Foundation(2017M622137);the Ministry of Education Virtual Reality Application Engineering Research Center Foundation(MEOBNUEVRA201601)

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

李恬, 张树美(), 赵俊莉   

  1. 青岛大学 数据科学与软件工程学院,山东 青岛 266071
  • 通讯作者: 张树美
  • 作者简介:李恬(1995—),女,山东济南人,硕士研究生,主要研究方向:人工智能、路径规划
    赵俊莉(1977—),女,山西新绛人,副教授,博士,主要研究方向:计算机视觉、计算机图形学、虚拟现实。
  • 基金资助:
    国家自然科学基金资助项目(61702293);中国博士后科学基金资助项目(2017M622137);教育部虚拟现实应用工程研究中心基金资助项目(MEOBNUEVRA201601)

Abstract:

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.

Key words: path finding, real-time strategy game, artificial intelligence, multi-Agent simulation, flow field

摘要:

针对即时战略游戏中多智能体寻路时间长和移动碰撞阻塞的问题,提出一种基于组合式改进的流场寻路算法。首先,采用红黑树存储数据,提高数据的存取速度;其次,采用惩罚函数将非线性的偏微分方程问题转化为线性的无约束问题,简化完整代价值的计算方式;最后,引入前置邻接点关联节点,生成流场方向。该算法与改进前的流场寻路算法相比,路径计算时间减少20%,平均移动时间稳定在20 s。实验结果表明,在即时战略游戏中采用改进后的流场寻路算法能够有效缩短寻路时间,提高智能体移动速度,提升游戏人工智能水平。

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

CLC Number: