Share
De stelling van de scheidende as wordt vaak gebruikt om te controleren op botsingen tussen twee eenvoudige veelhoeken, of tussen een veelhoek en een cirkel. Zoals met alle algoritmen, heeft het zijn sterke en zwakke punten. In deze zelfstudie bespreken we de wiskunde achter de stelling en laten we zien hoe deze kan worden gebruikt in de ontwikkeling van games met enkele voorbeeldcodes en demo's..
Notitie: Hoewel de demo's en broncode van deze tutorial Flash en AS3 gebruiken, zou je in bijna elke game-ontwikkelomgeving dezelfde technieken en concepten moeten kunnen gebruiken.
De Scheiding As Stelling (zat afgekort) verklaart in essentie als je in staat bent om een lijn te tekenen om twee polygonen te scheiden, dan botsen ze niet. Het is zo simpel.
In het bovenstaande diagram ziet u eenvoudig botsingen die zich voordoen op de tweede rij. Hoe je ook probeert een lijn tussen de vormen in te persen, je faalt. De eerste rij is precies het tegenovergestelde. Je kunt eenvoudig een lijn tekenen om de vormen te scheiden - en niet slechts één regel, maar veel:
Oké, laten we dit niet overdrijven; Ik denk dat je het begrijpt. Het belangrijkste argument hier is dat als je een dergelijke lijn kunt tekenen, er een opening moet zijn die de vormen scheidt. Dus hoe kunnen we dit controleren?
Laten we nu aannemen dat de polygonen waar we naar verwijzen vierkanten zijn: box1 aan de linkerkant en box2 aan de rechterkant. Het is gemakkelijk om te zien dat deze vierkanten horizontaal gescheiden zijn. Een eenvoudige benadering om dit in code te bepalen, is om de horizontale afstand tussen de twee vierkanten te berekenen en vervolgens de halve breedten van box1 en box2:
Accentsconagua
// Pseudo-code om de scheiding van box1 en box2 var-lengte te evalueren: Number = box2.x - box1.x; var half_width_box1: Number = box1.width * 0.5; var half_width_box2: Number = box2.width * 0.5; var gap_between_boxes: Number = length - half_width_box1 - half_width_box2; if (gap_between_boxes> 0) trace ("Het is een grote opening tussen de vakken") anders als (gap_between_boxes == 0) trace ("Boxen raken elkaar") else if (gap_between_boxes < 0) trace("Boxes are penetrating each other") Wat als de dozen niet goed zijn georiënteerd?
Hoewel de evaluatie van de kloof hetzelfde blijft, moeten we een andere benadering bedenken om de lengte tussen de middelpunten en de halve breedten te berekenen - dit keer langs de P as. Dit is waar vector wiskunde van pas komt. We projecteren vectoren A en B langs P om de halve breedte te krijgen.
Laten we wat revisie doen.
We beginnen met het samenvatten van de definitie van het puntproduct tussen twee vectoren EEN en B:
We kunnen het puntproduct definiëren met alleen de componenten van de twee vectoren:
\ [
\ begin bmatrix A_x \\ A_y \ end bmatrix.
\ begin bmatrix B_x \\ B_y \ end bmatrix =
(A_x) (B_x) + (à_ÿ) (B_y)
\]
Als alternatief kunnen we het puntproduct begrijpen met behulp van de magnitudes van de vectoren en de hoek ertussen:
\ [
\ begin bmatrix A_x \\ A_y \ end bmatrix.
\ begin bmatrix B_x \\ B_y \ end bmatrix =
A_ magnitude * B_ magnitude * cos (theta)
\]
Laten we nu eens kijken naar de projectie van vector EEN naar P.
Onder verwijzing naar het bovenstaande diagram, weten we dat de projectiewaarde \ (A_ magnitude * cos (theta) \) is (waarbij theta is de hoek tussen A en P). Hoewel we kunnen doorgaan en deze hoek berekenen om de projectie te verkrijgen, is het lastig. We hebben een directere aanpak nodig:
\ [
A. P = A_ magnitude * P_ magnitude * cos (theta) \\
A. \ frac P P_ magnitude = A_ magnitude * cos (theta) \\
\ begin bmatrix A_x \\ A_y \ end bmatrix.
\ begin bmatrix P_x / P_ magnitude \\ P_y / P_ magnitude \ end bmatrix =
A_ magnitude * cos (theta)
\]
Merk op dat \ (\ begin bmatrix P_x / P_ magnitude \\ P_y / P_ magnitude \ end bmatrix \) eigenlijk de eenheidsvector van P is.
Nu, in plaats van de rechterkant van de vergelijking te gebruiken, zoals we waren, kunnen we kiezen voor de linkerkant en toch hetzelfde resultaat bereiken.
Voordat we verder gaan, wil ik graag de naamgeving verduidelijken die wordt gebruikt om de vier hoeken van beide vakken aan te geven. Dit zal later in de code worden weergegeven:
Ons scenario is als volgt:
Laten we zeggen dat beide vakken 45 ° ten opzichte van de horizontale as zijn gericht. We moeten de volgende lengtes berekenen om de afstand tussen de vakken te bepalen.
Let vooral op de richtingen van de pijlen. Terwijl projectie van A en C op P een positieve waarde zal geven, zal projectie van B op P feitelijk een negatief waarde als de vectoren in tegenovergestelde richtingen wijzen. Dit wordt behandeld in regel 98 van de AS3-implementatie hieronder:
var dot10: Point = box1.getDot (0); var dot11: Point = box1.getDot (1); var dot20: Point = box2.getDot (0); var dot24: Point = box2.getDot (4); // Werkelijke berekeningen var-as: Vector2d = nieuwe Vector2d (1, -1) .unitVector; var C: Vector2d = new Vector2d (dot20.x - dot10.x, dot20.y - dot10.y) var A: Vector2d = new Vector2d (dot11.x - dot10.x, dot11.y - dot10.y) var B : Vector2d = new Vector2d (dot24.x - dot20.x, dot24.y - dot20.y) var projC: Number = C.dotProduct (axis) var projA: Number = A.dotProduct (axis); var projB: Number = B.dotProduct (axis); var gap: Number = projC - projA + projB; // projB is naar verwachting een negatieve waarde als (gap> 0) t.text = "Er is een opening tussen beide vakken" else if (gap> 0) t.text = "Boxes raken elkaar" else t.text = "Penetratie was gebeurd."
Hier is een demo met de bovenstaande code. Klik en sleep de rode middelste punt van beide vakken en bekijk de interactieve feedback.
Kijk voor de volledige bron DemoSAT1.as in de brondownload.
Welnu, we kunnen gaan met de bovenstaande implementatie. Maar er zijn een paar problemen - laat me ze wijzen:
Eerst worden de vectoren A en B vastgelegd. Dus als je de posities van ruilt box1 en box2, de botsing detectie mislukt.
Ten tweede evalueren we alleen de afstand langs één as, zodat situaties zoals die hieronder niet correct worden geëvalueerd:
Hoewel de vorige demo niet klopte, leerden we ervan het concept van projectie. Laten we het vervolgens verbeteren.
Dus eerst en vooral moeten we de minimale en maximale projecties van hoeken (met name de vectoren van de oorsprong tot de hoeken van de vakken) op P.
Het diagram hierboven toont de projectie van de minimale en maximale hoeken op P wanneer de dozen mooi langs P zijn gericht.
Maar wat als box1 en box2 zijn niet overeenkomstig georiënteerd?
Het diagram hierboven toont vakken die niet netjes langs P zijn georiënteerd, en hun bijbehorende min-max projecties. In deze situatie moeten we elke hoek van elk vak doorlopen en de juiste selecteren.
Nu we de min-max projecties hebben, zullen we evalueren of de dozen met elkaar botsen. Hoe?
Door het bovenstaande diagram te observeren, kunnen we duidelijk de geometrische weergave voor de projectie van box1.max en box2.min op as P.
Zoals je kunt zien, wanneer het een gat is tussen de twee vakken, box2.min-box1.max zal meer zijn dan nul - of met andere woorden, box2.min> box1.max. Wanneer de positie van de vakken is verwisseld, dan box1.min> box2.max impliceert dat er een kloof tussen hen is.
Vertaling van deze conclusie in code, we krijgen:
// SAT: Pseudocode om de scheiding van box1 en box2 te evalueren als (box2.min> box1.max || box1.min> box2.max) trace ("botsing langs as P is gebeurd") else trace ("no botsing langs de as P ") Laten we naar een meer gedetailleerde code kijken om dit uit te zoeken. Merk op dat de AS3-code hier niet is geoptimaliseerd. Hoewel het lang en beschrijvend is, is het een voordeel dat u kunt zien hoe de wiskunde erachter werkt.
Allereerst moeten we de vectoren voorbereiden:
// de vectoren voorbereiden van oorsprong naar punten // omdat oorsprong is (0,0), kunnen we gemakkelijk de coördinaten nemen // vormen vectoren var-as: Vector2d = nieuwe Vector2d (1, -1) .unitVector; var vecs_box1: Vector.= nieuwe Vector. ; var vecs_box2: Vector. = nieuwe Vector. ; for (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));
Vervolgens krijgen we de min-max projectie op box1. Je kunt een vergelijkbare aanpak zien gebruikt box2:
// setting min max for box1 var min_proj_box1: Number = vecs_box1 [1] .dotProduct (axis); var min_dot_box1: int = 1; var max_proj_box1: Number = vecs_box1 [1] .dotProduct (axis); var max_dot_box1: int = 1; voor (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 // selecteer de minimale projectie op de as in corresponderende vakhoeken if (curr_proj1> max_proj_box1) max_proj_box1 = curr_proj1 max_dot_box1 = j
Ten slotte evalueren we of er een botsing is op die specifieke as, P:
var isSeparated: 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."
Hier is een demo van de bovenstaande implementatie:
U kunt beide vakken rond het middelpunt slepen en deze roteren met de R- en T-toetsen. De rode stip geeft de maximale hoek voor een vak aan, terwijl geel het minimum aangeeft. Als een vak is uitgelijnd met P, kan het zijn dat deze punten flikkeren terwijl u sleept, omdat deze twee hoeken dezelfde kenmerken hebben.
Bekijk de volledige bron in DemoSAT2.as in de brondownload.
Als je het proces wilt versnellen, hoef je niet te berekenen voor de eenheidsvector van P. Je kunt dus nogal wat dure Pythagoras-theoretische berekeningen overslaan die betrekking hebben op Math.sqrt ():
\ [\ begin bmatrix A_x \\ A_y \ end bmatrix.
\ begin bmatrix P_x / P_ magnitude \\ P_y / P_ magnitude \ end bmatrix =
A_ magnitude * cos (theta)
\]
De redenering is als volgt (zie diagram hierboven voor enige visuele richtlijnen over variabelen):
/ * Let: P_unit is de eenheidsvector voor P, P_mag is P's magnitude, v1_mag is de grootte van v1, v2_mag is de grootte van v2, theta_1 is de hoek tussen v1 en P, theta_2 is de hoek tussen v2 en P, Then: box1.max < box2.min => v1.dotProduct (P_unit) < v2.dotProduct(P_unit) => v1_mag * cos (theta_1) < v2_mag*cos(theta_2) */
Wiskundig gezien blijft het teken van ongelijkheid hetzelfde als beide zijden van de ongelijkheid met hetzelfde aantal worden vermenigvuldigd, A:
/ * So: 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) */
Dus of het nu om een eenheidsvector gaat of niet, maakt eigenlijk niets uit - het resultaat is hetzelfde.
Houd er rekening mee dat deze benadering nuttig is als u alleen op overlapping controleert. Om de exacte penetratiallengte te vinden van box1 en box2 (wat voor de meeste spellen waarschijnlijk wel nodig is), moet je nog steeds de eenheidsvector van P berekenen.
Dus we hebben het probleem voor één as opgelost, maar dat is nog niet het einde. We moeten nog andere assen aanpakken - maar welke?
De analyse voor vakken is vrij eenvoudig: we vergelijken twee assen P en Q. Om een botsing te bevestigen, overlappende allemaal assen moeten waar zijn - als er een as is zonder overlapping, kunnen we concluderen dat er geen botsing is.
Wat als de dozen anders georiënteerd zijn??
Klik op de groene knop om naar een andere pagina te gaan. Dus van de P-, Q-, R- en S-assen is er slechts één as die geen overlapping toont tussen vakken, en onze conclusie is dat er geen botsing is tussen de vakken.
Maar de vraag is, hoe bepalen we welke assen moeten worden gecontroleerd op overlapping? Wel, we nemen de normalen van de polygonen.
In een gegeneraliseerde vorm, met twee vakken, moeten we acht assen controleren: n0, n1, n2 en n3 voor elk van box1 en box2. We kunnen echter zien dat het volgende op dezelfde assen ligt:
n0 en n2 van box1 n1 en n3 van box1 n0 en n2 van box2 n1 en n3 van box2 We hoeven dus niet alle acht te doorlopen; slechts vier zullen doen. En als box1 en box2 dezelfde oriëntatie delen, kunnen we verder reduceren om slechts twee assen te evalueren.
Hoe zit het met andere polygonen?
Helaas is er voor de driehoek en vijfhoek hierboven geen dergelijke snelkoppeling, dus moeten we cheques uitvoeren langs alle normalen.
Elk oppervlak heeft twee normalen:
Het diagram hierboven toont de linker en rechter normaal van P. Let op de geschakelde componenten van de vector en het teken voor elk.
Voor mijn implementatie gebruik ik een conventie met de wijzers van de klok mee, dus gebruik ik de links normalen. Hieronder is een uittreksel van SimpleSquare.as dit demonstreren.
openbare functie getNorm (): Vector.var normals: Vector. = nieuwe Vector. for (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;
Ik weet zeker dat je een manier kunt vinden om de volgende code te optimaliseren. Maar net zodat we allemaal een duidelijk beeld krijgen van wat er gebeurt, heb ik alles volledig uitgeschreven:
// resultaten van P, Q var result_P1: Object = getMinMax (vecs_box1, normals_box1 [1]); var result_P2: Object = getMinMax (vecs_box2, normals_box1 [1]); var result_Q1: Object = getMinMax (vecs_box1, normals_box1 [0]); var result_Q2: Object = getMinMax (vecs_box2, normals_box1 [0]); // resultaten van R, S var result_R1: Object = getMinMax (vecs_box1, normals_box2 [1]); var result_R2: Object = 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."
U zult zien dat sommige van de variabelen niet noodzakelijkerwijs zijn berekend om het resultaat te bereiken. Als een van separate_P, separate_Q, separate_R en separate_S is waar, dan zijn ze gescheiden en is het niet nodig om door te gaan.
Dit betekent dat we een behoorlijke hoeveelheid evaluatie kunnen besparen, gewoon door elk van die Booleans te controleren nadat ze zijn berekend. Hiervoor moet de code worden herschreven, maar ik denk dat je je er doorheen kunt werken (of bekijk het blok met opmerkingen in DemoSAT3.as).
Hier is een demo van de bovenstaande implementatie. Klik en sleep de vakken via hun middelste stippen en gebruik de R- en T-toetsen om de vakjes te draaien:
Wanneer dit algoritme wordt uitgevoerd, controleert het via de normale assen op overlappingen. Ik heb hier twee opmerkingen om erop te wijzen:
Hier is nog een voorbeeld van een codefragment om te controleren op een botsing tussen een zeshoek en een driehoek:
private function refresh (): void // prepare the normals var normals_hex: Vector.= hex.getNorm (); var normals_tri: Vector. = tri.getNorm (); var vecs_hex: Vector. = PrepVector (hex); var vecs_tri: Vector. = prepareVector (tri); var isSeparated: Boolean = false; // gebruik hexagon's normals om te evalueren voor (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."
Kijk voor de volledige code DemoSAT4.as in de brondownload.
De demo is hieronder. Interactie is hetzelfde als in eerdere demo's: sleep via de middelste punten en gebruik R en T om te roteren.
Botsing met een cirkel kan een van de eenvoudigere zijn. Omdat de projectie in alle richtingen hetzelfde is (het is gewoon de straal van de cirkel), kunnen we gewoon het volgende doen:
private function refresh (): void // prepare the vectors var v: Vector2d; var current_box_corner: Point; var center_box: Point = box1.getDot (0); var max: Number = Number.NEGATIVE_INFINITY; var box2circle: Vector2d = new Vector2d (c.x - center_box.x, c.y - center_box.y) var box2circle_normalised: Vector2d = box2circle.unitVector // haal het maximum op voor (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 = "Geen botsing" else t.text = "Botsing"
Bekijk de volledige bron in DemoSAT5.as. Sleep de cirkel of het vak om ze te laten botsen.
Wel, dat is het voor nu. Bedankt voor het lezen en laat uw feedback achter met een opmerking of vraag. Zie je de volgende zelfstudie!
