Bagaimana cara membuat agen A * menghindari agen lain?

Saya menerapkan algoritma multi-agen A * pada peta ubin. Agen hanya bergerak di sumbu X dan Y. Saya menghindari tabrakan di antara mereka dengan memeriksa di mana yang lain saat menghitung jalur.

Ini berfungsi dengan baik kecuali situasi di mana agen harus melewati ubin yang sama dari arah yang berbeda. Dalam situasi seperti ini, solusi optimal adalah untuk satu agen menunggu yang lain untuk lulus:

Juga, jika tidak ada koridor utara, maka pathfinding gagal.

Bagaimana saya bisa menerapkan algoritma seperti itu?

Anda bisa mulai dengan membiarkan pathfinding gagal. Pada kegagalan, pilih waktu acak di masa mendatang untuk mencoba merintis jalan lagi. Beberapa protokol jaringan tingkat rendah bekerja seperti itu , dan cukup baik. Yang harus Anda lakukan adalah membangun jalur satu per satu, dan tandai sebagai digunakan semua ubin agen akan melewati. Ketika jalur selanjutnya gagal, pengatur waktu acak untuk memulai ulang akan membantu menyebarkan pencarian jalur baru dan memecah kegagalan pengulangan.

Bagian kedua dari masalah Anda dapat ditangani dengan mengembalikan dua jalur. Jalur pertama adalah pengembalian reguler, meskipun gagal dari blok. Jalur kedua adalah jalur yang sepenuhnya mengabaikan semua agen. Anda kemudian dapat menggunakan pengetahuan yang diperoleh dari dua jalur ini untuk memutuskan apakah menunggu atau menempuh jalan yang jauh lebih baik. Heuristik untuk keputusan itu akan membutuhkan pekerjaan, tetapi lebih baik daripada tidak mencoba apa pun.

Dalam kasus yang sangat buruk di mana agen Anda sering diblokir oleh koridor lebar tunggal seperti ini, Anda mungkin harus menambahkan tempat yang aman untuk berdiri di mana agen dapat dengan cepat jalur ke dan menunggu jalan mereka yang sebenarnya untuk membuka (sehingga agen tidak hanya menunggu dan memblokir koridor).

Daripada menyelesaikan masalah Anda, inilah cara untuk mengambil lemon dan membuat limun.

Bertahun-tahun yang lalu seorang teman saya mengerjakan FPS yang sangat terkenal yang memiliki masalah persis seperti yang Anda gambarkan: area terbatas akan memiliki sejumlah karakter AI yang memiliki posisi yang diinginkan tertentu, dan algoritma pencarian jalur terus-menerus menabrak mereka. satu sama lain. Secara khusus, pemain akan, misalnya, melemparkan granat ke sebuah ruangan kecil yang penuh dengan musuh, dan karakter AI di daerah tersebut masing-masing akan mencoba lari ke pintu keluar mereka, tetapi saling berhadapan, dan akhirnya berhenti, berbalik, memukul orang lain, berbalik, dan sebagainya. Ini terlihat sangat tidak realistis.

Upaya untuk membangun algoritme pathfinding yang lebih baik yang dapat berjalan dengan sukses mengingat anggaran komputasi yang ketat gagal. Jadi, alih-alih menyelesaikan masalah pencarian jalan, teman saya menambahkan cek yang sangat murah ke AI: jika AI telah menabrak AI lain dua kali dalam periode waktu yang singkat, berhentilah mencoba mencari jalan keluar dan alih-alih berlindung. Jadi sekarang apa yang terjadi adalah, PC mengambil granat dan melihat sekelompok musuh berlari keluar. Mereka yang saling memukul, berbalik, dan sepertinya mereka menyadari bahwa mereka tidak bisa keluar, jadi mereka menunduk dan menutupi kepala mereka sebelum meledak. Ini terlihat realistis dan sangat memuaskan bagi pemain.

Apakah ada cara serupa yang bisa Anda lakukan untuk mengubah kelemahan dari algoritma penghasil benturan dan mengubahnya menjadi keuntungan?

Saya biasanya menemukan cara terbaik untuk menambah jalur A * dengan bentuk lain dari pencarian jalur untuk skenario lokal lainnya; Penghindaran unit biasanya salah satunya, terutama di dunia di mana ada banyak agen yang bergerak secara bersamaan dan dengan demikian menciptakan pemblokir dinamis).

Secara umum, teknik edge-following dapat digunakan untuk ini. Ketika Anda mengikuti jalur dan menemukan pemblokir yang bukan bagian dari perhitungan jalur asli, Anda pada dasarnya memilih arah (searah jarum jam atau berlawanan arah jarum jam) dan mencoba untuk melintasi pemblokir dengan berkeliling di sekitar itu ke arah itu. Jika Anda tidak bisa, Anda menunggu pemblokir untuk menyelesaikan sendiri (meskipun ini dapat menyebabkan kebuntuan).

Anda juga dapat menerapkan kemampuan bagi unit untuk jalur secara kooperatif; yaitu, suatu unit dapat meminta unit lain untuk sedikit bergerak ke samping sehingga dapat "memeras" unit pemblokiran. Ini tidak bekerja dengan baik di game berbasis ubin di mana Anda dibatasi untuk gerakan berbasis ubin, karena Anda masih bisa menemui jalan buntu di koridor lebar-tunggal seperti contoh Anda. Dalam hal ini Anda dapat menyediakan unit untuk meminta satu sama lain untuk "beralih tempat," yang menghasilkan resolusi sebagian besar waktu. Namun, kadang-kadang ini mengarah ke unit yang saling melompat-lompat.

