Deteksi Tabrakan 2D yang lebih cepat

Baru-baru ini saya telah mengerjakan penembak 2d yang bergerak cepat dan saya menemukan masalah besar. Deteksi tabrakan. Tentu, ini bekerja, tetapi sangat lambat. Tujuan saya adalah: Miliki banyak musuh di layar dan minta mereka untuk tidak saling menyentuh. Semua musuh mengejar entitas pemain. Sebagian besar dari mereka memiliki kecepatan yang sama sehingga cepat atau lambat mereka semua berakhir mengambil ruang yang sama saat mengejar pemain. Ini benar-benar menjatuhkan faktor kesenangan karena, bagi pemain, sepertinya Anda dikejar oleh satu musuh saja. Untuk mencegah mereka mengambil ruang yang sama saya menambahkan deteksi tabrakan (deteksi 2D yang sangat mendasar, satu-satunya metode yang saya tahu) yang.

Enemy class update method
    Loop through all enemies (continue; if the loop points at this object)
        If enemy object intersects with this object
            Push enemy object away from this enemy object

Ini berfungsi dengan baik. Selama aku hanya punya <200 entitas musuh. Ketika saya mendekati 300-350 entitas musuh, frame rate saya mulai turun drastis. Pertama saya pikir itu rendering yang buruk jadi saya menghapus panggilan imbang mereka. Ini tidak membantu sama sekali jadi tentu saja saya menyadari itu adalah metode pembaruan. Satu-satunya bagian berat dalam metode pembaruan mereka adalah bagian ini masing-masing musuh-loop-melalui-setiap-musuh. Ketika saya mendekati 300 musuh, game melakukan iterasi langkah 90000 (300x300). My my ~

Saya yakin pasti ada cara lain untuk mendekati deteksi tabrakan ini. Meskipun saya tidak tahu caranya. Halaman yang saya temukan adalah tentang bagaimana sebenarnya melakukan tabrakan antara dua objek atau bagaimana memeriksa tabrakan antara objek dan ubin. Saya sudah tahu dua hal itu.

tl; dr? Bagaimana cara mendekati deteksi tabrakan antara LOTS entitas?

Sunting cepat: Jika ada bantuan, saya menggunakan C # XNA.

Anda telah mencapai masalah Anda tepat di kepala, Anda memiliki setiap entitas memeriksa setiap entitas lainnya. Apa yang Anda inginkan adalah beberapa jenis sistem 'Level of Detail' (ini cukup banyak adegan grafik yang sangat sederhana, Anda hanya menggunakannya untuk hal-hal selain rendering :)) di mana kandidat tabrakan yang mungkin lebih baik dipilih.

Saya biasanya melakukan tiga koleksi untuk sistem seperti ini. Dan ketika Anda berbicara tentang jumlah entitas yang ingin Anda miliki, Anda mungkin perlu menggunakan grafik adegan penuh untuk ini sebagai data pelacakan (3 daftar per entitas dengan entri untuk setiap entitas lainnya) dapat dengan cepat keluar kontrol.

Meskipun pada dasarnya Anda memiliki tiga daftar. Yang pertama haruslah daftar entitas yang sangat kecil yang akan Anda periksa dengan interaksi setiap frame. Anda menentukan ini karena mereka berada dalam rentang X entitas yang dimaksud. Seperti disebutkan poin dari daftar ini adalah untuk mengandung setiap entitas yang dapat bertabrakan dengan yang lain.

Daftar berikutnya adalah daftar yang berada dalam kisaran buffer yang dapat bergerak ke kisaran entitas tanpa terlalu banyak upaya .. Kami akan menyebut kisaran ini X * 1.5 hanya untuk argumen. Ini adalah daftar irisan waktu di mana Anda hanya akan memperbarui beberapa dari mereka per frame tetapi memastikan bahwa Anda akan melalui mereka cukup cepat untuk menjaga penampilan hal-hal yang berfungsi dengan lancar.

