¹Graldy Tirta Kumala,² Wirawan Istiono

^1,2Universitas Multimedia Nusantara & Jl. Scientia Boulevard, Curug Sangereng Kelapa dua, Tangerang, Indonesia

Tower Defense is a game genre that uses a pathfinding algorithm. Pathfinding is a way to find a path from one point to another; pathfinding itself has many variants with different scenarios. One of these algorithms is the A-Star algorithm, a well- known and commonly used method for game pathfinding. Another algorithm is the Flow Field algorithm, which is an algorithm that is not widely known and has become the topic in this following research. This research will be carried out by comparing the time required by both algorithms to reach the target point from starting point, and time comparison will be carried out in 3 different scenarios. The result of the research is that the Flow Field algorithm reaches the target faster than A-Star Pathfinding in every scenario carried out in the simulation. This research concludes that the Flow Field algorithm can compete with the A-Star algorithm to find paths in the Tower Defense game.

Flow field algorithm, A-Star, Pathfinding, Artificial Intelligence, Algorithm Comparison

1) P. Avery, J. Togelius, E. Alistar, and R. P. Van Leeuwen, “Computational intelligence and tower defence games,” 2011 IEEE Congress of Evolutionary Computation, CEC 2011, no. July 2011, pp. 1084–1091, 2011, doi: 10.1109/CEC.2011.5949738.

2) S. L. Pardede, F. R. Athallah, Y. N. Huda, and F. D. Zain, “A Review of Pathfinding in Game Development,” [CEPAT] Journal of Computer Engineering: Progress, Application and Technology, vol. 1, no. 01, p. 47, 2022, doi: 10.25124/cepat.v1i01.4863.

3) N. H. Barnouti, S. S. M. Al-Dabbagh, and M. A. Sahib Naser, “Pathfinding in Strategy Games and Maze Solving Using A* Search Algorithm,” Journal of Computer and Communications, vol. 04, no. 11, pp. 15–25, 2016, doi: 10.4236/jcc.2016.411002.

4) H. Wang, S. Lou, J. Jing, Y. Wang, W. Liu, and T. Liu, “The EBS-A* algorithm: An improved A* algorithm for path planning,” PLoS ONE, vol. 17, no. 2 February, pp. 1–27, 2022, doi: 10.1371/journal.pone.0263841.

5) S. Erke, D. Bin, N. Yiming, Z. Qi, X. Liang, and Z. Dawei, “An improved A-Star based path planning algorithm for autonomous land vehicles,” International Journal of Advanced Robotic Systems, vol. 17, no. 5, pp. 1–13, 2020, doi: 10.1177/1729881420962263.

6) E. Emerson, “Crowd Pathfinding and Steering Using Flow Field Tiles,” Game AI Pro 360, pp. 67–76, 2019, doi: 10.1201/9780429055096-7.

7) A. Koesnaedi and W. Istiono, “Implementation Drunkard ’ s Walk Algorithm to Generate Random Level in Roguelike Games,” International Journal of Multidisciplinary Research and Publications, vol. 5, no. 2, pp. 97–103, 2022, [Online]. Available: Drunkard’s Walk, Guest User Satisfaction Scale, Procedural Content Generation, Video game.

8) J. Zhang, Q. Chen, M. Shi, H. Zhou, and L. Xu, “Interaction and influence of a flow field and particleboard particles in an airflow forming machine with a coupled Euler-DPM model,” PLoS ONE, vol. 16, no. 6 June, pp. 1–25, 2021, doi: 10.1371/journal.pone.0253311.

9) S. R. Lawande, G. Jasmine, J. Anbarasi, and L. I. Izhar, “A Systematic Review and Analysis of Intelligence-Based Pathfinding Algorithms in the Field of Video Games,” Applied Sciences (Switzerland), vol. 12, no. 11, 2022, doi: 10.3390/app12115499.

10) A. Hernàndez-Sabaté, M. Joanpere, N. Gorgorió, and L. Albarracín, “Mathematics learning opportunities when playing a Tower Defense Game,” International Journal of Serious Games, vol. 2, no. 4, 2015, doi: 10.17083/ijsg.v2i4.82.

11) C.-M. C. Steven K.C. Lo, Huan-Chao Keh, “A Multi-agents Coodination Mechanism to Improving Real-time Strategy on Tower Defense Game,” Journal of Applied Sciences, vol. 13, no. 5, pp. 683–691, 2013, doi: 10.3923/jas.2013.683.691.

12) S. L. Yin Fan, Chang-Hui, “12-Real-time visualization algorithm of 2D unsteady flow field.pdf,” Journal of Computer Applications, vol. 30, no. 9, p. 2434, 2010, doi: 10.3724/SP.J.1087.2010.02434.

13) A. Suryadibrata, J. C. Young, and R. Luhulima, “Review of Various A* Pathfinding Implementations in Game Autonomous Agent,” IJNMT (International Journal of New Media Technology), vol. 6, no. 1, pp. 43–49, 2019, doi: 10.31937/ijnmt.v6i1.1075.

14) N. L. Manuel, N. İnanç, and M. Y. Erten, “Control of mobile robot formations using A-star algorithm and artificial potential fields,” Journal of Mechatronics, Electrical Power, and Vehicular Technology, vol. 12, no. 2, pp. 57–67, 2021, doi: 10.14203/j.mev.2021.v12.57-67.

15) M. R. Wayahdi, S. H. N. Ginting, and D. Syahputra, “Greedy, A-Star, and Dijkstra’s Algorithms in Finding Shortest Path,” International Journal of Advances in Data and Information Systems, vol. 2, no. 1, pp. 45–52, 2021, doi: 10.25008/ijadis.v2i1.1206.

Volume 05 Issue 09 September 2022

There is an Open Access article, distributed under the term of the Creative Commons Attribution – Non Commercial 4.0 International (CC BY-NC 4.0) (https://creativecommons.org/licenses/by-nc/4.0/), which permits remixing, adapting and building upon the work for non-commercial use, provided the original work is properly cited.