Di bagian seri saya ini untuk membuat mesin fisika 2D khusus untuk gim Anda, kami akan menambahkan lebih banyak fitur ke resolusi impuls yang kami peroleh di bagian pertama. Secara khusus, kita akan melihat integrasi, pengaturan waktu, menggunakan desain modular untuk kode kita, dan deteksi tabrakan fase luas.

Pengenalan

Dalam posting terakhir di seri ini saya membahas topik resolusi impuls. Baca yang pertama, jika Anda belum melakukannya!

Mari selami topik yang dibahas dalam artikel ini. Topik-topik ini adalah semua kebutuhan mesin fisika setengah layak, jadi sekarang adalah waktu yang tepat untuk membangun lebih banyak fitur di atas resolusi inti dari artikel terakhir.

• Integrasi
• Timestepping
• Desain Modular
  • Tubuh
  • Bentuk
  • Gaya
  • Bahan
• Fase Luas
  • Pasangan kontak duplikat eliminasi
  • LAyering
• Tes Persimpangan Halfspace

Integrasi

Integrasi sepenuhnya sederhana untuk diterapkan, dan ada banyak area di internet yang memberikan informasi yang baik untuk integrasi berulang. Bagian ini sebagian besar akan menunjukkan bagaimana menerapkan fungsi integrasi yang tepat, dan menunjuk ke beberapa lokasi yang berbeda untuk membaca lebih lanjut, jika diinginkan.

Pertama, harus diketahui apa sebenarnya percepatan itu. Hukum Kedua Newton menyatakan:

\[Equation 1:\\
F = ma\]

Ini menyatakan bahwa penjumlahan semua gaya yang bekerja pada beberapa objek sama dengan massa objek m itu dikalikan dengan akselerasinya a. m adalah dalam kilogram,  a adalah meter / detik, dan F dalam Newton.

Menata ulang persamaan ini sedikit untuk memecahkan a hasilnya:

\[Equation 2:\\
a = \frac{F}{m}\\
\therefore\\
a = F * \frac{1}{m}\]

Langkah selanjutnya melibatkan menggunakan percepatan untuk melangkah objek dari satu lokasi ke lokasi lain. Karena permainan ditampilkan dalam bingkai terpisah terpisah dalam animasi mirip ilusi, lokasi setiap posisi pada langkah-langkah terpisah ini harus dihitung. Untuk sampul yang lebih mendalam dari persamaan ini silakan lihat: Demo Integrasi Erin Catto dari GDC 2009 dan tambahan Hannu pada Euler symplectic untuk stabilitas lebih dalam lingkungan FPS rendah.

Euler eksplisit (diucapkan "oiler") integrasi ditunjukkan dalam potongan berikut, di mana x adalah posisi dan v adalah kecepatan. Harap dicatat bahwa 1/m * F adalah akselerasi, seperti yang dijelaskan di atas:

// Explicit Euler
x += v * dt
v += (1/m * F) * dt

Ini akan bekerja, dan biasanya digunakan sebagai titik awal. Namun, ia memiliki ketidakakuratan numerik yang dapat kita singkirkan tanpa usaha ekstra. Berikut adalah apa yang dikenal sebagai Symplectic Euler:

// Symplectic Euler
v += (1/m * F) * dt
x += v * dt

Perhatikan bahwa semua yang saya lakukan adalah mengatur ulang urutan dua baris kode - lihat "> artikel tersebut dari Hannu.

Posting ini menjelaskan ketidakakuratan numerik dari Euler Eksplisit, tetapi diperingatkan bahwa ia mulai mencakup RK4, yang saya pribadi tidak merekomendasikan: gafferongames.com: Euler Inaccuracy.

Persamaan sederhana ini adalah semua yang kita butuhkan untuk memindahkan semua objek dengan kecepatan dan akselerasi linier.

Timestepping

Karena permainan ditampilkan pada interval waktu diskrit, perlu ada cara memanipulasi waktu di antara langkah-langkah ini dengan cara yang terkontrol. Pernahkah Anda melihat game yang akan berjalan pada kecepatan yang berbeda tergantung pada komputer apa yang sedang dimainkan? Itu adalah contoh dari permainan yang berjalan pada kecepatan tergantung pada kemampuan komputer untuk menjalankan permainan.

