Abstract
Algoritma A* merupakan algoritma tradisional yang sering digunakan untuk menyelesaikan masalah pathfinding. Algoritma long steering tradisional seperti A* tidak mampu untuk dipakai untuk menyelesaikan permasalahan real-time pathfinding. Real-time Pathfinding merupakan permasalahan pathfinding dalam lingkungan real-time dimana terdapat dynamic obstacles yang menambah kompleksitas permasalahan pathfinding. Dengan A* tradisional dalam lingkungan real-time, jika terdapat halangan dinamis akan dilakukan kalkulasi ulang yang akan memakan banyak sumber daya CPU. Salah satu algoritma short steering yang dapat diterapkan untuk menyelesaikan permasalahan real-time pathfinding adalah Reynolds Steering Obstacle Avoidance yang mampu menghindari adanya tabrakan dengan dynamic obstacles. Oleh karena itu, dalam penelitian ini dilakukan implementasi realtime pathfinding dengan mengintegrasikan antara algoritma long steering A* untuk pathfinding dan algoritma short steering Reynolds Steering Obstacle Avoidance untuk menghindari halangan dinamis sehingga tidak perlu dilakukan kalkulasi jalur ulang untuk mengoptimalkan kinerja dari CPU. Implementasi algoritma dilakukan dengan melakukan simulasi pada peta permainan 3D. Representasi ruang pencarian dari peta permainan yang digunakan berupa regular grids berbentuk persegi. Pada peta akan diletakan halangan dinamis dan statis lalu agen akan berjalan dari titik awal ke titik tujuan yang telah di perhitungkan jalurnya dengan menghindari halangan. Simulasi implementasi algoritma dibedakan menjadi 2 skenario. Simulasi dilakukan dengan game engine Unity versi 4.6. Pengujian panjang jalur pada 30 uji coba dalam skenario 1, menunjukkan bahwa implementasi real-time pathfinding dengan A* dan Reynolds Steering Obstacle Avoidance akan menghasilkan jalur yang lebih panjang dibandingkan dengan penghitungan jalur ulang dengan perbandingan 8:7. Sedangkan untuk pengujian FPS pada 30 uji coba dalam skenario 2, menunjukkan bahwa kinerja CPU pada implementasi real-time pathfinding dengan A* dan Reynolds Steering Obstacle Avoidance akan 2 kali optimal dibandingkan dengan menggunakan penghitungan jalur ulang.
