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

doi:10.11772/j.issn.1001-9081.2019071158

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

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)

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

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

青岛大学数据科学与软件工程学院，山东青岛 266071

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

Abstract

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:

TP18

Tian LI, Shumei ZHANG, Junli ZHAO. Design and implementation of intelligent flow field pathfinding algorithm for real-time strategy game[J]. Journal of Computer Applications, 2020, 40(2): 602-607.

李恬, 张树美, 赵俊莉. 即时战略游戏的智能流场寻路算法设计与实现[J]. 《计算机应用》唯一官方网站, 2020, 40(2): 602-607.

Figures/Tables 11

References 32

1	ROBERTSON G， WATSON I. A review of real-time strategy game AI［J］. AI Maganize， 2014， 35（4）：75-104. 10.1609/aimag.v35i4.2478
2	DIJKSTRA E W. A note on two problems in connexion with graphs［J］. Numerische Mathematk， 1959， 1（1）：269-271. 10.1007/bf01386390
3	HART P E， NILSSON N J， RAPHAEL B. A formal basis for the heuristic determination of minimum cost paths［J］. IEEE Transactions on Systems Science and Cybernetics， 1968， 4（2）：100-107. 10.1109/tssc.1968.300136
4	赵建民，朱信忠. 即时战略游戏中寻径问题的算法及实现技术研究［J］. 计算机科学， 2002， 29（Z2）：72-75. 10.3969/j.issn.1002-137X.2002.z2.021
	ZHAO J M， ZHU X Z. The algorithm of real-time strategic-game seek-route engine implement technology research［J］. Computer Science， 2002， 29（Z2）：72-75. 10.3969/j.issn.1002-137X.2002.z2.021
5	余帅，李艳，王熙照，等. 游戏场景中基于势场的交互寻路方法［J］. 计算机科学， 2014， 41（2）：131-135. 10.3969/j.issn.1002-137X.2014.02.029
	YU S， LI Y， WANG X Z， et al. Interactive path-planning method based on artificial potential field in game scenarios［J］. Computer Science， 2014， 41（2）：131-135. 10.3969/j.issn.1002-137X.2014.02.029
6	叶青，夏时洪，毛天露，等. Agent-Based群体模拟中的朝向计算方法［J］. 计算机辅助设计与图形学学报， 2011， 23（8）：1349-1356.
	YE Q， XIA S H， MAO T L， et al. Orientation computing in agent-based crowd simulation［J］. Journal of Computer-Aided Design and Computer Graphics， 2011， 23（8）：1349-1356.
7	MALINOWSKI A， CZARNUL P， CZURYLO K， et al. Multi-Agent large-scale parallel crowd simulation［J］. Procedia Computer Science， 2017， 108：917-926. 10.1016/j.procs.2017.05.036
8	SARTORETTI G， KERR J， SHI Y， et al. PRIMAL： pathfinding via reinforcement and imitation multi-Agent learning［J］. IEEE Robotics and Automation Letters， 2019， 4（3）：2378-2385. 10.1109/lra.2019.2903261
9	HO F， SALTA A， GERALDES R， et al. Multi-Agent path finding for UAV traffic management［C］// Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems. Richland， SC： International Foundation for Autonomous Agents and Multiagent Systems， 2019：131-139.
10	EMERSON E. Crowd pathfinding and steering using flow field tiles［M］// RABIN S. Game AI Pro： Collected Wisdom of Game AI Professionals. Boca Raton： CRC press， 2013：307-316. 10.1201/b16725-29
11	刘宝谦. 一款即时战略类游戏的关键技术研究与实现［D］. 成都：电子科技大学， 2010：1-5.
	LIU B Q. Research and implementation of key technologies for a real-time strategy game［D］. Chengdu： University of Electronic Science and Technology of China， 2010：1-5.
12	赵建民，朱信忠. 可移动物体环绕障碍物路线动态生成算法研究［J］.计算机科学， 2002， 29（Z1）：174-177. 10.3969/j.issn.1002-137X.2002.z1.064
	ZHAO J M， ZHU X Z. The algorithm of real-time strategic-game seek-route engine implement technology research［J］. Computer Science， 2002， 29（Z1）：174-177. 10.3969/j.issn.1002-137X.2002.z1.064
