Share
Teorema Axei de separare este adesea folosită pentru a verifica coliziunile dintre două poligoane simple sau între un poligon și un cerc. Ca și în cazul tuturor algoritmilor, el are punctele forte și slăbiciunile sale. În acest tutorial, vom trece peste matematica din spatele teoremei și vom arăta cum poate fi folosită în dezvoltarea jocului cu câteva exemple de cod și demonstrații.
Notă: Deși demonstrațiile și codul sursă al acestui tutorial utilizează Flash și AS3, ar trebui să puteți utiliza aceleași tehnici și concepte în aproape orice mediu de dezvoltare a jocului.
Teorema Axei de separare (SAT pe scurt) afirmă în esență dacă puteți trage o linie pentru a separa două poligoane, atunci ele nu se ciocnesc. Este atat de simplu.
În diagrama de mai sus, puteți observa cu ușurință coliziunile care apar în al doilea rând. Totuși, încercați să strângeți o linie între forme, veți eșua. Primul rând este exact opusul. Puteți desena cu ușurință o linie pentru a separa formele - și nu doar o singură linie, ci o mulțime de ele:
Bine, să nu exagerăm cu asta; Cred că înțelegeți. Argumentul cheie aici este că dacă puteți trage o astfel de linie, atunci trebuie să existe un spațiu care să separeze formele. Deci, cum să verificăm acest lucru?
Să presupunem acum că poligoanele la care ne referim sunt pătrate: Box1 în stânga și în dreapta Box2 pe dreapta. Este ușor de văzut că aceste pătrate sunt separate pe orizontală. O abordare simplă pentru a determina acest lucru în cod este să se calculeze distanța orizontală dintre cele două pătrate, apoi să se scadă jumătățile lățimii Box1 și Box2:
Accentsconagua
// Codul pseudo pentru a evalua separarea casetei 1 și a căsuței2 lungime var: Număr = caseta2.x - caseta1.x; var half_width_box1: Număr = box1.width * 0.5; var half_width_box2: Număr = caseta 2. lățime * 0.5; var gap_between_boxes: Număr = lungime - half_width_box1 - half_width_box2; dacă gap_between_boxes> 0) trace ("Este un decalaj mare între casete") altfel dacă (gap_between_boxes == 0) trace ("Cutii se ating reciproc") altceva (gap_between_boxes < 0) trace("Boxes are penetrating each other") Ce se întâmplă dacă cutiile nu sunt bine orientate?
Deși evaluarea decalajului rămâne aceeași, va trebui să ne gândim la o altă abordare pentru a calcula lungimea dintre centre și jumătăți de lățime - de data aceasta de-a lungul P axă. Acesta este locul unde matematica vectorului vine la îndemână. Vom proiecta vectorii A și B de-a lungul lui P pentru a obține jumătățile.
Să facem o revizuire matematică.
Vom începe prin recapitularea definiției produsului punct între două vectori A și B:
Putem defini produsul punct folosind doar componentele celor două vectori:
\ [
\ begin bmatrix A_x \\ A_y \ end bmatrix.
\ begin bmatrix B_x \\ B_y \ end bmatrix =
(A_x) (B_x) + (A_y) (B_y)
\]
Alternativ, putem înțelege produsul dot utilizând magnitudinea vectorilor și unghiul dintre ele:
\ [
\ begin bmatrix A_x \\ A_y \ end bmatrix.
\ begin bmatrix B_x \\ B_y \ end bmatrix =
A_ magnitudine * B_ magnitudine * cos (theta)
\]
Acum, să încercăm să ne dăm seama proeminență de vector A pe P.
Referindu-ne la diagrama de mai sus, stim ca valoarea proiectiei este \ (A_ magnitude * cos (theta) \) (unde teta este unghiul dintre A și P). Deși putem merge mai departe și putem calcula acest unghi pentru a obține proiecția, este dificil. Avem nevoie de o abordare mai directă:
\ [
A. P = A_ magnitudine * P_ magnitudine * cos (theta) \\
A. \ frac P P_ magnitudine = A_ magnitudine * cos (theta) \\
\ begin bmatrix A_x \\ A_y \ end bmatrix.
\ begin bmatrix P_x / P_ magnitudine \\ P_y / P_ magnitudine \ end bmatrix =
A_ magnitudine * cos (theta)
\]
Rețineți că \ (\ begin bmatrix P_x / P_ magnitude \\ P_y / P_ magnitude \ end bmatrix \) este de fapt vectorul unitar al lui P.
Acum, în loc să folosim partea dreaptă a ecuației, așa cum eram noi, putem opta pentru partea stângă și încă ajungem la același rezultat.
Înainte de a continua, aș dori să clarific convenția de numire folosită pentru a desemna cele patru colțuri ale ambelor cutii. Acest lucru se va reflecta mai târziu în cod:
Scenariul nostru este după cum urmează:
Să presupunem că ambele cutii sunt orientate la 45 ° față de axa orizontală. Trebuie să calculam următoarele lungimi pentru a determina diferența dintre cutii.
Luați notă de direcțiile săgeților. În timp ce proiecția lui A și C pe P va da o valoare pozitivă, proiecția lui B pe P va produce de fapt a negativ deoarece vectorii indică direcții opuse. Aceasta este inclusă în linia 98 a implementării AS3 de mai jos:
var punct10: Punct = box1.getDot (0); var dot11: Punct = box1.getDot (1); var dot20: Punct = box2.getDot (0); var dot24: Punct = box2.getDot (4); // Calcule efective var var: Vector2d = nou Vector2d (1, -1) .unitVector; var C: Vector2d = vector2d nou (dot20.x - dot10.x, dot20.y - dot10.y) var A: Vector2d = nou Vector2d (dot11.x - dot10.x, dot11.y - dot10.y) var B : Vector2d = Vector2d nou (dot24.x - dot20.x, dot24.y - dot20.y) var projC: Număr = C.dotProdus (axă) var projA: Număr = A.dotProdus (axă); var projB: Număr = Produsul B.dot (axă); varianta var: Numărul = projC - projA + projB; // projB este de așteptat să fie o valoare negativă dacă (gap> 0) t.text = "Există un decalaj între ambele casete" altceva dacă (gap> 0) t.text = "Cutii se ating unul pe altul" altceva t.text = "Sa întâmplat penetrarea."
Iată un demo folosind codul de mai sus. Faceți clic și trageți punctul de mijloc roșu din ambele casete și vedeți feedbackul interactiv.
Pentru sursa completă, verificați DemoSAT1.as în descărcarea sursei.
Putem merge cu implementarea de mai sus. Dar există câteva probleme - permiteți-mi să le subliniez:
Mai întâi, vectorii A și B sunt stabiliți. Deci când schimbi pozițiile Box1 și Box2, detectarea coliziunilor eșuează.
În al doilea rând, evaluăm doar decalajul de-a lungul unei axe, astfel încât situații precum cea de mai jos nu vor fi evaluate corect:
Deși demonstrația anterioară este defectuoasă, am învățat din ea conceptul de proiecție. Apoi, să ne îmbunătățim.
Deci, în primul rând, va trebui să obținem proiecțiile minime și maxime ale colțurilor (în special vectorii de la origine în colțurile cutiilor) pe P.
Diagrama de mai sus arată proiecția colțurilor minime și maxime pe P atunci când cutiile sunt orientate frumos de-a lungul lui P.
Dar dacă Box1 și Box2 nu sunt orientate în consecință?
Diagrama de mai sus prezintă casetele care nu sunt orientate în mod corespunzător de-a lungul lui P și proiecțiile lor min-max corespunzătoare. În această situație, va trebui să bifăm fiecare colț al fiecărei casete și să selectăm cele corecte, după caz.
Acum, când avem proiecțiile min-max, vom evalua dacă cutiile se ciocnesc între ele. Cum?
Observând diagrama de mai sus, putem vedea clar reprezentarea geometrică a proiecției box1.max și box2.min pe axa P.
După cum puteți vedea, atunci când este un decalaj între cele două cutii, box2.min-box1.max va fi mai mult decât zero - sau cu alte cuvinte, box2.min> box1.max. Când se schimbă poziția cutiilor, atunci box1.min> box2.max înseamnă că există un decalaj între ele.
Translatând această concluzie în cod, obținem:
// SAT: Pseudocod pentru a evalua separarea casetei1 si abox2 daca (box2.min> box1.max || box1.min> box2.max) trace ("coliziune de-a lungul axei P sa intamplat") altceva trace coliziune de-a lungul axei P ") Să ne uităm la un cod mai detaliat pentru a găsi acest lucru. Rețineți că codul AS3 aici nu este optimizat. Deși este lung și descriptiv, avantajul este că puteți vedea cum funcționează matematica din spatele ei.
Mai întâi de toate, trebuie să pregătim vectorii:
// prepararea vectorilor de la origine la punctele // deoarece originea este (0,0), putem lua coordonatele // pentru a forma vectori var ax: Vector2d = new Vector2d (1, -1) .unitVector; var vecs_box1: Vector.= Vector nou. ; var vecs_box2: Vector. = Vector nou. ; pentru (var i: int = 0; i < 5; i++) var corner_box1:Point = box1.getDot(i) var corner_box2:Point = box2.getDot(i) vecs_box1.push(new Vector2d(corner_box1.x, corner_box1.y)); vecs_box2.push(new Vector2d(corner_box2.x, corner_box2.y));
Apoi, obținem proiecția min-max Box1. Puteți vedea o abordare similară folosită Box2:
// setarea min max pentru box1 var min_proj_box1: Number = vecs_box1 [1] .dotProduct (axa); var min_dot_box1: int = 1; var max_proj_box1: Număr = vecs_box1 [1] .dotProdus (axă); var max_dot_box1: int = 1; pentru (var j: int = 2; < vecs_box1.length; j++) var curr_proj1:Number = vecs_box1[j].dotProduct(axis) //select the maximum projection on axis to corresponding box corners if (min_proj_box1 > (curr_proj1> max_proj_box1) max_proj_box1 = curr_proj1 max_dot_box1 = j // selectați proiecția minimă pe axă în colțurile corespunzătoare din cutie dacă (curr_proj1> max_proj_box1) max_proj_box1 = curr_proj1 max_dot_box1 = j
În cele din urmă, evaluăm dacă există o coliziune pe acea axă specifică, P:
var esteSeparat: Boolean = max_proj_box2 < min_proj_box1 || max_proj_box1 < min_proj_box2 if (isSeparated) t.text = "There's a gap between both boxes" else t.text = "No gap calculated."
Iată o demonstrație a implementării de mai sus:
Puteți să trageți fiecare cutie prin punctul său de mijloc și să o rotiți cu tastele R și T. Punctul roșu indică colțul maxim pentru o cutie, în timp ce galbenul indică minimul. Dacă o cutie este aliniată cu P, este posibil să observați că aceste puncte se aprind în timp ce trageți, deoarece cele două colțuri au aceleași caracteristici.
Verificați sursa completă în DemoSAT2.as în descărcarea sursei.
Dacă doriți să accelerați procesul, nu este nevoie să calculați pentru vectorul unitar al lui P. Prin urmare, puteți sări peste o serie de calcule teoretice scumpe ale lui Pythagoras care implică Math.sqrt ():
\ [începutul bmatrix A_x \\ A_y \ end bmatrix.
\ begin bmatrix P_x / P_ magnitudine \\ P_y / P_ magnitudine \ end bmatrix =
A_ magnitudine * cos (theta)
\]
Motivul este următorul (pentru schema de mai sus, consultați diagrama de mai sus pentru unele indicații vizuale cu privire la variabile):
/ * Fie: P_unit fi vectorul unității pentru P, P_mag să fie magnitudinea lui P, v1_mag să fie magnitudinea lui v1, v2_mag să fie v2 magnitudinea, theta_1 este unghiul dintre v1 și P, theta_2 este unghiul dintre v2 și P, apoi: box1.max < box2.min => v1.dotProduct (P_unit) < v2.dotProduct(P_unit) => v1_mag * cos (theta_1) < v2_mag*cos(theta_2) */
Acum, din punct de vedere matematic, semnul inegalității rămâne același, dacă ambele părți ale inegalității se înmulțesc cu același număr, A:
/ * Deci: A * v1_mag * cos (theta_1) < A*v2_mag*cos(theta_2) If A is P_mag, then: P_mag*v1_mag*cos(theta_1) < P_mag*v2_mag*cos(theta_2)… which is equivalent to saying: v1.dotProduct(P) < v2.dotProduct(P) */
Deci, fie că este un vector unic sau nu, nu contează - rezultatul este același.
Rețineți că această abordare este utilă dacă verificați numai suprapunerea. Pentru a găsi lungimea exactă a penetrării Box1 și Box2 (care pentru majoritatea jocurilor probabil că va trebui să), trebuie să calculați vectorul unității lui P.
Așa că am rezolvat problema pentru o axă, dar asta nu este sfârșitul. Trebuie încă să abordăm alte axe - dar care?
Analiza pentru cutii este destul de simplă: comparați două axe P și Q. Pentru a confirma o coliziune, suprapunerea pe toate axele trebuie să fie adevărate - dacă există o axă fără o suprapunere, putem concluziona că nu există o coliziune.
Ce se întâmplă dacă cutiile sunt orientate diferit?
Faceți clic pe butonul verde pentru a reveni la o altă pagină. Deci, din axele P, Q, R și S, există o singură axă care nu prezintă suprapuneri între cutii, iar concluzia noastră este că nu există o coliziune între cutii.
Dar întrebarea este, cum decidem ce axe să verificăm pentru suprapunere? Păi, luăm normalele a poligoanelor.
Într-o formă generalizată, cu două cutii, va trebui să verificăm de-a lungul a opt axe: n0, n1, n2 și n3 pentru fiecare dintre ele Box1 și Box2. Cu toate acestea, putem observa că următoarele se află pe aceleași axe:
n0 și n2 de Box1 n1 și n3 de Box1 n0 și n2 de Box2 n1 și n3 de Box2 Deci nu trebuie să trecem prin toate cele opt; doar patru vor face. Si daca Box1 și Box2 împărtășim aceeași orientare, putem reduce în continuare pentru a evalua numai două axe.
Și pentru alte poligoane?
Din păcate, pentru triunghiul și pentagonul de mai sus nu există o astfel de comandă rapidă, așa că va trebui să facem verificări de-a lungul tuturor normalelor.
Fiecare suprafață are două normale:
Diagrama de mai sus arată normalul stâng și drept al lui P. Observați componentele comutate ale vectorului și semnul pentru fiecare.
Pentru implementarea mea, folosesc o convenție în sensul acelor de ceasornic, așa că folosesc stânga normalele. Mai jos este un extras din SimpleSquare.as demonstrând acest lucru.
funcția publică getNorm (): Vector.var normale: Vector. = Vector nou. pentru (var i: int = 1; i < dots.length-1; i++) var currentNormal:Vector2d = new Vector2d( dots[i + 1].x - dots[i].x, dots[i + 1].y - dots[i].y ).normL //left normals normals.push(currentNormal); normals.push( new Vector2d( dots[1].x - dots[dots.length-1].x, dots[1].y - dots[dots.length-1].y ).normL ) return normals;
Sunt sigur că puteți găsi o modalitate de a optimiza codul următor. Dar doar pentru ca noi sa avem o idee clara despre ceea ce se intampla, am scris totul in intregime:
// rezultatele lui P, Q var rezultat_P1: Object = getMinMax (vecs_box1, normals_box1 [1]); var rezultat_P2: Object = getMinMax (vecs_box2, normals_box1 [1]); var rezultat_Q1: obiect = getMinMax (vecs_box1, normals_box1 [0]); var rezultat_Q2: obiect = getMinMax (vecs_box2, normals_box1 [0]); // rezultatele lui R, S var rezult_R1: Object = getMinMax (vecs_box1, normals_box2 [1]); var rezult_R2: obiect = getMinMax (vecs_box2, normals_box2 [1]); var rezultat_S1: obiect = getMinMax (vecs_box1, normals_box2 [0]); var rezultă_S2: obiect = getMinMax (vecs_box2, normals_box2 [0]); var separate_P: Boolean = result_P1.max_proj < result_P2.min_proj || result_P2.max_proj < result_P1.min_proj var separate_Q:Boolean = result_Q1.max_proj < result_Q2.min_proj || result_Q2.max_proj < result_Q1.min_proj var separate_R:Boolean = result_R1.max_proj < result_R2.min_proj || result_R2.max_proj < result_R1.min_proj var separate_S:Boolean = result_S1.max_proj < result_S2.min_proj || result_S2.max_proj < result_S1.min_proj //var isSeparated:Boolean = separate_p || separate_Q || separate_R || separate_S if (isSeparated) t.text = "Separated boxes" else t.text = "Collided boxes."
Veți vedea că unele variabile nu sunt neapărat calculate pentru a ajunge la rezultat. Dacă vreunul dintre ele separate_P, separate_Q, separate_R și separate_S este adevărat, atunci sunt separați și nu mai este nevoie să continuați.
Aceasta înseamnă că putem salva o sumă corectă de evaluare, doar verificând fiecare dintre acele Booleani după ce au fost calculate. Va fi nevoie să rescrieți codul, dar cred că puteți să vă deplasați prin el (sau să verificați blocul comentat din DemoSAT3.as).
Iată o demonstrație a implementării de mai sus. Faceți clic și trageți cutiile prin intermediul punctelor lor medii și folosiți tastele R și T pentru a roti casetele:
Când acest algoritm este rulat, acesta verifică prin axele normale pentru suprapuneri. Am două observații aici pentru a sublinia:
Iată un alt exemplu de fragment de cod pentru a verifica o coliziune între un hexagon și un triunghi:
funcția privată refresh (): void // pregătește normalele var normals_hex: Vector.= hex.getNorm (); var normals_tri: Vector. = tri.getNorm (); var vecs_hex: Vector. = pregătiVector (hex); var vecs_tri: Vector. = pregătiVector (tri); var esteSeparat: Boolean = false; // utilizați normalele hexagonului pentru a evalua pentru (var i: int = 0; i < normals_hex.length; i++) var result_box1:Object = getMinMax(vecs_hex, normals_hex[i]); var result_box2:Object = getMinMax(vecs_tri, normals_hex[i]); isSeparated = result_box1.max_proj < result_box2.min_proj || result_box2.max_proj < result_box1.min_proj if (isSeparated) break; //use triangle's normals to evaluate if (!isSeparated) for (var j:int = 1; j < normals_tri.length; j++) var result_P1:Object = getMinMax(vecs_hex, normals_tri[j]); var result_P2:Object = getMinMax(vecs_tri, normals_tri[j]); isSeparated = result_P1.max_proj < result_P2.min_proj || result_P2.max_proj < result_P1.min_proj if (isSeparated) break; if (isSeparated) t.text = "Separated boxes" else t.text = "Collided boxes."
Pentru codul complet, verificați DemoSAT4.as în descărcarea sursei.
Demo-ul este mai jos. Interacțiunea este aceeași ca în demo-urile anterioare: trageți prin punctele medii și folosiți R și T pentru a roti.
Coliziunea cu un cerc poate fi una dintre cele mai simple. Deoarece proiecția sa este aceeași în toate direcțiile (este pur și simplu raza cercului), putem face următoarele:
funcția privată refresh (): void // pregăti vectorii var v: Vector2d; var actual_box_corner: punct; var center_box: Punct = box1.getDot (0); var max: Număr = Număr.NEGATIVE_INFINITY; var box2circle: Vector2d = nou Vector2d (c.x - center_box.x, c.y - center_box.y) var box2circle_normalised: Vector2d = box2circle.unitVector // obțineți maximul pentru (var i: int = 1; < 5; i++) current_box_corner = box1.getDot(i) v = new Vector2d( current_box_corner.x - center_box.x , current_box_corner.y - center_box.y); var current_proj:Number = v.dotProduct(box2circle_normalised) if (max < current_proj) max = current_proj; if (box2circle.magnitude - max - c.radius > 0 && box2circle.magnitude> 0) t.text = "Nici o coliziune" altfel t.text = "Coliziune"
Verificați sursa completă în DemoSAT5.as. Glisați fie cercul, fie caseta pentru a le vedea că se ciocnesc.
Ei bine, asta e pentru moment. Vă mulțumim pentru lectură și nu vă lăsați feedback cu un comentariu sau o întrebare. Vedeți tutorialul următor!