Kami membutuhkan cara untuk memastikan bahwa mesin fisika kami hanya berjalan ketika jumlah waktu tertentu telah berlalu. Dengan cara ini, dt yang digunakan dalam perhitungan selalu merupakan angka yang sama persis. Menggunakan nilai dt yang sama persis dalam kode Anda di mana-mana akan benar-benar membuat mesin fisika Anda deterministik, dan dikenal sebagai timestep tetap. Ini adalah hal baik.

Mesin fisika deterministik adalah mesin yang selalu melakukan hal yang sama setiap kali dijalankan dengan asumsi input yang sama diberikan. Ini sangat penting untuk banyak jenis permainan di mana gameplay perlu sangat disesuaikan dengan perilaku mesin fisika. Ini juga penting untuk debugging mesin fisika Anda, karena untuk menentukan bug perilaku mesin Anda harus konsisten.

Pertama mari kita bahas versi sederhana dari timestep tetap. Berikut ini contohnya:

const float fps = 100
const float dt = 1 / fps
float accumulator = 0

// In units of seconds
float frameStart = GetCurrentTime( )

// main loop
while(true)
  const float currentTime = GetCurrentTime( )

  // Store the time elapsed since the last frame began
  accumulator += currentTime - frameStart( )

  // Record the starting of this frame
  frameStart = currentTime

  while(accumulator > dt)
    UpdatePhysics( dt )
    accumulator -= dt

  RenderGame( )

Ini menunggu, membuat game, hingga waktu yang cukup untuk memperbarui fisika. Waktu yang telah berlalu dicatat, dan potongan waktu dt-berukuran diskrit diambil dari akumulator dan diproses oleh fisika. Ini memastikan bahwa nilai yang sama dilewatkan ke fisika tidak peduli apa, dan bahwa nilai yang diteruskan ke fisika adalah representasi akurat dari waktu aktual yang dilewati dalam kehidupan nyata. Potongan dt dihapus dari accumulator sampai accumulator lebih kecil dari potongan dt.

Ada beberapa masalah yang bisa diperbaiki di sini. Yang pertama melibatkan waktu yang diperlukan untuk benar-benar melakukan pembaruan fisika: Bagaimana jika pembaruan fisika terlalu lama dan accumulator semakin tinggi dan semakin tinggi setiap putaran permainan? Ini disebut spiral kematian. Jika ini tidak diperbaiki, mesin Anda akan segera berhenti jika fisika Anda tidak dapat dijalankan dengan cukup cepat.

Untuk mengatasi ini, mesin benar-benar perlu menjalankan pembaruan fisika lebih sedikit jika accumulator terlalu tinggi. Cara sederhana untuk melakukan ini adalah dengan menjepit accumulator di bawah beberapa nilai sewenang-wenang.

const float fps = 100
const float dt = 1 / fps
float accumulator = 0

// In units seconds
float frameStart = GetCurrentTime( )

// main loop
while(true)
  const float currentTime = GetCurrentTime( )

  // Store the time elapsed since the last frame began
  accumulator += currentTime - frameStart( )

  // Record the starting of this frame
  frameStart = currentTime

  // Avoid spiral of death and clamp dt, thus clamping
  // how many times the UpdatePhysics can be called in
  // a single game loop.
  if(accumulator > 0.2f)
    accumulator = 0.2f

  while(accumulator > dt)
    UpdatePhysics( dt )
    accumulator -= dt

  RenderGame( )

Sekarang, jika permainan yang menjalankan loop ini pernah menemui semacam pengabaian untuk alasan apa pun, fisika tidak akan menenggelamkan diri dalam spiral kematian. Permainan akan berjalan sedikit lebih lambat, jika perlu.

Hal berikutnya untuk memperbaikinya cukup kecil dibandingkan dengan spiral kematian. Loop ini mengambil potongan dt dari accumulator sampai accumulator lebih kecil dari dt. Ini menyenangkan, tapi masih ada sisa waktu tersisa di accumulator. Hal ini menimbulkan masalah.

Asumsikan accumulator ditinggalkan dengan 1/5 dt chunk setiap frame. Pada frame keenam, accumulator akan memiliki cukup waktu tersisa untuk melakukan satu pembaruan fisika lebih dari semua frame lainnya. Ini akan menghasilkan satu bingkai setiap detik atau lebih melakukan lompatan diskrit sedikit lebih besar dalam waktu, dan mungkin sangat nyata dalam permainan Anda.

