Bagaimana cara kerja mesin collision?

Bagaimana tepatnya cara kerja mesin collision ?

Ini adalah pertanyaan yang sangat luas. Kode apa yang membuat benda-benda saling memantul, kode apa yang membuat pemain berjalan ke dinding alih-alih berjalan menembus dinding? Bagaimana kode terus-menerus menyegarkan posisi pemain dan posisi objek untuk menjaga gravitasi dan tabrakan berfungsi sebagaimana mestinya?

Jika Anda tidak tahu apa itu mesin tabrakan, pada dasarnya ini biasanya digunakan dalam permainan platform untuk membuat pemain menabrak dinding dan sejenisnya. Ada tipe 2D dan tipe 3D, tetapi mereka semua mencapai hal yang sama: tabrakan.

Jadi, apa yang membuat mesin tabrakan terus berdetak?

Ada perbedaan besar antara mesin tabrakan dan mesin fisika. Mereka tidak melakukan hal yang sama, meskipun mesin fisika umumnya mengandalkan mesin tabrakan.

Mesin tumbukan kemudian dibagi menjadi dua bagian: deteksi tumbukan dan respons tumbukan. Yang terakhir ini umumnya bagian dari mesin fisika. Inilah sebabnya mengapa mesin tabrakan dan mesin fisika biasanya digulung ke perpustakaan yang sama.

Deteksi tabrakan datang dalam dua bentuk, diskrit dan kontinu. Mesin canggih mendukung keduanya, karena mereka memiliki sifat yang berbeda. Secara umum, deteksi tabrakan berkelanjutan sangat mahal dan hanya digunakan di tempat yang sangat dibutuhkan. Mayoritas tabrakan dan fisika ditangani menggunakan metode diskrit. Dalam metode diskrit, benda-benda pada akhirnya akan saling menembus, dan mesin fisika kemudian bekerja untuk mendorongnya. Jadi mesin tidak benar-benar menghentikan pemain berjalan sebagian melalui dinding atau lantai, itu hanya memperbaikinya setelah mendeteksi bahwa pemain sebagian di dinding / lantai. Saya akan fokus pada pendeteksian tabrakan diskrit di sini, karena itulah yang paling banyak saya alami dari awal.

Deteksi Tabrakan

Deteksi tabrakan relatif mudah. Setiap objek memiliki transformasi dan bentuk (mungkin beberapa bentuk). Pendekatan naif akan membuat mesin tabrakan melakukan loop O (n ^ 2) melalui semua pasangan objek dan menguji jika ada tumpang tindih antara pasangan. Dalam pendekatan yang lebih cerdas ada beberapa struktur data spasial (misalnya, untuk objek statis vs dinamis), bentuk pembatas untuk setiap objek, dan sub-bentuk cembung multi-bagian untuk setiap objek.

Struktur data spasial mencakup hal-hal seperti KD-Trees, pohon Dynamic AABB, Octrees / Quadtrees, pohon Binary Space Partitioning, dan sebagainya. Masing-masing memiliki kelebihan dan kekurangan, itulah sebabnya beberapa mesin kelas atas menggunakan lebih dari satu. Pohon-pohon AABB dinamis misalnya sangat cepat dan bagus untuk menangani banyak objek bergerak sementara KD-Tree mungkin lebih cocok untuk geometri tingkat statis yang bertabrakan dengan objek. Ada opsi lain juga.

Fase luas menggunakan struktur data spasial dan volume pembatas abstrak untuk setiap objek. Volume pembatas adalah bentuk sederhana yang melingkupi seluruh objek, umumnya dengan tujuan melampirkannya "sekencang mungkin" sambil tetap murah untuk melakukan uji tabrakan. Bentuk pembatas yang paling umum adalah Bounding Box Axis-Aligned, Bounding Box-Aligned Box, Spheres, dan Capsules. AABB umumnya dianggap yang tercepat dan termudah (Spheres lebih mudah dan lebih cepat dalam beberapa kasus, tetapi banyak dari struktur data spasial akan membutuhkan mengubah bola menjadi AABB), tetapi mereka juga cenderung menyesuaikan banyak objek dengan agak buruk. Kapsul populer di mesin 3D untuk menangani tabrakan tingkat karakter. Beberapa mesin akan menggunakan dua bentuk pembatas,

