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

Pengesanan Perlanggaran Menggunakan Teorema Axis Terpisah

by
Difficulty:IntermediateLength:LongLanguages:

Malay (Melayu) translation by Aisyah Arrafah (you can also view the original English article)

Teorema Axis Pemisahan sering digunakan untuk memeriksa perlanggaran antara dua poligon mudah, atau antara poligon dan bulatan. Seperti semua algoritma, ia mempunyai kekuatan dan kelemahannya. Dalam tutorial ini, kami akan meneruskan matematik di sebalik teorem, dan menunjukkan bagaimana ia boleh digunakan dalam pembangunan permainan dengan beberapa kod sampel dan demo.

Nota: Walaupun demo dan sumber data tutorial ini menggunakan Flash dan AS3, anda harus menggunakan teknik dan konsep yang sama dalam hampir semua persekitaran pembangunan permainan.


Apa Negeri Teorem

Teorem Axis Pemisahan (SAT untuk pendek) pada dasarnya menyatakan jika anda boleh melukis garis untuk memisahkan dua poligon, maka mereka tidak bertembung. Itulah yang mudah.

SAT collision detection

Dalam rajah di atas, anda boleh melihat perlanggaran yang berlaku di baris kedua. Walau bagaimanapun anda cuba memerah garis di antara bentuk, anda akan gagal. Baris pertama adalah sebaliknya. Anda boleh dengan mudah melukis garis untuk memisahkan bentuk - dan bukan hanya satu baris, tetapi banyak daripada mereka:

Lines separating shapes

Okay, janganlah keterlaluan ini; Saya fikir anda mendapat titik. Hujah utama di sini ialah jika anda boleh melukis garis itu, maka harus ada jurang yang memisahkan bentuknya. Jadi bagaimana kita memeriksa ini?


Unjuran Sepanjang Axis Sewenang-wenang

basic idea of algorithm

Mari kita anggap sekarang bahawa poligon yang kita rujuk adalah kotak: box1 di sebelah kiri dan kotak2 di sebelah kanan. Adalah mudah untuk melihat bahawa dataran ini secara berasingan dipisahkan. Pendekatan mudah untuk menentukan ini dalam kod adalah untuk mengira jarak melintang antara dua kuasa dua, kemudian tolak separuh lebar kotak1 dan kotak2:

Bagaimana jika kotak tidak berorientasikan dengan baik?

oriented boxes

Walaupun penilaian jurang tetap sama, kita perlu memikirkan pendekatan lain untuk mengira panjang antara pusat dan separuh lebar -- kali ini di sepanjang paksi P. Ini adalah tempat matematik vektor berguna. Kami akan memproyeksikan vektor A dan B sepanjang P untuk mendapatkan separuh lebar.

Mari buat semakan matematik.


Penyemakan Semula Vektor

Kami akan mulakan dengan menerangkan definisi produk dot antara dua vektor A dan B:

Dot product operation

Kita boleh menentukan produk titik menggunakan hanya komponen dua vektor:

\ [
\begin{bmatrix} A_x \\A_y\end{bmatrix}.
\begin{bmatrix}B_x \\B_y\end{bmatrix} =
(A_x)(B_x) + (A_y)(B_y)
\]

Sebagai alternatif, kita dapat memahami produk titik menggunakan magnitud vektor dan sudut di antara mereka:

\[
\begin{bmatrix} A_x \\A_y\end{bmatrix}.
\begin{bmatrix} B_x \\B_y\end{bmatrix} =
A_ {magnitud}*B_ {magnitud}*cos(theta)
\]

Sekarang, mari kita cuba mencari unjuran vektor A ke P.

description of image

Merujuk kepada rajah di atas, kita tahu bahawa nilai unjuran ialah \(A_ {magnitude}*cos (theta) \) (di mana theta adalah sudut antara A dan P). Walaupun kita boleh meneruskan dan mengira sudut ini untuk mendapatkan unjuran, ianya sukar. Kita memerlukan pendekatan yang lebih langsung:

\[
A. P=A_ {magnitud}*P_ {magnitud}*cos (theta) \\
A. \frac {P}{P_ {magnitud}}=A_ {magnitud}*cos (theta)\\
\begin{bmatrix}A_x \\ A_y\end{bmatrix}.
\begin{bmatrix} P_x/P_{magnitud} \\P_y/P_{magnitud}\end{bmatrix} =
A_{magnitud}*cos (theta)
\]

Perhatikan bahawa \(\begin {bmatrix}P_x /P_ {magnitud} \\ P_y/P_ {magnitud}\end {bmatrix}\) sebenarnya vektor unit P.

Sekarang, bukannya menggunakan sebelah kanan persamaan, seperti yang kita ada, kita boleh memilih sebelah kiri dan masih sampai pada keputusan yang sama.


Permohonan Skenario

Sebelum kita meneruskan, saya ingin menjelaskan konvensyen penamaan yang digunakan untuk menandakan empat sudut kedua-dua kotak. Ini akan ditunjukkan dalam kod kemudian:

naming conventions of points

Senario kami adalah seperti berikut:

projection of various lengths

Katakan kedua-dua kotak berorientasikan 45 ° dari paksi mendatar. Kita mesti mengira panjang berikut untuk menentukan jurang antara kotak.

  • Unjuran A pada paksi P
  • Unjuran B pada paksi P
  • Unjuran C pada paksi P

Ambil perhatian khusus arahan anak panah. Walaupun unjuran A dan C ke P akan memberi nilai positif, unjuran B ke P sebenarnya menghasilkan nilai negatif apabila vektor menunjuk arah yang bertentangan. Ini diliputi dalam garis 98 pelaksanaan AS3 di bawah:

Inilah demo yang menggunakan kod di atas. Klik dan seret titik tengah merah kedua-dua kotak dan lihat maklum balas interaktif.

Untuk sumber penuh, lihat DemoSAT1.as dalam muat turun sumber.


The Flaws

Nah, kita boleh pergi dengan pelaksanaan di atas. Tetapi ada beberapa masalah -- biar saya menunjukkan mereka:

Pertama, vektor A dan B ditetapkan. Jadi apabila anda menukar posisi box1 dan box2, pengesanan perlanggaran gagal.

wrong vector selected

Kedua, kita hanya menilai jurang sepanjang satu paksi, jadi keadaan seperti yang di bawah tidak akan dinilai dengan betul:

only one axis evaluated

Walaupun demo sebelumnya cacat, kami belajar dari konsep konsep unjuran. Seterusnya, mari memperbaikinya.


Menyelesaikan Kesilapan Pertama

Jadi, pertama sekali, kita perlu mendapatkan unjuran minimum dan maksimum sudut (khususnya vektor dari asal ke sudut kotak) ke P.

projection of minimum and maximum of two boxes

Rajah di atas menunjukkan unjuran sudut minimum dan maksimum ke P apabila kotak diarahkan dengan baik di sepanjang P.

Tetapi bagaimana jika box1 dan box2 tidak berorientasikan dengan sewajarnya?

projection if boxes are not oriented accordingly

Rajah di atas menunjukkan kotak yang tidak berorientasikan dengan kemas di sepanjang P, dan unjuran min min yang bersesuaian. Dalam keadaan ini, kita perlu melangkau setiap sudut setiap kotak dan pilih yang betul sesuai.

Sekarang bahawa kami mempunyai unjuran min-max, kami akan menilai sama ada kotak bertabrakan antara satu sama lain. Bagaimana?

Checking for collision

Dengan memerhatikan rajah di atas, kita dapat melihat dengan jelas perwakilan geometri untuk unjuran kotak1.max dan box2.min ke paksi P.

Seperti yang anda dapat lihat, apabila jurang antara dua kotak, kotak2.min-box1.max akan menjadi lebih daripada sifar - atau dengan kata lain, box2.min> box1.max. Apabila kedudukan kotak ditukar, maka kotak1.min> box2.max menunjukkan ada jurang antara mereka.

