Share
Molti giochi richiedono l'uso di algoritmi di rilevamento delle collisioni per determinare quando due oggetti sono entrati in collisione, ma questi algoritmi sono spesso operazioni costose e possono rallentare notevolmente il gioco. In questo articolo impareremo a conoscere i quad e come usarli per accelerare il rilevamento delle collisioni saltando le coppie di oggetti troppo distanti per collidere.
Nota: Sebbene questo tutorial sia scritto usando Java, dovresti essere in grado di utilizzare le stesse tecniche e concetti in quasi tutti gli ambienti di sviluppo di giochi.
Il rilevamento delle collisioni è una parte essenziale della maggior parte dei videogiochi. Sia nei giochi 2D che in 3D, rilevare quando due oggetti sono entrati in collisione è importante poiché uno scarso rilevamento delle collisioni può portare a risultati molto interessanti:
Tuttavia, il rilevamento delle collisioni è anche un'operazione molto costosa. Diciamo che ci sono 100 oggetti che devono essere controllati per la collisione. Confrontare ogni coppia di oggetti richiede 10.000 operazioni: sono molti i controlli!
Un modo per accelerare le cose è ridurre il numero di controlli da effettuare. Due oggetti che si trovano alle estremità opposte dello schermo non possono eventualmente scontrarsi, quindi non è necessario verificare la presenza di una collisione tra di loro. È qui che entra in gioco un quadriponte.
Un quadrilatero è una struttura dati utilizzata per dividere una regione 2D in parti più gestibili. È un albero binario esteso, ma invece di due nodi figlio ne ha quattro.
Nelle immagini sottostanti, ogni immagine è una rappresentazione visiva dello spazio 2D e i quadrati rossi rappresentano oggetti. Ai fini di questo articolo, i sottonodi saranno etichettati in senso antiorario come segue:
Un quadrilatero inizia come un singolo nodo. Gli oggetti aggiunti al quadruplo vengono aggiunti al singolo nodo.
Quando più oggetti vengono aggiunti al quadrifoglio, alla fine si dividerà in quattro sottonodi. Ogni oggetto verrà quindi inserito in uno di questi sottonodi in base a dove si trova nello spazio 2D. Qualsiasi oggetto che non può integrarsi completamente all'interno del confine di un nodo verrà posizionato nel nodo genitore.
Ogni sottonodo può continuare a suddividersi man mano che vengono aggiunti più oggetti.
Come puoi vedere, ogni nodo contiene solo pochi oggetti. Sappiamo quindi che, ad esempio, gli oggetti nel nodo in alto a sinistra non possono essere in collisione con gli oggetti nel nodo in basso a destra, quindi non è necessario eseguire un costoso algoritmo di rilevamento delle collisioni tra tali coppie.
Dai un'occhiata a questo esempio di JavaScript per vedere un quadtree in azione.
L'implementazione di un quadruplo è abbastanza semplice. Il seguente codice è scritto in Java, ma le stesse tecniche possono essere utilizzate per la maggior parte degli altri linguaggi di programmazione. Commenterò dopo ogni snippet di codice.
Inizieremo creando la classe Quadtree principale. Di seguito è riportato il codice per Quadtree.java.
Quadtree di classe pubblica private int MAX_OBJECTS = 10; int privato MAX_LEVELS = 5; livello int privato; oggetti Elenco privati; limiti rettangolo privato; nodi Quadtree privati []; / * * Costruttore * / Quadtree pubblico (int pLevel, Rectangle pBounds) level = pLevel; objects = new ArrayList (); bounds = pBounds; nodes = new Quadtree [4];
Il quadtree la classe è semplice. MAX_OBJECTS definisce quanti oggetti un nodo può contenere prima che divida e MAX_LEVELS definisce il sottonodo di livello più profondo. Livello è il livello del nodo corrente (0 è il nodo più in alto), misura rappresenta lo spazio 2D occupato dal nodo e nodi sono i quattro sottonodi.
In questo esempio, gli oggetti che il quadrilatero manterrà sono rettangoli, ma per il tuo quadruplo può essere quello che vuoi.
Successivamente, implementeremo i cinque metodi di un quadruplo: chiaro, Diviso, getIndex, inserire, e recuperare.
/ * * Cancella il quadrilatero * / public void clear () objects.clear (); per (int i = 0; i < nodes.length; i++) if (nodes[i] != null) nodes[i].clear(); nodes[i] = null;
Il chiaro Il metodo cancella il quadrifoglio cancellando in modo ricorsivo tutti gli oggetti da tutti i nodi.
/ * * Divide il nodo in 4 sottonodi * / private void split () int subWidth = (int) (bounds.getWidth () / 2); int subHeight = (int) (bounds.getHeight () / 2); int x = (int) bounds.getX (); int y = (int) bounds.getY (); nodi [0] = nuovo Quadtree (livello + 1, nuovo rettangolo (x + subWidth, y, subWidth, subHeight)); nodi [1] = nuovo Quadtree (livello + 1, nuovo rettangolo (x, y, subWidth, subHeight)); nodes [2] = new Quadtree (level + 1, new Rectangle (x, y + subHeight, subWidth, subHeight)); nodes [3] = new Quadtree (level + 1, new Rectangle (x + subWidth, y + subHeight, subWidth, subHeight));
Il Diviso il metodo divide il nodo in quattro sottonodi dividendo il nodo in quattro parti uguali e inizializzando i quattro sottonodi con i nuovi limiti.
/ * * Determina a quale nodo appartiene l'oggetto. -1 significa che * l'oggetto non può adattarsi completamente all'interno di un nodo figlio ed è parte * del nodo genitore * / private int getIndex (Rectangle pRect) int index = -1; double verticalMidpoint = bounds.getX () + (bounds.getWidth () / 2); double horizontalMidpoint = bounds.getY () + (bounds.getHeight () / 2); // L'oggetto può adattarsi completamente ai quadranti superiori booleano topQuadrant = (pRect.getY () < horizontalMidpoint && pRect.getY() + pRect.getHeight() < horizontalMidpoint); // Object can completely fit within the bottom quadrants boolean bottomQuadrant = (pRect.getY() > horizontalMidpoint); // L'oggetto può adattarsi completamente ai quadranti di sinistra se (pRect.getX () < verticalMidpoint && pRect.getX() + pRect.getWidth() < verticalMidpoint) if (topQuadrant) index = 1; else if (bottomQuadrant) index = 2; // Object can completely fit within the right quadrants else if (pRect.getX() > verticalMidpoint) if (topQuadrant) index = 0; else if (bottomQuadrant) index = 3; indice di ritorno;
Il getIndex il metodo è una funzione di supporto del quadrifoglio. Determina il punto in cui un oggetto appartiene al quadrilatero determinando in quale nodo può essere inserito l'oggetto.
/ * * Inserisci l'oggetto nel quadrifoglio. Se il nodo * supera la capacità, verrà diviso e aggiunto tutti gli oggetti * ai nodi corrispondenti. * / public void insert (Rectangle pRect) if (nodes [0]! = null) int index = getIndex (pRect); if (index! = -1) nodes [index] .insert (pRect); ritorno; objects.add (pRect); if (objects.size ()> MAX_OBJECTS && level < MAX_LEVELS) if (nodes[0] == null) split(); int i = 0; while (i < objects.size()) int index = getIndex(objects.get(i)); if (index != -1) nodes[index].insert(objects.remove(i)); else i++;
Il inserire il metodo è dove tutto viene insieme. Il metodo determina innanzitutto se il nodo ha nodi figli e tenta di aggiungere l'oggetto lì. Se non ci sono nodi figli o l'oggetto non rientra in un nodo figlio, aggiunge l'oggetto al nodo genitore.
Una volta aggiunto l'oggetto, determina se il nodo deve essere suddiviso controllando se il numero corrente di oggetti supera gli oggetti massimi consentiti. La suddivisione farà sì che il nodo inserisca qualsiasi oggetto che possa essere contenuto in un nodo figlio da aggiungere al nodo figlio; altrimenti l'oggetto rimarrà nel nodo genitore.
/ * * Restituisce tutti gli oggetti che potrebbero entrare in collisione con l'oggetto specificato * / public List retrieve (List returnObjects, Rectangle pRect) int index = getIndex (pRect); if (index! = -1 && nodes [0]! = null) nodes [index] .retrieve (returnObjects, pRect); returnObjects.addAll (objects); return returnObjects;
Il metodo finale del quadrifoglio è il recuperare metodo. Restituisce tutti gli oggetti in tutti i nodi con cui l'oggetto dato potrebbe potenzialmente collidere. Questo metodo è ciò che aiuta a ridurre il numero di coppie per controllare la collisione.
Ora che abbiamo un quadripree pienamente funzionante, è il momento di usarlo per ridurre i controlli necessari per il rilevamento delle collisioni.
In un tipico gioco, inizierai creando il quadrilatero e superando i limiti dello schermo.
Quad quadripre = new Quadtree (0, new Rectangle (0,0,600,600));
Ad ogni fotogramma, inserirai tutti gli oggetti nel quadrifoglio liberando prima il quadrilatero e poi usando il inserire metodo per ogni oggetto.
quad.clear (); per (int i = 0; i < allObjects.size(); i++) quad.insert(allObjects.get(i));
Una volta che tutti gli oggetti sono stati inseriti, passerai attraverso ogni oggetto e recupererai una lista di oggetti con cui potrebbe collidere. Quindi verificherà le collisioni tra ciascun oggetto nell'elenco e l'oggetto iniziale, utilizzando un algoritmo di rilevamento delle collisioni.
List returnObjects = new ArrayList (); per (int i = 0; i < allObjects.size(); i++) returnObjects.clear(); quad.retrieve(returnObjects, objects.get(i)); for (int x = 0; x < returnObjects.size(); x++) // Run collision detection algorithm between objects
Nota: Gli algoritmi di rilevamento delle collisioni vanno oltre lo scopo di questo tutorial. Vedi questo articolo per un esempio.
Il rilevamento delle collisioni può essere un'operazione costosa e può rallentare le prestazioni del gioco. I quadri sono un modo per accelerare il rilevamento delle collisioni e mantenere il gioco alla massima velocità.
Post correlati
Accentsconagua