Unlimited WordPress themes, graphics, videos & courses! Unlimited asset downloads! From $16.50/m
Advertisement
  1. Game Development
  2. Game Physics
Gamedevelopment

Cara Membuat Custom 2D Physics Engine: Dasar dan Resolusi Impuls

by
Difficulty:IntermediateLength:LongLanguages:
This post is part of a series called How to Create a Custom Physics Engine.
How to Create a Custom 2D Physics Engine: The Core Engine

Indonesian (Bahasa Indonesia) translation by Sap (you can also view the original English article)

Ada banyak alasan Anda mungkin ingin membuat physics engine khusus: pertama, mempelajari dan mengasah keterampilan Anda dalam matematika, fisika, dan pemrograman merupakan alasan bagus untuk mencoba proyek semacam itu; kedua, physics engine khusus dapat mengatasi segala macam efek teknis yang dimiliki pembuat konten. Dalam artikel ini saya ingin memberikan pengantar yang solid tentang cara membuat physics engine kustom sepenuhnya dari awal.

Physics menyediakan cara yang bagus untuk memungkinkan pemain untuk membenamkan diri dalam permainan. Masuk akal bahwa penguasaan physics engine akan menjadi aset yang berguna bagi setiap programmer untuk dimiliki pada penyelesaian mereka. Optimasi dan spesialisasi dapat dilakukan setiap saat karena pemahaman mendalam tentang cara kerja physics engine.

Pada akhir tutorial ini topik-topik berikut akan dibahas, dalam dua dimensi:

  • Deteksi tabrakan sederhana
  • Generasi manifold sederhana
  • Impuls resolusi

Berikut demo cepatnya:

Catatan: Meskipun tutorial ini ditulis menggunakan C++, Anda harus mampu menggunakan teknik dan konsep yang sama di hampir semua lingkungan pengembangan game.


Prasyarat

Artikel ini melibatkan cukup banyak matematika dan geometri, dan pada tingkat yang jauh lebih rendah dari coding. Beberapa prasyarat untuk artikel ini adalah:

  • Pemahaman dasar matematika vektor sederhana
  • Kemampuan untuk melakukan matematika aljabar

Deteksi Tabrakan

Ada beberapa artikel dan tutorial di internet, termasuk di sini di Tuts+, yang mencakup deteksi tabrakan. Mengetahui hal ini, saya ingin menjalankan topik dengan sangat cepat karena bagian ini bukan fokus dari artikel ini.

Axis Aligned Bounding Box

Axis Aligned Bounding Box (AABB) adalah kotak yang memiliki empat sumbu yang disejajarkan dengan sistem koordinat tempat ia berada. Hal ini berarti bahwa kotak itu tidak dapat diputar, dan selalu dikuadratkan pada 90 derajat (biasanya sejajar dengan layar). Secara umum disebut sebagai "bounding box" karena AABB digunakan untuk mengikat bentuk yang lebih kompleks lainnya.

An example AABB

Contoh AABB.

AABB bentuk kompleks dapat digunakan sebagai tes sederhana untuk melihat apakah bentuk yang lebih kompleks di dalam AABBs dapat berpotongan. Namun dalam kasus sebagian besar game, AABB digunakan sebagai bentuk dasar, dan sebenarnya tidak mengikat yang lain. Struktur AABB Anda penting. Ada beberapa cara berbeda untuk mewakili AABB, namun inilah favorit saya:

Formasi ini memungkinkan AABB diwakili oleh dua poin. Titik min mewakili batas bawah sumbu x dan y, dan maks mewakili batas yang lebih tinggi - dengan kata lain, mereka mewakili sudut kiri atas dan bawah kanan. Untuk mengetahui apakah dua bentuk AABB berpotongan Anda perlu memiliki pemahaman dasar tentang Separating Axis Theorem (SAT).

Berikut adalah tes cepat yang diambil dari Deteksi Tabrakan Real-Time oleh Christer Ericson, yang menggunakan SAT:

Circles

Lingkaran diwakili oleh radius dan titik. Seperti inilah struktur lingkaran Anda terlihat:

