Share
Många spel kräver användning av kollisionsdetekteringsalgoritmer för att bestämma när två objekt har kolliderat, men dessa algoritmer är ofta dyra operationer och kan kraftigt sakta ner ett spel. I den här artikeln lär vi oss om quadtrees och hur vi kan använda dem för att påskynda kollisionsdetektering genom att hoppa över par objekt som är för långt ifrån varandra för att kollidera.
Notera: Även om denna handledning skrivs med Java, bör du kunna använda samma tekniker och begrepp i nästan vilken spelutvecklingsmiljö som helst.
Kollisionsdetektering är en viktig del av de flesta videospel. Både i 2D och 3D-spel, detekterar när två objekt har kolliderat är viktigt eftersom dålig kollisionsdetektering kan leda till några mycket intressanta resultat:
Kollisionsdetektering är emellertid också en mycket dyr operation. Låt oss säga att det finns 100 objekt som måste kontrolleras för kollision. Att jämföra varje par objekt kräver 10 000 operationer - det är många kontroller!
Ett sätt att påskynda saker är att minska antalet kontroller som måste göras. Två objekt som ligger i motsatta ändar av skärmen kan inte kollidera, så det är inte nödvändigt att kontrollera om det finns en kollision mellan dem. Här kommer en quadtree till spel.
En quadtree är en datastruktur som används för att dela upp en 2D-region i mer hanterbara delar. Det är ett förlängt binärt träd, men i stället för två barnnoder har det fyra.
I bilderna nedan är varje bild en visuell representation av 2D-rymden och de röda rutorna representerar objekt. I den här artikeln kommer undernoden att märkas moturs på följande sätt:
En quadtree startar som en enda nod. Objekt som läggs till quadtree läggs till i den enkla noden.
När fler objekt läggs till quadtree, delas det så småningom i fyra subnoder. Varje objekt kommer sedan att sättas in i en av dessa undernoder beroende på var den ligger i 2D-rymden. Alla objekt som inte helt kan passa inuti en nods gräns kommer att placeras i moderkoden.
Varje undernod kan fortsätta dela upp när fler objekt läggs till.
Som du kan se innehåller varje nod bara några föremål. Vi vet då att objekten i den övre vänstra noden inte kan kollidera med objekten i den nedre högra noden, så vi behöver inte köra en dyr kollisionsdetekteringsalgoritm mellan sådana par.
Ta en titt på det här JavaScript-exemplet för att se en quadtree i åtgärd.
Att implementera en quadtree är ganska enkel. Följande kod är skriven i Java, men samma tekniker kan användas för de flesta andra programmeringsspråk. Jag kommenterar efter varje kodbit.
Vi börjar med att skapa den viktigaste Quadtree-klassen. Nedan är koden för Quadtree.java.
allmän klass Quadtree privat int MAX_OBJECTS = 10; privat int MAX_LEVELS = 5; privat int nivå privata listobjekt privata rektangelgränser; privata Quadtree [] noder; / * * Constructor * / public Quadtree (int pLevel, rektangel pBounds) level = pLevel; objekt = ny ArrayList (); gränser = pBounds; noder = ny Quadtree [4];
De quadtree klassen är enkel. MAX_OBJECTS Definierar hur många objekt en nod kan hålla innan den splittras och MAX_LEVELS definierar den djupaste nivåns subnod. Nivå är den nuvarande nodnivån (0 är den högsta noden), gräns representerar det 2D-utrymme som noden upptar, och noder är de fyra undernoden.
I det här exemplet kommer objekten som quadtree håller är rektanglar, men för din egen quadtree kan det vara vad du vill.
Därefter implementerar vi de fem metoderna för en quadtree: klar, dela, getIndex, Föra in, och hämta.
/ * * Rensar quadtree * / public void clear () objects.clear (); för (int i = 0; i < nodes.length; i++) if (nodes[i] != null) nodes[i].clear(); nodes[i] = null;
De klar Metoden rensar quadtree genom att rekursivt rensa alla objekt från alla noder.
/ * * Splits noden i 4 subnoder * / privat void split () int subWidth = (int) (bounds.getWidth () / 2); int subHeight = (int) (bounds.getHeight () / 2); int x = (int) bounds.getX (); int y = (int) bounds.getY (); noder [0] = ny Quadtree (nivå + 1, ny rektangel (x + subWidth, y, subWidth, subHeight)); noder [1] = ny Quadtree (nivå + 1, ny rektangel (x, y, subWidth, subHeight)); noder [2] = ny Quadtree (nivå + 1, ny rektangel (x, y + subHeight, subWidth, subHeight)); noder [3] = ny Quadtree (nivå + 1, ny rektangel (x + subWidth, y + subHeight, subWidth, subHeight));
De dela Metoden delar noden i fyra subnoder genom att dividera noden i fyra lika delar och initialisera de fyra subnoden med de nya gränserna.
/ * * Bestäm vilken nod objektet tillhör. -1 betyder att * objektet inte helt kan passa in i en barnnod och är en del av modernoden * / privat int getIndex (rektangel pRect) int index = -1; dubbel verticalMidpoint = bounds.getX () + (bounds.getWidth () / 2); dubbel horizontalMidpoint = bounds.getY () + (bounds.getHeight () / 2); // Objektet kan helt passa in i toppkvadranterna booleanska topQuadrant = (pRect.getY () < horizontalMidpoint && pRect.getY() + pRect.getHeight() < horizontalMidpoint); // Object can completely fit within the bottom quadrants boolean bottomQuadrant = (pRect.getY() > horizontalMidpoint); // Objektet kan helt passa in i de vänstra kvadranterna om (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; annars om (bottomQuadrant) index = 3; returindex;
De getIndex Metoden är en hjälpfunktion för quadtree. Det bestämmer var ett objekt hör hemma i quadtree genom att bestämma vilken nod objektet kan passa in i.
/ * * Sätt in objektet i quadtree. Om noden * överstiger kapaciteten delas den och lägger till alla * objekt till deras motsvarande noder. * / public void insert (Rectangle pRect) om (noder [0]! = null) int index = getIndex (pRect); om (index! = -1) noder [index] .insert (pRect); lämna tillbaka; objects.add (pRect); om (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++;
De Föra in Metod är där allt kommer samman. Metoden bestämmer först om noden har några barnnoder och försöker lägga till objektet där. Om det inte finns några barnnoder eller objektet inte passar in i en barnnod, lägger den objektet till moderkoden.
När objektet är tillagt bestämmer det om noden behöver delas genom att kontrollera om det aktuella antalet objekt överstiger de maximalt tillåtna objekten. Splitting kommer att leda till att noden sätter in ett föremål som kan passa in i en barnnod som läggs till barnkoden; annars kommer objektet att ligga i moderkoden.
/ * * Returnera alla objekt som kan kollidera med det angivna objektet * / public List retrieve (Lista returnObjects, Rectangle pRect) int index = getIndex (pRect); om (index! = -1 && noder [0]! = null) noder [index] .retrieve (returnObjects, pRect); returnObjects.addAll (objekt); återvändande returnObjects;
Den sista metoden för quadtree är den hämta metod. Det returnerar alla objekt i alla noder som det angivna objektet eventuellt kan kollidera med. Denna metod är det som hjälper till att minska antalet par för att kontrollera kollision mot.
Nu när vi har en fullt fungerande quadtree, är det dags att använda den för att minska kontrollerna som behövs för kollisionsdetektering.
I ett typiskt spel börjar du med att skapa quadtree och passera gränserna på skärmen.
Quadtree quad = ny Quadtree (0, ny rektangel (0,0,600,600));
Vid varje ram lägger du in alla objekt i quadtree genom att först rensa quadtreeen med hjälp av Föra in metod för varje objekt.
quad.clear (); för (int i = 0; i < allObjects.size(); i++) quad.insert(allObjects.get(i));
När alla objekt har infogats går du igenom varje objekt och hämtar en lista över objekt som det eventuellt kan kollidera med. Du kontrollerar sedan för kollisioner mellan varje objekt i listan och det ursprungliga objektet med en kollisionsdetekteringsalgoritm.
Lista returnObjects = new ArrayList (); för (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
Notera: Kollisionsdetekteringsalgoritmer ligger utanför omfattningen av denna handledning. Se den här artikeln för ett exempel.
Kollisionsdetektering kan vara en dyr operation och kan sakta ner ditt spelets prestanda. Quadtrees är ett sätt du kan hjälpa till att påskynda kollisionsdetektering och hålla ditt spel igång med högsta hastighet.
relaterade inlägg
Accentsconagua