游戏场景中基于势场的交互寻路方法

计算机科学 ›› 2014, Vol. 41 ›› Issue (2): 131-135.

游戏场景中基于势场的交互寻路方法

余帅,李艳,王熙照,赵鹤玲

河北大学数学与计算机学院机器学习与计算智能重点实验室保定071002;河北大学数学与计算机学院机器学习与计算智能重点实验室保定071002;河北大学数学与计算机学院机器学习与计算智能重点实验室保定071002;中国人民解放军95866部队基础教研室保定071051

出版日期:2018-11-14 发布日期:2018-11-14
基金资助:
本文受国家自然科学基金项目(60903088,0),河北省自然科学基金(F2012201023),河北省第二批百名优秀人才支持计划(CPRC002)资助

Interactive Path-planning Method Based on Artificial Potential Field in Game Scenarios

YU Shuai,LI Yan,WANG Xi-zhao and ZHAO He-ling

Online:2018-11-14 Published:2018-11-14

摘要/Abstract

摘要： 在即时战略游戏中,路径规划是一种重要且常见的任务。游戏的实时性要求玩家能够快速寻找一条进攻的路径,而且游戏单元之间普遍存在的交互作用对寻路质量有着重要的影响。传统的寻路算法如Dijkstra算法虽然能够找到最优路径,但是耗时较多,而且未体现真实游戏中的交互。为此选取RTS游戏中一种典型的攻防场景,提出基于人工势场的快速高效动态寻路方法,同时为了体现RTS中游戏单元之间的交互性,将模糊测度引入到势场寻路中。实验结果表明,采用人工势场法寻路较Dijkstra算法耗时少、路径平滑；而引入模糊测度体现了真实游戏中单元之间的交互影响作用,与真实的游戏场景更为接近。

关键词: 即时战略游戏,Dijkstra算法,A*算法,人工势场法,模糊测度,模糊积分中图法分类号TP181文献标识码A

Abstract: In real-time strategy (RTS) games,path planning is one of the typical and important tasks for game players．To meet the requirement of real-time response,the game players need to find an offensive path quickly．Besides,there are often interactions among game units which will greatly influence the quality of path planning．Dijkstra algorithm is a traditional and widely used algorithm which can find an optimal path．However,this algorithm cannot meet the strict time limit in RTS games and does not consider the unit interactions．This paper selected a typical RTS game attack-defense scenario,and presented a fast and dynamic path-planning method based on artificial potential field．We also introduced the concept of fuzzy measure to describe the interaction of units．The experiment results show that the proposed method is more efficient and makes the selected game scenario closer to the real games.

Key words: Real-time strategy game,Dijkstra algorithm,A* algorithm,Artificial potential field,Fuzzy measure,Fuzzy integral

余帅,李艳,王熙照,赵鹤玲. 游戏场景中基于势场的交互寻路方法[J]. 计算机科学, 2014, 41(2): 131-135. https://doi.org/

YU Shuai,LI Yan,WANG Xi-zhao and ZHAO He-ling. Interactive Path-planning Method Based on Artificial Potential Field in Game Scenarios[J]. Computer Science, 2014, 41(2): 131-135. https://doi.org/

参考文献

[1] 刘天白,张舒白.机器学习技术在游戏中的应用研究——解决鼠标轨迹识别问题[J].电脑知识与技术,2011,7(13):3100-3102
[2] 杨佩,王皓,罗文杰．等.HUNTBot—第一人称射击游戏中NPC的结构设计[J].计算机科学,2008,35(11):290-292
[3] Huo P,Shiu S C-K,Wang H,et al．A neural evolutionary model for case-based planning in real time strategy games[C]∥ Next-Generation Applied Intelligence 2009．Berlin Heidelberg,2009:291-300
[4] Huo P,Shiu S C-K,Wang H,et al．Application and comparison of particle swarm optimization and genetic algorithm in strategy defense games[C]∥Fifth International Conference on Natural Computation．IEEE,2009:387-392
[5] Tong Xiao-lei,Li Yan,Li Wen-liang．Optimization Methods For Resources Allocation In Real-Time Strategy Games[C]∥Proceedings of the 2011International Conference on Machine Learning and Cybernetics．Guilin,2011,2:507-513
[6] Peter H F N,Li Y J,Shiu S C K．Unit Formation Planning in RTS game by using Potential Field and Fuzzy Integral[C]∥2011IEEE International Conference on Fuzzy Systems (FUZZY)．Taipei,2011:178-184
[7] Li Ying-jie,Li Yan,Simon C K S,et al.RTS game strategy evaluation using extreme learning machine[J]．Soft Computing,2012,16(9):1627-1637
[8] Hart P E,Nilsson N J,Raphael B.A formal basis for the heuris-tic determination of minimum cost paths in graphs[J]．IEEE Trans．Syst．Sci．and Cybernetics,SSC,1968,4(2):100-107
[9] Dijkstra E W．A note on two problems in connexion with graphs[J]．Numerische Mathematik,1959,1:269-271
[10] Khatib O．Real-Time Obstacle Avoidance For Manipulators and Mobile Robots[J]．Int．J.Robotics Res,1986,5(1):90-98
[11] Hagelback J,Johansson S．Using multi-agent potential fields inreal-time strategy games[C]∥Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems．2008:631-638
[12] Sugeno M．Theory of fuzzy integrals and its applications[D]．Tokyo:Tokyo Institute of Technology,1974
[13] 胡志华．基于离散人工势场的移动机器人动态路径规划研究[D]．长沙:中南大学,2009
[14] Peters J,Han L,Ramanna S．The Choquet integral in a rough software cost decision system[M]∥Fuzzy Measures and Integrals:Theory and Applications,Studies in fuzziness and soft computing,1999

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed