Merintis dengan efisien banyak musuh berkelompok di sekitar rintangan

Saya sedang berusaha meningkatkan pathfinding untuk musuh-musuh gim saya. Saat ini, mereka pada dasarnya hanya terus bergerak menuju posisi tepat pemain dengan menghitung sudut antara mereka dan para pemain dan bergerak ke arah itu. Saya juga memiliki algoritma berkelompok yang mencegah musuh menumpuk di atas satu sama lain, sehingga mereka akan membentuk ke dalam kelompok daripada klip melalui satu sama lain.

Namun, sekarang saya telah menambahkan peta berbasis ubin, saya membutuhkan musuh untuk juga dapat berjalan di sekitar rintangan dan dinding misalnya. Saya awalnya mencoba menambahkan nilai pemisahan ke ubin "non-walkable" sehingga algoritma berkelompok akan mempertimbangkan dinding dan rintangan sebagai objek untuk menjauh. Saya belum mencari tahu apakah ini layak atau tidak karena tes awal saya menunjukkan musuh memukul "dinding" yang tidak terlihat di mana tidak ada ubin yang tidak dapat dilewati, namun untuk beberapa alasan, mereka menabraknya dan mulai memuntahkannya.

Saya bertanya-tanya apakah itu mungkin terlalu berat untuk menghitung jalan ke pemain menggunakan A * dan kemudian menggunakan algoritma berkelompok untuk mencegah penggumpalan. Awalnya gim saya akan menjadi penembak berbasis gelombang, tetapi saya memutuskan untuk menjadikannya berbasis level di jalur Hotline Miami, jadi kemungkinan saya akan memiliki lebih sedikit musuh, dengan gerombolan sesekali, dan hanya membuat mereka lebih kuat.

Apakah ini solusi yang layak? Saya menggunakan Java dengan Slick2D sebagai mesin game saya. Atau adakah solusi / algoritma yang lebih baik yang menangani kedua masalah ini?

java algorithm ai path-finding Darin Beaudreau
sumber

Seperti yang saya jelaskan dalam edit, "apakah ini terlalu berat" adalah pertanyaan untuk diajukan kepada profiler Anda, karena itu akan tergantung pada implementasi Anda, perangkat keras target, anggaran kinerja, dan konteks permainan Anda - semua hal yang Anda dan profiler Anda ketahui intim tetapi orang asing Internet tidak. Jika Anda ingin mendapatkan pelacakan ternak secara efisien, kami dapat menyarankan strategi untuk membantu dengan itu, tetapi hanya profil Anda sendiri yang dapat menjawab apa yang cukup efisien untuk kebutuhan Anda. Jika Anda membuat profil dan mengidentifikasi masalah kinerja tertentu, kami juga dapat membantu Anda menemukan cara menyelesaikan masalah itu.

DMGregory

Bagaimana Anda menerapkannya memengaruhi kinerja. Misalnya, hanya menjalankan A * pada pemimpin & mengandalkan berkelompok untuk pengikut.

Pikalek

Jika gim Anda terutama didasarkan pada pertempuran musuh-musuh ini, algoritma yang Anda ambil akan memiliki dampak besar pada apa yang gim rasanya. Jadi, Anda harus mencoba pendekatan yang berbeda, misalnya apakah itu terasa seperti musuh mengetahui level dan posisi pemain dengan sempurna setiap saat dan mereka melacaknya seperti diarahkan oleh AI yang tahu segalanya? - pendekatan lain bisa membuat musuh berlari ke arah umum di mana pemain mengeluarkan suara dan hanya dengan saling berhadapan langsung berlari ke arahnya, atau berteriak dan memberi tahu musuh lain di mana pemain berada ...

Falco

@ Falco Karena permainan tidak lagi berbasis gelombang, dan akan berbasis level, dan karena musuh adalah zombie ... Saya sedang mempertimbangkan membuatnya jadi Anda harus melihat atau membuat suara agar mereka menemukan Anda. Jadi jika Anda menggunakan senjata yang berisik? Itu memancarkan suara dalam jangkauan dan semua musuh di jalur jangkauan menuju lokasi suara yang dipancarkan, dan kemudian akan jalur secara acak di sekitar area itu.

Darin Beaudreau

Jawaban:

Ini terdengar seperti kasus penggunaan untuk Field Fields.

