Share
Il Teorema dell'asse di separazione viene spesso utilizzato per verificare la presenza di collisioni tra due poligoni semplici o tra un poligono e un cerchio. Come con tutti gli algoritmi, ha i suoi punti di forza e le sue debolezze. In questo tutorial, esamineremo la matematica dietro al teorema e mostreremo come può essere utilizzato nello sviluppo del gioco con alcuni esempi di codice e demo.
Nota: Sebbene le demo e il codice sorgente di questo tutorial utilizzino Flash e AS3, dovresti essere in grado di utilizzare le stesse tecniche e concetti in quasi tutti gli ambienti di sviluppo di giochi.
Il Teorema dell'asse di separazione (SAT in breve) afferma essenzialmente se sei in grado di disegnare una linea per separare due poligoni, quindi non si scontrano. È così semplice.
Nel diagramma sopra, puoi vedere facilmente le collisioni che si verificano nella seconda riga. Comunque provi a spremere una linea tra le forme, fallirai. La prima fila è esattamente l'opposto. Puoi facilmente disegnare una linea per separare le forme - e non solo una linea, ma molte di esse:
Ok, non esageriamo con questo; Penso che tu abbia capito il punto. L'argomento chiave qui è che se puoi tracciare una linea di questo tipo, allora ci deve essere una distanza che separa le forme. Quindi, come possiamo verificarlo??
Supponiamo per ora che i poligoni a cui ci riferiamo siano quadrati: box1 a sinistra e box2 sulla destra. È facile vedere che questi quadrati sono separati orizzontalmente. Un semplice approccio per determinare questo nel codice è calcolare la distanza orizzontale tra i due quadrati, quindi sottrarre le mezze larghe di box1 e box2:
Accentsconagua
// Pseudo codice per valutare la separazione di box1 e box2 lunghezza var: 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 ("E 'una grande distanza tra le scatole") else if (gap_between_boxes == 0) trace ("Le scatole si toccano") else if (gap_between_boxes < 0) trace("Boxes are penetrating each other") Cosa succede se le scatole non sono ben orientate?
Sebbene la valutazione del gap rimanga la stessa, dovremo pensare a un altro approccio per calcolare la lunghezza tra i centri e le mezze larghe - questa volta lungo il P asse. È qui che la matematica vettoriale è utile. Proietteremo i vettori A e B lungo P per ottenere le mezze larghezze.
Facciamo qualche revisione matematica.
Inizieremo ricapitolando la definizione del prodotto punto tra due vettori UN e B:
Possiamo definire il prodotto punto usando solo i componenti dei due vettori:
\ [
\ begin bmatrix A_x \\ A_y \ end bmatrix.
\ begin bmatrix B_x \\ B_y \ end bmatrix =
(A_x) (B_x) + (A_y) (B_y)
\]
In alternativa, possiamo capire il prodotto punto utilizzando le grandezze dei vettori e l'angolo tra di loro:
\ [
\ begin bmatrix A_x \\ A_y \ end bmatrix.
\ begin bmatrix B_x \\ B_y \ end bmatrix =
A_ magnitudo * B_ magnitudo * cos (theta)
\]
Ora proviamo a capire il proiezione di vettore UN su P.
Facendo riferimento al diagramma sopra, sappiamo che il valore di proiezione è \ (A_ magnitudo * cos (theta) \) (dove theta è l'angolo tra A e P). Anche se possiamo andare avanti e calcolare questo angolo per ottenere la proiezione, è complicato. Abbiamo bisogno di un approccio più diretto:
\ [
A. P = A_ magnitudine * P_ magnitudine * cos (theta) \\
A. \ frac P P_ magnitudo = A_ magnitudo * cos (theta) \\
\ begin bmatrix A_x \\ A_y \ end bmatrix.
\ begin bmatrix P_x / P_ magnitude \\ P_y / P_ magnitude \ end bmatrix =
A_ magnitudo * cos (theta)
\]
Nota che \ (\ begin bmatrix P_x / P_ magnitudine \\ P_y / P_ magnitudine \ end bmatrix \) è in realtà il vettore unitario di P.
Ora, invece di usare il lato destro dell'equazione, come eravamo, possiamo optare per il lato sinistro e arrivare allo stesso risultato.
Prima di procedere, vorrei chiarire la convenzione di denominazione utilizzata per indicare i quattro angoli di entrambe le caselle. Questo si rifletterà nel codice più tardi:
Il nostro scenario è il seguente:
Supponiamo che entrambe le caselle siano orientate a 45 ° rispetto all'asse orizzontale. Dobbiamo calcolare le seguenti lunghezze per determinare il divario tra le caselle.
Prendi nota speciale delle indicazioni delle frecce. Mentre la proiezione di A e C su P darà un valore positivo, la proiezione di B su P produrrà effettivamente a negativo valore in quanto i vettori puntano in direzioni opposte. Questo è coperto nella riga 98 dell'implementazione AS3 qui sotto:
var dot10: Point = box1.getDot (0); var dot11: Point = box1.getDot (1); var dot20: Point = box2.getDot (0); var dot24: Point = box2.getDot (4); // Calcoli reali var axis: Vector2d = new 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 (asse) var projA: Number = A.dotProduct (asse); var projB: Number = B.dotProduct (axis); var gap: Number = projC - projA + projB; // projB dovrebbe essere un valore negativo se (gap> 0) t.text = "C'è uno spazio tra le due caselle" else if (gap> 0) t.text = "Le scatole si toccano" else t.text = "La penetrazione era avvenuta."
Ecco una demo usando il codice sopra. Fare clic e trascinare il punto centrale rosso di entrambe le caselle e vedere il feedback interattivo.
Per l'intera fonte, controlla DemoSAT1.as nel download di origine.
Bene, possiamo andare con l'implementazione di cui sopra. Ma ci sono alcuni problemi - permettetemi di indicarli:
Innanzitutto, i vettori A e B sono corretti. Quindi quando cambi le posizioni di box1 e box2, il rilevamento delle collisioni non riesce.
Secondo, valutiamo solo il gap lungo un asse, quindi situazioni come quella sottostante non verranno valutate correttamente:
Sebbene la demo precedente sia difettosa, abbiamo imparato da essa il concetto di proiezione. Avanti, miglioriamoci.
Quindi, prima di tutto, dovremo ottenere le proiezioni minime e massime degli angoli (in particolare i vettori dall'origine agli angoli delle caselle) su P.
Lo schema sopra mostra la proiezione degli angoli minimo e massimo su P quando le scatole sono orientate bene lungo P.
Ma cosa succede se box1 e box2 non sono orientati di conseguenza?
Il diagramma sopra mostra scatole che non sono orientate ordinatamente lungo P e le loro proiezioni min-max corrispondenti. In questa situazione, dovremo scorrere ogni angolo di ogni riquadro e selezionare quelli corretti, se necessario.
Ora che abbiamo le proiezioni min-max, valuteremo se le scatole si scontrano l'una con l'altra. Come?
Osservando il diagramma sopra, possiamo vedere chiaramente la rappresentazione geometrica per la proiezione di box1.max e box2.min sull'asse P.
Come puoi vedere, quando c'è uno spazio tra le due scatole, box2.min-box1.max sarà più di zero - o in altre parole, box2.min> box1.max. Quando la posizione delle caselle viene scambiata, quindi box1.min> box2.max implica che c'è un divario tra loro.
Traducendo questa conclusione in codice, otteniamo:
// SAT: Pseudocodice per valutare la separazione di box1 e box2 if (box2.min> box1.max || box1.min> box2.max) trace ("collisione lungo l'asse P è successo") else trace ("no collisione lungo l'asse P ") Diamo un'occhiata ad un codice più dettagliato per capire questo. Si noti che il codice AS3 qui non è ottimizzato. Anche se è lungo e descrittivo, il vantaggio è che puoi vedere come funziona la matematica.
Prima di tutto, dobbiamo preparare i vettori:
// preparare i vettori dall'origine ai punti // poiché l'origine è (0,0), possiamo comodamente prendere le coordinate // per formare i vettori var axis: Vector2d = new Vector2d (1, -1) .unitVector; var vecs_box1: Vector.= nuovo vettore. ; var vecs_box2: Vector. = nuovo vettore. ; per (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));
Successivamente, otteniamo la proiezione min-max su box1. Puoi vedere un approccio simile usato su box2:
// impostazione min max per box1 var min_proj_box1: Number = vecs_box1 [1] .dotProduct (asse); var min_dot_box1: int = 1; var max_proj_box1: Number = vecs_box1 [1] .dotProduct (asse); var max_dot_box1: int = 1; per (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 // seleziona la proiezione minima sull'asse agli angoli di riquadro corrispondenti se (curr_proj1> max_proj_box1) max_proj_box1 = curr_proj1 max_dot_box1 = j
Infine, valutiamo se c'è una collisione su quell'asse specifico, 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."
Ecco una demo dell'implementazione sopra:
Puoi trascinare i riquadri attraverso il punto centrale e ruotarli con i tasti R e T. Il punto rosso indica l'angolo massimo per una casella, mentre il giallo indica il minimo. Se una casella è allineata con P, potresti notare che questi puntini sfarfallano mentre trascini, poiché questi due angoli condividono le stesse caratteristiche.
Guarda l'origine completa in DemoSAT2.as nel download di origine.
Se desideri accelerare il processo, non è necessario calcolare il vettore unitario di P. Puoi quindi saltare un certo numero di costosi calcoli di teoremi di Pitagora che implicano Math.sqrt ():
\ [\ begin bmatrix A_x \\ A_y \ end bmatrix.
\ begin bmatrix P_x / P_ magnitude \\ P_y / P_ magnitude \ end bmatrix =
A_ magnitudo * cos (theta)
\]
Il ragionamento è il seguente (fare riferimento al diagramma sopra per alcune indicazioni visive sulle variabili):
/ * Sia: P_unit essere il vettore unitario per P, P_mag essere P grandezza, v1_mag essere grandezza v1, v2_mag essere grandezza v2, theta_1 essere l'angolo tra v1 e P, theta_2 essere l'angolo tra v2 e P, Then: box1.max < box2.min => v1.dotProduct (P_unit) < v2.dotProduct(P_unit) => v1_mag * cos (theta_1) < v2_mag*cos(theta_2) */
Ora, matematicamente, il segno di disuguaglianza rimane lo stesso se entrambi i lati della disuguaglianza sono moltiplicati per lo stesso numero, A:
/ * Quindi: 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) */
Quindi, indipendentemente dal fatto che sia o meno un vettore unitario, il risultato è lo stesso.
Tieni presente che questo approccio è utile se stai verificando solo la sovrapposizione. Per trovare la lunghezza di penetrazione esatta di box1 e box2 (che per la maggior parte dei giochi sarà probabilmente necessario), è comunque necessario calcolare il vettore unitario di P.
Quindi abbiamo risolto il problema per un asse, ma non è la fine. Dobbiamo ancora affrontare altri assi, ma quali?
L'analisi per le scatole è abbastanza semplice: confrontiamo due assi P e Q. Al fine di confermare una collisione, sovrapposizione su tutti gli assi devono essere veri - se c'è un asse senza una sovrapposizione, possiamo concludere che non c'è collisione.
Cosa succede se le caselle sono orientate in modo diverso?
Fai clic sul pulsante verde per passare a un'altra pagina. Quindi degli assi P, Q, R e S, c'è solo un asse che non mostra sovrapposizione tra le scatole, e la nostra conclusione è che non c'è collisione tra le scatole.
Ma la domanda è: come decidere quali assi controllare per sovrapposizioni? Bene, prendiamo il normali dei poligoni.
In una forma generalizzata, con due caselle, dovremo controllare lungo otto assi: n0, n1, n2 e n3 per ciascuno di box1 e box2. Tuttavia, possiamo vedere che la seguente menzogna sugli stessi assi:
n0 e n2 di box1 n1 e n3 di box1 n0 e n2 di box2 n1 e n3 di box2 Quindi non abbiamo bisogno di passare attraverso tutti e otto; solo quattro lo faranno. E se box1 e box2 condividere lo stesso orientamento, possiamo ridurre ulteriormente per valutare solo due assi.
Che dire di altri poligoni?
Sfortunatamente, per il triangolo e il pentagono sopra non c'è una scorciatoia del genere, quindi dovremo eseguire controlli su tutte le normali.
Ogni superficie ha due normali:
Lo schema sopra mostra la normale sinistra e destra di P. Notare le componenti commutate del vettore e il segno per ciascuna.
Per la mia implementazione, sto usando una convenzione in senso orario, quindi uso il sinistra normali. Di seguito è riportato un estratto di SimpleSquare.as dimostrando questo.
funzione pubblica getNorm (): Vector.Varali normali: Vector. = nuovo vettore. per (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;
Sono sicuro che puoi trovare un modo per ottimizzare il seguente codice. Ma solo per avere un'idea chiara di ciò che sta accadendo, ho scritto tutto per intero:
// risultati di P, Q var result_P1: Object = getMinMax (vecs_box1, normalals_box1 [1]); var result_P2: Object = getMinMax (vecs_box2, normalals_box1 [1]); var result_Q1: Object = getMinMax (vecs_box1, normalals_box1 [0]); var result_Q2: Object = getMinMax (vecs_box2, normalals_box1 [0]); // risultati di R, S var result_R1: Object = getMinMax (vecs_box1, normalals_box2 [1]); var result_R2: Object = getMinMax (vecs_box2, normalals_box2 [1]); var result_S1: Object = getMinMax (vecs_box1, normalals_box2 [0]); var result_S2: Object = getMinMax (vecs_box2, normalals_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."
Vedrai che alcune delle variabili non sono necessariamente calcolate per raggiungere il risultato. Se qualcuno di separate_P, separate_Q, separate_R e separate_S è vero, quindi sono separati e non c'è nemmeno bisogno di procedere.
Ciò significa che possiamo salvare una buona dose di valutazione, semplicemente controllando ciascuno di questi booleani dopo che sono stati calcolati. Richiederebbe la riscrittura del codice, ma penso che si possa lavorare su di esso (o controllare il blocco commentato in DemoSAT3.as).
Ecco una demo dell'implementazione di cui sopra. Fai clic e trascina le caselle tramite i loro punti centrali e usa i tasti R e T per ruotare le caselle:
Quando viene eseguito questo algoritmo, controlla gli assi normali per sovrapposizioni. Ho due osservazioni qui per sottolineare:
Ecco un altro esempio di snippet di codice per verificare la presenza di una collisione tra un esagono e un triangolo:
funzione privata refresh (): void // prepara le normali var normalals_hex: Vector.= hex.getNorm (); var normals_tri: Vector. = tri.getNorm (); var vecs_hex: Vector. = prepareVector (hex); var vecs_tri: Vector. = prepareVector (tri); var isSeparated: Boolean = false; // usa le normali esagono per valutare per (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."
Per il codice completo, controlla DemoSAT4.as nel download di origine.
La demo è qui sotto. L'interazione è la stessa delle precedenti demo: trascina tramite i punti centrali e usa R e T per ruotare.
La collisione con un cerchio potrebbe essere una delle più semplici. Poiché la sua proiezione è la stessa in tutte le direzioni (è semplicemente il raggio del cerchio), possiamo solo fare quanto segue:
private function refresh (): void // prepara i vettori 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 // ottiene il massimo per (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 = "Nessuna collisione" else t.text = "Collision"
Guarda l'origine completa in DemoSAT5.as. Trascina il cerchio o la casella per vederli scontrare.
Bene, è tutto per ora. Grazie per la lettura e lascia il tuo feedback con un commento o una domanda. Ci vediamo al prossimo tutorial!