Fase terakhir dari deteksi tabrakan adalah untuk mendeteksi secara tepat di mana geometri berpotongan. Ini biasanya menyiratkan menggunakan mesh (atau poligon dalam 2D), meskipun tidak selalu. Tujuan dari fase ini adalah untuk mengetahui apakah objek benar-benar benar-benar bertabrakan, jika diperlukan tingkat detail yang halus (misalnya, tabrakan peluru di penembak, di mana Anda ingin dapat mengabaikan tembakan yang nyaris tidak terjawab), dan juga untuk mencari tahu persis di mana objek bertabrakan, yang akan mempengaruhi bagaimana objek merespons. Misalnya, jika sebuah kotak duduk di tepi meja, mesin harus tahu pada titik mana meja mendorong terhadap kotak; tergantung pada seberapa jauh kotak tergantung, kotak mungkin mulai miring dan jatuh.

Hubungi Generasi Berjenis

Algoritma yang digunakan di sini termasuk algoritma GJK dan Minkowski Portal Refinement yang populer, serta tes Separating Axis. Karena algoritma populer biasanya hanya bekerja untuk bentuk cembung, perlu untuk memecah banyak objek kompleks menjadi sub-objek cembung, dan melakukan tes tabrakan untuk masing-masing secara individual. Ini adalah salah satu alasan mengapa jerat disederhanakan sering digunakan untuk tabrakan, serta pengurangan waktu pemrosesan untuk menggunakan lebih sedikit segitiga.

Beberapa dari algoritma ini tidak hanya memberi tahu Anda bahwa benda-benda telah bertabrakan dengan pasti, tetapi di mana mereka bertabrakan - seberapa jauh mereka saling menembus dan apa "titik kontak" itu. Beberapa algoritma memerlukan langkah-langkah tambahan, seperti kliping poligon, untuk mendapatkan informasi ini.

Respon Fisik

Pada titik ini, kontak telah ditemukan, dan ada cukup informasi untuk mesin fisika untuk memproses kontak. Penanganan fisika bisa menjadi sangat kompleks. Algoritma yang lebih sederhana bekerja untuk beberapa gim, tetapi bahkan sesuatu yang kelihatannya lurus ke depan seperti menjaga tumpukan kotak tetap menjadi sangat sulit dan membutuhkan banyak kerja dan peretasan yang tidak jelas.

Pada tingkat paling dasar, mesin fisika akan melakukan sesuatu seperti ini: ia akan mengambil objek bertabrakan dan kontak manifold dan menghitung posisi baru yang diperlukan untuk memisahkan objek bertabrakan. Ini akan memindahkan objek ke posisi baru ini. Ini juga akan menghitung perubahan kecepatan yang dihasilkan dari dorongan ini, dikombinasikan dengan restitusi (bounciness) dan nilai gesekan. Mesin fisika juga akan menerapkan gaya lain yang bekerja pada benda, seperti gravitasi, untuk menghitung kecepatan baru benda, dan kemudian (bingkai berikutnya) posisi baru mereka.

Respon fisika yang lebih maju menjadi rumit dengan cepat. Pendekatan di atas akan rusak dalam banyak situasi, termasuk satu objek duduk di atas dua lainnya. Berurusan dengan masing-masing pasangan dengan sendirinya akan menyebabkan "kegugupan" dan benda-benda akan melambung banyak. Teknik yang paling mendasar adalah melakukan sejumlah iterasi koreksi kecepatan pada pasangan objek bertabrakan. Misalnya, dengan kotak "A" duduk di atas dua kotak lainnya "B" dan "C", tabrakan AB akan ditangani terlebih dahulu, menyebabkan kotak A miring lebih jauh ke dalam kotak C. Kemudian tabrakan AC ditangani, malam keluar kotak agak, tetapi menarik A ke bawah dan ke dalam B. Kemudian iterasi lain dilakukan, sehingga kesalahan AB yang disebabkan oleh koreksi AC sedikit terselesaikan, menciptakan sedikit lebih banyak kesalahan dalam respon AC. Yang ditangani ketika AC diproses lagi. Jumlah iterasi yang dilakukan tidak tetap, dan tidak ada titik di mana iter menjadi "sempurna," melainkan jumlah iterasi yang berhenti memberikan hasil yang berarti. 10 iterasi adalah percobaan pertama yang khas, tetapi diperlukan penyesuaian untuk mencari tahu jumlah terbaik untuk mesin tertentu dan kebutuhan gim tertentu.

Kontak Caching

