Menentukan apakah dua objek yang bergerak cepat harus diserahkan untuk pemeriksaan tabrakan

8

Saya memiliki mesin fisika 2D dasar yang sedang berjalan. Ini cukup banyak mesin partikel, hanya menggunakan bentuk dasar seperti AABBs dan lingkaran, jadi tidak mungkin ada rotasi. Saya memiliki CCD yang diimplementasikan yang dapat memberikan TOI akurat untuk dua objek yang bergerak cepat dan semuanya bekerja dengan lancar.

Masalah saya sekarang adalah bahwa saya tidak tahu bagaimana menentukan apakah dua objek yang bergerak cepat bahkan harus diperiksa terhadap satu sama lain di tempat pertama. Saya menggunakan pohon quad untuk partisi spasial dan untuk setiap objek yang bergerak cepat, saya memeriksanya terhadap objek di setiap sel yang dilewatinya. Ini berfungsi dengan baik untuk menentukan tabrakan dengan geometri statis, tetapi itu berarti bahwa objek bergerak cepat lainnya yang bisa bertabrakan dengannya, tetapi tidak ada dalam sel yang diperiksa, tidak pernah dipertimbangkan.

Satu-satunya solusi untuk ini yang dapat saya pikirkan adalah memiliki sel yang cukup besar dan menyilangkan jari bahwa ini sudah cukup, atau untuk mengimplementasikan semacam algoritma brute force. Apakah ada cara yang tepat untuk menangani ini, mungkin seseorang memecahkan masalah ini secara efisien. Atau mungkin ada cara yang lebih baik untuk mempartisi ruang yang menyebabkan ini?

Berikut diagram:

masukkan deskripsi gambar di sini

Objek "dan efek" lintas Objek A dan B, harus diperiksa satu sama lain. Tetapi dengan cara saya saat ini memeriksa tabrakan tidak memperhitungkan ini. Sekali lagi, saya bisa memikirkan beberapa solusi untuk ini seperti benar-benar memeriksa jika jalur objek menyeberang setelah kecepatan mereka lebih tinggi dari x, atau sesuatu, tapi itu terasa seperti retasan dan itu berantakan untuk dicoba dan diimplementasikan.

collision-detection physics dreta
sumber
Bisakah Anda memberikan contoh skenario di mana metode Anda gagal?
Anko
1
Saya pikir akan seperti ini: objek A dan B berada dalam konfigurasi ini: [A] [] [B]. A akan ke kanan dan B ke kiri. Mereka cepat. Pemeriksaan tabrakan berjalan seperti itu: apakah sel berikutnya kosong untuk A? Ya, bcs tidak ada apa-apa di sel tengah. Apakah sel berikutnya kosong untuk B? Iya. Jadi tidak ada tabrakan. Tetapi fisika nyata akan menunjukkan bahwa A dan B kemungkinan akan bertabrakan (terutama dalam permainan satu dimensi yang saya
uraikan
@ Cystack Saya sudah menerapkan CCD. Situasi yang Anda uraikan bukanlah masalah. Dua objek saling lurus, implementasi yang saya jelaskan akan mengambilnya dan menyelesaikannya.
dreta
Fisika situasi jelas. Katakanlah Anda dapat mengidentifikasi objek sebagai 'bergerak cepat' sebelumnya. Kemudian ketika Anda melakukan pemeriksaan tabrakan, Anda perlu memeriksa tidak hanya untuk sel tempat objek saat ini, tetapi semua sel yang dilewati pada langkah terakhir kali. Jadi setiap objek yang bergerak cepat sebenarnya memiliki banyak lokasi, seperti seluruh petak hijau yang Anda gambar pada gambar di atas.
theJollySin
@ theJollySin saya sudah menggambarkan solusi yang Anda berikan, ini peretasan, kasus khusus, saya mencari solusi umum jika ada.
Dreta

Jawaban:

5

Masalah yang Anda bicarakan sering disebut 'deteksi tabrakan broadphase' dan solusi Anda adalah 'volume tersapu', bukan benar-benar retasan, hanya bagaimana hal itu dilakukan (cukup ambil AABB dari objek termasuk awal dan akhir gerakan dan gunakan itu untuk tabrakan - meskipun hal menjadi sedikit rumit dengan rotasi).

Kemudian, pergi ke algoritma pendeteksian benturan broadphase yang membuat ini cepat disebut 'Sweep and Prune.

Jeff Gates
sumber
Saya membuang SAP sebelum masalah ini muncul. Saya melakukan ini dalam JavaScript yang membuat overhead untuk daftar terlihat, juga array bisa menjadi tidak dapat diandalkan ketika datang ke kinerja. Kira saya harus mempertimbangkan kembali hal-hal. Terima kasih, algoritme memang menyelesaikan masalah.
dreta