Share
Mange spill krever bruk av kollisjonsdetekteringsalgoritmer for å bestemme når to objekter har kollidert, men disse algoritmene er ofte dyre operasjoner og kan i stor grad redusere et spill. I denne artikkelen lærer vi om quadtrees, og hvordan vi kan bruke dem til å øke kollisjonsdeteksjonen ved å hoppe over par objekter som er for langt fra hverandre for å kollidere.
Merk: Selv om denne opplæringen er skrevet ved hjelp av Java, bør du kunne bruke de samme teknikkene og konseptene i nesten hvilket som helst spillutviklingsmiljø.
Kollisjonsdeteksjon er en viktig del av de fleste videospill. Både i 2D og 3D-spill, som oppdager når to objekter har kollidert, er viktig, da dårlig kollisjonsdeteksjon kan føre til noen svært interessante resultater:
Kollisjonsdeteksjon er imidlertid også en veldig dyr operasjon. La oss si at det er 100 objekter som må kontrolleres for kollisjon. Å sammenligne hvert par objekter krever 10 000 operasjoner - det er mange sjekker!
En måte å øke hastigheten på er å redusere antall kontroller som må gjøres. To gjenstander som ligger i motsatte ender av skjermen kan ikke muligens kollidere, så det er ikke nødvendig å sjekke for en kollisjon mellom dem. Dette er hvor en quadtree kommer inn i spill.
En quadtree er en datastruktur som brukes til å dele en 2D-region i mer håndterbare deler. Det er et utvidet binært tre, men i stedet for to barnnoder har det fire.
I bildene nedenfor er hvert bilde en visuell representasjon av 2D-rommet og de røde firkantene representerer objekter. I denne artikkelen skal undernodes merkes mot klokken som følger:
En quadtree starter som en enkelt node. Objekter lagt til quadtree legges til enkeltknutepunktet.
Når flere objekter legges til quadtree, vil det til slutt splitte seg inn i fire undernoder. Hvert objekt blir da satt inn i en av disse undernumrene i henhold til hvor det ligger i 2D-rommet. Ethvert objekt som ikke helt kan passe inn i en knutepunkts grense, blir plassert i hovednoden.
Hver subnode kan fortsette å deles etter hvert som flere objekter blir lagt til.
Som du kan se, inneholder hver knute bare noen få objekter. Vi vet da at for eksempel objektene i den øverste venstre knutepunktet ikke kan kollidere med objektene i den nederste høyre noden, så vi trenger ikke å kjøre en dyr kollisjonsdetekteringsalgoritme mellom slike par.
Ta en titt på dette JavaScript-eksemplet for å se en quadtree i aksjon.
Det er ganske enkelt å implementere en quadtree. Følgende kode er skrevet i Java, men de samme teknikkene kan brukes til de fleste andre programmeringsspråk. Jeg vil kommentere etter hver kodebit.
Vi starter med å lage den viktigste Quadtree-klassen. Nedenfor er koden for Quadtree.java.
offentlig klasse Quadtree private int MAX_OBJECTS = 10; privat int MAX_LEVELS = 5; privat int nivå; private liste objekter; private rektangulære grenser; private Quadtree [] noder; / * * Constructor * / public Quadtree (int pLevel, rektangel pBounds) level = pLevel; objekter = ny ArrayList (); grenser = pBounds; noder = ny Quadtree [4];
De firertre klassen er grei. MAX_OBJECTS definerer hvor mange objekter en node kan holde før den splittes og MAX_LEVELS definerer det dypeste nivået subnode. Nivå er det nåværende nodenivået (0 er den øverste node), grensene representerer 2D-rommet som noden opptar, og noder er de fire subnodes.
I dette eksemplet vil objektene quadtree holdes er rektangler, men for din egen quadtree kan det være hva du vil.
Deretter implementerer vi de fem metodene for en quadtree: klar, dele, getIndex, sett inn, og hente.
/ * * Fjerner quadtree * / public void clear () objects.clear (); for (int i = 0; i < nodes.length; i++) if (nodes[i] != null) nodes[i].clear(); nodes[i] = null;
De klar Metode sletter quadtree ved rekursivt å rydde alle objekter fra alle noder.
/ * * Splits noden i 4 subnodes * / 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 (); noder [0] = ny Quadtree (nivå + 1, nytt rektangel (x + subWidth, y, subWidth, subHeight)); noder [1] = ny Quadtree (nivå + 1, nytt rektangel (x, y, subWidth, subHeight)); noder [2] = ny Quadtree (nivå + 1, nytt rektangel (x, y + subHeight, subWidth, subHeight)); noder [3] = ny Quadtree (nivå + 1, nytt rektangel (x + subWidth, y + subHeight, subWidth, subHeight));
De dele Metoden deler noden i fire subnoder ved å dele noden i fire like deler og initialisere de fire subnoderne med de nye grensene.
/ * * Bestem hvilken nod objektet tilhører. -1 betyr * objektet kan ikke helt passe inn i en barnekode og er en del * av stamnoden * / privat int getIndex (rektangel pRect) int index = -1; dobbel verticalMidpoint = bounds.getX () + (bounds.getWidth () / 2); dobbelt horizontalMidpoint = bounds.getY () + (bounds.getHeight () / 2); // Objektet kan passe helt inn i toppkvadranterne boolean topQuadrant = (pRect.getY () < horizontalMidpoint && pRect.getY() + pRect.getHeight() < horizontalMidpoint); // Object can completely fit within the bottom quadrants boolean bottomQuadrant = (pRect.getY() > horizontalMidpoint); // Objektet kan passe helt inn i venstre kvadranter hvis (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; annet hvis (bottomQuadrant) index = 3; returindeks;
De getIndex Metoden er en hjelpefunksjon av quadtree. Det bestemmer hvor et objekt tilhører quadtree ved å bestemme hvilken knute objektet kan passe inn i.
/ * * Sett inn objektet i quadtree. Hvis noden * overskrider kapasiteten, vil den dele og legge til alle * objekter til de tilhørende nodene. * / public void insert (rektangulær pRect) if (noder [0]! = null) int index = getIndex (pRect); hvis (indeks! = -1) noder [indeks] .insert (pRect); komme tilbake; objects.add (pRect); hvis (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 sett inn Metoden er hvor alt kommer sammen. Metoden bestemmer først om noden har noen barnnoder og prøver å legge til objektet der. Hvis det ikke finnes noen barnnoder eller objektet ikke passer inn i en barnekode, legger det objektet til foreldrenummeret.
Når objektet er lagt til, bestemmer det om noden må deles ved å sjekke om det nåværende antall objekter overskrider maksimum tillatt gjenstander. Splitting vil føre til at noden setter inn et objekt som kan passe inn i en barnekode som skal legges til barnekoden; ellers vil objektet forbli i hovednoden.
/ * * Retur alle objekter som kan kollidere med det gitte objektet * / offentlig Liste hente (Liste returnObjects, Rectangle pRect) int index = getIndex (pRect); hvis (index! = -1 && noder [0]! = null) noder [index] .retrieve (returnObjects, pRect); returnObjects.addAll (objekter); returnere tilbakeObjects;
Den endelige metoden for quadtree er hente metode. Det returnerer alle objekter i alle noder som det gitte objektet potensielt kunne kollidere med. Denne metoden er det som bidrar til å redusere antall par for å sjekke kollisjon mot.
Nå som vi har en fullt funksjonell quadtree, er det på tide å bruke den til å redusere kontrollene som trengs for kollisjonsdeteksjon.
I et typisk spill begynner du med å lage quadtree og passerer grensen på skjermen.
Quadtree quad = ny Quadtree (0, ny rektangel (0,0,600,600));
Ved hver ramme legger du inn alle objekter i quadtree ved å først rydde quadtree og deretter bruke sett inn metode for hvert objekt.
quad.clear (); for (int i = 0; i < allObjects.size(); i++) quad.insert(allObjects.get(i));
Når alle objekter er satt inn, går du gjennom hvert objekt og henter en liste over objekter som det muligens kan kollidere med. Du vil da sjekke om kollisjoner mellom hver gjenstand i listen og det opprinnelige objektet, ved hjelp av en kollisjonsdetekteringsalgoritme.
Liste returnObjects = new ArrayList (); for (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
Merk: Kollisjonsdetekteringsalgoritmer er utenfor omfanget av denne opplæringen. Se denne artikkelen for et eksempel.
Kollisjonsdeteksjon kan være en dyr operasjon og kan redusere ytelsen til spillet ditt. Quadtrees er en måte du kan hjelpe til med å øke kollisjonsdeteksjonen og holde spillet i topphastigheter.
Relaterte innlegg
Accentsconagua