Ada trik lain yang ternyata sangat berguna (lebih atau kurang perlu) ketika berhadapan dengan banyak jenis permainan. Caching kontak adalah salah satu yang lebih bermanfaat. Dengan cache kontak, setiap set objek yang bertabrakan disimpan dalam tabel pencarian. Setiap frame, ketika sebuah tabrakan terdeteksi, cache ini diminta untuk melihat apakah objek sebelumnya bersentuhan. Jika objek sebelumnya tidak bersentuhan, maka peristiwa "tabrakan baru" dapat dihasilkan. Jika objek sebelumnya bersentuhan, informasi dapat digunakan untuk memberikan respons yang lebih stabil. Setiap entri dalam cache kontak yang tidak diperbarui dalam bingkai menunjukkan dua objek yang dipisahkan, dan peristiwa "objek terpisah" dapat dihasilkan. Logika permainan sering kali memiliki kegunaan untuk acara ini.

Logika gim juga mungkin merespons peristiwa tabrakan baru dan menandainya sebagai diabaikan. Ini sangat membantu untuk mengimplementasikan beberapa fitur yang umum di platform, seperti platform yang dapat Anda lompati tetapi tetap berdiri. Implementasi naif mungkin mengabaikan tabrakan yang memiliki tabrakan platform-> karakter yang normal (menunjukkan kepala pemain mengenai bagian bawah platform), tetapi tanpa caching kontak, ini akan pecah jika kepala pemain muncul melalui platform dan kemudian ia mulai terjatuh. Pada titik itu, kontak normal mungkin berakhir mengarah ke atas, menyebabkan pemain muncul melalui platform ketika dia tidak seharusnya. Dengan caching kontak, mesin dapat dengan andal melihat tabrakan awal normal dan mengabaikan semua peristiwa kontak lebih lanjut sampai platform dan pemain terpisah lagi.

Tidur

Teknik lain yang sangat berguna adalah untuk menandai objek sebagai "tertidur" jika mereka tidak berinteraksi dengan. Benda tidur tidak mendapatkan pembaruan fisika, tidak bertabrakan dengan benda tidur lain, dan pada dasarnya hanya duduk di sana membeku dalam waktu sampai benda non-tidur bertabrakan dengannya.

Dampaknya adalah bahwa semua pasangan benda bertabrakan yang hanya duduk di sana melakukan apa-apa tidak memakan waktu pemrosesan. Juga, karena tidak ada jumlah konstan koreksi fisika kecil, tumpukan akan stabil.

Sebuah objek adalah kandidat untuk tidur ketika memiliki kecepatan mendekati nol untuk lebih dari satu frame. Perhatikan bahwa epsilon yang Anda gunakan untuk menguji kecepatan mendekati nol ini mungkin akan sedikit lebih tinggi daripada epsilon perbandingan titik mengambang yang biasa, seperti yang Anda harapkan beberapa jitter dengan objek bertumpuk, dan Anda ingin seluruh tumpukan benda tertidur jika mereka ' kembali "cukup dekat" ke kandang. Ambang tentu saja akan memerlukan penyesuaian dan eksperimen.

Kendala

Bit besar terakhir dari banyak mesin fisika adalah pemecah kendala. Tujuan dari sistem semacam itu adalah untuk memfasilitasi implementasi hal-hal seperti pegas, motor, sumbu roda, benda lunak yang disimulasikan, kain, tali dan rantai, dan kadang-kadang bahkan fluida (meskipun fluida sering diimplementasikan sebagai sistem yang sama sekali berbeda).

Bahkan dasar-dasar pemecahan kendala bisa menjadi sangat intensif matematika dan melampaui keahlian saya dalam materi pelajaran ini. Saya sarankan memeriksa seri artikel Randy Gaul yang luar biasa tentang fisika untuk penjelasan yang lebih mendalam tentang topik ini.

Masalah umum: tentukan yang mana dari semua kombinasi objek yang mungkin memiliki volume berpotongan nol.

Pendekatan naif, umum sederhana: Untuk setiap pasangan objek yang mungkin, hitung volume berpotongan. Ini biasanya tidak praktis, karena membutuhkan O (n ^ 2) operasi memotong yang relatif mahal.

Oleh karena itu, implementasi praktis sering dikhususkan, membuat asumsi tertentu untuk memungkinkan penghindaran pemeriksaan silang, atau pengurangan biaya mereka. Partisi spasial mengambil keuntungan dari fakta bahwa objek biasanya kecil relatif terhadap volume total, dan biasanya akan mengurangi jumlah perbandingan ke O (n log n). Kotak pembatas yang selaras sumbu dan bulatan pembatas menyediakan pemeriksaan perpotongan kasar yang murah, selama objek mematuhi asumsi kekompakan tertentu. Dan seterusnya.

Satu "mesin tabrakan" yang saya gunakan terasa sangat mudah untuk dipahami.

Pada dasarnya, API menyediakan semacam objek yang memiliki metode collidesWith, seperti itu