Menterjemahkan kesimpulan ini ke dalam kod, kita dapat:


Kod Permulaan

Mari lihat beberapa kod yang lebih terperinci untuk memikirkannya. Ambil perhatian bahawa kod AS3 di sini tidak dioptimumkan. Walaupun ia panjang dan deskriptif, kelebihannya ialah anda dapat melihat bagaimana matematik di belakangnya berfungsi.

Pertama sekali, kita perlu menyediakan vektor:

Seterusnya, kami memperoleh unjuran min-max pada kotak1. Anda boleh melihat pendekatan serupa yang digunakan pada kotak2:

Akhirnya, kita menilai sama ada terdapat perlanggaran pada paksi tertentu itu, P:

Inilah demo pelaksanaan di atas:

Anda boleh menyeret sama ada kotak sekitar melalui titik tengahnya, dan berputar dengan kekunci R dan T. Titik merah menandakan sudut maksimum untuk kotak, manakala kuning menandakan minimum. Jika kotak selaras dengan P, anda mungkin mendapati bahawa titik-titik ini berkedip ketika anda menyeret, kerana kedua-dua penjuru tersebut berkongsi ciri-ciri yang sama.

Lihat sumber penuh dalam DemoSAT2.as dalam muat turun sumber.


Pengoptimuman

Jika anda ingin mempercepatkan proses, tidak perlu mengira untuk vektor unit P. Anda boleh melangkau beberapa pengiraan teorem Pythagoras yang mahal yang melibatkan Math.sqrt():

\[\begin{bmatrix}A_x \\A_y\end{bmatrix}.
\\begin{bmatrix}P_x/P_ {magnitud}\\P_y/P_ {magnitud}\end{bmatrix} =
A_ {magnitud} * cos (theta)
\]

optimisation

Alasannya adalah seperti berikut (rujuk diagram di atas untuk beberapa panduan visual mengenai pembolehubah):

Sekarang, secara matematik, tanda ketidaksamaan tetap sama jika kedua-dua belah ketidaksamaan didarabkan dengan nombor yang sama, A:

Jadi sama ada ia vektor unit atau tidak sebenarnya tidak penting -- hasilnya sama.

Perlu diingatkan bahawa pendekatan ini berguna jika anda menyemak hanya tumpang tindih sahaja. Untuk mencari panjang penembusan yang tepat kotak1 dan kotak2 (yang untuk kebanyakan permainan anda mungkin perlu), anda masih perlu mengira vektor unit P.


Menyelesaikan Kecacatan Kedua

Oleh itu, kita menyelesaikan masalah ini untuk satu paksi, tetapi itu bukan akhirnya. Kami masih perlu mengatasi paksi lain -- tetapi yang mana?

overlappings on axes

Analisis untuk kotak adalah agak mudah: kita membandingkan dua paksi P dan Q. Untuk mengesahkan perlanggaran, tumpang tindih pada semua paksi mesti benar -- jika terdapat paksi apa-apa tanpa tumpang tindih, kita boleh membuat kesimpulan bahawa tiada perlanggaran.

Bagaimana jika kotak berorientasikan secara berbeza?

Klik butang hijau untuk beralih ke halaman lain. Oleh itu, paksi P, Q, R, dan S, hanya ada satu paksi yang tidak menunjukkan pertindihan di antara kotak, dan kesimpulannya ialah tidak ada perlanggaran antara kotak.

Tetapi persoalannya, bagaimanakah kita memutuskan mana paksi untuk memeriksa pertindihan? Nah, kita ambil norma poligon.

normals of boxes

Dalam bentuk umum, dengan dua kotak, kita perlu memeriksa bersama-sama lapan paksi: n0, n1, n2 dan n3 untuk setiap kotak1 dan kotak2. Walau bagaimanapun, kita dapat melihat bahawa pembohongan berikut pada paksi yang sama:

  • n0 dan n2 dari kotak1
  • n1 dan n3 dari kotak1
  • n0 dan n2 dari kotak2
  • n1 dan n3 dari kotak2

