Bagaimana saya harus merencanakan ulang A *?

Saya punya musuh bos yang merintis jalan yang mencari pemain menggunakan algoritma A *. Ini lingkungan yang cukup kompleks, dan saya melakukannya di Flash, sehingga pencarian bisa agak lambat ketika mencari jarak jauh. Jika pemain stasioner, saya hanya bisa mencari sekali, tetapi saat ini saya sedang mencari setiap frame. Ini cukup lama sehingga framerate saya menderita.

Apa solusi yang biasa untuk ini? Apakah ada cara untuk "merencanakan ulang" A * tanpa mengulang seluruh pencarian? Haruskah saya mencari sedikit lebih jarang (setiap setengah detik atau detik) dan menerima bahwa akan ada sedikit ketidakakuratan di jalan?

Anda tidak perlu mencari seluruh path dalam satu frame, saya telah melakukan ini dengan memberikan batasan pada loop pencarian, AI kemudian akan mulai mengikuti sedikit informasi yang dimilikinya, dan frame berikutnya saya akan mencari lagi , mungkin butuh 3 bingkai hingga jalur ditemukan. Ini bisa terlihat cukup meyakinkan, karena sepertinya AI sedang mencari.

Anda dapat menggunakan deteksi kedekatan untuk menjalankan algoritma setiap beberapa frame jika jaraknya sangat besar (karena dalam kebanyakan kasus jika jaraknya besar, jalur target tidak akan berubah secara drastis dari frame-ke-frame). Sebagai contoh:

      Distance > 100, run A* every 2 seconds
100 > Distance >  50, run A* every 1 second
50  > Distance >  25, run A* every 10 frames
25  > Distance <  25, run A* every frame

Ini dengan asumsi bahwa ada jarak di mana menjalankan A * setiap frame memiliki kinerja yang masih dapat diterima. Singkatnya, saya akan memilih opsi kedua. Terutama jika apa yang Anda miliki berfungsi, saya akan menghindari menerapkan kembali sesuatu yang lain jika saya dapat mengurangi apa yang berfungsi dengan baik. Intinya adalah Anda harus mencobanya untuk melihat apakah itu berfungsi untuk gim Anda.

Tidak benar-benar menjawab pertanyaan persis Anda, tetapi ... jika Anda mau "menipu", Anda dapat membuat pemain meninggalkan "remah roti" dan minta bos mengikuti mereka. Jika jalur remah roti memotong sendiri, ikuti yang terbaru (ini membuat bos menghindari loop dan jalur lain yang mungkin terlalu panjang, belum lagi tidak mengikuti jalur yang tepat dari pemain)

Ini akan bekerja dengan baik jika bos adalah sejenis binatang dengan indera penciuman yang baik. Ini akan banyak bekerja seperti mengikuti aroma pemain :)

Kasing Anda cukup sesuai dengan yang ditemukan oleh HPA * . Namun, jika itu kelihatannya berlebihan, saya akan cenderung berpikir bahwa merintis jalan setiap setengah detik akan berjalan dengan baik.

Jika lingkungannya statis maka Anda dapat menghitung ulang semua jalur terpendek semua-pasangan.

Saya membuat game untuk kompetisi game 48 di mana karakter A * mengikuti pemain di sekitar level. Karena implementasi A * saya lambat (tidak bisa menjalankan setiap frame) saya menempatkan interval pada penundaan tiga detik. Ini memiliki hasil yang tidak diinginkan yang memungkinkan pemain untuk "menipu" AI selama beberapa saat. Itu benar-benar membuat permainan lebih menyenangkan.

Kemudian, saya meningkatkan kinerja implementasi A * dan mencoba menjalankannya di setiap frame. Permainan berhenti menyenangkan karena musuh selalu mencari pemain dengan sempurna.

Itu tak terduga dan pengalaman belajar yang bagus.

Kecuali Anda benar-benar ingin (atau perlu) menggunakan A *, Anda juga bisa melihat ke dalam Perilaku Pengarah . Karena tidak ada perencanaan jalur lengkap per frame yang terlibat, itu harus jauh lebih ringan pada pemrosesan.