Unlimited Plugins, WordPress themes, videos & courses! Unlimited asset downloads! From $16.50/m
Advertisement
  1. Code
  2. ActionScript

Memprediksi Titik Benturan Dengan Matematika di AS3

by
Difficulty:IntermediateLength:LongLanguages:
This post is part of a series called Collision Detection and Reaction.
Pixel-Level Collision Detection
Pixel-Level Collision Detection Based on Pixel Colors

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

Dalam tutorial saya sebelumnya tentang deteksi tabrakan antara lingkaran dan garis, saya menutupi proyeksi pada garis menggunakan produk titik dari vektor. Dalam tutorial ini, kita akan melihat produk titik yang tegak lurus dan menggunakannya untuk memprediksi titik persimpangan untuk dua garis.


Pratinjau Hasil Akhir

Mari kita lihat hasil akhir yang akan kita kerjakan. Gunakan tombol panah kiri dan kanan untuk mengarahkan kapal (segitiga), dan tekan ke atas untuk meningkatkan kecepatan sementara. Jika titik tabrakan yang diproyeksikan di masa depan berada di dinding (garis), titik merah akan dilukis di atasnya. Untuk tabrakan yang 'sudah' terjadi (yaitu akan terjadi di masa lalu, berdasarkan arah saat ini), titik merah masih akan dicat tetapi sedikit transparan.

Anda juga dapat mengeklik mouse dan menyeret titik hitam untuk memindahkan dinding. Perhatikan bahwa kita tidak hanya memprediksi lokasi tabrakan, tetapi juga waktunya.


Langkah 1: Revisi

Sebelum masuk ke topik, mari lakukan beberapa revisi. Berikut persamaan produk titik (yang sebelumnya dibahas di sini):

dot product formula

Dan inilah definisi produk dot yang tegak lurus yang diekstraksi dari Wolfram:

perp dot product formula

Langkah 2: Produk Dot Tegak Lurus

Sekarang untuk membantu kami membentuk gambaran mental, saya telah menyiapkan gambar di bawah ini. Saya yakin pada titik ini Anda dapat memperoleh komponen vektor vertikal dan horizontal, sehingga komponen yang melibatkan sinus dan kosinus seharusnya tidak menjadi tantangan.

a mental picture for two formula

Mari gantikan kedua komponen dengan yang setara. Saya telah menggunakan A dengan topi untuk mewakili vektor satuan A (yaitu vektor yang menunjuk ke arah yang sama dengan A, tetapi memiliki magnitude tepat 1). Detail lainnya adalah bahwa tegak lurus B sebenarnya adalah normal B - lebih pada normals langkah berikutnya.

second mental picture for two formula

Dari diagram di atas kita dapat melihat bahwa proyeksi B pada A akan menghasilkan | B | * cos (theta). Tetapi mengapa proyeksi produk B yang normal | B | * sin (theta)?

Untuk lebih memahami ini, saya telah menyertakan demo Flash di bawah ini. Klik dan seret panah hitam. Saat Anda dengan lembut memindahkannya, Anda akan melihat bahwa sumbu tegak lurus juga mengikuti. Saat mereka berbelok, garis merah tebal juga akan dianimasikan. Perhatikan bahwa kedua panjang ini sama - maka persamaan produk dot tegak lurus.


Langkah 3: Normalnya

Normalnya, menurut definisi, terletak pada garis tegak lurus yang memotong garis minat Anda. Mari coba bayangkan garis-garis ini pada bidang geometris.

normals of a vector

Sistem koordinat Cartesian digunakan dalam diagram di atas. B adalah normal kiri dan C adalah normal yang benar. Kami melihat bahwa x-komponen B negatif (karena itu menunjuk ke kiri) dan komponen-y dari C negatif (karena itu mengarah ke bawah).

Tetapi periksa kesamaan antara B dan C. Komponen x dan y mereka sama dengan A, kecuali swizzled. Perbedaannya hanyalah posisi tanda. Jadi kami mencapai kesimpulan dengan gambar di bawah ini.

second mental picture for two formula

Perhatikan bahwa kami merujuk khusus ke sistem koordinat Cartesian dalam contoh ini. Sumbu y dari ruang koordinat Flash adalah pantulan dari satu di Cartesian, menghasilkan pertukaran antara kiri dan kanan normal.


Langkah 4: Memproyeksikan Titik Tabrakan

Untuk mengetahui titik tabrakan vektor k pada bidang A, kita harus menghubungkan ekor k dengan titik sembarang pada bidang A pertama. Untuk kasus di bawah ini, vektor j adalah vektor yang menghubungkan; kemudian kita mendapatkan proyeksi tegak lurus k dan j pada bidang A.

using perp dot product of vectors

Titik merah pada gambar di bawah ini adalah titik tumbukan. Dan saya harap Anda dapat melihat segitiga serupa dalam diagram di bawah ini.

similar triangles
  • | k |, besarnya vektor k
  • Panjang j tegak lurus dari bidang A
  • Panjang k pada bidang tegak lurus pesawat A

