Strategi untuk berurusan dengan orang banyak di choke-point

9

Saya baru-baru ini mengganti mesin permainan saya dari perilaku kemudi ke gerakan berbasis impuls dengan resolusi tabrakan berbasis waktu yang tepat. Ini telah memecahkan begitu banyak masalah (tidak lagi tunneling, yay) dan membuat simulasi jauh lebih stabil. Namun, dengan stabilitas telah muncul masalah baru.

Masalah tabrakan pintu.

Tiga bola memulai perjalanan mereka di dekat bagian bawah gambar, target mereka adalah di mana bola merah muda telah berhenti. Di tengah jalan, bola merah dan hijau tersangkut di titik choke di dinding.

Sebelumnya, saya bisa mengandalkan kesalahan floating point dan ketidakstabilan umum dari perilaku kemudi untuk membuat bola hijau dan merah saling berdesak-desakan sampai mereka berhasil melewati choke point. Sekarang dengan resolusi tabrakan yang tepat, gaya yang bekerja pada bola membatalkan satu sama lain yang menghasilkan bola tetap diam.

Metode apa yang biasanya digunakan untuk menyelesaikan situasi seperti itu? Mungkin semacam sistem antrian prioritas akan berfungsi, meskipun saya dapat melihatnya menjadi kompleks setelah saya perlu memutuskan prioritas antara lebih dari 2 objek.

Fibbles
sumber
Saya juga kecewa dengan manajemen kerumunan kemudi. Bisakah Anda menambahkan beberapa tautan tentang "gerakan berbasis impuls" ke dalam pertanyaan?
Kromster
Impuls hanya memaksa waktu. Apa yang saya coba katakan adalah bahwa saya pindah ke model berbasis fisik menggunakan deteksi tabrakan terus menerus daripada diskrit. Perilaku kemudi tidak benar-benar menghargai hal-hal seperti hukum gerak Newton, mereka dirancang untuk meniru kawanan burung daripada menjadi simulasi fisika. Saya tidak benar-benar memiliki tautan gamedev untuk gerakan, itu benar-benar hanya fisika sekolah menengah. Namun, buku Christer Ericson, Real Time Collision Detection adalah game yang cukup untuk deteksi tabrakan terus menerus.
Fibbles

Jawaban:

3

Tetapkan setiap objek bergerak indeks unik & melarang objek dengan indeks lebih tinggi dari memindahkan agen dengan indeks lebih rendah. Ini akan memungkinkan objek 'lama' untuk mendorong yang 'baru', tetapi tidak sebaliknya & lebih sedikit overhead daripada antrian. Pada dasarnya, indeks bertindak sebagai prioritas pergerakan.

Pikalek
sumber
1
Saya sudah menerapkan ini dan berfungsi di unit yang tidak lagi macet, meskipun saya harus mengatakan itu tidak selalu cantik. Beberapa peringatan: hanya menggunakan indeks untuk menentukan prioritas untuk objek bergerak dengan massa yang sama, objek besar harus mendorong benda kecil keluar dari jalan secara alami. Hanya gunakan indeks untuk menentukan prioritas objek di tim yang sama. Objek musuh seharusnya tidak dapat bertindak sebagai dinding tidak bergerak untuk objek pemain hanya karena itu ditelurkan terlebih dahulu dan karenanya memiliki prioritas yang lebih besar.
Fibbles
Saya belum mempertimbangkan massa atau tim; tweak Anda sepertinya cara logis untuk menambal jawaban saya.
Pikalek
2

tambahkan waktu ke pencarian jalur

di sini adalah sebuah makalah yang berbicara tentang kubus waktu: http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Applications_files/coop-path-AIWisdom.pdf

masukkan deskripsi gambar di sini

dan di sini adalah implementasi Objective-C: http://allseeing-i.com/ASIPathFinder

masukkan deskripsi gambar di sini

Rakka Rage
sumber
1
Saya sudah membaca dan mengimplementasikan ini sebelumnya. Bahkan dengan banyak utas itu tidak banyak digunakan dalam situasi saya. Dalam permainan RTS bisa ada ratusan unit yang bergerak dan peta-grid yang lebih besar dari 500 kotak ke samping. Biaya overhead untuk menghitung jalur berbasis waktu untuk setiap unit terlalu tinggi. Sekadar menambahkan, saya tidak mengatakan jawaban rakkarage salah, ini adalah algoritma yang sangat rapi. Saya hanya mengatakan bahwa situasi di mana itu berguna dibatasi oleh kompleksitasnya.
Fibbles
ya saya hanya menjalankan kembali seluruh algoritma pencarian jalur saya setiap belokan alih-alih sepenuhnya memahami dan menerapkan ini tetapi saya pikir saya mungkin harus akhirnya
Rakka Rage
0

