Bagaimana saya bisa mengimplementasikan deteksi tabrakan 2D yang cepat dan akurat?

11

Saya sadar bagaimana mendeteksi jika dua atau lebih objek 2D bertabrakan, tetapi saya tertarik bagaimana memutuskan apakah akan memeriksa tabrakan. Dalam proyek-proyek sebelumnya, saya baru saja memeriksa setiap objek terhadap setiap objek lain (saya tahu, O (n ^ 2) tingkat kebodohan) dan itu menciptakan gameplay yang kurang lancar.

Berbagai forum memuji kehebatan Quadtrees, B-Trees, dan jenis pohon atau struktur apa pun yang dapat Anda pikirkan.

Apa struktur yang paling efisien untuk menentukan apakah tumbukan harus diperiksa?

2d collision-detection data-structure Mike Cluck
sumber
1
Satu hal yang mungkin ingin Anda pertimbangkan adalah hanya memeriksa tabrakan untuk objek yang telah bergerak, dan satu-satunya objek yang dekat dengan Anda. Sistem saya saat ini berfungsi dengan baik (ratusan ribu objek) - dan hanya itu yang saya lakukan.
ultifinitus
Saya pikir gamedev.stackexchange.com/questions/14369/… dapat membantu Anda banyak. pada awalnya dimaksudkan untuk dan algoritma untuk pemrosesan paralel tetapi saya pikir algoritma yang sama juga dapat meningkatkan aplikasi berulir tunggal.
Ali1S232
1
@ultifinitus Pada dasarnya itulah yang saya tanyakan. Bagaimana cara menentukan objek mana yang berada di dekatnya tanpa mengulangi setiap objek dan memeriksa posisinya?
Mike Cluck
Mike, Anda dapat mengirim email kepada saya untuk beberapa kode spesifik yang saya gunakan, ada di c ++ - atau saya bisa memberi Anda struktur dasar, meskipun mungkin agak ambigu dan rumit karena itu.
ultifinitus
1
Ini bukan duplikat karena saya bertanya struktur apa yang paling cocok untuk menentukan apakah kita harus repot memeriksa tabrakan. Pertanyaan lain itu bertanya tentang tabrakan transparan vs tidak transparan. Belum lagi, pertanyaan ini ditanyakan sekitar satu tahun sebelum yang Anda tautkan.
Mike Cluck

Jawaban:

12

Untuk gim 2d, kecuali objek 2D memiliki distribusi yang sangat berat ke satu sisi peta Anda, kisi yang seragam hampir selalu merupakan cara untuk melakukannya. Kompleksitas memori lurus ke depan, (sebanding dengan dimensi peta Anda), dan dengan distribusi yang masuk akal, memiliki O (1) waktu pencarian dan rata-rata log (numberOfObjects / (baris * kolom)) ^ 2 tes persimpangan dilakukan per sel. Anda mungkin memutuskan untuk hanya memeriksa sel-sel yang memiliki objek bergerak di dalamnya, yang membuat geometri statis jauh lebih efisien. Sangat mudah untuk memodifikasi grid yang seragam dengan cepat, (jauh lebih sedikit daripada solusi berbasis pohon), dan lebih mudah untuk diterapkan. Satu-satunya waktu saya akan mengatakan untuk tidak menggunakannya dalam permainan 2D adalah ketika persyaratan memori dari grid yang seragam menjadi terlalu besar, (misalnya ruang sim di mana levelnya jarang tetapi sangat besar).

Darcy Rayner
sumber
Bagaimana solusi ini menangani objek yang membatasi 2 atau 4 sel kotak?
ashes999
1
Setiap sel objek yang tumpang tindih, itu dianggap berada di, sehingga objek dapat berada dalam banyak sel. Sebagian besar struktur data spasial akan menangani masalah tumpang tindih dengan cara yang sama.
Darcy Rayner
Wow, itu pintar sekali. +1 Bung ceria.
ashes999
1

Jika dunia Anda memiliki satu dimensi yang sangat "panjang" (sebut saja X), dibandingkan dengan yang lain, Anda dapat menyimpan objek dalam daftar berurutan yang dapat Anda sortir kembali saat mereka bergerak, dan kemudian deteksi tabrakan berarti hanya memeriksa objek yang tumpang tindih pada sumbu X.

Kemungkinan lain adalah menyimpan daftar objek aktif / pasif, dan tidak repot-repot dengan objek pasif (yang tidak bergerak sama sekali).

Jika mereka semua benda berukuran sedang yang dapat dilihat oleh pemain di layar, semuanya vs semuanya mungkin tidak terlalu buruk.

Selain itu, saya dengan Darcy, kotak seragam itu bagus.

MarkR
sumber