Cara Menyelesaikan Tumbukan Benda Tegar 2D

 (sassnow.ski)
3 poin oleh GN⁺ 2024-05-25 | 1 komentar | Bagikan ke WhatsApp
  • Penyelesaian tumbukan benda tegar dalam fisika game 2D adalah persoalan menghitung perubahan kecepatan agar objek yang sudah bersentuhan atau saling tumpang tindih tidak saling menembus pada frame berikutnya
  • Karena game loop memperbarui posisi setiap frame menggunakan kecepatan dan Δt, jika geometri pada posisi baru saling tumpang tindih, tanpa penanganan terpisah objek akan saling melewati
  • Tumbukan bukan sekadar apakah terjadi kontak, tetapi juga harus melihat apakah objek-objek yang bersentuhan masih bergerak saling mendekat dengan kecepatan saat ini
  • Apakah objek menjauh dari permukaan dapat ditentukan dari tanda hasil kali titik antara normal dan kecepatan; jika positif ada komponen searah, jika negatif ada komponen berlawanan arah
  • Untuk dua objek, yang penting bukan kecepatan masing-masing, melainkan kecepatan relatif dan normal tumbukan; dalam kondisi kontak, jika kecepatan normal relatif bernilai negatif, itu dapat dianggap sebagai tumbukan

Ruang Lingkup Fisika Benda Tegar dan Penyelesaian Tumbukan

  • Topiknya adalah fisika benda tegar (rigid body physics), yang menangani objek yang tidak berubah bentuk meskipun menerima gaya
    • Di dunia nyata, semua objek mengalami deformasi pada tingkat molekuler, sehingga benda tegar sempurna tidak ada
    • Dalam sebagian besar simulasi fisika, menghitung deformasi sedetail ini sangat sulit atau mahal secara komputasi
    • Jika objek terlihat cukup realistis, menyederhanakannya sebagai benda tegar adalah pendekatan yang praktis
  • Penanganan tumbukan dalam game engine biasanya dibagi menjadi dua tahap
    • deteksi tumbukan (collision detection): menentukan objek mana saja dalam scene yang sedang bertumbukan
    • penyelesaian tumbukan (collision resolution): menentukan keadaan berikutnya berdasarkan arah gerak, kecepatan, material, dan faktor lain dari objek yang sedang bertumbukan
  • Fokus pembahasan di sini bukan tahap mencari apakah ada perpotongan geometris, melainkan penyelesaian tumbukan yang menentukan gerakan setelah tumbukan

Cara Tumbukan Terjadi dalam Game Loop

  • Sebagian besar game berulang kali menghitung ulang posisi objek-objek dalam scene di dalam loop besar
  • Pada setiap iterasi, posisi objek diperbarui berdasarkan kecepatan (velocity) saat ini
    • Kecepatan adalah besaran vektor yang memiliki besar dan arah
    • Panjang panah menunjukkan kelajuan, dan arah panah menunjukkan arah gerak
  • Perubahan posisi selama interval waktu tetap Δt dinyatakan sebagai perpindahan (displacement)
    • Perpindahan juga merupakan besaran vektor yang memiliki besar dan arah
    • Jika game loop berjalan 60 kali per detik, Δt menjadi 1/60 detik
  • Posisi baru diperoleh dengan menambahkan perpindahan yang dihitung dari kecepatan saat ini ke posisi lama
  • Jika posisi baru dua objek membuat geometri keduanya saling tumpang tindih, tanpa penanganan terpisah objek akan menembus lalu melewati satu sama lain

Nilai yang Dicari oleh Penyelesaian Tumbukan

  • Tujuan penyelesaian tumbukan adalah menentukan perubahan kecepatan tiap objek agar saat simulasi berjalan, objek-objek tidak lagi saling menembus
  • Kecepatan sebelum dan sesudah tumbukan dinyatakan dengan notasi berikut
    • v_a,i, v_b,i: kecepatan objek a, b sebelum tumbukan
    • v_a,f, v_b,f: kecepatan objek a, b setelah tumbukan
    • Δv_a, Δv_b: perubahan kecepatan masing-masing objek akibat tumbukan
  • Pada akhirnya, penyelesaian tumbukan adalah persoalan mencari nilai Δv_a dan Δv_b
  • Agar menghasilkan tumbukan yang terlihat realistis, perubahan kecepatan yang dipilih harus memenuhi hukum fisika yang relevan

