Apakah A * efisien bahkan ketika hambatan sedang bergerak?

Saya baru mulai belajar tentang pencarian jalur dan telah mempelajari algoritma A * dan perhatian utama saya adalah bahwa semua contoh yang saya lihat menunjukkan hambatan statis yang dihitungnya.

Jika saya memiliki hambatan bergerak, misalnya karakter lain, bergerak di sekitar juga sehingga karakter harus menemukan jalan mereka, saya berasumsi saya harus menjalankan algoritma setiap frame, tapi saya khawatir itu akan menjadi agak mahal untuk perangkat keras untuk memproses setiap frame untuk setiap aktor yang bergerak.

Jadi, apakah A * masih cukup efisien untuk digunakan setiap kali rintangan bergerak juga, atau adakah metode lain untuk menemukan jalan yang menangani rintangan yang bergerak dengan lebih fasih?

Ada beberapa algoritma yang jauh lebih cepat daripada A * ketika Anda perlu menghitung ulang lintasan dengan rintangan yang bergerak. Lihat di sini di bawah "Penghitungan Ulang Sederhana".

Namun, Anda kemungkinan tidak akan menemukan solusi di luar rak untuk salah satu dari mereka, jadi dalam 99% kasus mereka membutuhkan banyak waktu untuk permainan. Waktu Anda akan dihabiskan dengan lebih baik menggunakan solusi A * yang sudah dioptimalkan sepenuhnya, dan menggunakan trik umum yang ada untuk mempercepat merintis jalan di game:

• Hanya menghitung ulang jalur terbaik dalam interval yang jarang
• Berbagi jalur terbaik di antara banyak unit ( contoh )
• Membuat grafik hierarkis sehingga Anda hanya perlu menghitung ulang bagian jalan

dll. Anda dapat menemukan lebih banyak info tentang trik ini dan lebih banyak di seluruh situs ini, atau di halaman A * Amit

Iya nih. A * masih merupakan cara untuk masuk dalam hampir setiap kasus. Ini adalah perhitungan biaya simpul Anda yang menjadi dinamis dan karenanya lebih rumit untuk dihitung dan dilacak.

Jika Anda sudah tahu di mana hambatan bergerak di masa depan, A * Anda dapat memperhitungkan temporalitas hambatan dalam fungsi biaya.

Misalnya: Node ini akan dicapai dalam 4 ticks, ditempati dari tick # 3 hingga tick # 6, jadi biaya perjalanan pada node ini adalah 6 - 4 = +2 ticks. Itu mungkin masih jalan terbaik.

Arah perjalanan dari rintangan juga harus diperhitungkan.

Jika Anda tidak tahu sebelumnya maka Anda dapat menganggap tidak ada rintangan dan menghitung ulang jalan ketika rintangan tercapai tetapi Anda perlu melakukan sesuatu tentang deadlock dan livelocks. (Hal yang sama berlaku jika Anda dapat memprediksi di mana hambatan akan tetapi itu sendiri adalah jenis kebuntuan / penghindaran livelock dan itu bisa cukup baik untuk tujuan Anda.)

Jalan buntu adalah ketika keduanya menunggu yang lain bergerak dan tidak ada yang bergerak.

Livelock adalah ketika keduanya ( atau lebih <- ini penting untuk dipertimbangkan) bergerak untuk menghindari yang lain dalam arah yang sama dan akhirnya bolak-balik tanpa kemajuan.

Mengatasi livelocks bisa menjadi sangat kompleks dan itu sepenuhnya tergantung pada aturan dan mekanisme tabrakan game Anda (misalnya: haruskah mereka bertarung dan menghancurkan rintangan?).

Sering kembali ke objek bergerak Anda menjadwalkan pemesanan node / jalur (jangan lupa pembatalan ketika mereka mengubah jalur atau mati) sehingga objek bergerak lainnya dapat merencanakan ke depan.

Setelah Anda memiliki informasi ini, Anda juga dapat merencanakan intersepsi.