A Review of Pathfinding in Game Development
DOI:
https://doi.org/10.25124/cepat.v1i01.4863Keywords:
Pathfinding, Game Programming, A* Algorithm, Dijkstra, Breadth First Search, Theta*Abstract
Pathfinding is one important method in many studies or works that consists of autonomous movement, such as robot, game, transportation, and so on. Pathfinding aims to find the most efficient route for the related autonomous entity. To date, there are many algorithms regarding to the pathfinding. Especially, there are four well-known pathfinding algorithms: A*, Theta*, Dijkstra, and Breadth First Search (BFS). Due to this circumstance, this work aims to observe and review these four well-known algorithms deeper. The discussion consists of the conceptual model or framework, the formalization, and the implementation. The result shows that these algorithms have been implemented in many game so that they are promising to be used in the future game development.
Downloads
References
Y. Sazaki, H. Satria and M. Syahroyni, "Comparison of A and dynamic pathfinding algorithm with dynamic pathfinding algorithm for NPC on car racing game," in 11th International Conference on Telecommunication Systems Services and Applications (TSSA), 2017.
D. Kurniadi, A. Mulyani and R. S. Maolani, "Implementation of Pathfinding Algorithm in Sundanese Land History Educational Game," in 2nd International Conference on Innovative and Creative Information Technology (ICITech), 2021.
G. T. Galam, T. P. Remedio and M. A. Dias, "Viral Infection Genetic Algorithm with Dynamic Infectability for Pathfinding in a Tower Defense Game," in 18th Brazilian Symposium on Computer Games and Digital Entertainment (SBGames), 2019.
L. Husniah, R. Mahendra and A. S. Kholimi, "Comparison Between A* And Obstacle Tracing Pathfinding In Gridless Isometric Game," in 2018 5th International Conference on Electrical Engineering, Computer Science and Informatics (EECSI), 2018.
A. N. Sabri, N. H. Radzi and A. A. Samah, "A study on Bee algorithm and A algorithm for pathfinding in games," in 2018 IEEE Symposium on Computer Applications & Industrial Electronics (ISCAIE), 2018.
J. Smo?ka, K. Miszta, M. Skublewska-Paszkowska and E. ?ukasik, "A* pathfinding algorithm modification for a 3D engine," in III International Conference of Computational Methods in Engineering Science (CMES’18), 2019.
L. Husniah, R. Mahendra, A. S. Kholimi and E. Cahyono, "Comparison Between A And Obstacle Tracing Pathfinding In Gridless Isometric Game," in 2018 5th International Conference on Electrical Engineering, Computer Science and Informatics (EECSI), 2018.
T. Subrando, D. Fitrianah and F. A. Prasetyatama, "Implementation of a* algorithm within navigation mesh in an artificial intelligence based video games," in International Journal of Engineering & Technology (IJET), 2018.
Y. Sazaki, H. Satria and M. Syahroyni, "Comparison of A and dynamic pathfinding algorithm with dynamic pathfinding algorithm for NPC on car racing game," in 2017 11th International Conference on Telecommunication Systems Services and Applications (TSSA), 2017.
A. Candra, M. A. Budiman and R. I. Pohan, "Application of A-Star Algorithm on Pathfinding Game," in 5 th International Conference on Computing and Applied Informatics (ICCAI 2020), 2020.
P. Harsani, I. Mulyana and D. Zakaria, "Fuzzy logic and A* algorithm implementation on goat foraging games," in IOP Conference Series: Materials Science and Engineering., 2017.
N. Barnouti, S. Al-Dabbagh and M. Naser, "Pathfinding in Strategy Games and Maze Solving Using A* Search Algorithm," in Journal of Computer and Communications, 2016.
S. Permana, B. Arifitama, K. Bintoro and A. Syahputra, "Comparative Analysis of Pathfinding Algorithms A *, Dijkstra, and BFS on Maze Runner Game," International Journal of Information System and Technology, vol. 1, no. 2, 2018.
Y. F. Yiu, J. Du and R. Mahapatra, "Evolutionary Heuristic A Search: Heuristic Function Optimization via Genetic Algorithm," in 2018 IEEE First International Conference on Artificial Intelligence and Knowledge Engineering (AIKE), 2018.
K. Daniel, A. Nash, S. Koenig and A. Felner, "Theta*: Any-Angle Path Planning on Grids," in arXiv e-prints, 2014.
B. P. Le and L. Ki-dong, "Applying Dynamic Weight on Theta Star Path-finding Algorithm in 2D Grid Map," in 2015 International Conference on Intelligent Computing, Electronics System and Information Technology, 2015.
E. R. Firmansyah, S. U. Masruroh and F. Fahrianto, "Comparative Analysis of A and Basic Theta Algorithm in Android-Based Pathfinding Games," in 6th International Conference on Information and Communication Technology for The Muslim World (ICT4M), 2016.
P. T. Le, N. T. Truong, M. S. Kim, W. So and J. H. Jung, "Applying Theta* in Modern Game," Journal of Computers, vol. 13, no. 5, 2018.
P. Mendonca and S. Goodwin, "C-Theta: Cluster Based Path-Planning on Grids," in 2015 International Conference on Computational Science and Computational Intelligence (CSCI), 2015.
S. Oh and H. W. Leong, "Strict Theta*: Shorter Motion Path Planning Using Taut Paths," in Twenty-Sixth International Conference on Automated Planning and Scheduling (ICAPS 2016), 2016.
S. D. Permana, K. B. Bintoro, B. Arifitama and A. Syahputra, "Maze Runner: Angel and Demon Path Finding Game Application using C-Theta* Algorithm," in The 1st International Conference on Computer Science and Engineering Technology, 2018.
A. Fitro, O. S. Bachri, A. I. S. Purnomo and I. Frendianata, "Shortest path finding in geographical information systems using node combination and dijkstra algorithm," International Journal of Mechanical Engineering and Technology (IJMET), vol. 9, no. 2, pp. 755-760, 2018.
G. Qing, Z. Zheng and X. Yue, "Path-planning of Automated Guided Vehicle based on Improved Dijkstra," in 2017 29th Chinese Control And Decision Conference (CCDC), 2017.
Yujin and G. Xiaoxue, "Optimal Route Planning of Parking Lot Based on Dijkstra Algorithm," in International Conference on Robots & Intelligent System, 2017.
M. Iqbal, K. Zhang, S. Iqbal and I. Tariq, "A Fast and Reliable Dijkstra Algorithm for Online Shortest Path," SSRG International Journal of Computer Science and Engineering ( SSRG – IJCSE ), vol. 5, no. 12, 2018.
A. Bozyi?it, G. Alanku? and E. Nasibo?lu, "Public Transport Route Planning: Modified Dijkstra's," in International Conference on Computer Science and Engineering (UBMK), 2017.
X. Z. Wang, "The Comparison of Three Algorithms in Shortest Path Issue," in Journal of Physics Conference Series, 2018.
H. Jason, "The Nature of Breadth-First Search," in School of Computer Science, Mathematics, and Physics James Cook University Australia, 2019.
V. Palanisamy and S. Vijayanathan, "Cluster Based Multi Agent System for Breadth First Search," in 2020 20th International Conference on Advances in ICT for Emerging Regions (ICTer), 2021.
S. Sularno, D. P. Mulya, R. Astri and D. Mulya, "Determination of The Shortest Route Based on BFS Algorithm for Purpose to Disaster Evacuation Shelter," Scientific Journal of Informatics, vol. 8, no. 1, 2021.
S. Permana, K. Bintoro, B. Arifitama and A. Syahputra, "Comparative Analysis of Pathfinding Algorithms A*, Dijkstra, and BFS on Maze Runner Game," International Journal of Information System and Technology, vol. 1, no. 2, 2018.
F. Zhang, H. Lin, J. Zhai, J. Cheng, D. Xiang, J. Li, Y. Chai and X. Du, "An Adaptive Breadth-?rst Search Algorithm on Integrated Architectures," The Journal of Supercomputing, vol. 74, p. 6135–6155, 2018.
T. N. Lina and M. S. Rumetna, "Comparison Analysis of Breadth First Search and Depth Limited Search Algorithms in Sudoku Game," Bulletin of Computer Science and Electrical Engineering, vol. 2, no. 2, pp. 74-83, 2021.
Downloads
Published
Issue
Section
License
CEPAT has chosen to apply the Creative Commons Attribution NonCommercial 4.0 License (CC BY-NC 4.0) to all manuscripts to be published. Authors who publish with this journal agree to the following terms.
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgment of the work’s authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal’s published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