Kontak Saja Tidak Cukup untuk Mengetahui Tumbukan

  • Dua objek yang saling bersentuhan tidak selalu berarti sedang bertumbukan
  • Tumbukan adalah situasi ketika, jika terus bergerak dengan kecepatan saat ini, objek-objek akan saling menembus
  • Pada adegan kontak yang sama sekalipun, bergantung pada arah kecepatan kedua objek, itu bisa saja tumbukan atau bukan
  • Karena itu, kondisi tumbukan membutuhkan dua hal sekaligus
    • Geometri objek harus bersentuhan atau saling tumpang tindih
    • Objek-objek masih harus bergerak ke arah tumbukan

Normal Permukaan dan Arah Menjauh

  • Apakah sebuah objek menjauh dari suatu permukaan dapat ditentukan menggunakan arah normal (normal direction) terhadap permukaan tersebut
  • Arah normal tegak lurus terhadap permukaan dan menunjuk ke arah yang langsung menjauhi permukaan
    • Pada permukaan datar, arah normal di semua titik sama
    • Pada permukaan melengkung, arah normal berbeda di setiap titik
    • Pada keliling lingkaran, arah dari pusat menuju titik pada keliling tersebut adalah arah normal
  • Arah normal dinyatakan sebagai vektor ternormalisasi dengan panjang 1
    • Vektor dengan panjang 1 juga disebut vektor satuan (unit vector)
    • Untuk menunjukkan bahwa sebuah vektor telah dinormalisasi, tanda ^ dapat ditambahkan di atas variabel
  • Arah normal di suatu titik tegak lurus terhadap garis singgung (tangent) permukaan pada titik itu

Menentukan Komponen Arah dengan Hasil Kali Titik

  • Untuk menghitung seberapa searah sebuah vektor dengan vektor lain, kita dapat menggunakan hasil kali titik (dot product)
  • Pada vektor 2D, hasil kali titik adalah jumlah hasil perkalian komponen-komponen yang bersesuaian, dan hasilnya bukan vektor melainkan skalar
  • Secara geometris, hasil kali titik dapat dilihat sebagai panjang proyeksi skalar satu vektor ke arah vektor lain, dikalikan panjang vektor yang menjadi arah proyeksi
  • Tanda hasil kali titik memberi tahu hubungan arah antara dua vektor
    • Jika sudut antara dua vektor kurang dari 90°, hasil kali titik bernilai positif dan secara umum menunjuk ke arah yang sama
    • Jika sudutnya lebih dari 90°, hasil kali titik bernilai negatif dan secara umum menunjuk ke arah berlawanan
    • Jika sudutnya tepat 90°, hasil kali titik bernilai 0
  • Jika hasil kali titik antara vektor kecepatan objek dan normal permukaan bernilai positif, objek sedang menjauh dari permukaan tersebut

Menerapkannya pada Tumbukan Dua Objek

  • Jika ada dua objek, seperti dua kotak, masing-masing objek memiliki satu vektor kecepatan
  • Dalam kasus ini, yang digunakan adalah kecepatan relatif (relative velocity), bukan kecepatan individual
    • Kecepatan relatif adalah selisih kecepatan dua objek
    • Secara geometris, ini adalah vektor dari ujung v_b ke ujung v_a
    • Misalnya, situasi dua mobil masing-masing 50km/h bertabrakan dari depan setara, jika kondisinya sama, dengan satu mobil menabrak mobil yang diam pada 100km/h
  • Arah yang berkaitan dengan permukaan dinyatakan sebagai normal tumbukan (collision normal)
    • Cara menghitung normal tumbukan bergantung pada bentuk atau geometri objek yang bertumbukan
    • Contoh di sini adalah vertex-edge collision, yaitu titik atau simpul dari satu objek bertumbukan dengan sisi objek lain
    • Pada vertex-edge collision, normal tumbukan tegak lurus terhadap sisi tersebut
  • Sesuai konvensi, jika objek diberi label a dan b, normal tumbukan mengarah ke objek a
    • Objek mana yang disebut a atau b tidak masalah selama konsisten di seluruh perhitungan