Jadi mengingat ketiga komponen di atas, kita dapat menggunakan konsep rasio untuk menyimpulkan panjang antara titik merah dan biru. Akhirnya, kami menetapkan besarnya vektor k ke panjang kata dan kami memiliki titik tumbukan kami!


Langkah 5: Implementasi ActionScript

Jadi inilah implementasi ActionScript. Saya telah menyertakan demo di bawah ini. Cobalah untuk memindahkan panah agar kedua garis berpotongan. Titik hitam kecil akan menandai titik persimpangan garis. Perhatikan bahwa segmen ini tidak selalu berpotongan, tetapi garis tak terbatas yang mereka wakili adalah.

Berikut skrip yang melakukan perhitungan. Lihat Basic.as di pengunduhan sumber untuk skrip lengkap.


Langkah 6: Persamaan Baris

Jadi saya harap pendekatan pertama yang saya sajikan mudah dipahami. Saya memahami kinerja dalam mendapatkan titik persimpangan itu penting, jadi selanjutnya saya akan memberikan pendekatan alternatif, meskipun itu akan membutuhkan beberapa revisi matematika. Beruang denganku!

Pertama, mari kita bicara tentang persamaan garis. Ada beberapa bentuk persamaan garis, tetapi kami hanya akan menyentuh dua di antaranya dalam tutorial ini:

  • Formulir umum
  • Bentuk parametrik

Saya telah menyertakan gambar di bawah ini untuk membantu Anda mengingat. Mereka yang tertarik dalam hal ini dapat merujuk pada entri ini di Wikipedia.

different forms of line equation

Langkah 7: Turunkan Formulir Standar

Sebelum kita melakukan manipulasi pada dua persamaan garis, kita harus menurunkan persamaan garis ini terlebih dahulu. Mari kita pertimbangkan skenario di mana kita diberi koordinat dua poin p1 (a, b). dan p2 (c, d). Kita dapat membentuk persamaan garis yang menghubungkan dua titik ini dari gradien:

derive constants

Kemudian, dengan menggunakan persamaan ini, kita dapat memperoleh konstanta A, B, dan C untuk bentuk standar:

derive constants

Selanjutnya, kita dapat melanjutkan untuk menyelesaikan persamaan garis simultan.


Langkah 8: Memecahkan Persamaan Simultan

Sekarang kita dapat membentuk persamaan garis, mari kita lanjutkan untuk mengambil dua persamaan garis dan menyelesaikannya secara simultan. Mengingat dua persamaan garis ini:

  • Ex + Fy = G
  • Px + Qy = R

Saya akan tabel koefisien ini sesuai dengan bentuk umum Ax + By = C.

A B C
E F G
P Q R

Untuk mendapatkan nilai y, kami melakukan hal berikut:

  1. Gandakan koefisien timbal balik dari x untuk seluruh persamaan.
  2. Lakukan operasi pengurangan (dari atas) pada kedua persamaan.
  3. Tata ulang persamaan yang didapat dalam hal y.
A B C Kalikan dengan
E F G P
P Q R E

Dan kita sampai di meja berikut.

A B C
EP FP GP
PE QE RE

Setelah kita kurangi dua persamaan, kita sampai di:

  • y (FP - QE) = (GP - RE), yang menata ulang ke:
  • y = (GP - RE) / (FP - QE)

Pindah untuk mendapatkan x:

A B C Kalikan dengan
E F G Q
P Q R F

Kami tiba di meja berikut

A B C
EQ FQ GQ
PF QF RF

Setelah kita kurangi dua persamaan, kita sampai di:

  • x (EQ - PF) = (GQ - RF), yang menyusun untuk:
  • x = (GQ - RF) / (EQ - PF)

Mari kita susun ulang y.

  • y = (GP - RE) / (FP - QE)
  • y = (GP - RE) / -(QE - FP)
  • y = (RE - GP) / (QE - FP)

Jadi kami tiba di titik persimpangan x dan y. Kami melihat mereka berbagi penyebut yang sama.

  • x = (GQ - RF) / (EQ - PF)
  • y = (RE - GP) / (QE - FP)

Sekarang setelah kami mengerjakan operasi matematika dan mendapatkan hasilnya, cukup masukkan nilai dan kami memiliki titik persimpangan.


Langkah 9: Menerapkan ke Actionscript

Berikut ini adalah implementasi Actionscript. Jadi semua operasi vektor direduksi menjadi aritmatika sederhana tapi itu akan membutuhkan beberapa aljabar kerja pada awalnya.

Tentu saja hasil yang sama seperti demo sebelumnya, hanya dengan lebih sedikit matematika yang terlibat, dan tanpa menggunakan kelas Vector2D.


Langkah 10: Matriks Alternatif

Alternatif lain untuk memecahkan masalah ini adalah dengan menggunakan matriks matematika. Sekali lagi, saya mengundang para pembaca yang tertarik untuk mengikuti kuliah Prof. Wildberger tentang persamaan garis. Di sini, kami hanya akan menerbangkan konsep itu dengan cepat.

