Share
Veel games vereisen het gebruik van botsingsdetectiealgoritmen om te bepalen wanneer twee objecten zijn gebotst, maar deze algoritmen zijn vaak dure bewerkingen en kunnen een game aanzienlijk vertragen. In dit artikel komen we meer te weten over quadreen en hoe we ze kunnen gebruiken om botsdetectie te versnellen door paren voorwerpen over te slaan die te ver uit elkaar liggen om te botsen.
Notitie: Hoewel deze tutorial geschreven is met behulp van Java, zou je in bijna elke game-ontwikkelomgeving dezelfde technieken en concepten moeten kunnen gebruiken.
Botsingsdetectie is een essentieel onderdeel van de meeste videogames. Zowel in 2D- als 3D-games is het belangrijk om te detecteren wanneer twee objecten zijn gebotst, omdat een slechte botsingdetectie tot zeer interessante resultaten kan leiden:
Botsingsdetectie is echter ook een erg dure operatie. Laten we zeggen dat er 100 objecten zijn die moeten worden gecontroleerd op een botsing. Het vergelijken van elk paar objecten vereist 10.000 bewerkingen - dat zijn heel wat controles!
Een manier om dingen te versnellen, is het aantal controles dat moet worden uitgevoerd verminderen. Twee objecten die zich aan de tegenovergestelde uiteinden van het scherm bevinden, kunnen onmogelijk in botsing komen, dus er hoeft niet te worden gecontroleerd op een botsing tussen beide objecten. Dit is waar een quadtree in het spel komt.
Een kwadratuur is een gegevensstructuur die wordt gebruikt om een 2D-gebied op te splitsen in meer beheersbare delen. Het is een uitgebreide binaire structuur, maar in plaats van twee onderliggende knooppunten heeft deze vier.
In de onderstaande afbeeldingen is elke afbeelding een visuele weergave van de 2D-ruimte en vertegenwoordigen de rode vierkanten objecten. Voor de doeleinden van dit artikel worden de subknooppunten als volgt tegen de klok in aangeduid:
Een quadboom begint als een enkel knooppunt. Objecten die aan de quadtree zijn toegevoegd, worden toegevoegd aan het enkele knooppunt.
Wanneer er meer objecten aan de kwadratuur worden toegevoegd, zal deze uiteindelijk in vier subknooppunten worden gesplitst. Elk object wordt vervolgens in een van deze subknooppunten geplaatst, afhankelijk van waar het zich in de 2D-ruimte bevindt. Elk object dat niet volledig in de rand van een knoop past, wordt in het bovenliggende knooppunt geplaatst.
Elke subnode kan verder worden onderverdeeld naarmate er meer objecten worden toegevoegd.
Zoals u kunt zien, bevat elk knooppunt slechts een paar objecten. We weten dan dat de objecten in het knooppunt linksboven niet in botsing kunnen komen met de objecten in het knooppunt rechtsonder, dus we hoeven geen duur collisiedetectiealgoritme uit te voeren tussen dergelijke paren.
Bekijk dit JavaScript-voorbeeld om een quadtree in actie te zien.
Het implementeren van een kwadrant is vrij eenvoudig. De volgende code is geschreven in Java, maar dezelfde technieken kunnen voor de meeste andere programmeertalen worden gebruikt. Ik zal reageren na elk codefragment.
We beginnen met het maken van de hoofdklasse Quadtree. Hieronder staat de code voor Quadtree.java.
public class Quadtree private int MAX_OBJECTS = 10; privé int MAX_LEVELS = 5; privé int niveau; privé-lijstobjecten; private Rectangle bounds; private Quadtree [] -knooppunten; / * * Constructor * / public Quadtree (int pLevel, Rectangle pBounds) level = pLevel; objecten = nieuwe ArrayList (); bounds = pBounds; knooppunten = nieuwe Quadtree [4];
De quadtree klasse is eenvoudig. MAX_OBJECTS definieert hoeveel objecten een knooppunt kan bevatten voordat het wordt gesplitst en MAX_LEVELS definieert het diepste niveau-subknooppunt. Niveau is het huidige knooppuntniveau (waarbij 0 het bovenste knooppunt is), bounds vertegenwoordigt de 2D-ruimte die het knooppunt in beslag neemt, en nodes zijn de vier subknooppunten.
In dit voorbeeld zijn de objecten die de quadboom zal bevatten rechthoeken, maar voor je eigen quadtree kan het zijn wat je maar wilt.
Vervolgens implementeren we de vijf methoden van een quadtree: duidelijk, spleet, getIndex, invoegen, en terugvinden.
/ * * Wist de quadtree * / public void clear () objects.clear (); voor (int i = 0; i < nodes.length; i++) if (nodes[i] != null) nodes[i].clear(); nodes[i] = null;
De duidelijk methode wist de kwadratuur door recursief alle objecten uit alle knooppunten te wissen.
/ * * Splitst het knooppunt in 4 subknooppunten * / 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 (); knooppunten [0] = nieuwe Quadtree (niveau + 1, nieuwe rechthoek (x + subWidth, y, subWidth, subHeight)); knooppunten [1] = nieuwe Quadtree (niveau + 1, nieuwe rechthoek (x, y, subWidth, subHeight)); knooppunten [2] = nieuwe Quadtree (niveau + 1, nieuwe rechthoek (x, y + subHeight, subWidth, subHeight)); knooppunten [3] = nieuwe Quadtree (niveau + 1, nieuwe rechthoek (x + subWidth, y + subHeight, subWidth, subHeight));
De spleet methode splitst het knooppunt in vier subknooppunten door het knooppunt te verdelen in vier gelijke delen en de vier subknooppunten te initialiseren met de nieuwe grenzen.
/ * * Bepaal tot welk knooppunt het object behoort. -1 betekent * object kan niet volledig in een onderliggende node passen en is onderdeel * van het bovenliggende knooppunt * / private int getIndex (Rectangle pRect) int index = -1; double verticalMidpoint = bounds.getX () + (bounds.getWidth () / 2); double horizontalMidpoint = bounds.getY () + (bounds.getHeight () / 2); // Object kan volledig in de bovenste kwadranten worden geplaatst boolean topQuadrant = (pRect.getY () < horizontalMidpoint && pRect.getY() + pRect.getHeight() < horizontalMidpoint); // Object can completely fit within the bottom quadrants boolean bottomQuadrant = (pRect.getY() > horizontalMidpoint); // Object kan volledig in de linker kwadranten passen als (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; return-index;
De getIndex methode is een helperfunctie van de kwadratuur. Het bepaalt waar een object thuishoort in de quadboom door te bepalen in welk knooppunt het object kan passen.
/ * * Plaats het object in de kwadrant. Als het knooppunt * de capaciteit overschrijdt, wordt het gesplitst en worden alle * objecten aan hun overeenkomstige knooppunten toegevoegd. * / public void insert (Rectangle pRect) if (nodes [0]! = null) int index = getIndex (pRect); if (index! = -1) nodes [index] .insert (pRect); terug te keren; 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++;
De invoegen methode is waar alles samenkomt. De methode bepaalt eerst of het knooppunt onderliggende knooppunten heeft en probeert het object daar toe te voegen. Als er geen onderliggende knooppunten zijn of het object niet in een onderliggende knoop past, wordt het object toegevoegd aan het bovenliggende knooppunt.
Nadat het object is toegevoegd, bepaalt het of het knooppunt moet worden gesplitst door te controleren of het huidige aantal objecten de maximaal toegestane objecten overschrijdt. Splitsen zorgt ervoor dat het knooppunt elk object invoegt dat in een kindknoop kan passen om aan het onderliggende knooppunt te worden toegevoegd; anders blijft het object in het bovenliggende knooppunt.
/ * * Retourneer alle objecten die kunnen botsen met het opgegeven object * / public List retrieve (List returnObjects, Rectangle pRect) int index = getIndex (pRect); if (index! = -1 && nodes [0]! = null) knooppunten [index] .retrieve (returnObjects, pRect); returnObjects.addAll (objecten); return returnObjects;
De laatste methode van de quadtree is de terugvinden methode. Het retourneert alle objecten in alle knooppunten waarmee het gegeven object mogelijk zou kunnen botsen. Deze methode is wat helpt om het aantal paren te verminderen om een aanvaring tegen te nemen.
Nu we een volledig functionele quadtree hebben, is het tijd om deze te gebruiken om de controles die nodig zijn voor botsingsdetectie te verminderen.
In een typische game begin je met het maken van de kwadratuur en het overschrijden van de grenzen van het scherm.
Quadtree quad = nieuwe Quadtree (0, nieuwe rechthoek (0,0,600,600));
Bij elk frame voeg je alle objecten in de quadtree in door eerst de quadtree te verwijderen en vervolgens de invoegen methode voor elk object.
quad.clear (); voor (int i = 0; i < allObjects.size(); i++) quad.insert(allObjects.get(i));
Nadat alle objecten zijn ingevoegd, doorloopt u elk object en haalt u een lijst met objecten op waarmee het mogelijk zou kunnen botsen. Vervolgens controleert u op botsingen tussen elk object in de lijst en het eerste object, met behulp van een botsingsdetectiealgoritme.
List returnObjects = new ArrayList (); voor (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
Notitie: Botsingsdetectie-algoritmen vallen buiten het bestek van deze zelfstudie. Zie dit artikel voor een voorbeeld.
Collision detection kan een dure operatie zijn en kan de prestaties van je game vertragen. Quadtrees zijn een manier om botsingsdetectie te versnellen en je game op topsnelheid te laten draaien.
gerelateerde berichten
Accentsconagua