Algoritma pendeteksian tabrakan fase-sempit

Ada tiga fase deteksi tabrakan.

1. Broadphase : Ini loop antara semua objek yang dapat berinteraksi, false positive diizinkan, jika itu akan mempercepat loop.

2. Narrowphase : Menentukan apakah mereka bertabrakan, dan kadang-kadang, bagaimana, tidak ada positif palsu

3. Resolusi : Mengatasi tabrakan.

Pertanyaan yang saya ajukan adalah tentang frasa sempit. Ada beberapa algoritma, berbeda dalam kompleksitas dan akurasi.

1. Persimpangan Hitbox : Ini adalah algoritma a-posteriori, yang memiliki kompleksitas terendah, tetapi juga tidak terlalu akurat,

2. Persimpangan warna : persimpangan Hitbox untuk setiap piksel, a-posteriori, piksel-sempurna, tidak akurat dalam hal waktu, kompleksitas lebih tinggi

3. Teorema sumbu pisah : Ini lebih sering digunakan, akurat untuk segitiga, namun, a-posteriori, karena tidak dapat menemukan tepi, ketika mengambil bingkai terakhir, lebih stabil

4. Linear raycasting : Algoritma A-priori, berguna untuk fisika yang tampak semi-realistis, menemukan titik persimpangan, bahkan lebih akurat daripada SAT, tetapi dengan lebih banyak kerumitan

5. Interpolasi spline : A-priori, bahkan lebih akurat daripada sinar linear, bahkan lebih banyak orang.

Mungkin ada banyak lagi yang saya lupa. Pertanyaannya adalah, kapan lebih baik menggunakan SAT, kapan sinar, kapan splines, dan apakah ada sesuatu yang lebih baik.

Dua yang Anda lewatkan yang langsung menonjol bagi saya adalah GJK dan MPR.

GJK adalah algoritma untuk menemukan titik terdekat dari dua poligon cembung. Dengan sedikit kerja ekstra Anda dapat menggunakannya untuk menemukan titik kejadian untuk memotong objek, dan karenanya menghitung manifold tabrakan. Ini dilakukan melalui kliping poligon, sama seperti jika menggunakan SAT, tetapi GJK menghemat beberapa langkah (karena Anda sudah memiliki poin terdekat).

MPR (Minkowski Portal Refinement) adalah algoritma lain, mirip dengan GJK (keduanya menggunakan ruang Minkowski). Itu tidak dapat menemukan titik terdekat antara objek yang tidak berpotongan seperti GJK, tetapi memiliki banyak properti bagus untuk gim, dan merupakan cara yang digunakan untuk mendapatkan bermacam-macam kontak.

MPR adalah salah satu yang paling populer untuk gim. Ini sangat efisien, stabil secara numerik, dan mudah diimplementasikan.

Fase sempit lainnya lebih banyak digunakan dalam permainan khusus. Game balap biasanya menggunakan ray casting sebagai pemodelan ban aktual dan mendapatkan perilaku realistis (atau bahkan hanya bersenang-senang) belum dimungkinkan menggunakan bentuk tumbukan tradisional dan pemodelan resolusi. Platformer juga biasanya menggunakan tabrakan dan fisika yang sangat tersesuaikan, karena fisika "seperti Mario" yang lebih disukai tidak dimodelkan dengan algoritma fisika tradisional. Anda juga akan sering melihat metode tabrakan dan fisika yang berbeda untuk cairan dan semacamnya, meskipun saya kurang tahu tentang itu.

Lihat:

• http://www.codezealot.org/archives/tag/gjk
• http://xenocollide.snethen.com/

Saya ingin mengatakan, itu Tes Sumbu Pemisah , bukan Teorema.

Anda akan menggunakan SAT pada poligon yang tidak bergerak (2D), meskipun Anda dapat memperluasnya untuk mengatasi gerakan linear relatif.

http://elancev.name/oliver/2D%20polygon.htm#tut3

Jangan gunakan GJK dalam 2D, saya menemukan itu sebenarnya lebih lambat dari sekadar memaksa SAT.

Teknik lain yang dapat Anda gunakan adalah Perbedaan Minkowski, yang menyusutkan satu objek ke satu titik dan 'menumbuhkan' yang lain dengan bentuk yang pertama. Kemudian Anda menguji objek gabungan terhadap titik yang jauh lebih mudah - ini memberi Anda jarak penetrasi dan normal. Saya menemukan alat ini secara konseptual sangat berguna untuk mendekati masalah deteksi tabrakan baru; lebih mudah divisualisasikan daripada SAT.

Untuk memindahkan dan memutar poligon (dan polihedron) Anda dapat menggunakan Kemajuan Konservatif untuk menemukan waktu dan titik kontak yang tepat.

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

Anda dapat membaca lebih lanjut tentang teknik ini di posting blog ini yang saya tulis beberapa waktu lalu:

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

Semoga itu bisa membantu!

Salam, Paul.

Ini sangat tergantung pada jenis gim yang Anda miliki. Setiap metode di atas memiliki trade-off sendiri.

Namun, SAT cukup standar dalam pengalaman saya untuk perpustakaan fisika generik, Kel. Box2D menggunakannya secara luas (Angry Birds, dan banyak game lain menggunakan Box2D).

Variasi persimpangan warna yang dicampur dengan persimpangan SAT atau Hitbox digunakan dalam game seperti Sonic, Megaman dengan hasil yang baik.

Saya tidak tahu banyak tentang # 4 dan # 5.