Menguji apakah dua lingkaran berpotongan sangat sederhana: ambil jari-jari dari dua lingkaran dan tambahkan mereka bersama-sama, lalu periksa untuk melihat apakah jumlah ini lebih besar daripada jarak antara dua lingkaran.

Pengoptimalan penting untuk dilakukan adalah menyingkirkan semua kebutuhan untuk menggunakan operator akar kuadrat:

Secara umum, perkalian adalah operasi yang jauh lebih murah daripada mengambil akar kuadrat dari suatu nilai.


Impulse Resolution

Impulse resolution adalah tipe tertentu dari strategi resolusi tabrakan. Resolusi tabrakan adalah tindakan mengambil dua objek yang ditemukan berpotongan dan memodifikasi mereka sedemikian rupa sehingga tidak memungkinkan mereka untuk tetap berpotongan.

Secara umum sebuah objek dalam physics engine memiliki tiga derajat kebebasan utama (dalam dua dimensi): gerakan dalam bidang xy dan rotasi. Dalam artikel ini kita secara implisit membatasi rotasi dan hanya menggunakan AABBs dan Circles, sehingga satu-satunya tingkat kebebasan yang benar-benar perlu kita pertimbangkan adalah pergerakan sepanjang xy plane.

Dengan menyelesaikan tabrakan yang terdeteksi kita menempatkan pembatasan pada gerakan sehingga objek tidak dapat tetap berpotongan satu sama lain. Gagasan di balik resolusi impuls adalah menggunakan impuls (perubahan kecepatan seketika) untuk memisahkan objek yang ditemukan bertabrakan. Untuk melakukan hal ini, massa, posisi, dan kecepatan setiap objek entah bagaimana harus diperhitungkan: kita ingin benda besar bertabrakan dengan yang lebih kecil untuk bergerak sedikit selama tabrakan, dan untuk mengirim benda-benda kecil terbang menjauh. Kita juga ingin objek dengan massa tak terbatas untuk tidak bergerak sama sekali.

Simple example of what impulse resolution can achieve

Contoh sederhana dari apa yang bisa dicapai oleh impulse resolution.

Untuk mencapai efek tersebut dan mengikuti intuisi alami tentang bagaimana benda-benda bergerak kita akan menggunakan tubuh yang kaku dan sedikit matematika yang wajar. Tubuh kaku adalah bentuk yang ditentukan oleh pengguna (yaitu, oleh Anda, pengembang) yang secara implisit didefinisikan menjadi tidak dapat diubah bentuknya. Baik AABB dan Circles dalam artikel ini tidak bisa diubah bentuknya, dan akan selalu menjadi AABB atau Circles. Tidak ada pengapitan atau peregangan yang diizinkan.

Bekerja dengan badan kaku memungkinkan banyak matematika dan derivasi menjadi sangat disederhanakan. Inilah sebabnya mengapa tubuh kaku biasanya digunakan dalam simulasi game, dan mengapa kita akan menggunakannya dalam artikel ini.

Objek Kita Bertabrakan - Sekarang Apa?

Dengan asumsi kita memiliki dua bentuk yang ditemukan berpotongan, bagaimana cara memisahkan keduanya? Mari kita asumsikan deteksi tabrakan memberi kita dua informasi penting:

  • Tabrakan normal
  • Penyusupan mendalam

Untuk menerapkan dorongan ke kedua objek dan memisahkannya, kita perlu tahu arah mana untuk mendorongnya dan seberapa banyak. Tabrakan normal adalah arah di mana impuls akan diterapkan. Kedalaman penyusupan (bersama dengan beberapa hal lain) menentukan seberapa besar dorongan akan digunakan. Ini berarti satu-satunya nilai yang perlu dipecahkan adalah besarnya dorongan kita.

Sekarang mari kita melakukan perjalanan panjang untuk menemukan bagaimana kita bisa memecahkan dorongan besar ini. Kita akan mulai dengan dua objek yang telah ditemukan berpotongan:

Persamaan 1

\[ V^{AB} = V^B - V^A \] Perhatikan bahwa untuk membuat vektor dari posisi A ke posisi B, Anda harus melakukan: endpoint - startpoint. \(V ^{AB}\) adalah kecepatan relatif dari A ke B. Persamaan ini harus dinyatakan dalam hal tabrakan normal \(n\) - yaitu, kita ingin mengetahui kecepatan relatif dari A ke B sepanjang arah tabrakan normal:

