Algoritma pathing dinamis untuk game menara pertahanan

16

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.

Dani
sumber

Jawaban:

8

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

John Haugeland
sumber
Jika saya tidak terbiasa dengan A *, bagaimana saya mengatasi lingkungan yang berubah secara dinamis? Menghitung ulang di setiap frame? Saat tabrakan?
Justin L.
1
Secara umum Anda akan menelusuri ulang setiap frame dalam permainan sederhana seperti ini. Kotak peta kemungkinan akan sangat kecil dan jumlah agen paling banyak. Jika akhirnya menjadi masalah kinerja yang sangat besar, Anda bisa mengoptimalkannya nanti dengan tidak membangun kembali pohon kecuali bila diperlukan.
coderanger
6
Jika lamban, rekomendasi saya: jangan menghitung jalur untuk setiap massa. Kemungkinan, mereka semua mengambil jalan yang sama. Saya hanya menghitung ulang pada penempatan menara baru, dan menara berada di jalur saat ini . Bahkan kemudian, Hanya lakukan perhitungan ulang untuk monster di titik-titik di jalan sebelum blok persegi, bukan untuk massa yang melewatinya dan karena itu tidak peduli. Dan kemudian, untuk membuat pathfinding lebih pendek, Anda bisa membatasi untuk menemukan cara kuadrat setelah kuadrat diblokir, karena Anda sudah tahu jalan dari sana.
seanmonstar
4
Sebenarnya, "mob" adalah istilah industri (dan pemain MMO / MUD) untuk "objek mobile".
3
Apapun, itu sudah lama, dating kembali ke MUD1, dan cukup standar untuk muncul di banyak publikasi. en.wikipedia.org/wiki/Mob_%28computer_gaming%29
19

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.

ek
sumber
1
Juga akan mudah untuk menyebarkan frame ini secara dinamis saat beban CPU berubah.
Tenpn
+1 untuk A * bukan algoritma yang tepat untuk digunakan.
Ricket
5

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).

Richard Fabian
sumber
4

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.

ZorbaTHut
sumber
1
Perlu dicatat bahwa Tower Defense populer di ponsel, di mana merintis jalan tidak cepat. Terutama pada perangkat yang sedikit lebih tua, seperti perangkat Sidekick, atau Android 1.6.
seanmonstar
1
Pengembang telah menggunakan algoritma pathfinding seperti A * dan Dijkstra pada perangkat keras yang jauh lebih kuat selama beberapa dekade (pikirkan Game Boy). Setiap ponsel yang cukup baru untuk memiliki layar yang memadai untuk bermain game seharusnya tidak memiliki masalah, asalkan tentu saja implementasinya cukup efisien. Ada beberapa optimisasi bagus yang dibahas di sini: harablog.files.wordpress.com/2009/06/beyondastar.pdf
Mike Strobel
+1. Saya sampai pada kesimpulan yang sama ketika saya sedang mengembangkan klon DTD saya sendiri. Saya mencoba memperbarui jalur secara bertahap tetapi algoritme menjadi terlalu rumit. Setelah menghabiskan satu hari di atasnya, saya beralih ke perhitungan penuh pada setiap perubahan. Itu berhasil, dan dengan beberapa penyesuaian saya bisa membuatnya cukup cepat.
finnw
2

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.

tenpn
sumber
1

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.

Loktar
sumber
Ini hanya berfungsi untuk game-game TD di mana Anda hanya bisa menempatkan menara di sisi jalan - bukan game yang memungkinkan penempatan menara di mana saja di papan tulis.
Iain
ya awalnya penulis tidak menentukan jenis yang dia inginkan jadi saya anggap tidak dinamis.
Loktar
1

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 :)

Ian Schreiber
sumber
1

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).

MrValdez
sumber
1
Agaknya dia berbicara tentang sesuatu seperti Desktop TD di mana pengguna membuat peta dengan cepat. Masih untuk musuh "bodoh" yang mungkin merupakan solusi yang bagus sehingga Anda dapat membuat musuh dengan AI yang lebih baik sedikit meningkatkan kesulitan.
coderanger