Algoritma pathing dinamis untuk game menara pertahanan

Saya membuat Tower Defense dan saya membutuhkan algoritma pathing yang bagus untuk itu.

Saya telah memikirkan Dijkstra tetapi saya membutuhkan Dijkstra yang dinamis; itu harus dapat memperbarui sendiri ketika satu sisi dihapus atau ditambahkan tanpa perhitungan ulang penuh.

Saya mengkode dalam C # jika itu membantu.

Anda biasanya ingin menggunakan A *, kecuali ada sesuatu yang berbeda yang Anda cari.

Saya perlu memecahkan masalah yang sama: mencari jalan di kotak besar seperti labirin dengan "biaya" dan penghalang yang terus berubah.

Masalahnya adalah, dalam permainan menara pertahanan jumlah entitas yang perlu diselesaikan jalurnya untuk mereka biasanya jauh lebih besar daripada jumlah node dalam grafik. A * bukan algoritma yang paling tepat untuk menangani ini, karena Anda harus menyelesaikannya lagi setiap kali ada perubahan. Yah itu tepat jika Anda hanya perlu menemukan satu jalur, tetapi dalam kasus saya, saya harus dapat menangani entitas yang dapat muncul di lokasi yang berbeda dan masing-masing memiliki jalurnya sendiri.

The Floyd-Warshall algoritma jauh lebih tepat, meskipun untuk kasus saya saya menulis algoritma kustom yang setiap kali perubahan node, itu kembali menghitung biaya untuk node yang dari semua tetangganya, dan kemudian jika tetangga telah diubah itu dipanggil secara rekursif pada mereka.

Jadi di awal permainan, saya hanya menjalankan algoritma ini di semua "tujuan" node saya. Kemudian, setiap kali satu node berubah (misalnya, menjadi tidak bisa dilewati), saya hanya menjalankannya pada node itu dan perubahan tersebut disebarkan ke semua node yang akan terpengaruh, dan kemudian berhenti. Jadi tidak perlu perhitungan ulang global, dan algoritme sepenuhnya independen dari jumlah entitas yang akan memerlukan pencarian jalan.

Algoritma saya pada dasarnya adalah sesuatu seperti (pseudo-code):

update_node method in Node class:
    $old <- $my_score
    find $neighbor node among all neighbors such that
        $neighbor.score + distance_to($neighbor) is minimal
    $my_score <- $neighbor.score + distance_to($neighbor)
    $next_node <- $neighbor
    if ($my_score != $old)
        for each $neighbor
            $neighbor.update_node()

Dengan skor awal tergantung pada apakah node adalah target atau semacam penghalang.

Algoritme rute yang saya gunakan pada TD saya mundur dari jalur A * normal karena jumlah entitas yang saya miliki dalam permainan. Alih-alih merutekan dari tujuan ke orang jahat, saya dialihkan dari tujuan ke setiap kotak kosong di papan tulis.

Ini tidak memakan waktu lama, Anda hanya perlu mengulanginya sampai Anda menemukan "biaya" Anda, dan itu memberikan umpan balik yang baik untuk rute yang diblokir (jika Anda melakukan itu). Menggunakan algoritma Floyd cepat dan ramah cache dibandingkan dengan A * karena tidak melakukan pencarian tergantung data, itu hanya memuat dan beroperasi pada data dalam aliran.

Mulailah dengan papan Anda yang disetel ke biaya tak terbatas, lalu tetapkan kuadrat sasaran menjadi nol, kemudian beralih di papan memeriksa untuk melihat apakah sel tetangga lebih murah dari biaya saat ini ditambah biaya perjalanan. Biaya perjalanan adalah tempat Anda meletakkan heuristik Anda (dalam kasus saya, biaya perjalanan secara diagonal tidak terbatas, tetapi biaya perjalanan melalui menara tinggi, sehingga mereka diizinkan untuk makan melalui menara, tetapi tidak kecuali mereka tidak memiliki pilihan)

Setelah Anda mendapatkan kisi biaya, Anda dapat dengan cepat membangun kisi "aliran" dari situ dengan menguji gradien biaya yang paling tinggi pada sel. Ini bekerja sangat baik untuk sejumlah besar orang jahat karena tidak ada dari mereka yang pernah harus mencari jalan, mereka hanya mengikuti rambu-rambu virtual.

Manfaat lain adalah bahwa dengan cara ini Anda hanya perlu menjalankan tugas ini setiap kali Anda menyesuaikan penghalang (atau dalam permainan saya, ketika seekor creep makan melalui salah satu menara Anda). Tidak setiap kali creep / mob memasuki lapangan (yang dengan ribuan massa dan puluhan per detik akan cukup sakit kepala).

Pathfinding cepat, dan pada sesuatu yang seukuran permainan pertahanan menara normal, Anda tidak akan kesulitan menjalankan lintasan A * atau Dijkstra penuh setiap kali ada perubahan. Kami berbicara dengan baik di bawah milidetik untuk penyegaran penuh. Setiap jenis pathfinding adaptif berakhir sangat rumit. Lakukan saja dengan cara sederhana, kecuali Anda membuat kisi pertahanan menara terbesar di dunia.

Bagaimana cara kerja A * pathfinding? mungkin tempat yang bagus untuk memulai :-)

Ini mungkin berlebihan untuk solusi Anda, tetapi pikirkan rute mundur dan bukan ke depan.

Dalam permainan TD, musuh umumnya berusaha mencapai tujuan tertentu. Rute mundur dari tujuan itu ke musuh pertama, lalu tembolok jalur itu. Pada pembuatan jalur untuk musuh selanjutnya, gunakan jalur pertama sebagai titik awal, dan seterusnya. Jika Anda memiliki beberapa titik masuk musuh, atau beberapa tujuan, miliki rentang jalur pra-tembolok untuk memulai.

Pathfinding waypoint mungkin akan menjadi yang terbaik untuk permainan td, karena umumnya berdasarkan level ai mengikuti jalur langsung. Pada dasarnya Anda mengatur node atau titik jalan Anda kemudian memiliki titik "ai" ke arah waypoiny dan berjalan ke sana, setelah itu cukup dekat untuk itu pergi ke titik jalan berikutnya, hadapi dan bergerak ke arah itu.

Karena seseorang bertanya, Anda mengatasi lingkungan yang berubah secara dinamis dengan menghitung ulang lintasan setiap kali pemain menempatkan atau memindahkan menara, dan Anda hanya menyimpan lintasan itu di memori dalam waktu yang bersamaan. Lingkungan tidak berubah di setiap bingkai.

Perhatikan bahwa beberapa game TD memiliki jalur yang ditetapkan dan tidak memungkinkan Anda untuk menempatkan menara di atasnya, sehingga mereka menyelesaikan pencarian jalan dengan cara yang mudah: dengan meng-hardcoding jalur dan tidak membiarkan Anda memblokirnya :)

Solusi sederhana adalah dengan curang.

Rancang peta sebelumnya untuk memastikan tidak ada jalan buntu. Kemudian di setiap persimpangan, tambahkan pemicu yang membuat karakter memilih rute (contoh: selalu belok kiri, selalu belok kanan, atau acak).