Tumbukan yang Didefinisikan dengan Kecepatan Normal Relatif

  • Dengan menghitung hasil kali titik antara kecepatan relatif v_ab dan normal tumbukan n^, kita dapat menentukan apakah dua objek bergerak ke arah tumbukan
  • Nilai ini disebut kecepatan normal relatif (relative normal velocity)
    • Ini adalah komponen kecepatan relatif pada arah normal tumbukan
    • Di sini tandanya penting, tetapi nilai ini juga berperan penting saat menghitung gaya yang bekerja selama tumbukan nantinya
  • Tanda kecepatan normal relatif membedakan keadaan tumbukan
    • Jika nilainya positif, kedua objek sudah saling menjauh
    • Jika nilainya negatif, kedua objek masih saling menabrak
  • Pada akhirnya, tumbukan terjadi ketika titik sebuah objek bersentuhan dengan objek lain dan kecepatan normal relatif bernilai negatif

Bacaan terkait

1 komentar

 
GN⁺ 2024-05-25
Komentar Hacker News
  • Halo, saya penulisnya! Sedikit latar belakang: tulisan ini hanyalah bagian pertama dari seri blog fisika benda tegar yang ingin saya tulis.
    Tulisan ini ditujukan untuk orang seperti saya yang bukan pengembang game dan juga tidak punya latar belakang matematika yang kuat. Jadi saya menjelaskan cukup panjang bahkan konsep-konsep yang mungkin tampak nyaris jelas bagi orang yang berpengalaman di bidang ini. Kalau ada pertanyaan, saya dengan senang hati akan menjawab
    • Sebagai masukan, contoh pembuka “Mario memantul saat menginjak Goomba…” tampaknya bisa sedikit menyesatkan. Sebagian besar game Super Mario klasik era NES dan SNES tidak memerlukan, dan memang tidak menggunakan, sebagian besar perhitungan semacam ini.
      Pemula dalam pengembangan game sering salah paham dan mengira bahwa untuk menangani tabrakan mereka memerlukan perhitungan tumbukan benda tegar atau engine fisika 2D seperti Box2D. Itu benar jika Anda ingin membuat game seperti biliar atau Angry Birds, di mana kotak-kotak roboh, tetapi untuk platformer 2D biasanya cukup membandingkan persegi panjang yang sejajar sumbu untuk mendeteksi tabrakan, lalu mengubah koordinat X/Y karakter untuk membatalkan tumpang tindih, atau mengatur kecepatan Y setelah melompat atau mendarat. Dengan cara ini, rasa kontrol karakter juga lebih mudah disetel dengan rinci, dan meskipun ada inersia, biasanya bukan inersia yang realistis secara fisik. Saat pemula mencoba memakai fisika realistis, gerakannya sering terasa melayang dan kurang memuaskan.
      Contoh tutorial untuk memulai dengan pendekatan sederhana tanpa engine fisika ini: https://www.love2d.org/wiki/Tutorial:Baseline_2D_Platformer
    • Sangat bagus. Bagian “A word about math” benar-benar penting. Saya juga bukan orang yang jago matematika, tetapi dulu saya pernah membuat simulasi fisika yang sangat dasar dengan menyederhanakan konsep matematika secara ekstrem.
      Saya menumpuk berulang kali komponen seperti titik dan garis, dan karena memakai langkah-langkah kecil serta banyak garis debug visual, hasilnya memang sangat kikuk dan lambat, tetapi tetap bekerja sampai tingkat tertentu
    • Tulisannya luar biasa dan menyenangkan untuk dibaca. Saya juga bukan orang dengan latar belakang matematika yang kuat, jadi terima kasih sudah menjelaskan konsep-konsep yang “jelas” seperti ini :)
      Apakah Anda juga berencana membaca dan menjelaskan XPBD (Extended Position Based Dynamics - http://mmacklin.com/xpbd.pdf) ke depannya? Konsep ini tampaknya makin mendapat perhatian, dan saya pernah memakainya dengan cukup sukses di Bevy lewat https://github.com/Jondolf/bevy_xpbd. Kelihatannya lebih stabil daripada pendekatan umum
    • Saya benar-benar menikmati membaca tulisan ini :) Bahkan dari sudut pandang orang yang dulu kesulitan dengan topik serupa di sekolah, penjelasannya mudah dipahami.
      Akan sangat bagus jika Anda menambahkan feed RSS agar kami bisa terus mengikuti
    • Penjelasannya sangat bagus!
      Sekadar penasaran, alat apa yang Anda pakai untuk membuat halaman itu?
  • Wah! Tulisan yang diteliti dengan baik, dijelaskan dengan mendalam, dan bahkan interaktif.
    Sejujurnya, saat pertama kali melihat nama domainnya dan sadar bahwa domain tingkat atasnya adalah “.ski”, saya mengira ini situs orang yang menulis Mechanical Watch [1] dan tulisan-tulisan keren lainnya. Ternyata orangnya benar-benar berbeda, tetapi kualitasnya mirip. Apa rahasia spesial dari domain tingkat atas ".ski" ini ya :)
    1. https://news.ycombinator.com/item?id=31261533
    • Alasannya sangat sederhana. “ski” adalah akhiran yang paling umum dalam nama keluarga Polandia, dan contoh paling terkenalnya adalah Kowalski. Ada cukup banyak orang Polandia atau keturunan Polandia.
      Penulis artikel di https://ciechanow.ski yang kita sukai di sini juga seorang programmer Polandia yang bekerja di Apple
  • Saat ini saya sedang membuat game tembak-menembak luar angkasa 2D bersama anak saya sebagai side project. Sudut pandangnya top-down, dan idenya adalah tiap pemain mengendalikan sebuah kapal yang terbang di ruang tertutup penuh puing luar angkasa sambil menembaki lawannya.
    Elemen penting dalam game ini adalah bahwa puing-puing luar angkasa bisa digerakkan di dalam arena, dan digunakan secara kreatif untuk menjebak lawan atau menghalangi pencapaian tujuan. Sebagai bagian dari proyek ini, kami sengaja ingin melewati penggunaan game engine. Saya ingin sedikit lebih banyak mengajarkan struktur aplikasi kepada anak saya, dan walaupun nantinya memakai game engine yang sudah jadi, saya ingin setidaknya pernah melalui proses mengimplementasikan semuanya sendiri. Sampai sebelum mendekati deteksi dan penanganan tabrakan, semuanya baik-baik saja. Setelah itu, keadaan cepat memburuk. Meski saya punya latar belakang matematika teoretis, saya segera kewalahan oleh begitu banyak kasus tepi, dan akhirnya menyerah lalu memutuskan memakai Box2D. Saya bukan pengembang game profesional, tetapi punya pengalaman pengembangan lebih dari 20 tahun dan latar belakang matematika, namun tetap saja saya membuat kesalahan dengan meremehkan masalah ini. Jika hanya dibicarakan, ini tampak mudah, tetapi semakin masuk ke detail, kompleksitasnya terasa meningkat secara eksponensial
    • Apakah game itu benar-benar membutuhkan tumbukan fisika yang realistis? Jika tidak, itu bisa jadi kompleksitas yang tidak perlu. Hampir semua game shooter 2D sebelum tahun 2000, dan hanya sebagian kecil setelahnya, tidak memakai pendekatan seperti itu.
      Cara umum membuat game shooter dengan perbandingan persegi panjang yang sangat sederhana ada di sini: https://kidscancode.org/blog/2016/08/pygame_shmup_part_3/
      Namun, jika objek puing luar angkasa itu memang harus bertabrakan dan saling menumpuk secara realistis, dan Anda ingin kapal pemain sulit mendorong kumpulan benda berat, maka memakai library fisika memang masuk akal
    • Sudah pernah melihat integrasi Verlet [1]? Ini cukup meyakinkan dan praktis untuk berbagai kegunaan, dan sebenarnya cukup sederhana. Saya sendiri terkejut bisa membuat sistem fisika dasar hanya dalam beberapa jam setelah melihat tutorial hebat ini [2].
      [1]https://m.youtube.com/watch?v=lS_qeBy3aQI&pp=ygUSVmVybGV0IGl...