Persamaan 2

\[ V^{AB} \cdot n = (V^B - V^A) \cdot n \]

Kita sekarang memanfaatkan dot product. Dot product itu sederhana; merupakan jumlah dari produk-produk component-wise:

Persamaan 3

\[ V_1 = \begin{bmatrix}x_1 \\y_1\end{bmatrix}, V_2 = \begin{bmatrix}x_2 \\y_2\end{bmatrix} \\ V_1 \cdot V_2 = x_1 * x_2 + y_2 * y_2 \]

Langkah selanjutnya adalah memperkenalkan apa yang disebut coefficient of restitution. Restitusi adalah istilah yang berarti elastisitas, atau pantulan. Setiap objek di mesin fisika Anda akan memiliki ganti rugi yang direpresentasikan sebagai nilai desimal. Namun hanya satu nilai desimal yang akan digunakan selama perhitungan impuls.

Untuk memutuskan restitusi apa yang digunakan (dilambangkan dengan \(e\) untuk epsilon), Anda harus selalu menggunakan restitusi terendah yang terlibat dalam tabrakan untuk hasil yang intuitif:

Setelah \(9e\) diperoleh, kita dapat menempatkannya ke dalam pemecahan persamaan untuk besaran impuls.

Hukum Restitusi Newton menyatakan hal-hal berikut:

Persamaan 4

