Optimasi Heapsort A*(A-Star) Untuk Mencari Rute Terpendek Pada Game Pathway-Finding 3d

Permainan 3D modern sering kali menampilkan dunia yang kompleks dengan banyak rute yang tersedia untuk karakter pemain. Untuk menavigasi dunia ini secara efisien, diperlukan algoritma pencarian jalur yang cepat dan akurat. Algoritma A* adalah salah satu algoritma pencarian jalur yang paling populer dan efektif. Penelitian ini mengusulkan optimasi algoritma A* dengan menggunakan algoritma Heapsort untuk mengelola daftar prioritas. Heapsort adalah algoritma pengurutan yang efisien yang dapat digunakan untuk mempercepat pencarian jalur. Implementasi algoritma A* yang dioptimalkan dengan Heapsort diuji pada game 3D dan hasilnya menunjukkan bahwa algoritma yang dioptimalkan secara signifikan lebih cepat daripada algoritma A* standar.
Metode yang digunakan pada penelitian ini dengan menggunakan metode eksperimen. Pengujian ini digunakan dengan menggunakan beberapa parameter seperti pengujian white box, jumlah node, waktu eksekusi, nilai heuristik, kelancaran jalur robustness, optimalisasi heapsort. Hasil dari berbagai pengujian yang dilakukan. jumlah node lebih besar di mana waktu eksekusi dapat berkurang hingga 16.7% sampai 20%. Pada tingkat akurasi waktu eksekusi rata-rata untuk algoritma A* meningkat 34,51%. Pada nilai heuristik dan kelancaran jalur yang dihasilkan oleh Algoritma A* dengan optimasi heapsort memiliki kualitas yang lebih baik dan lebih mulus dibandingkan dengan Algoritma A* biasa. Pada optimalisasi jalur Rata-rata jarak jalur berkurang sekitar 1-2% di semua level.