Menurut Prof Wildberger, ada dua kerangka kerja yang kita dapat mengadopsi:

  • Kerangka Cartesian
  • Kerangka parameterised vektor

Mari kita lihat yang Cartesian dulu. Lihat gambar di bawah ini.

Cartesian matrix operation

Perhatikan bahwa matriks T dan S mengandung nilai konstan. Apa yang tersisa tidak diketahui adalah A. Jadi menata ulang persamaan matriks dalam hal A akan memberi kita hasil. Namun, kita harus mendapatkan matriks invers T.


Langkah 11: Menerapkan Dengan AS3

Berikut implementasi di atas dengan ActionScript:


Langkah 12: Bentuk Parametrik

Terakhir, ada bentuk parametrik persamaan garis, dan kami akan mencoba menyelesaikannya melalui matriks matematika lagi.

deriving matrix from parametric equations

Kami ingin mendapatkan titik persimpangan. Mengingat semua informasi kecuali untuk u dan v yang kami coba temukan, kami akan menulis ulang kedua persamaan ke dalam bentuk matriks dan menyelesaikannya.


Langkah 13: Manipulasi Matriks

Jadi sekali lagi, kami melakukan matrix manipulasi untuk sampai pada kami hasil.

arriving at result

Langkah 14: Menerapkan dengan AS3

Jadi di sini adalah penerapan bentuk matriks:


Langkah 15: Kinerja

Kita telah membahas empat pendekatan untuk memecahkan masalah ini sedikit. Jadi bagaimana dengan kinerja? Yah saya pikir saya akan membiarkan masalah ini kepada pembaca untuk menilai, meskipun saya percaya perbedaannya dapat diabaikan. Jangan ragu untuk memanfaatkan harness pengujian kinerja ini dari Grant Skinner.

Jadi sekarang bahwa kami telah mendapat pemahaman ini, apa berikutnya? Menerapkannya!


Langkah 16: Memprediksi Waktu Tabrakan

Menganggap partikel bergerak dalam path terikat bertabrakan dengan dinding. Kita dapat menghitung waktu untuk dampak oleh persamaan sederhana:

Velocity = Perpindahan / Waktu

concept of tunneling

Bayangkan Anda dalam putaran partikel ini jeruk dan untuk setiap frame lewat dan pengumuman dibuat pada waktu berbenturan dengan dinding. Anda akan mendengar:

"Waktu untuk dampak: 1,5 frame"-Frame 1

'Waktu untuk berdampak: 0,5 bingkai' - Bingkai 2

'Waktu untuk berdampak: -0,5 frame' - Bingkai 3

Ketika kita mencapai frame 3, tabrakan dengan garis telah terjadi (seperti yang ditunjukkan oleh tanda negatif). Anda harus memundurkan waktu untuk mencapai titik tabrakan. Jelas tabrakan terjadi beberapa waktu antara frame 2 dan 3, tetapi Flash bergerak secara bertahap satu frame. Jadi jika tabrakan terjadi di tengah-tengah antara frame, flip tanda untuk negatif akan menunjukkan bahwa tabrakan telah terjadi.


Langkah 17: Waktu Negatif

getting negative displacement

Untuk mendapatkan waktu negatif, kami akan menggunakan produk titik vektor. Kita tahu bahwa ketika kita memiliki dua vektor dan arahnya tidak berada dalam 90 derajat di sisi yang lain, mereka akan menghasilkan produk titik negatif. Juga, produk titik adalah ukuran seberapa paralel dua vektor. Jadi ketika tabrakan telah terjadi, kecepatan dan arah vektor ke titik di dinding akan menjadi negatif - dan sebaliknya.


Langkah 18: Implementasi ActionScript

Jadi inilah skripnya (termasuk dalam CollisionTime.as). Saya juga telah menambahkan deteksi tabrakan dalam segmen garis di sini. Bagi mereka yang merasa asing, lihat tutorial saya tentang deteksi tabrakan antara lingkaran dan segmen garis, Langkah 6. Dan untuk bantuan pada kapal kemudi, inilah referensi lain.


Langkah 19: Hasil Akhir

Jadi, inilah demo dari apa yang akan Anda dapatkan. Gunakan tombol panah kiri dan kanan untuk mengarahkan kapal (segitiga), dan tekan Naik untuk meningkatkan kecepatan sementara. Jika titik tabrakan yang diperkirakan di masa depan ada di dinding (garis), titik merah akan dilukis di atasnya. Untuk tabrakan yang telah 'sudah' terjadi, titik merah masih akan dicat tetapi sedikit transparan. Anda juga dapat menyeret titik-titik hitam di kedua sisi dinding untuk memindahkannya.

Kesimpulan

Jadi saya harap tutorial ini informatif. Berbagilah jika Anda benar-benar menerapkan ide ini di tempat lain dari yang telah saya sebutkan. Saya berencana menulis singkat tentang menerapkannya untuk melukis target laser - apa yang Anda pikirkan? Terima kasih telah membaca dan beri tahu saya jika ada kesalahan.

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.