Untuk mengatasi ini, penggunaan interpolasi linier diperlukan. Jika ini terdengar menakutkan, jangan khawatir - penerapannya akan ditampilkan. Jika Anda ingin memahami penerapannya, ada banyak sumber daya online untuk interpolasi linier.

// linear interpolation for a from 0 to 1
// from t1 to t2
t1 * a + t2(1.0f - a)

Dengan menggunakan ini kita dapat melakukan interpolasi (perkiraan) di mana kita mungkin berada di antara dua interval waktu yang berbeda. Ini dapat digunakan untuk membuat keadaan permainan di antara dua pembaruan fisika yang berbeda.

Dengan interpolasi linier, rendering mesin dapat berjalan pada kecepatan yang berbeda dari mesin fisika. Ini memungkinkan penanganan yang bagus dari accumulator sisa dari pembaruan fisika.

Berikut ini contoh lengkapnya:

const float fps = 100
const float dt = 1 / fps
float accumulator = 0

// In units seconds
float frameStart = GetCurrentTime( )

// main loop
while(true)
  const float currentTime = GetCurrentTime( )

  // Store the time elapsed since the last frame began
  accumulator += currentTime - frameStart( )

  // Record the starting of this frame
  frameStart = currentTime

  // Avoid spiral of death and clamp dt, thus clamping
  // how many times the UpdatePhysics can be called in
  // a single game loop.
  if(accumulator > 0.2f)
    accumulator = 0.2f

  while(accumulator > dt)
    UpdatePhysics( dt )
    accumulator -= dt

  const float alpha = accumulator / dt;

  RenderGame( alpha )

void RenderGame( float alpha )
  for shape in game do
    // calculate an interpolated transform for rendering
    Transform i = shape.previous * alpha + shape.current * (1.0f - alpha)
    shape.previous = shape.current
    shape.Render( i )

Di sini, semua benda di dalam permainan dapat ditarik pada saat-saat variabel antara timestesis fisika diskrit. Ini dengan anggun akan menangani semua kesalahan dan sisa akumulasi waktu. Ini sebenarnya rendering yang sedikit di belakang apa yang saat ini telah dipecahkan oleh fisika, tetapi ketika menonton game menjalankan semua gerakan dihaluskan dengan sempurna oleh interpolasi.

Pemain tidak akan pernah tahu bahwa rendernya sangat sedikit di belakang fisika, karena pemain hanya akan tahu apa yang mereka lihat, dan apa yang akan mereka lihat adalah transisi yang sangat halus dari satu bingkai ke yang lain.

Anda mungkin bertanya-tanya, "mengapa kita tidak melakukan interpolasi dari posisi saat ini ke yang berikutnya?". Saya mencoba ini dan itu membutuhkan rendering untuk "menebak" di mana objek akan berada di masa depan. Seringkali, benda-benda dalam mesin fisika membuat perubahan tiba-tiba dalam gerakan, seperti saat tabrakan, dan ketika gerakan tiba-tiba berubah, objek akan berteleportasi karena interpolasi yang tidak akurat ke masa depan.

Desain modular

Ada beberapa hal yang diperlukan setiap benda fisika. Namun, hal-hal spesifik yang diperlukan setiap objek fisik dapat berubah sedikit dari objek ke objek. Cara cerdas untuk mengatur semua data ini diperlukan, dan akan diasumsikan bahwa semakin sedikit jumlah kode yang harus ditulis untuk mencapai organisasi seperti itu yang diinginkan. Dalam hal ini beberapa desain modular akan berguna.

Desain modular mungkin terdengar agak sombong atau terlalu rumit, tetapi itu masuk akal dan cukup sederhana. Dalam konteks ini, "desain modular" hanya berarti kita ingin memecah objek fisik menjadi bagian-bagian yang terpisah, sehingga kita dapat menghubungkan atau memutuskannya namun kita mau.

Tubuh

Tubuh fisika adalah objek yang berisi semua informasi tentang beberapa objek fisika yang diberikan. Ini akan menyimpan bentuk (s) bahwa objek diwakili oleh, data massa, transformasi (posisi, rotasi), kecepatan, torsi, dan sebagainya. Inilah yang seharusnya terlihat seperti body kita:

struct body
{
  Shape *shape;
  Transform tx;
  Material material;
  MassData mass_data;
  Vec2 velocity;
  Vec2 force;
  real gravityScale;
};

Ini adalah titik awal yang bagus untuk desain struktur tubuh fisika. Ada beberapa keputusan cerdas yang dibuat di sini yang cenderung ke arah organisasi kode yang kuat.

Hal pertama yang perlu diperhatikan adalah bahwa suatu bentuk terkandung di dalam tubuh melalui penunjuk. Ini merupakan hubungan yang longgar antara tubuh dan bentuknya. Tubuh dapat berisi bentuk apa pun, dan bentuk tubuh dapat ditukarkan sesuka hati. Bahkan, tubuh dapat diwakili oleh berbagai bentuk, dan tubuh seperti itu akan dikenal sebagai "komposit", karena akan terdiri dari berbagai bentuk. (Saya tidak akan membahas komposit dalam tutorial ini.)

Shape itu sendiri bertanggung jawab untuk menghitung bentuk-bentuk pembatas, menghitung massa berdasarkan kerapatan, dan rendering.

Mass_data adalah struktur data kecil yang berisi informasi yang berhubungan dengan massa:

struct MassData
{
  float mass;
  float inv_mass;

  // For rotations (not covered in this article)
  float inertia;
  float inverse_inertia;
};

Sangat menyenangkan untuk menyimpan semua nilai yang berhubungan dengan massa dan intertia dalam satu struktur tunggal. Massa tidak boleh diatur dengan massa tangan harus selalu dihitung oleh bentuk itu sendiri. Massa adalah jenis nilai yang agak tidak intuitif, dan pengaturannya dengan tangan akan membutuhkan banyak waktu penyesuaian. Ini didefinisikan sebagai:

\[ Equation 3:\\Mass = density * volume\]

Setiap kali seorang desainer menginginkan bentuk lebih "besar" atau "berat", mereka harus memodifikasi kerapatan bentuk. Kepadatan ini dapat digunakan untuk menghitung massa bentuk yang diberikan volumenya. Ini adalah cara yang tepat untuk pergi tentang situasi, karena kepadatan tidak dipengaruhi oleh volume dan tidak akan pernah berubah selama runtime dari permainan (kecuali secara khusus didukung dengan kode khusus).

Beberapa contoh bentuk seperti AABB dan Lingkaran dapat ditemukan di tutorial sebelumnya dalam seri ini.

MAterial

Semua pembicaraan tentang massa dan kerapatan ini mengarah pada pertanyaan: Di mana nilai densitas berada? Itu berada di dalam struktur Material:

struct Material
{
  float density;
  float restitution;
};

Setelah nilai-nilai materi ditetapkan, bahan ini dapat diteruskan ke bentuk tubuh sehingga tubuh dapat menghitung massa.

Hal terakhir yang patut disebutkan adalah gravity_scale. Skala gravitasi untuk objek yang berbeda sangat sering diperlukan untuk menyesuaikan gameplay yang terbaik untuk hanya memasukkan nilai dalam setiap tubuh khusus untuk tugas ini.

Beberapa pengaturan material yang berguna untuk jenis material umum dapat digunakan untuk membuat objek Material dari nilai enumerasi:

Rock       Density : 0.6  Restitution : 0.1
Wood       Density : 0.3  Restitution : 0.2
Metal      Density : 1.2  Restitution : 0.05
BouncyBall Density : 0.3  Restitution : 0.8
SuperBall  Density : 0.3  Restitution : 0.95
Pillow     Density : 0.1  Restitution : 0.2
Static     Density : 0.0  Restitution : 0.4

Gaya

Ada satu hal lagi yang perlu dibicarakan dalam struktur body. Ada anggota data yang disebut force. Nilai ini dimulai dari nol pada awal setiap pembaruan fisika. Pengaruh lain dalam mesin fisika (seperti gravitasi) akan menambahkan vektor Vec2 ke dalam anggota data force ini. Sebelum integrasi semua kekuatan ini akan digunakan untuk menghitung percepatan tubuh, dan digunakan selama integrasi. Setelah integrasi, anggota data force ini dimusnahkan.

