Bagaimana cara merintis jalan di game RTS bekerja?

42

[crossposted from stackoverflow]

Dalam permainan seperti Warcraft 3 atau Age of Empires, cara-cara yang dapat dilakukan lawan AI untuk bergerak di peta tampak hampir tanpa batas. Peta sangat besar dan posisi pemain lain terus berubah.

Bagaimana cara pencarian jalur AI dalam game seperti ini berfungsi? Metode pencarian grafik standar (seperti DFS, BFS atau A *) tampaknya tidak mungkin dilakukan dalam pengaturan seperti itu.

selimut
sumber
2
Mengapa A * tidak berfungsi dalam grafik ini?
user712092
Blog terkait: ai-blog.net/archives/000152.html
tenfour
1
@tenfour, tautannya rusak sekarang.
Montreal

Jawaban:

29

Dalam kebanyakan kasus, menggunakan A * di atas jala navigasi (biasanya disebut sebagai "navmesh") adalah solusi pathfinding yang digunakan RTS komersial. Ada penjelasan terperinci tentang cara kerja navmeshes, mengapa navmeshes merupakan solusi yang lebih baik daripada sistem waypoint, dan tautan ke sumber daya implementasi, di sini .

Jika Anda berencana mengembangkan mode permainan khusus (penangkapan titik / simpul) atau unit yang berpatroli, berlindung, dll., Anda mungkin ingin menerapkan lapisan titik arah di atas navmesh Anda, untuk mengontrol perilaku AI ( bukan merintis jalan ).

Ari Patrick
sumber
17

Check out Flowfield algoritma yang digunakan di Panglima Tertinggi 2. Ia melakukan pekerjaan yang jauh lebih baik daripada kebanyakan RTS sistem merintis jalan jangan (langsung beralih ke 0:50 untuk beberapa contoh.)

