Implementasi Dan Analisis Algoritma A*(star) Untuk Menentukan Jalur Dengan Multiple Goal Pada Pergerakan Npc(non-playable Character)

Abstract

Industri game sampai saat ini tidak pernah berkurang peminatnya bahkan semakin meningkat dari waktu ke waktu. Salah satu genre game yang banyak dimainkan adalah turn-based strategy, yaitu game (yang biasanya permainan perang terutama strategi perang) dimana pemain secara bergantian mengatur strateginya untuk mendekati pihak lawan. Selain dimainkan dengan player lain, biasanya game dengan genre ini pun bisa dimainkan dengan NPC atau biasa disebut Non- playable character. Oleh karena itu dibutuhkan NPC yang pintar dan bisa bersaing layaknya manusia yangmemainkannya. Pembuatan NPC yang pintar membutuhkan algoritma pencarian jalur yang bisa memudahkan NPC tersebut mencapai musuh dengan tepat dan cepat. Untuk menciptakan NPC yang sesuai dibutuhkan algoritma yang bisa menentukan rute yang optimal yang bisa diimplementasikan untuk kasus lebih dari satu karakter. Pada umumnya algoritma A*(A Star) sering digunakan pada game untuk kasus pencarian jalur. Penerapan algoritma A*(Star) dengan menggunakan nilai heuristik yang didapat dari mengkombinasikan jarak garis lurus antar masing-masing tujuan mampu menyelesaikan kasus multiple-goal dengan hasil yang complete dan optimal.

Kata kunci :algoritma, jalur, tercepat, optimal, multiple-goal, non-playable character, A*(Star), heuristic, mobile game