Hal ini memungkinkan sejumlah kekuatan untuk bertindak pada objek kapan pun mereka mau, dan tidak ada kode tambahan yang perlu ditulis ketika jenis kekuatan baru akan diterapkan ke objek.

Mari kita ambil contoh. Katakanlah kita memiliki lingkaran kecil yang mewakili objek yang sangat berat. Lingkaran kecil ini terbang di dalam permainan, dan itu sangat berat sehingga menarik objek lain ke arahnya sedikit. Berikut ini beberapa pseudocode kasar untuk menunjukkan ini:

HeavyObject object
for body in game do
  if(object.CloseEnoughTo( body )
    object.ApplyForcePullOn( body )

Fungsi ApplyForcePullOn() mungkin dapat menerapkan kekuatan kecil untuk menarik body ke arah HeavyObject, hanya jika body cukup dekat.

Tidak masalah berapa banyak kekuatan yang ditambahkan ke force tubuh, karena mereka semua akan menambah satu vektor gaya dijumlahkan untuk tubuh itu. Ini berarti bahwa dua kekuatan yang bekerja pada tubuh yang sama dapat berpotensi membatalkan satu sama lain.

Fase yang luas

Dalam artikel sebelumnya di seri ini rutin deteksi tabrakan diperkenalkan. Rutinitas ini sebenarnya terpisah dari apa yang dikenal sebagai "fase sempit". Perbedaan antara fase luas dan fase sempit dapat diteliti lebih mudah dengan pencarian Google.

(Singkatnya: kami menggunakan deteksi tabrakan fase luas untuk mengetahui pasangan benda mana yang mungkin bertabrakan, dan kemudian deteksi tabrakan fase sempit untuk memeriksa apakah mereka benar-benar bertabrakan.)

Saya ingin memberikan beberapa contoh kode bersama dengan penjelasan tentang bagaimana menerapkan fase luas dari  \(O(n^2)\)  perhitungan string kompleksitas waktu 

Karena kita bekerja dengan pasangan objek, akan berguna untuk membuat struktur seperti ini:

struct Pair
{
  body *A;
  body *B;
};

Fase luas harus mengumpulkan banyak kemungkinan tabrakan dan menyimpannya semua dalam struktur Pair. Pasangan ini kemudian dapat diteruskan ke bagian lain dari mesin (fase sempit), dan kemudian diselesaikan.

Contoh fase luas:

// Generates the pair list.
// All previous pairs are cleared when this function is called.
void BroadPhase::GeneratePairs( void )
{
  pairs.clear( )

  // Cache space for AABBs to be used in computation
  // of each shape's bounding box
  AABB A_aabb
  AABB B_aabb

  for(i = bodies.begin( ); i != bodies.end( ); i = i->next)
  {
    for(j = bodies.begin( ); j != bodies.end( ); j = j->next)
    {
      Body *A = &i->GetData( )
      Body *B = &j->GetData( )

      // Skip check with self
      if(A == B)
        continue

      A->ComputeAABB( &A_aabb )
      B->ComputeAABB( &B_aabb )

      if(AABBtoAABB( A_aabb, B_aabb ))
        pairs.push_back( A, B )
    }
  }
}

Kode di atas cukup sederhana: Periksa setiap badan terhadap setiap tubuh, dan lewati pemeriksaan-sendiri.

Mengurangi Duplikat

Ada satu masalah dari bagian terakhir: banyak pasangan duplikat akan dikembalikan! Duplikat ini harus diambil dari hasil. Beberapa keakraban dengan algoritma penyortiran akan diperlukan di sini jika Anda tidak memiliki semacam perpustakaan pengurutan yang tersedia. Jika Anda menggunakan C++ maka Anda beruntung:

// Sort pairs to expose duplicates
sort( pairs, pairs.end( ), SortPairs );

// Queue manifolds for solving
{
  int i = 0;
  while(i < pairs.size( ))
  {
    Pair *pair = pairs.begin( ) + i;
    uniquePairs.push_front( pair );

    ++i;

    // Skip duplicate pairs by iterating i until we find a unique pair
    while(i < pairs.size( ))
    {
      Pair *potential_dup = pairs + i;
      if(pair->A != potential_dup->B || pair->B != potential_dup->A)
        break;
      ++i;
    }
  }
}

Setelah menyortir semua pasangan dalam urutan tertentu dapat diasumsikan bahwa semua pasangan dalam wadah pairs akan memiliki semua duplikat yang berdekatan satu sama lain. Tempatkan semua pasangan unik ke dalam wadah baru yang disebut uniquePairs, dan tugas dari pemilahan duplikat telah selesai.

Hal terakhir yang perlu disebutkan adalah predikat SortPairs(). Fungsi SortPairs() ini adalah apa yang sebenarnya digunakan untuk melakukan penyortiran, dan mungkin terlihat seperti ini:

bool SortPairs( Pair lhs, Pair rhs )
{
  if(lhs.A < rhs.A)
    return true;

  if(lhs.A == rhs.A)
    return lhs.B < rhs.B;

  return false;
}

Layering

Layering mengacu pada tindakan memiliki objek yang berbeda tidak pernah bertabrakan satu sama lain. Ini adalah kunci karena peluru yang ditembakkan dari objek tertentu tidak mempengaruhi objek tertentu lainnya. Sebagai contoh, pemain di satu tim mungkin ingin roket mereka untuk menyakiti musuh tetapi tidak satu sama lain.

Layering paling baik diimplementasikan dengan bitmask - lihat Bagaimana Bitmask Cepat untuk Programmer dan halaman Wikipedia untuk pengenalan cepat, dan bagian Penyaringan dari panduan Box2D untuk melihat bagaimana mesin itu menggunakan bitmask.

Layering harus dilakukan dalam fase yang luas. Di sini saya hanya akan menempelkan contoh fase luas jadi:

// Generates the pair list.
// All previous pairs are cleared when this function is called.
void BroadPhase::GeneratePairs( void )
{
  pairs.clear( )

  // Cache space for AABBs to be used in computation
  // of each shape's bounding box
  AABB A_aabb
  AABB B_aabb

  for(i = bodies.begin( ); i != bodies.end( ); i = i->next)
  {
    for(j = bodies.begin( ); j != bodies.end( ); j = j->next)
    {
      Body *A = &i->GetData( )
      Body *B = &j->GetData( )

      // Skip check with self
      if(A == B)
        continue

      // Only matching layers will be considered
      if(!(A->layers & B->layers))
        continue;

      A->ComputeAABB( &A_aabb )
      B->ComputeAABB( &B_aabb )

      if(AABBtoAABB( A_aabb, B_aabb ))
        pairs.push_back( A, B )
    }
  }
}

Layering ternyata sangat efisien dan sangat sederhana.

Perpotongan Halfspace

Halfspace dapat dilihat sebagai satu sisi garis dalam 2D. Mendeteksi apakah suatu titik berada di satu sisi garis atau yang lain adalah tugas yang cukup umum, dan harus dipahami secara menyeluruh oleh siapa pun yang menciptakan mesin fisika mereka sendiri. Sayang sekali topik ini tidak benar-benar dibahas di mana pun di internet dengan cara yang berarti, setidaknya dari apa yang saya lihat - sampai sekarang, tentu saja!

Persamaan umum dari garis dalam 2D adalah:

\[Equation 4:\\
General \: form: ax + by + c = 0\\
Normal \: to \: line: \begin{bmatrix}
a \\
b \\
\end{bmatrix}\]

Perhatikan bahwa, terlepas dari namanya, vektor normal tidak perlu dinormalisasi (artinya, tidak harus memiliki panjang 1).

Untuk melihat apakah suatu titik berada pada sisi tertentu dari garis ini, semua yang perlu kita lakukan adalah menghubungkan titik ke dalam variabel x dan y dalam persamaan dan memeriksa tanda hasil. Hasil dari 0 berarti titik berada di garis, dan sisi negatif positif / negatif dari garis yang berbeda.

Hanya itu saja! Mengetahui ini jarak dari titik ke garis sebenarnya hasil dari tes sebelumnya. Jika vektor normal tidak dinormalisasi, maka hasilnya akan diskalakan oleh besarnya vektor normal.

Kesimpulan

Sekarang mesin fisika yang lengkap, meskipun sederhana, dapat dibangun seluruhnya dari awal. Topik yang lebih maju seperti gesekan, orientasi, dan pohon AABB dinamis dapat dibahas di tutorial selanjutnya. Silakan ajukan pertanyaan atau berikan komentar di bawah ini, saya senang membaca dan menjawabnya!