Daftar ketiga adalah daftar 'segalanya' dan cara untuk menghindari memiliki yang satu ini mungkin bernilai sementara (Memindai seluruh daftar entitas dan mungkin memeriksa untuk melihat apakah ada di salah satu daftar lain sebelum berkembang mungkin? Tergantung pada ukuran daftar ini mungkin bekerja, atau mungkin membuat segalanya jauh lebih buruk.) Objek dalam daftar ini diperiksa paling tidak karena harus mengambil lebih dari beberapa bingkai untuk ditempatkan ke dalam salah satu dari dua daftar lainnya.

Apa yang Anda juga perlu lakukan untuk mempertahankan ini adalah ketika Anda melakukan tes tabrakan, pastikan Anda memperbarui daftar entitas yang masuk. Orang-orang yang keluar dari jangkauan harus diturunkan dan juga yang bergerak lebih dekat harus ditingkatkan menjadi daftar lebih aktif diperiksa.

Dengan asumsi Anda menjaga hal-hal yang cukup sederhana ini sesuai dengan kebutuhan Anda. Jika Anda dapat memasukkan informasi tambahan ke grafik adegan rendering yang ada (dengan asumsi Anda memilikinya) maka Anda dapat meminta informasi untuk mendapatkan daftar entitas yang berada dalam kisaran yang akan lebih baik karena itu adalah seluruh titik grafik adegan anyways (akses cepat ke daftar data yang relevan berdasarkan posisi). Ini hanya berpotensi mengambil lebih banyak pekerjaan untuk dilakukan dan Anda harus selalu mempertimbangkan apa yang perlu Anda lakukan vs apa yang seharusnya Anda lakukan.

Semoga ini membantu.

Anda harus menangani tabrakan dengan struktur data yang diurutkan, sehingga Anda dapat memiliki n * log (n) kali alih-alih mengerikan n ^ 2. Dan n * log (n) hampir linier seperti yang Anda tahu. Salah satu contoh (klasik) adalah quadtree, ada tutorial yang cukup sederhana dan ditulis dengan baik di sini, dengan grafik dan kode (Java):

http://gamedev.tutsplus.com/tutorials/implementation/quick-tip-use-quadtrees-to-detect- maybe-collisions-in-2d-space/

Rq: cukup mudah untuk menemukan implementasi untuk QuadTrees dalam bahasa apa pun. Namun, Anda harus berpikir tentang 'granularity' yang tepat untuk pohon tersebut, dan semakin besar ukuran pohonnya, semakin banyak kita memiliki entitas yang tidak muat di dalam simpul.
Rq 2: karena partisi ruang Anda dilakukan hanya untuk deteksi tabrakan, Anda memiliki kebebasan sempurna untuk membagi ruang sesuka Anda. Sebagai contoh, saya tidak akan membagi menjadi empat bagian egal tetapi saya akan menggunakan baricenter dari entitas tingkat saat ini sebagai pusat untuk kesenjangan baru. 1) algoritma masih n * log (n), 2) Anda kehilangan kemungkinan untuk 'membangun kembali' adegan dari pohon -tapi Anda tidak peduli- dan 3) Anda memiliki pohon yang jauh lebih seimbang, lebih sedikit overhead .
Rq3: Setelah Anda memiliki pohon, 'tabrakan' antara layar dan entitas memberi Anda ... entitas yang terlihat !! pada suatu waktu lebih suka log (n), jadi mengapa tidak jika n besar? (Kasus terburuk jelas merupakan waktu yang tepat untuk pendekatan ini.)

pohon partisi ruang biner, quadtree, octree (untuk 3D) adalah pohon yang mungkin Anda dapat hasilkan (atau pertahankan, jika Anda berambisi) di setiap panggilan pembaruan untuk setiap objek yang ingin Anda tabrakan untuk diterapkan.

Saya cukup naif ketika pembicaraan tentang quad atau oct tree. Tetapi saya pikir metode ini harus dilakukan:

Anda perlu memodifikasi struktur pemain / kelas. Tambahkan array / vektor pointer ke struktur pemain lain.

Setiap detik periksa jarak antara masing-masing dua pemain. Jika sangat rendah sehingga memungkinkan untuk mencapai dalam 1 detik kemudian tambahkan pointer pemain ke array tabrakan pemain saat ini.

Sekarang hanya periksa tabrakan antara pemain di setiap daftar yang lain.