Share
Multe jocuri necesită folosirea algoritmilor de detectare a coliziunilor pentru a determina când două obiecte s-au ciocnit, dar acești algoritmi sunt operațiuni adesea costisitoare și pot încetini foarte mult jocul. În acest articol vom afla despre quadtrees și cum le putem folosi pentru a accelera detectarea coliziunilor, sărind peste perechi de obiecte care sunt prea departe pentru a se ciocni.
Notă: Deși acest tutorial este scris folosind Java, ar trebui să puteți folosi aceleași tehnici și concepte în aproape orice mediu de dezvoltare a jocului.
Detectarea coliziunilor este o parte esențială a majorității jocurilor video. Atât în jocurile 2D cât și în cele 3D, detectarea când s-au ciocnit două obiecte este importantă, deoarece detecția proastă a coliziunii poate duce la rezultate foarte interesante:
Cu toate acestea, detectarea coliziunii este, de asemenea, o operație foarte costisitoare. Să presupunem că există 100 de obiecte care trebuie verificate pentru coliziune. Comparând fiecare pereche de obiecte necesită 10.000 de operațiuni - multe verificări!
O modalitate de a accelera lucrurile este de a reduce numărul de controale care trebuie făcute. Două obiecte care se află la extremitățile opuse ale ecranului nu se pot ciocni, deci nu este nevoie să verificați dacă există o coliziune între ele. Aici intră în joc un quadtree.
Un quadtree este o structură de date utilizată pentru a împărți o regiune 2D în părți mai ușor de gestionat. Este un copac binar extins, dar în loc de două noduri copil are patru.
În imaginile de mai jos, fiecare imagine este o reprezentare vizuală a spațiului 2D, iar pătratele roșii reprezintă obiecte. În sensul prezentului articol, subnodurile vor fi etichetate în sens contrar acelor de ceasornic după cum urmează:
Un quadtree începe ca un singur nod. Obiectele adăugate la quadtree sunt adăugate la un singur nod.
Atunci când se adaugă mai multe obiecte în quadtree, se vor împărți în cele patru subnoduri. Fiecare obiect va fi apoi plasat într-una din aceste subnoduri în funcție de locul unde se află în spațiul 2D. Orice obiect care nu se poate încadra complet în limita unui nod va fi plasat în nodul părinte.
Fiecare subnod poate continua să se subdivizeze în timp ce se adaugă mai multe obiecte.
După cum puteți vedea, fiecare nod conține doar câteva obiecte. Știm apoi că, de exemplu, obiectele din nodul superior-stâng nu se pot ciocni cu obiectele din nodul de jos-dreapta, deci nu este nevoie să rulați un algoritm scump de detecție a coliziunii între astfel de perechi.
Aruncați o privire la acest exemplu JavaScript pentru a vedea un quadtree în acțiune.
Implementarea unui quadtree este destul de simplă. Următorul cod este scris în Java, însă aceleași tehnici pot fi folosite pentru majoritatea altor limbi de programare. Voi comenta după fiecare fragment de cod.
Vom începe prin crearea clasei principale Quadtree. Mai jos este codul pentru Quadtree.java.
clasa publică Quadtree private int MAX_OBJECTS = 10; private int MAX_LEVELS = 5; nivel privat int; obiecte private de inventar; dreptunghiuri privat privat; private Quadtree [] noduri; / * * Constructor * / Quadtree public (int pLevel, Rectangle pbounds) level = pLevel; obiecte = nou ArrayList (); limite = pBounds; noduri = nou Quadtree [4];
quadtree clasa este simplă. MAX_OBJECTS definește câte obiecte poate păstra un nod înainte de a se împărți și MAX_LEVELS definește subnodul cel mai adânc al nivelului. Nivel este nivelul nodului curent (0 fiind nodul cel mai de sus), hotar reprezintă spațiul 2D pe care nodul ocupă și noduri sunt cele patru subnoduri.
În acest exemplu, obiectele care vor păstra quadtree sunt dreptunghiuri, dar pentru propriul dvs. quadtree poate fi orice vreți.
Apoi vom implementa cele cinci metode ale unui quadtree: clar, Despică, getIndex, introduce, și recupera.
/ * * Șterge quadtree * / public void clar () objects.clear (); pentru (int i = 0; i < nodes.length; i++) if (nodes[i] != null) nodes[i].clear(); nodes[i] = null;
clar metoda șterge quadtree-ul prin eliminarea recursivă a tuturor obiectelor din toate nodurile.
/ * * Împărțiți nodul în 4 subnoduri * / split privat void () int subwidth = (int) (bounds.getWidth () / 2); int subeight = (int) (bounds.getHeight () / 2); int x = (int) bounds.getX (); int int = (int) bounds.getY (); noduri [0] = Quadtree noi (nivel + 1, nou dreptunghi (x + subwidth, y, subwidth, subHeight)); noduri [1] = noi Quadtree (nivel + 1, nou dreptunghi (x, y, subwidth, subHeight)); noduri [2] = Quadtree noi (nivel + 1, nou dreptunghi (x, y + subHeight, subwidth, subHeight)); noduri [3] = Quadtree noi (nivel + 1, nou dreptunghi (x + subwidth, y + subHeight, subwidth, subHeight));
Despică metoda împarte nodul în patru subnoduri prin împărțirea nodului în patru părți egale și inițializarea celor patru subnoduri cu noile limite.
/ * * Determina nodul de care aparține obiectul. -1 Obiect * înseamnă că obiectul nu se poate încadra complet într-un nod copil și este parte a nodului părinte * / int int getIndex (Rectangle pRect) int index = -1; dublu verticalMidpoint = bounds.getX () + (bounds.getWidth () / 2); dublu orizontalMidpoint = bounds.getY () + (bounds.getHeight () / 2); // Obiectul se poate potrivi complet în top quadrants boolean topQuadrant = (pRect.getY () < horizontalMidpoint && pRect.getY() + pRect.getHeight() < horizontalMidpoint); // Object can completely fit within the bottom quadrants boolean bottomQuadrant = (pRect.getY() > horizontalMidpoint); // Obiectul se poate potrivi complet în cadranele stânga dacă (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; altceva dacă (bottomQuadrant) index = 3; return index;
getIndex metoda este o funcție de ajutor a quadtree-ului. Acesta determină unde un obiect aparține în quadtree prin determinarea nodului în care se poate potrivi obiectul.
/ * * Introduceți obiectul în quadtree. Dacă nodul * depășește capacitatea, acesta se va împărți și va adăuga toate * obiectele la nodurile corespunzătoare. * / void public insert (pct. dreptunghi) if (noduri [0]! = null) int index = getIndex (pRect); dacă (index! = -1) noduri [index] .insert (pRect); întoarcere; objects.add (pRect); dacă (objects.size ()> MAX_OBJECTS && nivel < 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++;
introduce metoda este în cazul în care totul vine împreună. Metoda determină mai întâi dacă nodul are noduri copii și încearcă să adauge obiectul acolo. Dacă nu există noduri copil sau obiectul nu se potrivește într-un nod copil, acesta adaugă obiectul la nodul părinte.
Odată ce obiectul este adăugat, acesta determină dacă nodul trebuie împărțit verificând dacă numărul curent de obiecte depășește obiectele maxime permise. Împărțirea va determina nodul să introducă orice obiect care se poate potrivi într-un nod copil care urmează să fie adăugat la nodul copil; altfel obiectul va rămâne în nodul părinte.
/ * * Retur toate obiectele care ar putea intra în coliziune cu obiectul dat * / public Retrieve List (Lista returnObjects, Rectangle pRect) int index = getIndex (pRect); dacă (index! = -1 && node [0]! = null) noduri [index]. retrieve (returnObjects, pRect); returnObjects.addAll (obiecte); retur retur Obiecte;
Metoda finală a quadtree este recupera metodă. Returnează toate obiectele din toate nodurile pe care obiectele date ar putea să le coliziască. Această metodă ajută la reducerea numărului de perechi pentru a controla coliziunea împotriva.
Acum că avem un quadtree pe deplin funcțional, este timpul să îl folosim pentru a reduce controalele necesare pentru detectarea coliziunilor.
Într-un joc tipic, veți începe prin crearea cadrului quad și trecerea limitelor ecranului.
Quadtree quad = Quadtree nouă (0, nou dreptunghi (0,0600,600));
La fiecare cadru, veți introduce toate obiectele în quadtree, mai întâi eliminând quadtree-ul, apoi folosind introduce pentru fiecare obiect.
quad.clear (); pentru (int i = 0; i < allObjects.size(); i++) quad.insert(allObjects.get(i));
Odată ce toate obiectele au fost inserate, veți trece prin fiecare obiect și veți regăsi o listă de obiecte cu care ar putea intra în conflict. Veți verifica apoi coliziunile dintre fiecare obiect din listă și obiectul inițial, utilizând un algoritm de detecție a coliziunii.
Listă returnObjects = nou ArrayList (); pentru (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
Notă: Programele de detecție a coliziunii depășesc scopul acestui tutorial. Vedeți acest articol pentru un exemplu.
Detectarea coliziunilor poate fi o operație costisitoare și poate încetini performanța jocului. Quadtrees sunt o modalitate prin care puteți contribui la accelerarea detectării coliziunilor și vă puteți menține jocul la viteze maxime.
postări asemănatoare
Accentsconagua