Penerapan Algoritma Pathfinding A* dalam Game Dual Legacy berbasis  Android

Felix Octavian; Latius Hermawan

doi:10.24002/jbi.v14i01.6928

Authors

Felix Octavian Universitas Katolik Musi Charitas
Latius Hermawan Universitas Katolik Musi Charitas

DOI:

https://doi.org/10.24002/jbi.v14i01.6928

Keywords:

A Star (A*) algorithm, NPC, game, Android, 2D side-scrolling RPG

Abstract

A* Pathfinding Algorithm Implementation in Dual Legacy Game based on Android. Games have 2 characters, the player, and the NPC (Non-Playable Character) which cannot be controlled by the player,so the NPC movements are easy to predict. A Star (A*) algorithm is a pathfinding algorithm or finding a way to a destination, in this case searching for the closest path to the player and avoiding obstacles. The enemy NPC is tasked with chasing the player, and the enemy NPC must reduce the player's health. A* algorithm calculatesthe distance of one of the paths and then calculatesthe distance of the other paths. The algorithm will choose the shortest path when all paths have been completed. Research focuses on the NPC's task of finding the shortest route. The A* in the
“Dual Legacy” 2D Side-Scrolling RPG game based on Android is expected with this algorithm NPC can search for and chase players/players via the nearest path. The conclusion is that the A Star Algorithm has been successfully implemented, the NPC approaches the player through the shortest distance by avoiding obstacles.
Keywords: A Star (A*) algorithm, NPC, game, Android, 2D side-scrolling RPG

Penerapan Algoritma Pathfinding A* dalam Game Dual Legacy berbasis Android. Game biasanya terdapat 2 karakter yaitu player dan NPC (Non-Playable Character) yang tidak bisa dikendalikan oleh player sehingga pergerakan karakter NPC mudah ditebak. Algoritma A Star (A*) merupakan algoritma pathfinding atau mencari jalan ke tujuan, dalam kasus ini mencari jalan terdekat ke player dan menghindari rintangan yang ada. NPC musuh ini bertugas untuk mengejar player dan NPC musuhharus mengurangi darah player. Algoritma A* menghitung jarak satu jalur,
menyimpannya, lalu menghitung jarak jalur lainnya. Setelah semua jalur dihitung, algoritma A* memilih jalur terpendek . Penelitian berfokus pada tugas NPC untuk pencarian rute terdekat. Menerapkan algoritma pathfinding A* pada NPC game Dual Legacy 2D Side-Scrolling RPG berbasis Android diharapkan dengan algoritma tersebut NPC dapat mencari dan mengejar pemain / player melalui jalan terdekat. Kesimpulan perancangan ini adalah algoritma A Star berhasil diimplementasikan, NPC mendekati player melalui jarak terdekat dengan menghindari halangan yang ada.
Kata Kunci: algoritma A Star (A*), NPC, game, Android, 2D side-scrolling RPG

References

Hermawan, L and M. B. Ismiati, “Penerapan Augmented reality Berbasis Minimax Algorithm pada Game Papan Cerdas,” J. Buana Informatika, pp. 21–30, 2022.

W. Widodo and I. Ahmad, “Penerapan Algoritma A Star (A*) pada Game Petualangan Labirin Berbasis Android,” Khazanah Inform. J. Ilmu Komput. dan Inform., vol. 3, no. 2, p. 57, 2018, doi: 10.23917/khif.v3i2.5221.

T. Bhosale, S. Kulkarni, and S. N. Patankar, “2D Platformer Game in Unity Engine,” Int. Res. J. Eng. Technol., pp. 3021–3024, 2018, [Online]. Available: www.irjet.net

A. Darmawan, E. Muhammad, A. Jonemaro, and T. Afirianto, “Penerapan Dynamic Audio Pada 2D Endless Runner Game Menggunakan Pure Data,” vol. 3, no. 5, pp. 4142–4147, 2019.

