Peta permainan yang dapat diamati sebagian - apakah A * pantas?

16

Saya tahu sedikit tentang pengembangan game dan saya mencoba untuk menyelimuti algoritma pathfinding.

Pertimbangkan pengaturan ini: agen ada di peta 2D dan harus menemukan jalur terpendek ke objek yang diketahui secara global tetapi hanya memiliki informasi tentang hambatan dalam lingkup penglihatan lokalnya (mis. Hanya hambatan langsung yang diketahui, tata letak umum peta tidak diketahui ).

Juga, setiap gerakan ke kotak yang berdekatan mahal dan algoritma pathfinding harus meminimalkan jumlah gerakan.

Efisiensi komputasi juga sangat penting dan lebih penting daripada akurasi.

Apakah A * sesuai untuk kasus penggunaan ini?

algorithm path-finding maps David Chouinard
sumber

Jawaban:

19

Anda harus menggunakan algoritma D * , yang dirancang untuk skenario yang tepat ini. Secara khusus, implementasi D * Lite adalah varian paling efisien dan sederhana.

jmegaffin
sumber
2
Sangat relevan . Memahami D * -lite sederhana setelah Anda memahami LPA * (algoritma D * -lite didasarkan pada) , tetapi LPA * itu sendiri cukup kompleks. Jadi, jika Anda berencana untuk benar-benar menerapkan D * -lite, makalah tentang LPA * akan menjadi tempat untuk memulai (dengan asumsi Anda sudah mengerti A *, yaitu)
BlueRaja - Danny Pflughoeft
3

Banyak implementasi game AI dalam situasi itu akan memilih untuk menipu, dan memberi mereka pengetahuan penuh tentang peta, di mana lawan manusia mereka tidak memilikinya. Anda kemudian dapat menerapkan A * ke peta lengkap.

Bagaimana masuk akal ini terlihat untuk unit yang dikendalikan komputer akan tergantung pada hal-hal seperti seberapa labirin seperti peta, dan jika pemain cenderung mempelajari tata letak peta dari waktu ke waktu.

Jika ini untuk unit yang dikontrol pemain, Anda juga dapat mencegah pemain memilih tujuan yang belum dieksplorasi, untuk memaksa mereka menjelajah secara manual.

Adam
sumber
2
Saran yang bagus, tidak sesuai untuk kasus penggunaan saya, tetapi bisa bermanfaat bagi orang lain. (Saya sedang mengembangkan AI untuk bersaing dalam simulasi permainan)
David Chouinard
ada juga permainan yang menggunakan implementasi pencarian jalur dengan asumsi bahwa daerah yang belum dijelajahi dapat dilintasi, sementara daerah yang dikunjungi sebelumnya tidak memiliki perubahan dalam lintas sejak kunjungan terakhir (yaitu tidak akan tahu bahwa tembok mungkin telah dihancurkan atau dibangun sampai mengunjungi daerah tersebut. lagi).
Lie Ryan