Abstract :
Permainan telah menjadi satu hal yang ada di dalam keseharian kita. Dalam sebuah game, terdapat beberapa unsur yang dapat dianggap penting untuk mendukung jalannya game dan realitas dari dunia game yaitu cerita. Cerita yang coba diterapkan dalam game yang dibangun adalah cerita rakyat Tadulako Bulili. Selain cerita, unsur penting lainnya adalah Non Playable Character (NPC). Salah satu kemampuan NPC adalah kemampuan NPC menentukan jalur tercepat (Pathfinding) untuk menemukan atau mencapai tujuan utama NPC tersebut. Algoritma A* (A Star) adalah algoritma pencarian yang dapat digunakan untuk melakukan pathfinding, dalam hal ini algoritma A* digunakan untuk mencari suatu jarak terpendek antara NPC dan karakter player. Algoritma A* diterapkan pada salah satu karakter NPC yang bernama Tadulako Bantaili. Penelitian ini bertujuan untuk menerapkan algoritma A Star (A*) terhadap non playable character dalam sebuah game bergenre Role Playing Game sehingga memberikan pengalaman yang cukup menarik dalam sebuah permainan sekaligus menjadikan cerita rakyat daerah sebagai cerita utama dalam permainan agar dapat menjadi media pengenalan dan pelestarian budaya daerah. Cerita rakyat berhasil diterapkan ke dalam game dengan memecah cerita menjadi beberapa narasi dan mengintegrasikan narasi tersebut kedalam sebuah misi. Berdasarkan hasil pengujian menunjukkan bahwa penerapan algoritma A* dalam game dengan genre role playing game ini mampu memecahkan permasalahan bagaimana NPC dapat menemukan jalur terpendek untuk mencapai target/tujuan NPC tersebut. Pengujian dilakukan dengan menggunakan 4 skenario, skenario ke 1 diselesaikan dalam waktu 5ms, skenario ke 2 diselesaikan dalam waktu 6ms, skenario ke 3 dalam waktu 5ms, skenario ke 4 diselesaikan dalam waktu 25ms.