Merintis jalan dan menghindari tabrakan di ponsel

Saat ini saya sedang mengembangkan game seperti Diablo untuk platform seluler (iphone5 +).

Pencarian A * sederhana akan menemukan jalan, tetapi penghindaran tabrakan masih perlu dipertimbangkan.

Akan ada sekitar 50 monster yang aktif pada saat yang bersamaan, jadi performanya sangat penting.

Saya menemukan beberapa metode yang mungkin berhasil.

1. NavMesh + RVO

   The perombakan / memutar perpustakaan bekerja dengan baik pada pathfindingsebagian, tapi simulasi kerumunan dengan cepat mencapai batas (lebih dari 5ms untuk 30 agen).

   RVO2 perpustakaan lain tampaknya baik-baik saja (kurang dari 2ms untuk 50 agen), tetapi perpustakaan memiliki beberapa masalah lisensi.

2. Bidang Aliran + Mesin Fisika

   Banyak game RTS menggunakan metode ini, tetapi tampaknya diperlukan mesin fisika untuk menyelesaikan tabrakan. Jika banyak agen tidak memiliki tujuan yang sama, metode ini mungkin lebih mahal daripada penelusuran jalur tradisional A *.

3. Perilaku Kemudi + Mesin Fisika

   Steering Behaviors mencakup banyak konsep, saya pikir simple avoidance behaviormungkin berhasil (belok kiri / kanan jika ada sesuatu di depan), tetapi metode ini masih membutuhkan mesin fisika untuk bekerja bersama.

Saya masih tidak yakin mana yang harus digunakan, mungkin ada metode lain pathfinding dan collision avoidance.

PS Halo:Spartan Strikemenggunakan Havok AI (berdasarkan RVO?), Tapi saya tidak melihat banyak musuh dalam game itu, jadi saya bertanya-tanya apakah metode pertama (NavMesh + RVO) akan bekerja dengan baik di platform seluler.

Ini adalah pertanyaan yang cukup menarik, dan saya akan mencoba berkontribusi dengan apa yang saya bisa.

Pertama, saya pikir Anda harus mendefinisikan dengan jelas batas-batas permainan yang Anda coba buat, dan mendefinisikan pertanyaan-pertanyaan itu (beberapa mungkin sudah dijawab).

• Seberapa jauh aggro monster?
• Berapa banyak monster sekaligus target Anda?
• Bagaimana medan Anda? Apakah itu ubin?
• Berapa banyak penghindaran tabrakan yang Anda inginkan?

Mengutip jawaban dari sini tentang bagaimana pathfinding dilakukan di starcraft 2:

Starcraft II menggunakan triangulasi Delaunay terbatas pada medan peta dan bangunan untuk menghasilkan navmesh; A * dengan filter corong digunakan untuk menelusuri sepanjang mesh ini, dengan mempertimbangkan jari-jari satuan akun; kemudian lapisan penghindaran kemudi dan tabrakan lokal ditambahkan di atas itu, termasuk fitur kooperatif "push idle unit out of the way" di mana dimungkinkan untuk memindahkan unit alih-alih berjalan di sekitarnya dalam kasus-kasus tertentu. Selain itu, unit yang bergerak secara paralel diabaikan untuk tujuan menghindari tabrakan karena mereka dapat dijamin tidak saling mempengaruhi; [...] SC2 menggunakan enam kekuatan kemudi: mengikuti, berkelompok, pengelompokan, pemisahan, penghindaran, dan kedatangan.

Jadi kembali ke 3 proposisi Anda:

1. NavMesh + RVO -> Jika ada masalah lisensi, maka itu bukan pilihan. Ini mungkin implementasi yang paling mudah.
2. Field Flows + Mesin Fisika -> Ini tergantung jujur, tetapi tampaknya benar-benar menghitung intensif dalam lingkungan semi dinamis seperti apa yang Anda inginkan
3. Steering Behaviors + Physics Engine -> Perilaku Steering menurut saya adalah cara yang harus saya tempuh. Dengan begitu Anda dapat mendefinisikan beberapa perilaku kawanan yang cukup bagus untuk gim Anda, tergantung misalnya pada jenis monster. Dan itu berskala baik dengan nomor massa. Namun, saya akan menjauh dari fisika untuk deteksi tabrakan. Perilaku menghindar yang sederhana sudah cukup, mengurangi kecepatan atau meningkatkan, memutar, dll.

Beberapa catatan tentang perilaku Kemudi, Anda dapat menentukan kekuatan kemudi sebanyak yang Anda butuhkan, dengan area yang Anda inginkan. Anda membutuhkan setidaknya 3, untuk berkelompok / tarik / jijik, tetapi lebih mungkin menarik.

Kemudian, cobalah untuk menemukan perpustakaan yang mengarahkan perilaku untuk melihat apakah itu sesuai dengan kebutuhan Anda (seperti ini ? Saya tidak benar-benar tahu, tetapi ada).

Jika perpustakaan tidak sesuai dengan kebutuhan Anda, maka Anda siap untuk bersenang-senang! Tetapi ada sumber daya dan algoritma yang cukup untuk menerapkan perilaku berkelompok sendiri. Contoh 1 Contoh 2

Jika Anda memilih untuk menerapkan sendiri, ketahuilah ada beberapa optimasi yang bagus untuk dilakukan, karena ruang lingkup agen Anda dikurangi misalnya dengan lokasinya di dalam kawanan. Lagi pula itu harus dimasukkan dalam beberapa algoritma.

Yah itu yang terbaik dari pengetahuan saya, saya tidak yakin juga

Jika jalur musuh tidak terlalu dinamis (Dinamis akan setiap agen pasangan menyerang target yang berbeda dan jalur ke target tersebut harus diperbarui setiap frame pasangan)

Lalu saya akan melakukan kombinasi flowfields dan perilaku kemudi jika kinerja adalah perhatian utama Anda. Ada beberapa mata pelajaran yang lebih rumit yang terlibat seperti mempartisi ruang agen Anda sehingga menemukan tetangga lebih mudah tetapi itu adalah taruhan terbaik Anda untuk kinerja. (menghapus pencarian A * Anda dan menggunakan flowfield untuk mengarahkan agen Anda)

Gabungan kedua algoritma tersebut umumnya dianggap sebagai solusi paling optimal untuk adegan agen yang padat dengan pathing yang tidak terlalu dinamis.

Saya akan menghindari fisika apa pun pilihan akhir Anda karena dapat menjadi berat.

Tabrakan antara agen hampir seluruhnya dapat ditangani oleh perilaku kemudi dan alur aliran mengurangi berat 50 agen menghitung jalur. Namun perlu diingat bahwa flowfields semakin mahal, semakin besar ukuran peta Anda, dan semakin kecil ukuran kisi Anda, dan semakin dinamis pilihan target Anda.