Share
Separasjonsaksestudien brukes ofte til å sjekke for kollisjoner mellom to enkle polygoner, eller mellom en polygon og en sirkel. Som med alle algoritmer har den sine styrker og svakheter. I denne opplæringen vil vi gå over matematikken bak teorien, og vise hvordan den kan brukes i spillutvikling med noen eksempler og demoer.
Merk: Selv om demoene og kildekoden til denne opplæringen bruker Flash og AS3, bør du kunne bruke de samme teknikkene og konseptene i nesten hvilket som helst spillutviklingsmiljø.
Separasjonsaksetormen (SAT for kort) angir i hovedsak om du kan tegne en linje for å skille to polygoner, så kolliderer de ikke. Det er så enkelt.
I diagrammet ovenfor kan du enkelt se kollisjoner som forekommer i andre rad. Men du prøver å klemme en linje mellom figurene, du vil mislykkes. Den første raden er akkurat det motsatte. Du kan enkelt tegne en linje for å skille figurene - og ikke bare en linje, men mange av dem:
Ok, la oss ikke overdrive dette; Jeg tror du får poenget. Hovedargumentet her er at hvis du kan tegne en slik linje, må det være et gap som skiller formene. Så hvordan sjekker vi på dette?
La oss antar for tiden at polygonene vi refererer til, er firkanter: box1 til venstre og BOX2 til høyre. Det er lett å se at disse rutene er horisontalt skilt. En enkel tilnærming til å bestemme dette i kode er å beregne den horisontale avstanden mellom de to rutene, deretter trekke halvbreddene av box1 og BOX2:
Accentsconagua
// Pseudokode for å evaluere separasjonen av boks1 og boks2 varlengde: Nummer = boks2.x - boks1.x; var half_width_box1: Number = box1.width * 0.5; var half_width_box2: Number = box2.width * 0,5; var gap_between_boxes: Number = lengde - half_width_box1 - half_width_box2; hvis (gap_between_boxes> 0) trace ("Det er et stort gap mellom bokser") ellers hvis (gap_between_boxes == 0) spore ("bokser berører hverandre") ellers hvis (gap_between_boxes < 0) trace("Boxes are penetrating each other") Hva om boksene ikke er orientert pent?
Selv om evalueringen av gapet forblir den samme, må vi tenke på en annen tilnærming til å beregne lengden mellom sentre og halvbredder - denne gangen langs P akser. Dette er hvor vektormatematikk er nyttig. Vi vil projisere vektorer A og B langs P for å få halvbredder.
La oss gjøre noen matte revisjon.
Vi starter med å gjenopprette definisjonen av punktproduktet mellom to vektorer EN og B:
Vi kan definere prikkproduktet ved å bruke bare komponentene i de to vektorene:
\ [
\ begin bmatrix A_x \\ A_y \ end bmatrix.
\ begin bmatrix B_x \\ B_y \ end bmatrix =
(A_x) (B_x) + (A_y) (B_y)
\]
Alternativt kan vi forstå punktproduktet ved hjelp av vektorens størrelser og vinkelen mellom dem:
\ [
\ begin bmatrix A_x \\ A_y \ end bmatrix.
\ begin bmatrix B_x \\ B_y \ end bmatrix =
A_ størrelse * B_ størrelse * cos (theta)
\]
La oss nå prøve å finne ut det projeksjon av vektor EN videre til P.
Med henvisning til diagrammet ovenfor, vet vi at projeksjonsverdien er \ (A_ magnitude * cos (theta) \) (hvor theta er vinkelen mellom A og P). Selv om vi kan gå videre og beregne denne vinkelen for å oppnå projeksjonen, er det vanskelig. Vi trenger en mer direkte tilnærming:
\ [
A. P = A_ magnitude * P_ magnitude * cos (theta) \\
A. \ frac p P_ størrelses = a_ størrelse * cos (theta) \\
\ begin bmatrix A_x \\ A_y \ end bmatrix.
\ begin bmatrix P_x / P_ magnitude \\ P_y / P_ magnitude \ end bmatrix =
A_ størrelse * cos (theta)
\]
Merk at \ (\ begin bmatrix P_x / P_ magnitude \\ P_y / P_ magnitude \ end bmatrix \) er faktisk enhetsvektoren til P.
Nå, i stedet for å bruke høyre side av ligningen, som vi var, kan vi velge venstre side og fremdeles komme til samme resultat.
Før vi fortsetter, vil jeg gjerne avklare navngivningskonvensjonen som brukes til å betegne de fire hjørnene i begge boksene. Dette vil gjenspeiles i koden senere:
Vårt scenario er som følger:
La oss si at begge boksene er orientert 45 ° fra den horisontale akse. Vi må beregne følgende lengder for å bestemme gapet mellom boksene.
Vær spesielt oppmerksom på pilens anvisninger. Mens projeksjon av A og C på P vil gi en positiv verdi, vil projeksjon av B på P faktisk produsere a negativ verdi som vektorer peker i motsatt retning. Dette er dekket i linje 98 i AS3 implementeringen nedenfor:
var dot10: Point = box1.getDot (0); var dot11: Point = box1.getDot (1); var dot20: Punkt = box2.getDot (0); var dot24: Point = box2.getDot (4); // Faktiske beregninger var akse: Vector2d = ny Vector2d (1, -1) .unitVector; var C: Vector2d = ny Vector2d (dot20.x - dot10.x, dot20.y - dot10.y) var A: Vector2d = ny Vector2d (dot11.x - dot10.x, dot11.y - dot10.y) var B : Vector2d = ny Vector2d (dot24.x - dot20.x, dot24.y - dot20.y) var projC: Nummer = C.dotProdukt (akse) var projA: Nummer = A.dotProdukt (akse); var projB: Nummer = B.dotProdukt (akse); var gap: Number = projC - projA + projB; // projB forventes å være en negativ verdi hvis (gap> 0) t.text = "Det er et mellomrom mellom begge boksene" ellers hvis (gap> 0) t.text = "Bokser berører hverandre" ellers t.text = "Inntrenging hadde skjedd."
Her er en demo ved hjelp av koden ovenfor. Klikk og dra den røde midtpunkten i begge boksene og se den interaktive tilbakemeldingen.
For hele kilden, sjekk ut DemoSAT1.as i kilden nedlasting.
Vel, vi kan gå med implementeringen ovenfor. Men det er noen problemer - la meg peke på dem:
Først er vektorer A og B løst. Så når du bytter posisjonene til box1 og BOX2, kollisjonsdeteksjonen mislykkes.
For det andre vurderer vi bare gapet langs en akse, slik at situasjoner som den nedenfor ikke vil bli vurdert riktig:
Selv om forrige demo er feil, lærte vi fra det begrepet projeksjon. Neste, la oss forbedre det.
Så først og fremst må vi få minimum og maksimale fremskrivninger av hjørner (spesifikt vektorene fra opprinnelsen til boksens hjørner) på P.
Diagrammet ovenfor viser projeksjonen av minimum og maksimale hjørner på P når boksene er orientert pent langs P.
Men hva om box1 og BOX2 er ikke orientert tilsvarende?
Diagrammet ovenfor viser bokser som ikke er pent orientert langs P, og deres tilsvarende min-maksimale fremskrivninger. I denne situasjonen må vi løse gjennom hvert hjørne av hver boks og velge de riktige som passer.
Nå som vi har min-maks-projeksjonene, vurderer vi om boksene kolliderer med hverandre. Hvordan?
Ved å observere diagrammet ovenfor kan vi tydelig se den geometriske representasjonen for projeksjon av box1.max og box2.min på aksen P.
Som du kan se, når det er et mellomrom mellom de to boksene, box2.min-box1.max vil være mer enn null - eller med andre ord, box2.min> box1.max. Når plasseringen av boksene byttes, da box1.min> box2.max innebærer at det er et gap mellom dem.
Oversetter denne konklusjonen til kode får vi:
// SAT: Pseudocode for å evaluere separasjonen av boks1 og boks2 hvis (box2.min> box1.max || box1.min> box2.max) trace ("kollisjon langs akse P skjedde") annet spor kollisjon langs aksen P ") La oss se på en mer detaljert kode for å finne ut dette. Merk at AS3-koden her ikke er optimalisert. Selv om det er lang og beskrivende, er fordelen at du kan se hvordan matematikken bak den virker.
Først av alt må vi forberede vektorer:
// forbereder vektorene fra opprinnelse til poeng // siden opprinnelsen er (0,0), kan vi enkelt ta koordinatene // for å danne vektorer var akse: Vector2d = ny Vector2d (1, -1) .unitVector; var vecs_box1: Vector.= Ny Vector. ; var vecs_box2: Vector. = Ny Vector. ; for (var jeg: 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));
Deretter får vi min-maks projeksjon på box1. Du kan se en lignende tilnærming som brukes på BOX2:
// innstilling min maks for boks1 var min_proj_box1: Nummer = vecs_box1 [1] .dotProdukt (akse); var min_dot_box1: int = 1; var max_proj_box1: Nummer = vecs_box1 [1] .dotProdukt (akse); var max_dot_box1: int = 1; for (var j: int = 2; j < 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) min_proj_box1 = curr_proj1 min_dot_box1 = j // velg minimum projeksjon på akse til tilhørende boks hjørner hvis (curr_proj1> max_proj_box1) max_proj_box1 = curr_proj1 max_dot_box1 = j
Til slutt vurderer vi om det er en kollisjon på den spesifikke akse, P:
var erSeparert: 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."
Her er en demonstrasjon av implementeringen ovenfor:
Du kan dra enten en boks rundt via midtpunktet, og roter den med R og T-tastene. Den røde prikken angir maksimalt hjørne for en boks, mens gul angir minimum. Hvis en boks er justert med P, kan du oppdage at disse punktene flimrer mens du drar, da de to hjørnene deler de samme egenskapene.
Sjekk ut hele kilden i DemoSAT2.as i kilden nedlasting.
Hvis du ønsker å fremskynde prosessen, er det ikke nødvendig å beregne for enhedsvektoren til P. Du kan derfor hoppe over ganske mange dyre Pythagoras teoremberegninger som involverer Math.sqrt ():
\ [\ begin bmatrix A_x \\ A_y \ end bmatrix.
\ begin bmatrix P_x / P_ magnitude \\ P_y / P_ magnitude \ end bmatrix =
A_ størrelse * cos (theta)
\]
Begrunnelsen er som følger (se diagram over for noen visuell veiledning om variabler):
/ * La: P_unit være enhetvektoren for P, P_mag være Ps størrelse, v1_mag være v1s størrelse, v2_mag være v2s størrelse, theta_1 være vinkelen mellom v1 og P, theta_2 være vinkelen mellom v2 og P, deretter: box1.max < box2.min => v1.dotProduct (P_unit) < v2.dotProduct(P_unit) => v1_mag * cos (theta_1) < v2_mag*cos(theta_2) */
Nå er matematisk signaturet for ulikhet det samme hvis begge sidene av ulikheten blir multiplisert med samme tall, A:
/ * Så: 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) */
Så om det er en enhetsvektor eller ikke, betyr det egentlig ingen rolle - resultatet er det samme.
Husk at denne tilnærmingen er nyttig hvis du bare ser etter overlapping. For å finne den nøyaktige penetrasjonslengden på box1 og BOX2 (som for de fleste spillene du sannsynligvis trenger), må du fortsatt beregne enhetens vektor av P.
Så løste vi problemet for en akse, men det er ikke slutten på det. Vi trenger fortsatt å takle andre akser - men hvilken?
Analysen for bokser er ganske enkel: vi sammenligner to akse P og Q. For å bekrefte en kollisjon, overlapper på alle akser må være sant - hvis det er noen akse uten en overlapping, kan vi konkludere med at det ikke er kollisjon.
Hva om boksene er orientert annerledes?
Klikk på den grønne knappen for å gå til en annen side. Så av P-, Q-, R- og S-aksene er det bare en akse som ikke viser overlapp mellom bokser, og vår konklusjon er at det ikke er kollisjon mellom boksene.
Men spørsmålet er hvordan bestemmer vi hvilke akser som skal kontrolleres for overlapping? Vel, vi tar normaler av polygonene.
I en generalisert form, med to bokser, må vi sjekke langs åtte akser: n0, n1, n2 og n3 for hver av box1 og BOX2. Imidlertid kan vi se at følgende ligger på samme akser:
n0 og n2 av box1 n1 og n3 av box1 n0 og n2 av BOX2 n1 og n3 av BOX2 Så vi trenger ikke å gå gjennom alle åtte; bare fire vil gjøre. Og hvis box1 og BOX2 Del samme retning, vi kan ytterligere redusere for å bare vurdere to akser.
Hva med andre polygoner?
Dessverre, for trekant og femkant over det er ingen slik snarvei, så vi må løpe sjekker langs alle normaler.
Hver overflate har to normaler:
Diagrammet ovenfor viser venstre og høyre normal av P. Merk de vekslede komponentene til vektoren og tegnet for hver.
For implementeringen min bruker jeg en klokka konvensjon, så jeg bruker venstre normaler. Nedenfor er et utdrag av SimpleSquare.as demonstrerer dette.
offentlig funksjon getNorm (): Vector.var normals: Vector. = Ny Vector. for (var jeg: 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;
Jeg er sikker på at du kan finne en måte å optimalisere følgende kode på. Men bare slik at vi alle får en klar ide om hva som skjer, har jeg skrevet alt ut i sin helhet:
// resultater av P, Q var result_P1: Objekt = getMinMax (vecs_box1, normals_box1 [1]); var result_P2: Objekt = getMinMax (vecs_box2, normals_box1 [1]); var result_Q1: Objekt = getMinMax (vecs_box1, normals_box1 [0]); var result_Q2: Objekt = getMinMax (vecs_box2, normals_box1 [0]); // resultater av R, S var result_R1: Object = getMinMax (vecs_box1, normals_box2 [1]); var result_R2: Objekt = getMinMax (vecs_box2, normals_box2 [1]); var result_S1: Object = getMinMax (vecs_box1, normals_box2 [0]); var result_S2: Object = 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."
Du ser at noen av variablene ikke nødvendigvis beregnes for å nå resultatet. Hvis noen av separate_P, separate_Q, separate_R og separate_S er sant, da er de skilt og det er ikke nødvendig å fortsette.
Dette betyr at vi kan lagre en hel del evaluering, bare ved å sjekke hver av disse booleskerne etter at de har blitt beregnet. Det ville kreve omskriving av koden, men jeg tror du kan jobbe deg gjennom det (eller sjekk ut kommentert blokk i DemoSAT3.as).
Her er en demonstrasjon av implementeringen ovenfor. Klikk og dra boksene via de midterste punktene, og bruk R og T-tastene for å rotere boksene:
Når denne algoritmen kjøres, sjekker den gjennom de normale aksene for overlappinger. Jeg har to observasjoner her for å påpeke:
Her er en annen prøvekodebit for å sjekke for en kollisjon mellom en sekskant og en trekant:
privat funksjon oppdatering (): void // forberede normalene var normals_hex: Vector.= hex.getNorm (); var normals_tri: Vector. = tri.getNorm (); var vecs_hex: Vector. = prepareVector (hex); var vecs_tri: Vector. = prepareVector (tri); var erSeparert: Boolsk = false; // bruk sekskantens normaler for å evaluere for (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."
For hele koden, sjekk ut DemoSAT4.as i kilden nedlasting.
Demoen er under. Samspillet er det samme som i tidligere demoer: Dra gjennom midtpunktene, og bruk R og T for å rotere.
Kollisjon med en sirkel kan være en av de enkleste. Fordi projeksjonen er den samme i alle retninger (det er bare sirkelens radius), kan vi bare gjøre følgende:
privat funksjon oppdatering (): void // lag vektorer var v: Vector2d; var current_box_corner: Point; var center_box: Point = box1.getDot (0); var max: Number = Number.NEGATIVE_INFINITY; var box2circle: Vector2d = ny Vector2d (c.x - center_box.x, c.y - center_box.y) var box2circle_normalised: Vector2d = box2circle.unitVector // få maksimum for (var i: int = 1; i < 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 = "Ingen kollisjon" annet t.text = "Kollisjon"
Sjekk ut hele kilden i DemoSAT5.as. Dra enten sirkelen eller boksen for å se at de kolliderer.
Vel, det er det for nå. Takk for at du leser og la igjen tilbakemelding med en kommentar eller et spørsmål. Se deg neste opplæring!
