Analisis Perbandingan Algoritma Dijkstra dan Algoritma A-Star dalam Pergerakan NPC (Non-Playable Character) pada Single-Player Game (Studi Kasus: Game Chaos Crossing)

Abstract

Kecerdasan buatan dalam sebuah game berperan penting dalam meningkatkan pengalaman bermain pemain, terutama dalam single-player game. NPC adalah sarana interaksi utama dalam single-player game, membantu dan membimbing pemain layaknya berinteraksi dengan pemain lain. Chaos Crossing membutuhkan teknologi pathfinding untuk pergerakan NPC yang optimal, memungkinkan mereka untuk menavigasi lingkungan berbasis grid sambil menghindari environment statis. Algoritma Dijkstra dan A-Star perlu dibandingkan karena berdasarkan penelitian sebelumnya, algoritma Dijkstra terbukti efektif untuk menghitung jarak terpendek ke titik tujuan dalam environment statis berbasis grid dua dimensi dengan karakter bergerak di itu, serta algoritma A-Star dapat menghindari environment statis berbasis grid dan digunakan untuk menentukan jarak terpendek ke titik tujuan dalam pergerakan karakter. Penelitian ini bertujuan untuk menemukan solusi yang mengoptimalkan pergerakan NPC dengan menguji dan membandingkan algoritma Dijkstra dan A-Star dalam environment statis berbasis grid berdasarkan game Chaos Crossing. Hasil pengujian dan analisis perbandingan menunjukkan bahwa algoritma A-Star melakukan pencarian rute lebih cepat dengan nilai rata-rata 36,37 detik dibandingkan algoritma Dijkstra dengan nilai rata-rata 20,76 detik dan memanfaatkan memori lebih efisien dengan nilai rata-rata 20,19 MB dibandingkan algoritma Dijkstra dengan nilai rata-rata 22,17 MB. Namun algoritma Dijkstra menghasilkan jarak lintasan yang sedikit lebih pendek dengan nilai rata-rata 42,26 unit, dibandingkan dengan algoritma A-Star dengan nilai rata-rata 42,39 unit.