Optimisasi Algoritma A* untuk Pencarian Rute Menggunakan Media Roblox

Abstract

Pengembangan Non-Player Character (NPC) yang realistis dalam platform metaverse seperti Roblox membutuhkan sistem yang efisien. Namun, permasalahan utama yang dihadapi pengembang adalah tingginya biaya komputasi dan kurangnya data mengenai kinerja algoritma A* pada bahasa pemrograman Luau. Penelitian ini bertujuan untuk mengevaluasi kinerja algoritma A* pada Roblox dengan bahasa pemrograman Luau melalui analisis komparatif dengan memvariasikan fungsi heuristik (Manhattan, Euclidean, Chebyshev, dan Octile) dan metode sorting (Quick Sort dan Min-Heap Priority Queue). Penelitian dilakukan dengan pendekatan eksperimental kuantitatif di dalam Roblox Studio. Pengujian dilaksanakan pada tiga skenario labirin statis dengan ukuran grid 64x64, 128x128, dan 256x256 studs. Evaluasi didasarkan pada dua metrik utama, yaitu total waktu eksekusi dan total panjang rute yang dihasilkan. Hasil penelitian menunjukkan bahwa penggunaan Min-Heap Priority Queue membuat waktu eksekusi mengalami penurunan rata – rata 46,5% dibandingkan implementasi default dengan efektivitas tertinggi sebesar 73,3% pada skenario ukuran 256 studs x 256 studs. Waktu eksekusi dan hasil rute untuk setiap fungsi heuristik memiliki perbedaan yang tidak signifikan kecuali Euclidean Distance. Fungsi heuristik Euclidean Distance mencatatkan waktu eksekusi tercepat di antara fungsi lain sebesar 2,03ms di 64x64, 5,8ms di 128x128, dan 42,35ms di 256x256. Selain itu, fungsi Euclidean Distance menghasilkan rute yang kurang optimal dengan jarak terjauh sebesar 134 studs di 64x64, 427 studs di 128x128, dan 1062 studs di 256x256 dibandingkan fungsi heuristik lainnya. Penelitian ini membuktikan bahwa dalam pengembangan Roblox, pemilihan konfigurasi dan optimisasi algoritma yang tepat sangat krusial bagi pengembang untuk menyeimbangkan antara kecepatan proses dan akurasi rute sesuai kebutuhan.