Issue

Vol. 11, No. 4, November 2026 (Article in Progress)

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Optimizing Non-Playable Characters Navigation through the A-Star Algorithm in Complex 3D Game Environments

https://doi.org/10.22219/kinetik.v11i4.2482
Muttabik Fathul Lathief
Politeknik Negeri Semarang
Liliek Triyono
Politeknik Negeri Semarang
Bhatinden Sejiarga Ergun Giortagma
Politeknik Negeri Semarang
Dedy Setiawan Eka Arianto
Politeknik Negeri Semarang
Mosiur Rahaman
Asia University, Taiwan
Karisma Trinanda Putra
Universitas Muhammadiyah Yogyakarta

Corresponding Author(s) : Muttabik Fathul Lathief

muttabik.fathul@polines.ac.id

Kinetik: Game Technology, Information System, Computer Network, Computing, Electronics, and Control, Vol. 11, No. 4, November 2026 (Article in Progress)

Abstract

This study presents the implementation and evaluation of the A-Star algorithm for adaptive navigation of Non-Playable Characters (NPCs) in three-dimensional game environments. The research addresses the need for intelligent pathfinding systems that enhance player engagement through realistic NPC behavior and dynamic environmental adaptation. A comprehensive experimental framework compared A-Star against Dijkstra's algorithm and Unity NavMesh across four maze environments with varying complexity and terrain penalty systems. The implementation employs a grid-based environment model with 8-connected neighborhood topology, integrating terrain penalty systems for intelligent route selection. Performance evaluation utilized six metrics: execution time, path quality, waypoint count, total path length, character traversal time, and navigation success rate. Testing involved 10 iterations per algorithm per environment, totaling 120 experimental trials. Results demonstrate A-Star's superior computational efficiency, achieving the fastest average execution time of 0.01272 seconds compared to Dijkstra (0.01775 seconds) and Unity NavMesh (0.02055 seconds), representing 28.3% and 38.1% performance improvements respectively. A-Star exhibited unique intelligent adaptation, selecting alternative routes to avoid high-penalty terrain in 30% of test cases, while other algorithms showed no adaptive behavior. All algorithms achieved 100% pathfinding success rates. Performance consistency analysis revealed trade-offs between speed and stability. A-Star demonstrated higher variability (CV = 33.45%) reflecting adaptive computational behavior, while Unity NavMesh exhibited greater consistency (CV = 23.5%). The findings validate A-Star as an optimal solution for modern games requiring adaptive NPC behavior, contributing to intelligent navigation systems that enhance gameplay dynamics.

Keywords

