Penerapan Algoritma A* Untuk Pencarian Rute Terdekat Pada Permainan Berbasis Ubin (Tile Based Game)

Abstract

Penggunaan Kecerdasan Buatan (Artificial Intelligence) pada sebuah permainan bertujuan untuk membuatnya lebih menarik. Beberapa jenis kecerdasan buatan dapat diterapkan pada sebuah game, salah satunya yaitu algoritma pathfinding yang merupakan kecerdasan buatan yang dapat
menemukan lintasan terpendek. Salah satu algoritma pathfinding yang seringkali digunakan adalah Algoritma A*. Algoritma A*(AStar) merupakan algoritma Best First Search yang menggabungkan Uniform Cost Search dan Greedy Best-First Search. Cost yang diperhitungkan didapat dari cost
sebenarnya ditambah dengan cost perkiraan. Dengan perhitungan cost seperti ini, algoritma A*(AStar) dapat optimal dan lengkap dalam menentukan jalur. Permainan berbasis ubin merupakan permainan yang menggunakan ubin (tile) sebagai salah satu elemen dasar dalam permainan. Dimana gambar-gambar background game yang terlalu besar dipotong menjadi kotak-kotak kecil seperti ubin atau dikenal dengan istilah tiles. Selanjutnya potongan-potongan map tersebut akan dipanggil ke dalam game dengan fungsi array untuk membentuk pola map game. Berdasarkan hasil pengujian algoritma A*(AStar) yang digunakan pada game ini teruji 100% efektif untuk menemukan jalur terpendek dari
pergerakan objek dalam game. Pengujian heuristik pada algoritma A*(AStar), jalur terpendek yang ditemukan adalah sama, namun rute yang di gunakan dari tiap heuristik berbeda