Temukan jalur terpendek melalui rintangan saat semua jalur normal diblokir

10

Saya membuat Tower Defense dan saya punya dasar pathfinding yang berfungsi, tapi saya punya masalah.

Saya ingin membuat jalur dapat diblokir, dan ketika sebuah blok terjadi, pelari akan menyerang menara pemblokiran.

Jadi yang saya butuhkan adalah cara untuk menemukan jalur terpendek yang, lebih penting, memiliki jumlah menara terendah di jalan.

Bagaimana aku melakukan itu?

algorithm path-finding tower-defense Dani
sumber
1
bukankah itu akan menjadi deteksi tabrakan dalam jalur walkable Anda?
Prix
Karena menara pemblokir dapat dirusak, sebenarnya ada jalan. Hanya biaya bergerak melalui mereka jauh lebih tinggi daripada bergerak di sepanjang jalan yang tidak terhalang. (Lihat jawaban dari coderanger di bawah ini)
bummzack

Jawaban:

21

Di jalur Anda, mencetak hanya membuatnya melewati menara harganya sama dengan melewati sejumlah besar ubin. Secara umum ia akan mencoba untuk mengelilinginya, tetapi jika tidak ada jalan seperti itu output masih akan melewati paling sedikit hambatan. Anda dapat menyetel penalti sehingga terkadang mereka hanya akan melalui alih-alih mengitari peta jika Anda mau.

pembuat kode
sumber
akan senang melihat contoh kode implementasi ini, terdengar sederhana dan kuat
DFectuoso
3
Algoritma A * ( en.wikipedia.org/wiki/A * _search_algorithm) bekerja dengan biaya jalur. Tingkatkan biaya untuk segmen yang berjalan melalui menara. Agen Anda kemudian akan mencoba untuk menghindari menara, atau jika "lebih murah" untuk menyerang menara, mereka akan menyerangnya. Gagasan dari algoritma A * adalah untuk meminimalkan biaya, sehingga Anda harus dapat mencapai apa yang Anda inginkan dengan hanya mengubah biaya jalur ...
bummzack
Ini adalah solusi hebat yang tidak akan saya pikirkan, terima kasih!
jhocking
Hanya sebuah catatan: Memberi menara node biaya pergerakan yang besar tanpa juga meningkatkan perkiraan yang digunakan untuk algoritma A * ketika jalurnya jelas diblokir akan berarti bahwa agen Anda akan memeriksa setiap node pada bagian dari hambatan sebelum memutuskan untuk break- melalui titik. Bergantung pada jumlah node dan agen, ini mungkin membuat algoritma sangat lambat.
Martin Sojka