A-Star NPC Navigation 3D Game Pathfinding Intelligent Behavior Performance Analysis
Lathief, M. F., Liliek Triyono, Bhatinden Sejiarga Ergun Giortagma, Dedy Setiawan Eka Arianto, Mosiur Rahaman, & Karisma Trinanda Putra. (2026). Optimizing Non-Playable Characters Navigation through the A-Star Algorithm in Complex 3D Game Environments. Kinetik: Game Technology, Information System, Computer Network, Computing, Electronics, and Control, 11(4). https://doi.org/10.22219/kinetik.v11i4.2482
Download Citation
Endnote/Zotero/Mendeley (RIS)
BibTeX
References
  1. C. Ying, C. Yuhang, and W. Yaodong, “Research on Monster Path Planning Scheme in Horror Game Based on Whale optimization Algorithm,” 2021 IEEE 6th Int. Conf. Intell. Comput. Signal Process. ICSP 2021, no. Icsp, pp. 111–114, 2021, https://doi.org/10.1109/ICSP51882.2021.9408889
  2. R. Kolchmeyer, A. Dobson, and K. E. Bekris, “Expected path degradation when searching over a sparse grid hierarchy,” Proc. 8th Annu. Symp. Comb. Search, SoCS 2015, vol. 2015-Janua, pp. 176–180, 2015, https://doi.org/10.1609/socs.v6i1.18379
  3. H. Xu, L. Shu, and M. Huang, “Planning paths with fewer turns on grid maps,” Proc. Int. Symp. Comb. Search, vol. 4, no. 1, pp. 193–200, Aug. 2021. https://doi.org/10.1609/socs.v4i1.18298
  4. K. C. Lamia, A. S. M. Lumenta, and B. A. Sugiarso, “Implementasi Algoritma A* (A Star) Pada Game 3D Kebudayaan Suku Minahasa,” J. Tek. Elektro dan Komput., vol. 11, no. 2, p. 55, 2022, https://doi.org/10.35793/jtek.v11i2.40153
  5. G. Prajena et al., “The adventure of BipBop: An android app pathfinding adventure game,” Adv. Sci. Technol. Eng. Syst., vol. 5, no. 2, pp. 299–304, 2020, http://dx.doi.org/10.25046/aj050239
  6. H. Bai, “Game Pathfinding System Design based on A-Star Pathfinding Algorithm,” vol. 0, pp. 57–63, 2024, http://dx.doi.org/10.54254/2755-2721/94/2024MELB0067
  7. A. Geramifard, P. Chubak, and V. Bulitko, “Biased cost pathfinding,” Proc. 2nd Artif. Intell. Interact. Digit. Entertain. Conf. AIIDE 2006, pp. 112–114, 2021, https://doi.org/10.1609/aiide.v2i1.18756
  8. T. K. Nobes, D. D. Harabor, M. Wybrow, and S. D. C. Walsh, “The Jump Point Search Pathfinding System in 3D Introduction and Related Work,” SoCS： Int. Symp. Comb. Search, no. iii, 2022, https://doi.org/10.1609/socs.v15i1.21762
  9. F. Badri and M. F. Al Habib, “IMPLEMENTASI ALGORITMA A* (A Star) PADA NPC (NON-PLAYABLE CHARACTER) GAME PACMAN MENGGUNAKAN GAME ENGINE UNITY 5 BERBASIS ANDROID,” Tek. Eng. Sains J., vol. 4, no. 2, p. 49, 2020, https://doi.org/10.51804/tesj.v4i2.295.49-56
  10. F. Zufar Ardana, A. Fahrudi Setiawan, and F. Santi Wahyuni, “Perancangan Game 3D Maggie’S Odyssey Dengan Metode Pathfinding,” JATI (Jurnal Mhs. Tek. Inform., vol. 7, no. 4, pp. 2411–2418, 2023, https://doi.org/10.36040/jati.v7i4.7532
  11. 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,” Appl. Sci., vol. 12, no. 11, 2022, https://doi.org/10.3390/app12115499
  12. Z. Abd Algfoor, M. S. Sunar, and H. Kolivand, “A comprehensive study on pathfinding techniques for robotics and video games,” Int. J. Comput. Games Technol., vol. 2015, 2015, http://dx.doi.org/10.1155/2015/736138
  13. I. Zarembo and S. Kodors, “Pathfinding algorithm efficiency analysis in 2D grid,” Vide. Tehnol. Resur. - Environ. Technol. Resour., vol. 2, no. June, pp. 46–52, 2013, http://dx.doi.org/10.17770/etr2013vol2.868
  14. L. M. Duc, A. S. Sidhu, and N. S. Chaudhari, “Hierarchical Pathfinding and AI‐Based Learning Approach in Strategy Game Design,” Int. J. Comput. Games Technol., vol. 2008, no. 1, 2008, http://dx.doi.org/10.1155/2008/873913
  15. A. Nash, K. Daniel, S. Koenig, and A. Feiner, “Theta*: Any-angle path planning on grids,” Proc. Natl. Conf. Artif. Intell., vol. 2, pp. 1177–1183, 2007. http://dx.doi.org/10.1613/jair.2994
  16. A. Botea, M. Müller, and J. Schaeffer, “Near optimal hierarchical path-finding,” J. game Dev., no. January 2004, pp. 1–30, 2004, [Online]. Available: https://www.researchgate.net/publication/228785110_Near_optimal_hierarchical_path-finding_HPA
  17. A. Kherrour, M. Robol, M. Roveri, and P. Giorgini, “A multi-algorithm pathfinding method: Exploiting performance variations for enhanced efficiency,” Ann. Math. Artif. Intell., 2024, https://doi.org/10.1007/s10472-024-09957-3
  18. N. Sturtevant and M. Buro, “Improving collaborative pathfinding using map abstraction,” Proc. 2nd Artif. Intell. Interact. Digit. Entertain. Conf. AIIDE 2006, pp. 80–85, 2006, https://doi.org/10.1609/aiide.v2i1.18750
  19. D. Harabor and A. Grastien, “Improving jump point search,” Proc. Int. Conf. Autom. Plan. Sched. ICAPS, vol. 2014-Janua, no. January, pp. 128–135, 2014, http://dx.doi.org/10.1609/icaps.v24i1.13633
  20. S. L. Pardede, F. R. Athallah, Y. N. Huda, and F. D. Zain, “A Review of Pathfinding in Game Development,” [CEPAT] J. Comput. Eng. Progress, Appl. Technol., vol. 1, no. 01, p. 47, 2022, http://dx.doi.org/10.25124/cepat.v1i01.4863
  21. A. Rafiq, T. Asmawaty Abdul Kadir, and S. Normaziah Ihsan, “Pathfinding Algorithms in Game Development,” IOP Conf. Ser. Mater. Sci. Eng., vol. 769, no. 1, 2020, http://dx.doi.org/10.1088/1757-899X/769/1/012021
  22. J. Hagelbäck, “Hybrid Pathfinding in StarCraft,” IEEE Trans. Comput. Intell. AI Games, vol. 8, no. 4, pp. 319–324, 2016, http://dx.doi.org/10.1109/TCIAIG.2015.2414447.
  23. G. Airlangga, “A comparative analysis of pathfinding algorithms in static environments: modified A*, PSO, and FLA,” J. Mantik, vol. 7, no. 4, pp. 2685–4236, 2024. https://doi.org/10.35335/mantik.v7i4.4795
  24. P. E. Hart, N. J. Nilsson, and B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” IEEE Trans. Syst. Sci. Cybern., no. 2, pp. 100–107, 1968. https://doi.org/10.1109/TSSC.1968.300136
  25. O. Amine and M. Mohammed, “Generating A-Star Algorithm Admissible Heuristics Using a Dynamic Dataloader on Neural Networks, Enhanced With Genetic Algorithms, on a Distributed Architecture,” IEEE Access, vol. 11, no. February, pp. 18356–18373, 2023, https://doi.org/10.1109/ACCESS.2023.3247773
  26. S. Koenig and M. Likhachev, “Fast replanning for navigation in unknown terrain,” IEEE Trans. Robot., vol. 21, no. 3, pp. 354–363, 2005, https://doi.org/10.1109/TRO.2004.838026
  27. T. Uras, S. Koenig, and C. Hernández, “Subgoal graphs for optimal pathfinding in eight-neighbor grids,” ICAPS 2013 - Proc. 23rd Int. Conf. Autom. Plan. Sched., no. Botea, pp. 224–232, 2013, https://doi.org/10.1609/icaps.v23i1.13568
  28. W. Zeng and R. L. Church, “Finding shortest paths on real road networks: The case for A,” Int. J. Geogr. Inf. Sci., vol. 23, no. 4, pp. 531–543, 2009, http://dx.doi.org/10.1080/13658810801949850
  29. V. Bulitko, N. Sturtevant, J. Lu, and T. Yau, “Graph abstraction in real-time heuristic search,” J. Artif. Intell. Res., vol. 30, no. June, pp. 51–100, 2007, https://doi.org/10.1613/jair.2293
  30. A. Stentz, “Optimal and Efficient Path Planning for Partially-Known Environments,” Int. J. Robot. Autom., vol. 10, no. 3, pp. 89–100, 1995. https://doi.org/10.1007/978-1-4615-6325-9_11
  31. N. R. Sturtevant, “Benchmarks for grid-based pathfinding,” IEEE Trans. Comput. Intell. AI Games, vol. 4, no. 2, pp. 144–148, 2012, https://doi.org/10.1109/TCIAIG.2012.2197681
  32. O. Shechtman, “The Coefficient of Variation as an Index of Measurement Reliability,” no. Cv, pp. 39–49, 2013, http://dx.doi.org/10.1007/978-3-642-37131-8_4
Read More
Author biographies is not available.
Download this PDF file
Statistic
Read Counter : 0

Downloads

Download data is not yet available.