Jadi kita tidak perlu melewati semua lapan; hanya empat sahaja yang akan dilakukan. Dan jika box1 dan box2 berkongsi orientasi yang sama, kita dapat mengurangkan lagi untuk hanya menilai dua paksi.

Bagaimana dengan poligon lain?

normals of triangles and pentagons

Malangnya, untuk segitiga dan pentagon di atas tidak ada jalan pintas sedemikian, maka kita perlu menjalankan pemeriksaan sepanjang semua normals.


Mengira Normal

Setiap permukaan mempunyai dua jenis:

calculating normals

Rajah di atas menunjukkan normal kiri dan kanan P. Perhatikan komponen beralih vektor dan tanda untuk setiap satu.

left normals used

Untuk pelaksanaan saya, saya menggunakan konvensyen mengikut arah jam, jadi saya menggunakan normals kiri. Berikut adalah cabutan SimpleSquare.as yang menunjukkan ini.


Pelaksanaan Baru

Saya pasti anda boleh mencari jalan untuk mengoptimumkan kod berikut. Tetapi hanya supaya kita semua mendapat gambaran yang jelas tentang apa yang berlaku, saya telah menulis semuanya dengan lengkap:

Anda akan melihat bahawa beberapa pembolehubah tidak perlu dikira untuk mencapai hasilnya. Jika mana-mana dari terpisah_P, terpisah_Q, terpisah_R dan terpisah_S adalah benar, maka mereka dipisahkan dan tidak perlu untuk meneruskan.

Ini bermakna kita boleh menyimpan jumlah penilaian yang adil, hanya dengan memeriksa setiap orang Booleans selepas mereka dikira. Ia memerlukan penulisan ulang kod, tetapi saya fikir anda boleh menggunakan jalan anda (atau periksa blok komen dalam DemoSAT3.as).

Inilah demo pelaksanaan di atas. Klik dan seret kotak melalui titik tengah mereka, dan gunakan kekunci R dan T untuk memutar kotak:


Setelah Pemikiran

Apabila algoritma ini dijalankan, ia memeriksa paksi normal untuk overlappings. Saya mempunyai dua pemerhatian di sini untuk menunjukkan:

  • SAT optimistik bahawa tidak akan ada perlanggaran antara poligon. Algoritma boleh keluar dan dengan senang hati membuat kesimpulan "tidak perlanggaran" apabila paksi mana-mana tidak menunjukkan pertindihan. Jika terdapat sebarang perlanggaran, SAT perlu menjalankan semua paksi untuk mencapai kesimpulan tersebut -- oleh itu, semakin banyak perlanggaran di sana sebenarnya, semakin buruknya algoritma tersebut.
  • SAT menggunakan normal setiap tepi poligon. Jadi semakin kompleks poligon itu, SAT yang lebih mahal akan menjadi.

Hexagon-Triangle Detection Collision

Berikut ialah coretan kod contoh lain untuk memeriksa perlanggaran di antara segi segi enam dan segi tiga:

Untuk kod penuh, lihat DemoSAT4.as dalam muat turun sumber.

Demo di bawah. Interaksi adalah sama seperti dalam demo sebelumnya: seret melalui titik tengah, dan gunakan R dan T untuk berputar.


Pengesanan Perlanggaran Kotak-Lingkaran

collision with circle

Perlanggaran dengan bulatan mungkin salah satu yang lebih mudah. Kerana unjurannya adalah sama dalam semua arah (ia hanya jejari bulatan), kita boleh melakukan yang berikut:

Lihat sumber penuh dalam DemoSAT5.as. Seret sama ada bulatan atau kotak untuk melihatnya bertembung.


Kesimpulan

Nah, itulah untuk masa sekarang. Terima kasih kerana membaca dan meninggalkan maklum balas anda dengan ulasan atau soalan. Lihat tutorial seterusnya!

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.