1. parameternya adalah berbagai jenis objek yang "memenuhi syarat" untuk tabrakan
2. mengembalikan benar atau salah tergantung pada apakah tabrakan terjadi atau tidak
3. ada opsi yang memungkinkan untuk memilih apakah semua persegi panjang yang terikat untuk objek memicu peristiwa tabrakan atau hanya piksel buram dalam persegi panjang ini (deteksi tingkat piksel)

Dalam aplikasi saya, saya secara berkala dipanggil collidesWithuntuk mencari tahu apakah tabrakan terjadi atau tidak.

Cukup sederhana bukan?

Mungkin satu-satunya hal yang memerlukan hamparan imajinasi kecil adalah ketika persegi panjang yang terikat polos tidak cukup untuk mensimulasikan geometri objek bertabrakan. Dalam hal ini kita hanya perlu menggunakan beberapa objek yang dapat di collidable daripada satu.

Secara umum, ketika Anda mengetahui bahwa persegi panjang tabrakan tunggal tidak melakukan apa yang Anda butuhkan, Anda menemukan cara untuk menguraikan hal-hal menjadi lebih banyak sub-elemen persegi panjang sehingga ketika dikombinasikan, elemen-elemen ini mensimulasikan / memperkirakan perilaku yang diinginkan.

• Pengguna akhir tidak peduli berapa banyak objek yang ada di belakang layar. Mereka senang selama hasil akhirnya terasa seperti yang mereka harapkan, misalnya seperti rumah dengan pagar halaman belakang di sekitarnya:

  

Saya pikir Anda sedikit bingung tentang apa yang Anda bicarakan, dan berbicara tentang beberapa hal yang berbeda.

kemampuan untuk mengatakan bahwa item ini dipindahkan dari lokasi X ke lokasi Y didasarkan pada fisika (ini juga menyerang cara mereka bergerak, dan mengapa mereka bergerak)

metode yang digunakan untuk deteksi tabrakan ditentukan berdasarkan pada struktur gim Anda. jika gim Anda adalah dunia terbuka yang luas, maka Anda harus mempertimbangkan Pemartisian ruang (quad-tree [oct-tree untuk 3D]), BSP, Grid tradisional, atau pendekatan uji segalanya kuno)

cara terbaik untuk menerapkan sistem deteksi tabrakan adalah melakukannya dalam langkah-langkah.

1. Tempatkan semua objek ke volume / bentuk pembatas generik, dan kemudian uji itu

2. jika 1 lulus maka ulangi dengan volume / bentuk yang lebih kompleks, ulangi hingga siap untuk menguji geometri absolut

3. uji geometri absolut jumlah waktu Anda mengulangi langkah 2 harus ditentukan pada kompleksitas bentuk Anda, dan seberapa akurat bentuk-bentuk itu.

Anda harus mempertimbangkan masing-masing langkah ini sebagai langkah awal, dan untuk tujuan menghilangkan tabrakan saat Anda pergi, dan hanya mengembalikan true pada langkah 3 jika benar-benar menyentuh.

Kemudian untuk bagian terakhir adalah resolusi tabrakan. ini menentukan apa yang terjadi setelah Anda menemukan tabrakan dan telah membuktikan bahwa itu benar-benar tabrakan, dan apa yang harus dilakukan tentang hal itu. ini biasanya ditangani oleh fisika.

loop tradisional terlihat seperti ini:

receive input
update physics
collision detection
collision resolution
render
repeat

Pada tingkat kartu grafis (di mana Anda berurusan dengan biasanya segitiga), ide umumnya adalah untuk mempartisi adegan Anda dalam beberapa cara sehingga Anda tidak perlu memeriksa semua segitiga N (ini dapat dilakukan sebagai langkah pra-pemrosesan ), dan kemudian cari tahu di mana Anda berada di tempat kejadian dan periksa hanya 10-50 segitiga di partisi itu.

Lihat pohon BSP dan Kd untuk info lebih lanjut. Ada juga pendekatan partisi lainnya.

Pertama, saya pikir pekerjaan yang paling penting dari mesin tabrakan adalah untuk menentukan apa yang tidak perlu diperiksa untuk tabrakan dalam situasi tertentu berdasarkan frame demi frame dan mengambil objek-objek itu dari pemeriksaan lebih lanjut.

Kedua, tetapi juga penting, periksa dengan cara yang lebih detail (akurat) terhadap benda-benda yang tersisa yang tidak diambil pada langkah pertama itu.

Ketiga, gunakan metode yang paling efisien / tepat untuk melakukan pemeriksaan.