\[V' = e * V \]

Semua ini mengatakan bahwa kecepatan setelah tabrakan sama dengan kecepatan sebelumnya, dikalikan dengan beberapa konstanta. Konstanta ini mewakili "faktor pentalan". Mengetahui hal ini, menjadi cukup mudah untuk mengintegrasikan restitusi ke dalam derivasi kita saat ini:

Persamaan 5

\[ V^{AB} \cdot n = -e * (V^B - V^A) \cdot n \]

Perhatikan bagaimana kita memperkenalkan tanda negatif di sini. Dalam Hukum Restitusi Newton, \(V'\), vektor yang dihasilkan setelah bouncing, sebenarnya berjalan berlawanan arah V. Jadi bagaimana kita mewakili arah yang berlawanan dalam derivasi kita? Memperkenalkan tanda negatif.

Sejauh ini baik-baik saja. Sekarang kita perlu untuk dapat mengekspresikan kecepatan ini sementara di bawah pengaruh dorongan. Berikut adalah persamaan sederhana untuk memodifikasi vektor dengan beberapa dorongan skalar \(j\) sepanjang \(n\) arah tertentu:

Persamaan 6

\ [V' = V + j * n \]

Mudah-mudahan persamaan di atas akal, karena sangat penting untuk memahami. Kita memiliki vektor satuan \(n\) yang mewakili arah. Kita memiliki skalar \(j\) yang mewakili berapa lama \(n\). Kita kemudian menambahkan vektor skala (n) ke \(V\) untuk menghasilkan \(V'\). Ini hanya menambahkan satu vektor ke vektor lainnya, dan kita dapat menggunakan persamaan kecil ini untuk menerapkan impuls satu vektor ke vektor lainnya.

Ada sedikit pekerjaan yang harus dilakukan di sini. Secara formal, suatu impuls didefinisikan sebagai perubahan momentum. Momentum adalah mass * velocity. Mengetahui hal ini, kita dapat mewakili suatu dorongan karena secara resmi didefinisikan seperti ini:

Persamaan 7

\[ Impulse = mass * Velocity \\ Velocity = \frac{Impulse}{mass} \therefore V' = V + \frac{j * n}{mass}\]

Ketiga titik dalam segitiga kecil (\(\therefore\)) dapat dibaca sebagai "oleh karena itu". Ini digunakan untuk menunjukkan bahwa benda itu sebelumnya dapat digunakan untuk menyimpulkan bahwa apa pun yang terjadi selanjutnya adalah benar.

Kemajuan yang bagus telah dibuat sejauh ini! Namun kita harus mampu mengekspresikan dorongan menggunakan \(j\) dalam dua benda yang berbeda. Selama tabrakan dengan objek A dan B, A akan didorong ke arah yang berlawanan dari B:

Persamaan 8

\[ V'^A = V^A + \frac{j * n}{mass^A} \\ V'^B = V^B - \frac{j * n}{mass^B} \]

Kedua persamaan ini akan mendorong A menjauh dari B sepanjang vektor unit arah \(n\) oleh skalar impuls (besarnya \(n\)) \(j\).

Semua yang dibutuhkan sekarang adalah menggabungkan Persamaan 8 dan 5. Persamaan yang dihasilkan akan terlihat seperti ini:

Persamaan 9

\[ (V^A - V^V + \frac{j * n}{mass^A} + \frac{j * n}{mass^B}) * n = -e * (V^B - V^A) \cdot n \\ \therefore \\ (V^A - V^V + \frac{j * n}{mass^A} + \frac{j * n}{mass^B}) * n + e * (V^B - V^A) \cdot n = 0 \]

Jika Anda ingat, tujuan awalnya adalah mengisolasi magnitude kita. Ini karena kita tahu apa arah untuk menyelesaikan tabrakan (diasumsikan diberikan oleh deteksi tabrakan), dan hanya tersisa untuk menyelesaikan besarnya arah ini. Besaran yang tidak diketahui dalam kasus kita adalah \(j\); kita harus mengisolasi \(j\) dan memecahkannya.

Persamaan 10

\[ (V^B - V^A) \cdot n + j * (\frac{j * n}{mass^A} + \frac{j * n}{mass^B}) * n + e * (V^B - V^A) \cdot n = 0 \\ \therefore \\ (1 + e)((V^B - V^A) \cdot n) + j * (\frac{j * n}{mass^A} + \frac{j * n}{mass^B}) * n = 0 \\ \therefore \\ j = \frac{-(1 + e)((V^B - V^A) \cdot n)}{\frac{1}{mass^A} + \frac{1}{mass^B}} \]

Wah! Itu sedikit matematika! Semuanya sudah berakhir untuk sekarang. Sangat penting untuk diperhatikan bahwa pada versi terakhir dari Persamaan 10 kita memiliki \(j\) di sebelah kiri (magnitudo kita) dan semua yang ada di sebelah kanan semuanya diketahui. Ini berarti kita dapat menulis beberapa baris kode untuk menyelesaikan skalar impuls \(j\). Dan anak laki-laki adalah kode yang jauh lebih mudah dibaca daripada notasi matematika!

Ada beberapa hal penting yang perlu diperhatikan dalam contoh kode di atas. Hal pertama adalah pemeriksaan di Jalur 10, if(VelAlongNormal > 0). Pemeriksaan ini sangat penting; itu memastikan bahwa Anda hanya menyelesaikan tabrakan jika objek bergerak ke arah satu sama lain.

Two objects collide but velocity will separate them next frame Do not resolve this type of collision

Dua benda bertabrakan, tetapi kecepatan akan memisahkan mereka frame berikutnya. Jangan selesaikan jenis tabrakan ini.

Jika objek bergerak menjauh satu sama lain, kita tidak ingin melakukan apa-apa. Ini akan mencegah benda-benda yang seharusnya tidak benar-benar dianggap bertabrakan dari saling menjauh satu sama lain. Ini penting untuk membuat simulasi yang mengikuti intuisi manusia tentang apa yang seharusnya terjadi selama interaksi objek.

Hal kedua yang perlu diperhatikan adalah bahwa massa terbalik dihitung beberapa kali tanpa alasan. Sebaiknya simpan saja massa terbalik Anda dalam setiap objek dan lakukan pra-komputasi satu kali:

Banyak physics engines tidak benar-benar menyimpan massa mentah. Physics engines sering kali menyimpan massa invers dan massa terbalik saja. Kebetulan bahwa sebagian besar matematika yang melibatkan massa dalam bentuk 1/massa.

Hal terakhir yang perlu diperhatikan adalah kita secara cerdas mendistribusikan skalar impuls \(j\) di atas dua objek. Kita ingin benda-benda kecil untuk bangkit dari benda-benda besar dengan sebagian besar \(j\), dan benda-benda besar untuk memiliki kecepatan mereka diubah oleh porsi yang sangat kecil dari \(j\).

Untuk melakukan ini, Anda dapat melakukan:

Penting untuk menyadari bahwa kode di atas setara dengan fungsi sampel ResolveCollision() dari sebelumnya. Seperti dinyatakan sebelumnya, massa invers cukup berguna dalam physics engine.

Sinking Objects

Jika kita terus menggunakan kode yang kita miliki sejauh ini, objek akan saling bertabrakan dan terpental. Ini bagus, meskipun apa yang terjadi jika salah satu objek memiliki massa yang tak terbatas? Kita membutuhkan cara yang baik untuk mewakili massa tak terbatas dalam simulasi.

Saya sarankan menggunakan nol sebagai massa tak terbatas - meskipun jika kita mencoba untuk menghitung massa invers suatu objek dengan nol kita akan memiliki pembagian dengan nol. Solusi untuk ini adalah melakukan hal berikut saat menghitung inversi massal:

Nilai nol akan menghasilkan perhitungan yang tepat selama resolusi impuls. Ini masih oke. Masalah tenggelamnya objek muncul ketika sesuatu mulai tenggelam ke objek lain karena gravitasi. Mungkin sesuatu dengan restitusi rendah menyentuh dinding dengan massa tak terbatas dan mulai tenggelam.

Tenggelam ini disebabkan oleh kesalahan floating point. Selama setiap perhitungan floating point kesalahan floating point kecil diperkenalkan karena perangkat keras. (Untuk informasi lebih lanjut, Google [Floating point error IEEE754].) Seiring waktu, kesalahan ini terakumulasi dalam kesalahan posisi, menyebabkan objek tenggelam ke dalam satu sama lain.

Untuk memperbaiki kesalahan ini harus diperhitungkan. Untuk memperbaiki kesalahan posisi ini saya akan menunjukkan kepada Anda metode yang disebut proyeksi linier. Proyeksi linier mengurangi pentusupan dua objek dengan persentase kecil, dan ini dilakukan setelah impuls diterapkan. Koreksi posisi sangat sederhana: gerakkan setiap objek di sepanjang tabrakan normal \(n\) dengan persentase kedalaman penyusupan:

Perhatikan bahwa kita mengukur penetrationDepth dengan total massa sistem. Ini akan memberikan koreksi posisi sebanding dengan berapa banyak massa yang kita hadapi. Benda kecil mendorong jauh lebih cepat daripada benda yang lebih berat.

Ada sedikit masalah dengan implementasi ini: jika kita selalu menyelesaikan kesalahan posisional kita maka objek akan naik-turun sementara mereka beristirahat pada satu sama lain. Untuk mencegah hal ini, beberapa slack harus diberikan. Kita hanya melakukan koreksi posisi jika penyusupan berada di atas beberapa ambang arbitrer, yang disebut sebagai "slop":

Hal ini memungkinkan objek untuk menembus sedikit tanpa koreksi posisi menendang.


Generasi Manifold Sederhana

Topik terakhir yang dibahas dalam artikel ini adalah generasi manifold sederhana. Manifold dalam istilah matematika adalah sesuatu di sepanjang garis "kumpulan poin yang mewakili area dalam ruang". Namun, ketika saya merujuk ke manifold istilah saya mengacu pada objek kecil yang berisi informasi tentang tabrakan antara dua objek.

Berikut ini adalah pengaturan manifold yang khas:

Selama deteksi tabrakan, penyusupan dan tabrakan yang normal harus dihitung. Untuk menemukan info ini algoritma pendeteksi tabrakan asli dari bagian atas artikel ini harus diperluas.

Circle vs Circle

Mari kita mulai dengan algoritma tabrakan yang paling sederhana: Circle vs Circle. Tes ini kebanyakan sepele. Dapatkah Anda membayangkan apa arah untuk menyelesaikan tabrakan akan terjadi? Ini adalah vektor dari Lingkaran A ke Lingkaran B. Ini dapat diperoleh dengan mengurangi posisi B dari A.

Kedalaman penyusupan berhubungan dengan jari-jari lingkaran dan jarak satu sama lain. Tumpang tindih Lingkaran dapat dihitung dengan mengurangi jari-jari dijumlahkan oleh jarak dari masing-masing objek.

Berikut ini adalah contoh algoritma lengkap untuk menghasilkan manifold dari tabrakan Circle vs Circle:

Hal yang paling penting di sini adalah: kita tidak melakukan akar kuadrat apa pun sampai perlu (objek ditemukan bertabrakan), dan kita memeriksa untuk memastikan lingkaran tidak pada posisi yang sama persis. Jika mereka pada posisi yang sama jarak kita akan nol, dan kita harus menghindari pembagian dengan nol ketika kita menghitung t/d.

AABB vs AABB

Tes AABB to AABB sedikit lebih kompleks daripada Circle vs Circle. Tabrakan yang normal tidak akan menjadi vektor dari A ke B, tetapi akan menjadi tampilan normal. AABB adalah kotak dengan empat tampilan. Setiap tampilan memiliki normal. Normal ini merupakan vektor satuan yang tegak lurus dengan tampilan.

Periksa persamaan umum garis dalam 2D:

\[ ax + by + c = 0 \\ normal = \begin{bmatrix}a \\b\end{bmatrix} \]

custom-physics-line2d

Dalam persamaan di atas, a dan b adalah vektor normal untuk suatu garis, dan vektor (a, b) diasumsikan dinormalkan (panjang vektor adalah nol). Sekali lagi, tabrakan kita normal (arah untuk menyelesaikan tabrakan) akan berada di arah salah satu norma tampilan.

Apakah Anda tahu apa yang diwakili c oleh persamaan garis umum? c adalah jarak dari asal. Ini sangat berguna untuk menguji untuk melihat apakah suatu titik berada di satu sisi garis atau yang lain, seperti yang akan Anda lihat di artikel berikutnya.

Sekarang semua yang diperlukan adalah untuk mengetahui tampilan mana yang bertabrakan pada salah satu objek dengan objek lain, dan kita memiliki normal. Namun terkadang beberapa tampilan  dari dua AABB dapat berpotongan, seperti ketika dua sudut saling berpotongan. Ini berarti kita harus menemukan sumbu penyusupan terkecil.

Two axes of penetration the horizontal x axis is axis of least penetration and this collision should be resolved along the x axis

Dua sumbu penyusupan; sumbu x horizontal adalah sumbu penyusupan terkecil dan tabrakan ini harus diselesaikan sepanjang sumbu x.

Berikut ini adalah algoritma lengkap untuk AABB untuk generasi manifold AABB dan deteksi tabrakan:

custom-physics-aabb-diagram

Circle vs AABB

Tes terakhir yang akan saya bahas adalah tes Circle vs AABB. Idenya di sini adalah untuk menghitung titik terdekat pada AABB ke Circle; dari sana tes berubah menjadi sesuatu yang mirip dengan uji Circle vs Circle. Setelah titik terdekat dihitung dan tabrakan terdeteksi normal adalah arah titik terdekat ke pusat lingkaran. Kedalaman penyusupan adalah perbedaan antara jarak titik terdekat dengan lingkaran dan jari-jari lingkaran.

AABB to Circle intersection diagram
AABB untuk Circle persimpangan diagram.

Ada satu kasus khusus yang rumit; jika pusat lingkaran berada dalam AABB maka pusat lingkaran harus dipotong ke tepi terdekat dari AABB, dan kebutuhan normal akan dibalik.


Kesimpulan

Semoga sekarang Anda telah belajar satu atau dua hal tentang simulasi physics . Tutorial ini cukup untuk memungkinkan Anda mengatur physics engine kustom sederhana yang seluruhnya terbuat dari awal. Di bagian selanjutnya, kita akan mencakup semua ekstensi yang diperlukan yang diperlukan oleh semua physics engines, termasuk:

  • Hubungi pasangan menyortir dan memusnahkan
  • Broadphase
  • Layering
  • Integrasi
  • Timestepping
  • Persimpangan Halfspace
  • Desain Modular (bahan, massa dan kekuatan)

Saya harap Anda menikmati artikel ini dan saya berharap dapat menjawab pertanyaan di komentar.

Advertisement
Advertisement
Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.