ZorbaTHut
sumber
4
itu adalah demo yang sangat keren tetapi tidak memberi tahu saya tentang implementasinya sendiri
MetaGuru
4
Mereka menyebutkannya dalam satu kalimat - ini berdasarkan penelitian aliran kerumunan UW, yang dapat Anda temukan di grail.cs.washington.edu/projects/crowd-flows .
Algoritma flowfield tampaknya cukup menarik, dan jelas tampaknya melakukan pekerjaan pathing yang jauh lebih baik daripada kebanyakan algoritma, tapi saya berharap ada dokumentasi publik tentang bagaimana sistem itu sendiri bekerja, bukan hanya bagaimana sistem itu didasarkan pada kerjanya. Secara alami, ada banyak pertanyaan yang harus diajukan pengembang sebelum menerapkan sistem inti seperti ini, tetapi, dalam kasus ini, tampaknya satu-satunya cara untuk menjawab pertanyaan itu adalah dengan menerapkan sistem terlebih dahulu. :(
Ari Patrick
2
@ Kragen: Anda benar-benar hanya perlu dua unit sebelum dataran A * (terutama waypointed) menyebabkan mereka saling bertabrakan berulang-ulang, dan Anda membutuhkan semacam sistem untuk mengatasinya.
5
Berdasarkan video, pathfinding Starcraft 2 terlihat seperti ini. Apakah SC2 menggunakan flowfield?
Chris Bui
7

Banyak game lama menggunakan A *. Starcraft asli menggunakan A *; yang menyebabkan beberapa masalah dalam berurusan dengan tabrakan. Starcraft 2 menangani tabrakan dengan sangat baik, menggunakan perilaku swaming / berkelompok untuk mempertahankan kontrol cairan kelompok besar. Ini artikel gamedev membahas bagaimana ini mungkin menjadi dicapai.

phillipwei
sumber
2

Saya setuju dengan jawaban lain dia sudah, tetapi juga, mencoba menganggap WoW / Warcraft3 sebagai dunia 2D yang sebenarnya. Mereka berbeda dari tilebased, itu hanya ubin.

Anda juga bisa memikirkan bagaimana GPS menemukan jalur terbaik? ada banyak algortim untuk merintis jalan melalui peta yang ditautkan.

Saya pikir beberapa skrip "Gempa bot" pertama juga dapat membantu Anda, karena skrip ini dikembangkan untuk bekerja di "area yang tidak diketahui" karena kami dapat merancang level kami sendiri dari awal.

Secara keseluruhan, cara pribadi saya untuk menangani peta semacam itu, akan menganggapnya sebagai pathfinder A *. Tapi pertama-tama saya akan menghitung terlebih dahulu setiap "titik ubin" dan mengindeks semua ini dengan "tetangga terdekat" dll. Kemudian ketika sebuah objek perlu beralih dari A ke B kemudian hanya mencari di B, lihat apa yang terhubung dan terus mengulangi sampai Anda mencapai tujuan.

Bergantung pada jenis permainan dan lanskap / skenario, berbagai taktik pra-pemindaian mungkin berguna juga. Beberapa permainan memiliki sedikit hambatan dan ini bisa menjadi gerakan "garis lurus" + beberapa "bagaimana saya bisa berkeliling" untuk objek.

Semoga ini masuk akal dan mungkin memberi Anda beberapa pemikiran untuk dikerjakan.

BerggreenDK
sumber
1

Sebagian besar game menggunakan semacam Algoritma Pencarian atau A * untuk menemukan jalur di peta. AI disesuaikan dalam beberapa aspek jelas karena alasan kinerja.

Anda akan melihat ini di Starcraft 2 di mana Zerglings jelas tidak jalan sama sekali, itu akan menjadi mimpi buruk CPU untuk melakukan itu untuk Zerglings. Mereka hanya melakukan yang terbaik untuk mendapatkan dari A ke B dan bahkan tidak berusaha untuk menemukan jalan terbaik. Mereka akan mendapatkan sedekat mungkin kemudian leher botol di choke atau landai.

Bryan Harrington
sumber
1

Peta adalah kisi. Kisi adalah grafik. A * berfungsi pada grafik, ini adalah algoritma pencarian grafik. A * harus mencari beberapa node grafik.

Seperti yang telah disebutkan mereka dapat menggunakan navigasi mesh. Tetapi A * (atau sesuatu yang serupa) akan berada di atas jala itu, karena poligon dari jala ini hanyalah simpul dari grafik; A * kemudian akan mencari jalur dari satu poligon ke poligon lain.

Tidak yakin tentang Warcraft atau game komersial, tetapi ada juga teknik yang disebut Difusi Kolaboratif dan sangat sederhana; biasanya dilakukan di grid. Ada juga teknik yang disebut Bidang Potensial , yang sangat mirip dengan yang sebelumnya jika tidak sama.

Anda mungkin juga mencoba:

  • apakah beberapa game ini memiliki kode sumber yang tersedia
  • apakah beberapa klon dari game ini memiliki sumber yang tersedia
  • apakah SDK atau editor tidak mengisyaratkan sesuatu
  • tanya majikan perusahaan yang membuat game ini, beberapa dari mereka mungkin bersedia untuk berbagi
pengguna712092
sumber
0

Saya sama sekali tidak berpengalaman, tapi saya pikir solusi yang baik didasarkan pada heuristik, bukan pada pemeriksaan lengkap dari peta yang diketahui. Heuristik yang bisa saya pikirkan berbasis lokal dan berdasarkan pengalaman. Kontrol lokal dapat didasarkan pada cek medan dan rintangan lokal, terus bergerak ke arah yang diperlukan. Saya pikir sebagian besar peta tidak memerlukan gerakan rumit seperti labirin, tetapi cukup terhubung. Heuristik lain adalah menggunakan jalur yang diketahui sebelumnya (dieksplorasi oleh unit lain atau secara eksplisit oleh pengguna) untuk memindahkan unit ke posisi yang diketahui atau hampir diketahui. Tapi saya berbicara tentang pindah di peta besar, tidak benar-benar di ruang tertutup seperti kata ZorbaTHut. Dalam kasus yang ramai algoritma mungkin lebih kompleks, membutuhkan semacam "prediksi", koordinasi antara unit tim yang sama atau hanya strategi menunggu semafor. Juga,

Saya pikir algoritma heuristik baik karena mereka biasanya memberikan solusi yang baik pada ruang besar dengan waktu perhitungan yang masuk akal (yang penting, ketika Anda memindahkan banyak unit).

Maaf jika ini adalah jawaban umum: Saya bekerja dengan orang banyak, tetapi ruangnya cukup aneh dan saya tidak bisa menjelaskan dengan tepat bagaimana algoritme bekerja (berdasarkan agen, toh, tidak didefinisikan secara global). Saya harap Anda bisa mendapatkan beberapa ide yang bermanfaat dari jawaban saya.

AkiRoss
sumber
Mmmh saya bertanya-tanya apa yang salah dengan apa yang saya katakan ... Apakah terlalu sulit untuk memberikan komentar?
AkiRoss
BTW, saya ingin menyoroti bahwa A * menggunakan pendekatan heuristik. Terima kasih untuk -2.
AkiRoss
Jawaban Anda sama dengan, "Parit A * dan sejenisnya, lalu gulir sendiri". Itu bisa menjadi awal untuk jawaban yang masuk akal tetapi Anda memberikan sedikit info selain saran. Menurutnya alasan untuk melakukan voting adalah Anda tidak menjelaskan betapa sulitnya solusi Anda untuk diimplementasikan. Saya tidak ragu bahwa seorang jenius super yang diberikan waktu tidak terbatas dapat memberikan kode / menyetel algoritme pathing untuk RTS tertentu yang akan lebih unggul dari A * di navmesh. Tetapi "genius" dan "tidak terbatas" sangat sulit didapat.
deft_code
Oh ... Benar. Saya pikir lelaki itu menginginkan jawaban yang umum, karena dia tidak bertanya bagaimana membuatnya, tetapi bagaimana cara kerjanya secara umum. Pokoknya saya bukan ahli seperti yang saya katakan: Saya hanya memberikan beberapa info tentang solusi yang saya tahu tentang menjelajahi ruang besar dalam aplikasi IA umum. Terima kasih atas komentar Anda.
AkiRoss