Dynamic Pathfinding for Non-Player Character Follower on Game

Authors

  • Paulus Harsadi STMIK Sinar Nusantara
  • Siti Asmiatun Universitas Semarang
  • Astrid Novita Putri Universitas Semarang

DOI:

https://doi.org/10.35335/cit.Vol13.2021.68.pp51-58

Keywords:

Artificial Intelligence, Dynamic pathfinding, Artificial Potential Field, Flocking behavior, Game, Unity 3D

Abstract

Artificial Intellegences in video game are important things that can challenge game player. One of them is creating character or NPC Follower (Non-player character Follower) inside the video game, such as real human/animal attitude. Artificial Intelligences have some techniques in which pathfinding is one of Artificial Intellegence techniques that is more popular in research than other techniques. The ability to do dynamic pathfinding is Dynamic Particle Chain (DPC) algorithm. This algorithm has the ability of flocking behavior called boid to explore the environment. But, the algoritm method moves from one boid’s point to another according to the nearest radius, then it will be able to increase computation time or needed time toward the target. To finish higher computation problem in dynamic pathfinding, the researcher suggests an algorithm that is able to handle dynamic pathfinding process through attractive potential field function of Artificial Potential Field to start pathfinding toward the target and flocking behavior technique to avoid the obstacle. Based on the test result by simulation of moving environment and complex, the computation time of algorithm is faster than comparison algorithms, DPC and Astar. It concludes that the suggested method can be used to decrease computation level in dynamic pathfinding.

Downloads

Download data is not yet available.

References

I. Millington and J. Funge, Artificial Intelligence for Games, Second Edition. 2009.

D. N. Adi Botea, Bruno Bouzy, Michael Buro, Christian Bauckhage, “Pathfinding in Games.†pp. 21–31, 2013.

P. Yap, “Grid-Based Path-Finding,†2002, pp. 44–55.

P. Hart, N. Nilsson, and B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,†IEEE Trans. Syst. Sci. Cybern., vol. 4, no. 2, pp. 100–107, 1968.

P. Cowling et al., “Search in Real-Time Video Games,†Artif. Comput. Intell. Games, vol. 6, pp. 1–19, 2014.

Bjornsson Yngvi, V. Bulitko, and N. Sturtevant, “TBA*: Time-Bounded A*,†IJCAI, pp. 431–436, 2009.

N. Sturtevant, V. Bulitko, and Y. Björnsson, “On learning in agent-centered search,†Proc. 9th Int. Conf. Au- tonomous Agents Multiagent Syst. (AAMAS 2010), pp. 333–340, 2010.

V. Bulitko and Y. Björnsson, “{kNN LRTA*}: Simple Subgoaling for Real-Time Search,†AIIDE 2009 - AI Interact. Digit. Entertain. Conf., pp. 2–7, 2009.

A. F. D. V Machado et al., “Real time pathfinding with genetic algorithm,†Brazilian Symp. Games Digit. Entertain. SBGAMES, pp. 215–221, 2011.

M. a. P. Garcia, O. Montiel, O. Castillo, R. Sepúlveda, and P. Melin, “Path planning for autonomous mobile robot navigation with ant colony optimization and fuzzy cost function evaluation,†Appl. Soft Comput., vol. 9, no. 3, pp. 1102–1110, 2009.

S. Liu, L. Mao, and J. Yu, “Path Planning Based on Ant Colony Algorithm and Distributed Local Navigation for Multi-Robot Systems,†2006 Int. Conf. Mechatronics Autom., pp. 1733–1738, 2006.

M. Brand, M. Masuda, N. Wehner, and Xiao-Hua Yu, “Ant Colony Optimization algorithm for robot path planning,†in 2010 International Conference On Computer Design and Applications, 2010, vol. 3, no. Iccda, pp. V3-436-V3-440.

J.-W. Lee, J.-J. Kim, and J.-J. Lee, “Improved Ant Colony Optimization Algorithm by Potential Field Concept for Optimal Path Planning,†Humanoid Robot., pp. 662–667, 2008.

H. Qu, K. Xing, and T. Alexander, “An improved genetic algorithm with co-evolutionary strategy for global path planning of multiple mobile robots,†Neurocomputing, vol. 120, pp. 509–517, 2013.

A. Tuncer and M. Yildirim, “Dynamic path planning of mobile robots with improved genetic algorithm,†Comput. Electr. Eng., vol. 38, no. 6, pp. 1564–1572, 2012.

Z. Y. Z. Yao and L. M. L. Ma, “A Static Environment-Based Path Planning Method by Using Genetic Algorithm,†Comput. Control Ind. Eng. (CCIE), 2010 Int. Conf., vol. 2, pp. 405–407, 2010.

Y. Sazaki, A. Primanita, and M. Syahroyni. "Pathfinding car racing game using dynamic pathfinding algorithm and algorithm A*" ,in Proc. -ICWT 2017 3rd Int. Conf. Wirel. Telemat. 2017, pp.164–169, July 2018.

P. Harsani, I. Mulyana, and D. Zakaria. "Fuzzy logic and A* algorithm implementation on goat foraging games", IOP Conf. Ser. Mater. Sci. Eng., Vol. 332, No. 1, 2018.

J. Espelosín, L. Acosta, and D. Alonso, “Path planning approach based on flock dynamics of moving particles,†Appl. Soft Comput. J., vol. 13, no. 4, pp. 2159–2170, 2013.

Kapi, Azyan Yusra, Mohd Shahrizal Sunar, and Muhamad Najib Zamri. "A review on informed search algorithms for video games pathfinding." International Journal 9.3, 2020.

C. W. Reynolds, “Flocks, herds and schools: A distributed behavioral model,†ACM SIGGRAPH Comput. Graph., vol. 21, no. 4, pp. 25–34, 1987.

N. R. Sturtevant, “Moving Path Planning Forward,†pp. 1–6, 2012.

C. W. Reynolds, “Steering behaviors for autonomous characters,†Game Dev. Conf., pp. 763–782, 1999.

O. Khatib, “Real-Time Obstacle Avoidance for Manipulators and Mobile Robots,†The International Journal of Robotics Research, vol. 5, no. 1. pp. 90–98, 1986.

L. Zhou and W. Li, “Adaptive Artificial Potential Field Approach for Obstacle Avoidance Path Planning,†2014 Seventh Int. Symp. Comput. Intell. Des., no. 1, pp. 429–432, 2014.

C. Zhang, M. Niu, H. Wu, J. He, and Y. Xiao, “A multi-motor synchronous control algorithm for artificial potential field with adjacent attractive force,†26th Chinese Control Decis. Conf. CCDC 2014, pp. 820–825, 2014.

M. Hazewinkel, Encyclopaedia of Mathematics (set). Springer Netherlands, 1994.

Downloads

Published

2021-09-30

How to Cite

Harsadi, P. ., Asmiatun, S. ., & Putri, A. N. . (2021). Dynamic Pathfinding for Non-Player Character Follower on Game. Jurnal Teknik Informatika C.I.T Medicom, 13(2), 55–63. https://doi.org/10.35335/cit.Vol13.2021.68.pp51-58