[2]https://m.youtube.com/watch?v=3HjO_RGIjCU&pp=ygUSdmVybGV0IGl...

  • Meski begitu, sepertinya ini akan menjadi pelajaran yang baik untuk putranya. Tidak selalu ada nilai dalam mengikuti mimpi untuk membuat sendiri secara murni setiap bagian dari proyek
  • Kalaupun bukan sekarang, ini akan menjadi bahan referensi yang berguna nanti. http://www.jeffreythompson.org/collision-detection/table_of_... membahas deteksi tabrakan antara titik, lingkaran, persegi panjang, garis, poligon, dan segitiga
  • Saya selalu menyukai penjelasan dari game N ini: https://www.metanetsoftware.com/technique/tutorialA.html
    Itu adalah masa ketika Flash ada di mana-mana
  • Saya bersenang-senang membuat demo TypeScript bertema bola memantul dan bertabrakan untuk topik ini. Saya belajar banyak
    Kode: https://github.com/vandrieu/canvas-bouncing-ball
    Logika tabrakan ada di src/collision.ts
    Hasil/demo: https://vandrieu.github.io/canvas-bouncing-ball/
    • Demo yang sangat bagus, kerja yang hebat! Kalau tidak keberatan, saya ingin mencoba mengubahnya menjadi game multipemain kecil
      Kalau bisa, bisakah Anda menambahkan lisensi?
  • Jika ingin mendalami hingga dinamika benda tegar dan kondisi constraint, seri tulisan blog ini sangat membantu: https://www.toptal.com/game/video-game-physics-part-i-an-int...
  • Tabrakan adalah pelanggaran terhadap constraint non-interpenetrasi berpasangan antar benda. Gaya tumbukan adalah pengali Lagrange dari constraint ini. Normal tumbukan adalah turunan parsial ternormalisasi dari fungsi constraint terhadap konfigurasi salah satu benda
    • Pendekatan seperti itu tampaknya cocok jika Anda menghitung fisika pada 1kHz atau lebih, dan memakai algoritme integrasi yang stabil secara numerik serta menghormati konservasi energi
      Namun dalam game, pembaruan fisika sering turun hingga 30Hz dan menggunakan pendekatan Euler-Cromer yang arbitrer, jadi diperlukan pendekatan yang cukup berbeda
    • Menarik! Apakah ada materi yang menjelaskan sudut pandang ini lebih lanjut?
  • Sangat keren! Saya menyukai penjelasannya, interaktivitasnya, dan terutama nada tulisan yang ramah. Saya menantikan tulisan-tulisan berikutnya
  • Membuat mesin fisika benda tegar 2D benar-benar proyek yang sangat menyenangkan. Saya pernah membuatnya dengan JavaScript sebelum belajar aljabar linear, dan menggali matematika secara mendalam agar bisa membuatnya berjalan
    Saya menghabiskan beberapa bulan, tetapi bahkan sedikit melampaui dasar-dasar yang dikenal luas pun rasanya baru menggores permukaan. Membuat mesin yang stabil tanpa benda saling menekan masuk atau bergetar adalah lubang kelinci tanpa dasar, dan tulisan-tulisan yang sangat matematis yang bisa saya temukan pun hampir tidak membahasnya. Saya memahami matematikanya lewat seri tulisan lama Christ Hecker
    http://www.chrishecker.com/Rigid_Body_Dynamics
    • Betul! “Part 3: Collision Response” pada dasarnya adalah materi yang saya jadikan referensi untuk tulisan-tulisan ini
  • Saya mulai belajar JavaScript lewat canvas, lalu membuat beberapa game browser kecil yang lucu tanpa pengalaman pengembangan game. Salah satunya adalah klon Galaga, dan secara umum berjalan cukup baik
    Bagian yang sulit adalah tabrakan proyektil. Saya seharusnya mengambil posisi peluru saat ini dan pada langkah waktu berikutnya, lalu melihat hitbox musuh dengan cara yang sama untuk memeriksa apakah keduanya berpotongan, tetapi saya hanya memeriksa langkah waktu saat ini. Akibatnya, peluru bisa secara ajaib lolos melewati musuh! Konyol sekali. Mungkin suatu hari saya akan kembali dan memperbaikinya.