T. Stanley et al., “PEMBUATAN GAME FIGHTING,” vol. 2, pp. 177–187, 2019.

Pamungkas. dkk, “Penerapan Algoritma A* ( A Star ) Pada Game Edukasi The Maze Island Berbasis Android,” Penerapan Algorithm., no. x, pp. 1–11, 2014.

B. Setiawan and L. Hermawan, “Edukasi Protokol Kesehatan Berbasis Game,” Jurnal Informatika Polinema, vol.8, no.1, pp. 25–30, 2021.

A. Pane and M. Darwis Dasopang, “Belajar Dan Pembelajaran,” FITRAHJurnal Kaji. Ilmuilmu Keislam., vol. 3, no. 2, p. 333, 2017, doi: 10.24952/fitrah.v3i2.945.

Winata H and Liliana, “Meningkatkan Variasi Tindakan Non-Playable Character Pada Game Survival Menggunakan Metode Markov", Jurnal INFRA, vol.8, no.2, 2021.

Jaya, Hendra and Sabran, "Kecerdasan Buatan". Fakultas MIPA Universitas Negeri Makassar, pp. 1-315, 2018.

I. P. W. Merta, I. M. G. Sunarya, and I. K. R. Arthana, “Handgesture To Text Dengan Metode Artificial intelligence KNN (K-Nearest Neighbour),” KARMAPATI (Kumpulan Artik. Mhs. Pendidik. Tek. Inform., vol. 4, no. 1, pp. 18–27, 2015, [Online]. Available:

https://ejournal.undiksha.ac.id/index.php/KP/article/view/19789

Zhu, X. "Behavior tree design of intelligent behavior of non-player character (NPC) based on Unity3D". Journal of Intelligent and Fuzzy Systems, 37(5), 6071–6079, 2019.

Jeon. "An Implementation of Othello Game Player Using ANN based Records Learning and Minimax Search Algorithm". The Transactions of The Korean Institute of Electrical Engineers. 2018.

Hidayat, E. W. "Penerapan Finite State Machine pada Battle Game Berbasis Augmented Reality". Jurnal Edukasi Dan Penelitian Informatika (JEPIN), 5(1), 54, 2019.

Mustofa, S. and Rahmawati, E. "Penerapan Finite State Machine Untuk Pengendalian Animasi Pada Video Game RPG Nusantara Legacy". Jurnal Sistem Komputer Musi Rawas, vol. 03, no. 01, 2018.

Sunandar U., Raharjo AS. "Perancangan Permainan Ular Tangga Berbasis Virtual Reality Dengan Algoritma Random Number Generator". e-Proceeding of Engineering : Vol.8, No.5 Oktober 2021

P. L. Ekawati and A. Z. Fallani, "Pemanfaatan Teknologi Game Untuk Pembelajaran Ragam Budaya Indonesia Berbasis Android," Jurnal Link, pp. 5-30, 2015.

Hermawan, L, Malla M., Ismiati MB. “Penerapan Algoritma PRNG Dalam Permainan Snack and Ladders Berbasis Digital". Jurnal Informatika Upgris Vol 8, No 2, 2022.

Calvinus W. "Implementasi Algoritma Minimax Dalam Game Othello". JTIUST, Volume 02 Nomor 01, Juni 2017.

Hermawan L, Hariadi M, Basuki RS. "Koordinasi Nonplayer Character Follower Menggunakan Algoritma Potential Fields Berbasis Multibehaviour". Jurnal Cyberku Volume 13 No 1. 2017

Minsong Liu. "An Improved Minimax-Q Algorithm Based on Generalized Policy Iteration to Solve a Chaser-Invader Game". Auckland University of Technology. IEEE Xplore. 2020.

K. Rokoyah, Y. I. Chandra, and S. Lukman, “PENERAPAN MODEL INCREMENTAL DALAM MERANCANG APLIKASI PENGENALAN BENTUK DAN FUNGSI GIGI PADA MANUSIA BERBASIS WEB,” 2022.