13	ONTAÑÓN S， SYNNAEVE G， URIARTE A， et al. A survey of real-time strategy game AI research and competition in StarCraft［J］. IEEE Transactions on Computational Intelligence and AI in Games， 2013， 5（4）：293-311. 10.1109/tciaig.2013.2286295
14	何国辉，陈家琪. 游戏开发中智能路径搜索算法的研究［J］. 计算机工程与设计， 2006， 27（13）：2334-2337. 10.3969/j.issn.1000-7024.2006.13.009
	HE G H， CHEN J Q. Research on algorithm of AI pathfinding in game development［J］. Computer Engineering and Design， 2006， 27（13）：2334-2337. 10.3969/j.issn.1000-7024.2006.13.009
15	ONTAÑÓN S， MISHRA K， SUGANDH N， et al. Case-based planning and execution for real-time strategy games［C］// Proceedings of the 2007 International Conference on Case-based Reasoning， LNCS4626. Berlin： Springer， 2007：164-178. 10.1007/978-3-540-74141-1_12
16	荆东星. 人工神经网络在游戏寻路中的应用研究［D］. 长沙：长沙理工大学， 2010：5-6.
	JING D X. Application of artificial neural network in game pathfinding［D］. Changsha： Changsha University of Science and Technology， 2010：5-6.
17	WYATT P. The StarCraft path-finding hack［EB/OL］. .
18	DICKHEISER M. Game Programming Gems 6［M］. Needham Heights， MA： Charles River Media， 2006： 291-306.
19	曹朋朋，张晶晶，许志强，等. 一种基于GIS的铁路设备维修路线规划方法［J］. 计算机应用与软件， 2017， 34（12）：77-81. 10.3969/j.issn.1000-386x.2017.12.015
	CAO P P， ZHANG J J， XU Z Q， et al. Path planning for railway equipment maintenance based on GIS［J］. Computer Applications and Software， 2017， 34（12）：77-81. 10.3969/j.issn.1000-386x.2017.12.015
20	张渭军，王华. 城市道路最短路径的Dijkstra算法优化［J］. 长安大学学报（自然科学版）， 2005， 25（6）：62-65. 10.3321/j.issn:1671-8879.2005.06.015
	ZHANG W J， WANG H. Optimination Dijkstra arithmetic for shortest path of urban traffic net［J］. Journal of Chang’an University （Natural Science Edition）， 2005， 25（6）：62-65. 10.3321/j.issn:1671-8879.2005.06.015
21	王华. 一种物流配送最短路径混合算法［J］. 测绘科学， 2014， 39（9）：135-137.
	WANG H. A mixed algorithm of shortest path in logistics and distribution［J］. Science of Surveying and Mapping， 2014， 39（9）：135-137.
22	盖文妹，蒋仲安，邓云峰，等. 重大事故救灾路线双目标优化模型及算法［J］. 北京科技大学学报， 2014， 36（4）：535-542. 10.1109/chicc.2014.6896499
	GAI W M， JIANG Z A， DENG Y F， et al. Bi-objective optimization model and algorithm of rescue routes during major accident time［J］. Journal of University of Science and Technology Beijing， 2014， 36（4）：535-542. 10.1109/chicc.2014.6896499
23	潘长安. 基于改进A星算法的城市交通寻径的研究［D］. 厦门：华侨大学， 2015： 1-5. 10.1061/9780784479292.309
	PAN C A. Research on urban traffic pathfinding based on improved A* algorithm［D］. Xiamen： Huaqiao University， 2015： 1-5. 10.1061/9780784479292.309
24	易星. 改进的A*算法在物流配送中的车辆调度方法［J］. 金陵科技学院学报， 2017， 33（4）：31-34.
	YI X. Vehicle scheduling method in logistics distribution based on improved A* algorithm［J］. Journal of Jinling Institute of Technology， 2017， 33（4）：31-34.