Dalam teknik ini, Anda melakukan kueri penelusuran jalan keluar tunggal dari objek pemain Anda, menandai setiap sel yang Anda temui dengan sel tempat Anda menjangkaunya.

Jika semua ubin Anda / tepi memiliki biaya traversal yang sama, maka Anda dapat menggunakan pencarian sederhana pertama untuk ini. Jika tidak, algoritma Dijkstra (seperti A * tanpa tujuan / heuristik) berfungsi.

Ini menciptakan bidang aliran: tabel pencarian yang mengaitkan setiap sel dengan langkah berikutnya menuju objek pemain terdekat dari posisi itu.

Sekarang musuh Anda masing-masing dapat mencari posisi mereka saat ini di bidang aliran untuk menemukan langkah berikutnya dalam jalur penghindaran rintangan tersingkat mereka ke objek pemain terdekat, tanpa masing-masing melakukan kueri penelusuran jalan mereka sendiri.

Ini berskala lebih baik dan lebih baik semakin banyak musuh yang Anda miliki dalam kawanan Anda. Untuk musuh tunggal, ini lebih mahal daripada A * karena ia mencari seluruh peta (meskipun Anda bisa lebih awal begitu Anda mencapai semua agen merintis jalan). Tetapi saat Anda menambahkan lebih banyak musuh, mereka dapat berbagi lebih banyak dan lebih banyak biaya pencarian jalan dengan menghitung segmen jalan bersama sekali daripada berulang kali. Anda juga mendapatkan keunggulan dari fakta bahwa BFS / Dijkdtra lebih sederhana daripada A *, dan biasanya lebih murah untuk mengevaluasi per sel yang diperiksa.

Tepat saat titik impas mencapai, dari individu A * menjadi lebih murah, ke A * dengan memoisasi menjadi lebih murah (di mana Anda menggunakan kembali beberapa hasil untuk kueri penelusuran jalan yang lalu untuk mempercepat yang berikutnya), untuk mengalirkan bidang menjadi lebih murah, akan tergantung pada implementasi Anda, jumlah agen, dan ukuran peta Anda. Tetapi jika Anda pernah merencanakan segerombolan besar musuh mendekati dari berbagai arah di area terbatas, satu bidang aliran hampir pasti akan lebih murah daripada A * yang diulang.

Sebagai contoh ekstrem, Anda dapat melihat video di sini dengan 20.000 agen yang secara bersamaan merintis jalur di kotak yang cukup kecil .

DMGregory
sumber

Teknik ini terdengar sangat rapi. Saya akan mengeceknya.

Darin Beaudreau

Dimungkinkan untuk menggunakan algoritma hibrid yang membangun bidang aliran parsial tanpa mencari lebih banyak dari peta daripada panggilan berulang ke A *, dan tidak pernah mencari posisi yang sama dua kali. Ide dasarnya adalah memilih musuh yang sewenang-wenang dan memulai pencarian A * dari pemain ke arah musuh itu, menandai sel saat Anda menjumpainya seperti pada generasi bidang aliran normal. Setelah pencarian menemukan musuh itu, pilih musuh lain (yang belum Anda temukan) sebagai target, sortir ulang set terbuka sesuai dengan heuristik baru dan lanjutkan pencarian. Berhentilah ketika Anda telah menemukan semua musuh.

Ilmari Karonen

Bagaimana dengan menghindari tabrakan? Itu (agak) disebutkan dalam OP (menghindari kliping ketika mereka mencapai pemain). Menurut saya, Anda harus menjalankan kembali jjikstras penuh setiap kali sesuatu dipindahkan (atau tambahkan beberapa logika tambahan)

Mars

@ Mars OP berbicara tentang berkelompok, jadi saya berasumsi bahwa semua individu dapat bergerak dengan kecepatan yang sama; satu-satunya tempat di mana tabrakan akan menjadi masalah adalah kemacetan, yang mengharuskan beberapa kawanan untuk berhenti dan menunggu. Namun, itu tidak benar-benar perlu mengubah pathfinding - antrian sederhana mungkin akan bekerja dengan cukup baik di sebagian besar kasus, dan beberapa biasing jalur (beberapa pilihan jalur alternatif pseudo-acak dengan biaya yang sama) akan bekerja untuk menghasilkan kawanan yang tampak lebih alami mengalir yang juga menghindari seluruh kawanan domba mencoba melalui satu celah ubin tunggal :)

