Meningkatkan Efisiensi Pencarian Jalur Pada Game Berbasis Tile Menggunakan Algoritma A* Dengan Penambahan Parameter Heuristik

Zaidan Rahadian Huda

Abstract


Algoritma A* merupakan algoritma populer yang digunakan dalam pencarian jalur karena keefektifannya dalam menemukan rute terpendek. Dalam lingkungan seperti game terutama game berbasis tile, keberadaan rintangan atau jebakan dapat memengaruhi efisiensi jalur yang diambil. Penelitian ini mengusulkan modifikasi pada fungsi heuristik A* dengan menambahkan nilai penalti ketika algoritma mendeteksi adanya rintangan atau jebakan di sekitar jalur. Tujuan dari modifikasi ini adalah untuk meningkatkan efisiensi serta menghasilkan jalur yang lebih aman dan realistis bagi karakter dalam permainan. Pengujian dilakukan pada delapan jenis lingkungan berbeda yang memiliki tingkat kerumitan dan rintangan bervariasi. Hasil penelitian menunjukkan bahwa modifikasi heuristik pada algoritma A* mampu menghasilkan jalur yang lebih aman, serta meningkatkan efisiensi dalam sebagian besar skenario. Meskipun pada satu lingkungan hasil yang diperoleh serupa dengan algoritma A* standar, algoritma yang dimodifikasi tetap menunjukkan keunggulan dari segi pemilihan jalur yang lebih aman dan sesuai konteks permainan. Dengan demikian, pendekatan ini dapat menjadi alternatif yang efektif untuk implementasi pathfinding dalam pengembangan game berbasis tile.


Keywords


Algoritma A*; Heuristik; Pencarian Jalur; Modifikasi Heuristik; Game Berbasis Tile

Full Text:

PDF

References


S. Nasution, A. H. Nasution, and A. L. Hakim, “Pembuatan Plugin Tile-Based Game Pada Unity 3D,” IT J. Res. Dev., vol. 4, no. 1, pp. 46–60, Aug. 2019, doi: 10.25299/itjrd.2019.vol4(1).3517.

P. Yap, “New Ideas in Pathfinding,” in Artificial Intelligence and Interactive Entertainment II, Stanford, CA: AAAI, 2002, pp. 95–97. [Online]. Available: https://cdn.aaai.org/Symposia/Spring/2002/SS-02-01/SS02-01-018.pdf

X. Cui and H. Shi, “A*-based Pathfinding in Modern Computer Games,” vol. 11, no. 1, pp. 125–130, 2011.

E. Sumantri and S. Hidayatullah, “Penerapan Algoritma A* pada Pencarian Rute Terpendek pada Rute Angkot Di Kota Sukabumi,” vol. 8, no. 1, pp. 21–35, 2020, doi: https://doi.org/10.55338/saintek.v5i2.1432.

H. Hermawan and H. Setiyani, “IMPLEMENTASI ALGORITMA A-STAR PADA PERMAINAN KOMPUTER ROGUELIKE BERBASIS UNITY,” J. Algoritma Log. Dan Komputasi, vol. 2, no. 1, May 2019, doi: 10.30813/j-alu.v2i1.1571.

D. Foead, A. Ghifari, M. B. Kusuma, N. Hanafiah, and E. Gunawan, “A Systematic Literature Review of A* Pathfinding,” Procedia Comput. Sci., vol. 179, pp. 507–514, Jan. 2021, doi: 10.1016/j.procs.2021.01.034.

C. Niu, A. Li, X. Huang, W. Li, and C. Xu, “Research on Global Dynamic Path Planning Method Based on Improved A ∗ Algorithm,” Math. Probl. Eng., vol. 2021, no. 1, p. 4977041, 2021, doi: 10.1155/2021/4977041.

Z. Li and H. Li, “Study of the Interception Scheme Based on A* Path Finding Algorithm in Computer Game,” J. Comput. Commun., vol. 08, no. 07, pp. 32–49, 2020, doi: 10.4236/jcc.2020.87004.




DOI: https://doi.org/10.62411/tcv.v3i1.3241

Refbacks

  • There are currently no refbacks.


Copyright (c) 2026 Zaidan Rahadian Huda