Respon tabrakan game 2D: SAT & perpindahan minimum di sepanjang sumbu yang diberikan?

Saya mencoba menerapkan sistem tabrakan dalam game 2D yang saya buat. Teorema sumbu pemisah (seperti yang dijelaskan oleh tutorial tabrakan metanet ) sepertinya merupakan cara yang efisien dan tangguh dalam menangani deteksi tabrakan, tapi saya tidak terlalu menyukai metode respons tabrakan yang mereka gunakan. Dengan memindahkan secara membabi buta di sepanjang sumbu tumpang tindih paling sedikit, algoritma hanya mengabaikan posisi sebelumnya dari objek bergerak, yang berarti bahwa itu tidak bertabrakan dengan objek stasioner sebanyak itu masuk dan kemudian memantul.

Berikut adalah contoh situasi di mana ini penting:

Menurut metode SAT yang dijelaskan di atas, persegi panjang hanya akan keluar dari segitiga tegak lurus dengan sisi miringnya:

Namun, secara realistis, persegi panjang harus berhenti di sudut kanan bawah segitiga, karena itu akan menjadi titik tabrakan pertama jika bergerak terus menerus sepanjang vektor perpindahannya:

Sekarang, ini mungkin tidak terlalu penting selama bermain game, tapi saya ingin tahu apakah ada cara yang efisien dan umumnya mendapatkan perpindahan akurat dengan cara ini. Saya telah memeras otak saya selama beberapa hari terakhir, dan saya belum mau menyerah!

(Diposting silang dari StackOverflow, harap itu tidak melanggar aturan!)

Inilah metode yang saya temukan. Mungkin cacat, tetapi saya belum menemukan masalah dengan itu dalam analisis sepintas saya. Ini juga berfungsi untuk poligon sewenang-wenang dengan beberapa modifikasi kecil.

Dalam ilustrasi di bawah ini, objek biru bergerak dan objek merah stasioner. Langkah 1: Untuk setiap poligon, temukan dua titik terjauh sepanjang proyeksi poligon itu ke garis yang tegak lurus dengan vektor gerakan. Langkah 2: Bagilah setiap poligon di sepanjang garis yang menghubungkan titik-titik ini. Setengah dari poligon yang menghadap poligon lain di sepanjang vektor gerak adalah "lambung depan". Ini adalah satu-satunya bagian dari poligon yang dapat bertabrakan. Langkah 3:Proyeksikan vektor dari setiap titik pada "lambung maju" setiap poligon di sepanjang vektor gerakan ke arah poligon yang berlawanan, dan periksa untuk persimpangan dengan setiap tepi "lambung maju" poligon yang berlawanan. (Mungkin lambat, tetapi komputer saat ini cukup cepat - bukan?) (Maaf tentang panah miring. Semua panah harus paralel.) Langkah 4: Ambil vektor terpendek. Ini adalah jarak tumbukan yang tepat. Langkah 5: Voila!

Lihat pertanyaan serupa ini: Resolusi Tabrakan

Dan juga, dari http://www.metanetsoftware.com/technique/tutorialA.html#section5 (yang Anda poskan tautannya ke :))

BAGIAN 5: Objek Bergerak Cepat

Seperti disebutkan di atas, objek kecil dan / atau bergerak cepat dapat menghasilkan masalah saat menggunakan uji tabrakan statis. Ada beberapa pendekatan yang dapat diambil untuk menangani objek seperti itu - yang paling sederhana adalah membatasi desain game Anda sehingga objek seperti itu tidak diperlukan.

Jika Anda benar-benar harus memilikinya, ada dua metode umum untuk menangani objek kecil dan / atau bergerak cepat: tes tabrakan-sapu, dan multisampling.

- = tes sapuan = -

Alih-alih menguji untuk persimpangan antara dua bentuk statis, kita bisa membuat bentuk baru dengan menyapu bentuk asli sepanjang lintasannya, dan menguji tumpang tindih antara bentuk menyapu ini.

Ide dasar dijelaskan dalam [Gomez], untuk tes lingkaran-lingkaran dan AABB-AABB.

- = multisampling = -

Alternatif yang jauh lebih sederhana untuk menyapu tes adalah dengan multisampel; alih-alih melakukan uji statis tunggal pada posisi baru objek, lakukan beberapa tes pada beberapa posisi yang terletak di antara posisi sebelumnya dan baru. Teknik ini digunakan untuk bertabrakan Ragdoll di N.

Jika Anda memastikan bahwa sampel selalu ditempatkan pada jarak kurang dari radius objek, ini akan menghasilkan hasil yang sangat baik. Dalam implementasi kami, kami membatasi jumlah sampel maksimum, sehingga kecepatan yang sangat tinggi kadang-kadang akan menimbulkan masalah; ini adalah sesuatu yang dapat diubah berdasarkan aplikasi spesifik Anda.

EDIT

Dalam ringkasan dan AFAIK, ada beberapa solusi

1. Batasi gim Anda agar tidak pernah memiliki benda kecil dan / atau bergerak cepat yang bahkan dapat menyebabkan ini
2. Terapkan sistem yang menghentikan tabrakan agar tidak benar-benar terjadi, seperti dijelaskan dalam tautan pertama yang saya posting
3. Tingkatkan laju sampling Anda untuk objek bergerak cepat dan / atau kecil
4. ... mungkin lebih, tapi aku bukan ahli.

Itu tergantung apakah Anda hanya ingin gerakan linier, atau jika Anda perlu mengatasi gerakan sudut juga.

Alternatif untuk menggunakan SAT:

Dalam kasus linear hanya Anda dapat ray-cast terhadap Perbedaan Minkowski dari dua poligon dari asal ke arah kecepatan linear delta objek.

Jika sinar menyentuh MD, kedua benda akan bertabrakan dan titik hit akan memberi tahu Anda waktu t di mana mereka bertabrakan.

Sekarang, jika objek bergerak dan berputar semakin sulit, tetapi Anda masih bisa menggunakan teknik serupa. Kemajuan Konservatif akan memungkinkan Anda untuk menangani kasus ini. Teknik ini berulang; setiap iterasi akan menghasilkan MD baru dan membawa Anda lebih dekat ke waktu persimpangan.

Inilah draf makalah asli tentang Perkembangan Konservatif:

http://www.continuousphysics.com/BulletContinuousCollisionDetection.pdf

Saya menulis sebuah artikel yang menjelaskan teknik secara rinci di sini:

http://www.wildbunny.co.uk/blog/2011/04/20/collision-detection-for-dummies/

Semoga bantuan ini!