"Penghindaran unit" adalah topik yang cukup umum ketika membahas pencarian jalan dalam game, ada banyak hits di sana untuk itu. Khususnya Anda mungkin ingin memeriksa pertanyaan ini pada "aliran bidang" merintis jalan digunakan di Panglima Tertinggi 2. RTSs biasanya mengalami masalah ini banyak dan menyelesaikannya dalam segala macam cara yang menarik.

Jika Anda memiliki sistem pergerakan berbasis belokan / tik maka Anda dapat membuat grafik 3D di mana setiap transisi memindahkan agen ke bagaimana peta akan terlihat di masa depan. Kemudian mintalah masing-masing agen mengklaim ubin tempat mereka berada pada titik itu di masa depan dan tandai sebagai tidak dapat diakses. Setiap agen kemudian memiliki opsi tambahan "menunggu" untuk centang berikutnya sebagai cara ke-3 untuk transisi melalui grafik. Ini akan lebih sulit pada sistem Anda tetapi akan memberi Anda hasil yang lebih baik daripada menunggu secara acak. Bahkan lebih baik jika Anda mengizinkan 2 agen untuk berkomunikasi tetapi memiliki salah satu dari mereka mengirim pesan "Saya ingin melewati Anda" jika itu jalur terpendek melewati agen itu,

Saat menggunakan algoritma seperti A * Anda memiliki garis lintang terbesar dalam bekerja dengan heuristik biaya.

Dalam kasus khusus ini Anda dapat menyesuaikan heuristik untuk meningkatkan biaya pergerakan yang membawa agen dekat dengan agen lain, masalahnya ada kemungkinan Anda akan berakhir dengan keduanya mencoba mengambil rute yang lebih tinggi, dan Anda bisa berakhir dengan mereka berosilasi bolak-balik antara jalur saat mereka menutup satu sama lain tergantung pada waktu yang tepat.

Kemungkinan lain adalah untuk melacak rute yang dituju agen dan menyesuaikan biaya ke atas di sepanjang jalur agen yang dimaksud. Ini secara efektif memungkinkan agen untuk saling berkoordinasi sampai batas tertentu. Masalah utama di sini adalah jika semua rute diblokir mencari jalan mungkin terus gagal untuk agen yang bergerak terakhir.

Dalam kasus di mana hanya ada satu jalan, maka pencarian jalan akan gagal atau mereka akan maju satu sama lain sampai mereka menemui jalan buntu.

Jika tidak satu pun dari keduanya cukup baik maka Anda harus mulai melacak waktu ketika menghitung biaya Anda juga. Biaya untuk agen kedua harus menjadi jumlah waktu yang dibutuhkan untuk agen pertama untuk mendapatkan kejelasan ditambah biaya traversal normal, dengan cara itu agen Anda akan dapat memutuskan dengan benar kapan harus menunggu dibandingkan mengambil jalur lain.

Memperhatikan waktu dapat menjadi upaya yang lebih signifikan, sehingga kebanyakan orang puas untuk mengubah tata letak level dan nilai biaya hingga semuanya cukup baik.

Biasanya saya akan menyarankan Anda untuk menggunakan perilaku kemudi untuk menyelesaikan masalah seperti ini selama mengikuti jalur. Dan Anda mungkin masih harus mengambil banyak hal dari mereka untuk mendapatkan inspirasi untuk perilaku pengelompokan. Tapi sayangnya itu tidak benar-benar langsung berlaku untuk gerakan berbasis ubin sederhana.

Karena Anda sudah memiliki penghindaran tabrakan yang berfungsi untuk sebagian besar situasi, mari fokus pada yang satu ini. Saya kira Anda sedang melakukan pathfinding kembali setiap kali agen ingin pindah, atau saya tidak bisa melihat bagaimana mereka bereaksi terhadap orang lain yang bergerak selama perpindahan mereka. Kedua saya kira agen-agen itu ramah satu sama lain.

Anda menyarankan satu agen menunggu yang lain dan saya akan menyarankan Anda untuk melakukan hal itu. Berikan agen cara untuk mengakses jalur yang lain, cari ubin pertama dari jalur Anda sendiri yang bukan bagian dari jalur lain dan pergi ke sana. Masalah dengan teknik ini mungkin:

1. Bagaimana Anda memutuskan apakah ada cara lain yang dapat diterima di sekitar agen lain atau tidak? Anda tidak ingin menunggu agen lain jika ada cukup ruang untuk mengelilinginya. Kegagalan pathfinding ketika mempertimbangkan agen lain adalah tanda yang jelas dari situasi yang ingin Anda perbaiki, tetapi dalam contoh Anda dibesarkan tidak akan ada kegagalan pathfinding. Tetapi Anda dapat - dengan sedikit perhitungan - memutuskan apakah jalur alternatif A * memberi Anda hanya berkeliling agen lain dalam lingkaran kecil, atau menggunakan jalur yang sama sekali berbeda seperti koridor utara.

2. Saya tidak tahu seberapa jauh agen dapat melakukan perjalanan selama satu putaran / operasi, tetapi jika itu tidak cukup jauh, atau jika semua agen bergerak paralel, kedua agen akan memutuskan untuk menunggu di ujung jalan yang lain. Ini dapat diperbaiki dengan menandakan agen lain bahwa Anda membebaskan jalannya.

Salah satu solusi yang mungkin adalah untuk menonaktifkan tabrakan unit di tempat-tempat yang sangat sempit.

Misalnya dalam game Starcraft, pekerja (SCV, Probe, Drone) tidak saling bertabrakan ketika menambang kristal.