IMPLEMENTASI ALGORITMA A* UNTUK MENENTUKAN PERGERAKAN NPC(NON-PLAYABLE CHARACTER) PADA GAME HUNGRY PIGS

Sebuah karakter pada game biasanya memerlukan pergerakan untuk dapat melewati tiap levelnya. Dan biasanya juga seorang pembuat game menentukan pergerakannya secara statis dimana rute dari pergerakan karakter tersebut akan selalu sama secara berulang, kelemahannya karakter ini tidak memiliki tujuan(aimless) dan sangat mudah terjebak(stuck). Penanggulangannya adalah dengan menggunakan AI(Artificial Intelligence) pada pergerakannya, dimana nantinya karakter yg mempunyai AI ini akan bergerak dengan cara mencari jalurnya sendiri(path finding). Game pathfinding yang dibuat dengan AI(Artificial Intelligence) tersebut menerapkan algoritma A* (A Star). Algoritma ini digunakan untuk menentukan pilihan jalan terpendek menuju titik tujuan, untuk mengetahui performansi dalam hal waktu pencarian, jumlah langkah dari titik awal menuju titik tujuan dan simpul yang diperiksa pada game pathfinding. Penerapan algoritma A* dalam game pathfinding dibuat berdasarkan prosedur A* untuk mendapatkan langkah terbaik dari posisi titik awal. Algoritma A* merupakan perbaikan dari metode best-first search (BFS) dengan menggunakan fungsi heuristic. Fungsi heuristic yang terkenal ada dua yakni Euclidean dan Manhattan distance, dimana pada masing-masing heuristik memiliki kelebihan dan kekurangan. Dengan melakukan implementasi algoritma A* pada Non-Playable Character di game Hungry Pigs penulis telah mencoba melakukan beberapa pengujian dan penyesuaian pada fungsi heuristik yang digunakan sehingga didapatkan hasil yang cukup mengejutkan. Diharapkan kedepannya ada lagi yang akan melakukan penelitian lebih lanjut sehingga hasil yang dicapai menjadi lebih baik lagi