Perpustakaan Digital ITB

Pathfinding adalah pencarian lintasan terpendek dari titik awal ke titik tujuan pada suatu peta. Algoritma pathfinding umum digunakan dalam permainan komputer. Di permainan komputer, algoritma pathfinding tidak hanya dijalankan sekali, tetapi umumnya dijalankan berkali-kali selama permainan untuk titik awal dan titik tujuan yang berbeda. Kebutuhan interaksi yang realtime dalam permainan komputer dan keterbatasan sumber daya prosesor dan memori menuntut dikembangkannya algoritma pathfinding yang efisien agar lintasan terpendek dapat dihitung dengan cepat. Algoritma Block A* adalah pengembangan algoritma A* pada grid. Algoritma ini membagi peta berupa grid menjadi blok-blok berukuran sama. Pra-komputasi dilakukan terhadap setiap kemungkinan konfigurasi halangan blok untuk memperoleh data jarak terpendek lokal antar sisi sel pada blok. Data ini disimpan ke dalam struktur data bernama LDDB dan digunakan untuk mempercepat perhitungan ekspansi blok pada algoritma utama Block A*. Peningkatan ukuran blok berpotensi meningkatkan kinerja waktu pemrosesan algorima Block A*. Hasil tugas akhir ini menunjukkan bahwa ukuran blok mempengaruhi peningkatan kinerja waktu pemrosesan algoritma Block A*. Terjadi peningkatan kinerja secara logaritmik dimana secara umum terdapat penurunan waktu proses yang signifikan pada perbesaran ukuran blok untuk ukuran blok yang kecil. Namun, peningkatan semakin tidak signifikan saat ukuran blok diperbesar. Pada ukuran blok yang cukup besar, secara umum terjadi penurunan kinerja akibat dari proses inisialisasi yang lebih dominan pada ukuran blok yang besar