Penerapan Algoritma A-Star sebagai Metode Pathfinding pada Game Lokasi Logika Cerdas untuk Non-Player Character

Kevin Gibran; Rudi Heriansyah; Zaid Romegar Mair

doi:10.33506/insect.v12i01.5508

Authors

Kevin Gibran Program Studi Teknik Informatika, Universitas Indo Global Mandiri
Rudi Heriansyah Program Studi Teknik Informatika, Universitas Indo Global Mandiri
Zaid Romegar Mair Program Studi Teknik Informatika, Universitas Indo Global Mandiri

DOI:

https://doi.org/10.33506/insect.v12i01.5508

Keywords:

Game, A-Star, Pathfinding, Non-Player Character, Heuristic, Roblox Studio

Abstract

Perkembangan game simulasi modern menuntut sistem navigasi Non-Player Character (NPC) yang efisien dan adaptif dalam lingkungan virtual yang kompleks. Algoritma A-Star (A*) banyak digunakan dalam pathfinding karena mengombinasikan biaya aktual dan estimasi heuristic untuk menghasilkan jalur optimal. Namun, performanya dipengaruhi oleh jenis heuristic yang digunakan. Penelitian ini bertujuan mengimplementasikan A* pada sistem navigasi NPC berbasis Roblox Studio serta menganalisis kinerja Manhattan Distance dan Euclidean Distance. Metode yang digunakan adalah eksperimen komputasional pada tiga tingkat kompleksitas map (25×25, 50×50, dan 75×75 node) dengan dua mode pergerakan, yaitu 4-arah dan 8-arah. Parameter evaluasi meliputi waktu pencarian, panjang jalur, dan tingkat optimalitas. Hasil menunjukkan bahwa Manhattan Distance lebih efisien dalam waktu pencarian, terutama pada map Level 3 mode 8-arah (1.220,1 ms dibandingkan 6.990,5 ms pada Euclidean Distance). Sebaliknya, Euclidean Distance menghasilkan jalur lebih pendek dan optimal pada mode 8-arah (99 node dibandingkan 106 node pada Manhattan Distance). Temuan ini menunjukkan adanya trade-off, yaitu tidak bisa mendapatkan semuanya sekaligus secara maksimal antara efisiensi waktu dan kualitas jalur. Penelitian ini memberikan dasar empiris dalam pemilihan heuristic yang sesuai untuk sistem navigasi NPC tiga dimensi.

References

[1] U. Wilhelmsson, W. Wang, R. Zhang, and M. Toftedahl, “Shift from game-as-a-product to game-as-a-service research trends,” Serv. Oriented Comput. Appl., vol. 16, no. 2, pp. 79–81, 2025, doi: 10.1007/s11761-022-00335-7.

[2] Z. R. Mair, “Strategi Pendekatan Konsep Pemrograman Dasar Komputer Dengan Game Dan Storytelling,” vol. 3, no. 3, pp. 229–236, 2023, doi: 10.23960/jpkmt.v3i3.99.

[3] Z. R. Mair, Coding Asyik For Kids. Yogyakarta: Deepublish, 2024.

[4] N. Al, S. Kanaka, R. Heriansyah, and S. Puspasari, “TIN : Terapan Informatika Nusantara Perbandingan Algoritma Decision Tree dan Support Vector Machine Dalam Pemilihan Calon Mahasiswa Penerima KIP-K TIN : Terapan Informatika Nusantara,” vol. 4, no. 9, pp. 613–619, 2024, doi: 10.47065/tin.v4i9.4902.

[5] Z. R. Mair, M. H. Irfani, and D. Marcelina, “Kajian Bakat Anak Melalui Pola Tulisan Tangan dengan Algoritma Convolutional Neural Network .,” vol. 10, no. 2, pp. 66–71, 2022.

[6] Z. R. Mair, W. Cholil, E. Yulianti, D. Marcelina, Theresiawati, and I. N. Isnainiyah, “Convolutional Neural Network Analysis on Handwriting Patterns and Its Relationship to Personality : A Systematical Review,” pp. 308–312, 2023.

[7] E. G. Agung, D. Eridani, and A. Fauzi, “Implementasi Metode Pathfinding dengan Algoritma A * pada Game Rogue-like menggunakan Unity,” vol. 7, no. December, pp. 81–94, 2022, doi: 10.34818/indojc.2022.7.3.677.

[8] A. C. Rizki, K. R. Athallah, S. M. Siddiq, and Z. Kusmanidar, “Performance Analysis of Dijkstra and A-star Algorithm in Maritime Navigation Pathfinding,” vol. 2, no. 2, pp. 31–50, 2025.

[9] U. Affandi, S. Iskandar, N. M. Diah, M. Ismail, and A. Abdullah, “Comparing the efficiency of Pathfinding Algorithms for NPCs in platform games,” J. Posit. Sch. Psychol., vol. 6, no. 3, pp. 8434–8441, 2022.

[10] R. N. Sarbini, I. Ahmad, R. O. Bura, and L. Simbolon, “COMPARATIVE ANALYSIS OF PATHFINDING ARTIFICIAL INTELLIGENCE USING DIJKSTRA AND A * ALGORITHMS BASED ON RPG MAKER MV,” 2020.

[11] R. P. Cahyani and R. Heriansyah, “Identification of Ginger Varieties Using Manhattan Distance on Image Pixel Vectors and Histograms,” vol. 8, no. 2, 2025, doi: 10.32877/bt.v8i2.3019.

[12] F. S. Esen, H. Tinmaz, and M. Singh, Metaverse: Technologies, Opportunities and Threats, 1st ed. in Studies in Big Data. Beach Road: Springer Nature Singapore, 2023. [Online]. Available: https://books.google.co.id/books?id=iMfcEAAAQBAJ

[13] Y. Zhang, “ASL-DWA : An Improved A-Star Algorithm for Indoor Cleaning Robots,” IEEE Access, vol. 10, no. August, pp. 99498–99515, 2022, doi: 10.1109/ACCESS.2022.3206356.

[14] R. Mussabayev, “Optimizing Euclidean Distance Computation,” pp. 1–36, 2024.

[15] M. Kiepe, Mastering Roblox Coding: The unofficial guide to leveling up your Roblox scripting skills and building games using Luau programming, 1st ed. Birmingham: Packt Publishing, 2022. [Online]. Available: https://books.google.co.id/books?id=YG1_EAAAQBAJ