25	岳贵杰，杜黎明，刘凤德，等. A*搜索算法的正射影像镶嵌线自动提取［J］. 测绘科学， 2015， 40（4）：151-154. 10.16251/j.cnki.1009-2307.2015.04.033
	YUE G J， DU L M， LIU F D， et al. Automatic seamline detection for orthophoto mosaicking based on A* searching algorithm［J］. Science of Surveying and Mapping， 2015， 40（4）：151-154. 10.16251/j.cnki.1009-2307.2015.04.033
26	程丽平，谭永海. 改进的分层A*算法在停车场路径寻优中的应用［J］.计算机测量与控制， 2015， 23（1）：183-186. 10.3969/j.issn.1671-4598.2015.01.056
	CHENG L P， TAN Y H. Application of improved hierarchical A* algorithm for optimal parking path planning［J］. Computer Measurement and Control， 2015， 23（1）：183-186. 10.3969/j.issn.1671-4598.2015.01.056
27	荣明，王钦钊，李小龙，等. 基于A*算法的虚拟士兵城市作战路径规划［J］. 装甲兵工程学院学报， 2010， 24（6）：59-62. 10.3969/j.issn.1672-1497.2010.06.014
	RONG M， WANG Q Z， LI X L， et al. Path planning based on A* algorithm for virtual soldier in urban combat simulation［J］. Journal of Academy of Armored Force Engineering， 2010， 24（6）：59-62. 10.3969/j.issn.1672-1497.2010.06.014
28	FU Z， KIRBY R M， WHITAKER R T. A fast iterative method for solving the eikonal equation on tetrahedral domains［J］. SIAM Journal on Scientific Computing， 2013， 35（5）：C473-C494. 10.1137/120881956
29	SETHIAN J A. Level Set Methods and Fast Marching Methods［M］. Cambridge： Cambridge University Press， 1999：29-32. 10.1007/978-3-0348-8724-3_36
30	ROUY E， TOURIN A. A viscosity solutions approach to shape-from-shading［J］. SIAM Journal on Numerical Analysis， 1992， 29（3）：867-884. 10.1137/0729053
31	王树西，李安渝.Dijkstra算法中的多邻接点与多条最短路径问题［J］.计算机科学，2014，41（6）：217-224. 10.11896/j.issn.1002-137x.2014.06.043
	WANG S X， LI A Y. Multi-adjacent-vertexes and multi-shortest-paths problem of Dijkstra algorithm［J］. Computer Science， 2014， 41（6）：217- 224. 10.11896/j.issn.1002-137x.2014.06.043
32	杨元超.基于HTML5的即时战略网页游戏的设计与实现［D］.成都：电子科技大学，2014：1-2.（YANG Y C. Design and implementation of the real time strategy game based on HTML5［D］. Chengdu： University of Electronic Science and Technology of China， 2014： 1-2.）

所用路径算法	移动智能体数量
所用路径算法	1	10	20	50	100	200
Dijkstra算法	0.269 4	0.720 8	1.178 8	2.862 0	4.437 6	8.406 9
A*算法	0.200 3	0.727 7	1.092 2	2.440 4	4.149 4	8.381 5
人工势场法	0.407 5	0.653 8	0.923 7	1.959 2	3.537 6	6.830 1
流场寻路算法	0.563 6	0.555 6	0.582 8	0.475 9	0.525 5	0.481 8
改进后寻路算法	0.353 4	0.428 8	0.327 2	0.413 5	0.458 5	0.338 0

所用路径算法	移动智能体数量
所用路径算法	1	10	20	50	100	200
Dijkstra算法	0.269 4	0.720 8	1.178 8	2.862 0	4.437 6	8.406 9
A*算法	0.200 3	0.727 7	1.092 2	2.440 4	4.149 4	8.381 5
人工势场法	0.407 5	0.653 8	0.923 7	1.959 2	3.537 6	6.830 1
流场寻路算法	0.563 6	0.555 6	0.582 8	0.475 9	0.525 5	0.481 8
改进后寻路算法	0.353 4	0.428 8	0.327 2	0.413 5	0.458 5	0.338 0