Sebenarnya, saya tidak berpikir Anda harus memperbaikinya. Jika (saya bisa menebak) panah menunjukkan vektor gaya yang diterapkan pada bidang apa pun, pada posisi apa pun di kisi (mungkin diinterpolasi "bi-linier" atau juga, atau entah bagaimana lebih banyak "analog" daripada hanya menjadi 0/1), maka perilaku secara fisik benar dan Anda harus memberi selamat kepada diri sendiri karena memiliki solusi yang berperilaku baik.

2 bola berada dalam keseimbangan yang baik, karena mereka duduk di sana dan saling membenci. Rupanya, jika mereka bergerak sedikit ke kanan, "panah kekuatan" ke kanan mempengaruhi bola sisi kanan sedikit lebih (dan sebaliknya di bola sisi kiri; sedikit kurang), dan karenanya mereka bergerak kembali ke keseimbangan. Beginilah seharusnya.

Imho, apa yang harus diperbaiki adalah dinding, atau ukuran bola, atau sesuatu yang lain di antara batu bata itu sendiri. Anda telah menciptakan suatu kemustahilan dan perilaku yang benar dalam situasi itu merupakan jalan buntu (maaf untuk kata-kata yang menyalahgunakan, saya harap Anda mendapatkannya :-)).

Mungkin sebaliknya menonaktifkan panah kekuatan kiri / kanan terdekat, atau mengaturnya dengan cara lain yang tidak simetris dan tidak mendorong untuk menyeimbangkan ?

Saya pikir itu akan menjadi perbaikan buruk untuk memperbaikinya secara palsu ... akan menjadi terlalu dini.

Angin badai
sumber
Ini tidak menjawab pertanyaan. Saya mengerti motivasi Anda, tetapi pada akhirnya pertanyaannya adalah bagaimana menghadapi situasi tersebut. Kami tidak tahu niat gameplay, jadi menilai apakah ini masalah atau tidak, terserah Fibbles. Mengubah dinding dapat mengubah tujuan chokepoint. Pertanyaannya adalah masalah valid yang bisa diselesaikan.
Felsir
Jawaban saya pada dasarnya: (mengatur ulang) kekuatan atau mengatur kembali sesuatu yang lain dalam skenario tetapi tidak berebut pemecah fisika (" Imho, apa yang harus diperbaiki adalah dinding, atau ukuran bola, atau sesuatu yang lain di antara buildstones) diri mereka sendiri. "). Pertanyaannya adalah " Metode apa yang biasanya digunakan untuk menyelesaikan situasi seperti itu?" Saya pikir A saya sangat banyak "metode yang biasa digunakan" dan sangat banyak solusi untuk masalah ini. Misalnya game minigolf daring (yang diingatkan Q akan melakukan banyak hal) benar-benar mencekik, jika lingkungan meminta hal itu terjadi. Fisika yang tidak menentu adalah cara yang buruk, imo.
Stormwind
Saya setuju bahwa pemecah fisika harus tetap bijaksana. Pertanyaannya menyatakan bola harus mencari target, pada dasarnya bagaimana mengubah perilaku agen (sehingga bukan fisika atau tata letak level). Mengubah tata letak level dapat menyelesaikan kejadian ini - tetapi ini mungkin memotong dalam tata letak yang berbeda. Jadi pertanyaannya berbeda dari contoh minigolf yang Anda berikan karena dalam contoh ini pertanyaannya adalah untuk secara khusus menghindari kebuntuan.
Felsir
Seperti yang Anda lihat, saya juga mengusulkan mengatur ulang kekuatan dalam jawabannya. Tampaknya sedikit tersisa setelah itu :-).
Stormwind
Mengatur ulang dinding atau mengubah ukuran bola tidak layak dalam kasus saya, meskipun mungkin di orang lain. Tangkapan layar berasal dari mode debug mesin RTS. Ada banyak ukuran unit yang berbeda dan dinding dapat ditempatkan sesuka hati oleh pemain. Panah yang Anda lihat dihasilkan oleh algoritma Fast Flow Fields saya. Mereka adalah vektor dinormalisasi yang digunakan untuk mempengaruhi arah perjalanan unit bergerak. Tidak dimungkinkan untuk mengubah panjang vektor karena semua unit yang dapat bergerak dalam grup berbagi Field Flow yang sama.
Fibbles