Luaan

@Luaan Dalam game berbasis ubin, Anda akan terkejut betapa seringnya tabrakan terjadi. Secara pribadi, saya menemukan opsi "antrian" kurang optimal. Juga, jika unit tidak dapat saling melewati, Anda harus menghitung ulang ketika unit mulai masuk ke posisi akhir mereka dan banyak kasing tepi lainnya. Berkelompok itu sulit;)

Mars

A * tidak terlalu berat kinerjanya. Saya akan mendekati situasi ini dengan memvariasikan algoritma. Lakukan A * dari waktu ke waktu dan di antara waktu memeriksa apakah langkah berikutnya bebas untuk melangkah ke atas atau Anda perlu menghindari.

Misalnya, lacak jarak pemain dari lokasi target A *, jika di atas ambang batas hitung ulang a * dan kemudian lakukan gerakan pembaruan. Sebagian besar gim menggunakan kombinasi titik jalan, misalnya kisi yang disederhanakan untuk pencarian jalur dan logika yang menangani pergerakan antara titik jalan dengan algoritme penghindaran menggunakan raycast. Para agen mencoba lari ke titik jauh dengan bermanuver di sekitar rintangan di dekat mereka adalah pendekatan terbaik menurut saya.

Cara terbaik adalah bekerja dengan mesin negara yang terbatas di sini dan membaca buku "Programming Game AI By Example" oleh Mat Buckland. Buku ini menawarkan teknik yang terbukti untuk masalah Anda dan detail matematika yang diperlukan. Kode sumber dari buku tersedia di web; buku ini dalam C ++ tetapi beberapa terjemahan (termasuk Java) tersedia.

D3d_dev
sumber

Dengan pendekatan A * yang jarang diperbarui, mungkin akan membantu untuk mengubah-ubah pembaruan Anda, mempertahankan anggaran untuk berapa banyak musuh yang diizinkan untuk menelusuri kembali pada satu frame. Dengan cara itu Anda dapat menjaga agar biaya puncak pathfinding Anda dibatasi, dan menangani banyak AI pathing dengan lebih kuat dengan mengamortisasi total biaya mereka dalam beberapa frame. AI yang menggunakan jalur basi untuk satu atau dua frame ketika anggaran untuk frame telah terlampaui, atau jatuh kembali pada perhitungan mati jika dekat, biasanya tidak akan mengganggu.

DMGregory

Mungkin menyatakan yang jelas di sini, tetapi jika Anda hanya akan memperbarui beberapa jalur Anda dalam bingkai tertentu, Anda mungkin menginginkan sistem prioritas berdasarkan jarak ke pemain. Ini mungkin lebih penting bagi musuh di dekat pemain untuk memperbarui jalur mereka, sementara itu mungkin OK untuk musuh jauh menggunakan jalur basi.

Tidak hanya itu layak, saya percaya itu dilakukan dalam permainan komersial di tahun 90-an - BattleZone (1998).

Game itu memiliki unit 3D dengan gerakan bebas berbasis ubin, dan konstruksi basis berbasis ubin.

Begini cara kerjanya:

Pertama, A * atau sesuatu yang serupa (kemungkinan variasi A * dengan batas ketat pada berapa lama jalur itu dapat ditemukan, sehingga tidak pernah membutuhkan terlalu banyak sumber daya untuk berjalan tetapi tidak selalu menemukan jalur sepanjang jalan ke tujuan) akan digunakan untuk menemukan jalan bagi hovertank untuk mencapai tujuannya tanpa terjebak dalam hambatan berbasis ubin.

Kemudian tangki akan terbang mengitari ruang yang sebelumnya seolah-olah tertarik ke tengah ubin terdekat di jalurnya, dan jijik oleh rintangan, tank terdekat lainnya, dll.

Robyn
sumber

Jadi apa cara yang baik untuk menangani mengikuti jalan, tetapi tidak tepatnya? Jika saya membiarkan menikung anak kecil, saya harus dapat menghentikan musuh dari bertabrakan dengan sudut rintangan. Haruskah saya menjaga perilaku berkelompok untuk musuh dan rintangan dan menambahkan A * untuk menghadapi situasi itu?

Darin Beaudreau