所用路径算法	移动智能体数量
所用路径算法	1	10	20	50	100	200
Dijkstra算法	1.881 0	8.865 8	22.189	53.759	98.207	213.280
A*算法	1.988 0	9.348 0	19.446	48.112	98.113	212.720
人工势场法	1.708 9	8.054 5	17.263	43.970	73.749	147.570
流场寻路算法	7.556 4	15.649 0	18.786	19.901	20.582	21.341
改进后寻路算法	7.631 8	15.091 0	18.307	19.596	19.431	19.961

所用路径算法	移动智能体数量
所用路径算法	1	10	20	50	100	200
Dijkstra算法	1.881 0	8.865 8	22.189	53.759	98.207	213.280
A*算法	1.988 0	9.348 0	19.446	48.112	98.113	212.720
人工势场法	1.708 9	8.054 5	17.263	43.970	73.749	147.570
流场寻路算法	7.556 4	15.649 0	18.786	19.901	20.582	21.341
改进后寻路算法	7.631 8	15.091 0	18.307	19.596	19.431	19.961

[1]	LIU Zichen, LI Xiaojuan, WEI Wei. Automatic patent price evaluation based on recurrent neural network [J]. Journal of Computer Applications, 2021, 41(9): 2532-2538.
[2]	DING Yin, SANG Nan, LI Xiaoyu, WU Feizhou. Prediction method of capacity data in telecom industry based on recurrent neural network [J]. Journal of Computer Applications, 2021, 41(8): 2373-2378.
[3]	Zhixiang LIU, Huichao LIU, Dongmei HUANG, Liping ZHOU, Cheng SU. IB-LBM parallel optimization method mixed with multiple task scheduling modes [J]. Journal of Computer Applications, 2020, 40(2): 386-391.
[4]	ZHANG Junjie, SUN Guangmin, ZHENG Kun. Review of gaze tracking and its application in intelligent education [J]. Journal of Computer Applications, 2020, 40(11): 3346-3356.
[5]	XIA Bin, BAI Yuxuan, YIN Junjie. Generative adversarial network-based system log-level anomaly detection algorithm [J]. Journal of Computer Applications, 2020, 40(10): 2960-2966.
[6]	WEI Xiaona, LI Yinghao, WANG Zhenyu, LI Haozun, WANG Hongzhi. Methods of training data augmentation for medical image artificial intelligence aided diagnosis [J]. Journal of Computer Applications, 2019, 39(9): 2558-2567.
[7]	ZHANG Qiang, YANG Jian, FU Lizhen. Two-input stream deep deconvolution neural network for interpolation and recognition [J]. Journal of Computer Applications, 2019, 39(8): 2271-2275.
[8]	WANG Yuanlong. Rendering algorithm of dynamic participating media based on optical flow [J]. Journal of Computer Applications, 2016, 36(5): 1352-1355.
[9]	. Real-time visualization algorithm of 2D unsteady flow field [J]. Journal of Computer Applications, 2010, 30(9): 2434-2437.
[10]	. Path finding algorithm in massive multiplayer online games based on anchor points and path reuse [J]. Journal of Computer Applications, 2010, 30(12): 3215-3217.
[11]	. Automatic path finding method for real-time rendering of 3D scene [J]. Journal of Computer Applications, 2010, 30(1): 85-89.
[12]	. Methods of conception soft-and operation in cloud model [J]. Journal of Computer Applications, 2008, 28(10): 2510-1512.
[13]	Zhao Bin. Robust estimation of optical flow based on linear brightness model [J]. Journal of Computer Applications, 2008, 28(1): 216-219.
[14]	Tai-Lin Cao Yao-Lin Gu. Visualization of time-dependent 2D vector fields based on topological method [J]. Journal of Computer Applications, 2007, 27(9): 2129-2130.
[15]	. Flow field visualization method based on particle texture blending [J]. Journal of Computer Applications, 2007, 27(8): 2011-2013.

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

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 11

References 32

Related Articles 15

Recommended Articles

Metrics