Share
Bei vielen Spielen müssen Kollisionserkennungsalgorithmen verwendet werden, um zu bestimmen, wann zwei Objekte kollidiert sind. Diese Algorithmen sind jedoch häufig kostspielige Operationen und können ein Spiel erheblich verlangsamen. In diesem Artikel erfahren Sie mehr über Quadtrees und wie wir sie einsetzen können, um die Kollisionserkennung zu beschleunigen, indem Sie Objektpaare überspringen, die zu weit voneinander entfernt sind, um zusammenzustoßen.
Hinweis: Obwohl dieses Tutorial mit Java geschrieben wurde, sollten Sie in der Lage sein, in fast jeder Spieleentwicklungsumgebung dieselben Techniken und Konzepte anzuwenden.
Die Kollisionserkennung ist ein wesentlicher Bestandteil der meisten Videospiele. Bei 2D- und 3D-Spielen ist die Erkennung, wenn zwei Objekte kollidiert sind, wichtig, da eine schlechte Kollisionserkennung zu sehr interessanten Ergebnissen führen kann:
Die Kollisionserkennung ist jedoch auch ein sehr teurer Vorgang. Angenommen, es gibt 100 Objekte, die auf Kollision geprüft werden müssen. Um jedes Objektpaar zu vergleichen, sind 10.000 Operationen erforderlich - das sind viele Überprüfungen!
Eine Möglichkeit, die Dinge zu beschleunigen, besteht darin, die Anzahl der durchzuführenden Prüfungen zu reduzieren. Zwei Objekte, die sich an entgegengesetzten Enden des Bildschirms befinden, können möglicherweise nicht kollidieren, so dass keine Kollision zwischen ihnen zu suchen ist. Hier kommt ein Quadtree ins Spiel.
Ein Quadtree ist eine Datenstruktur, mit der ein 2D-Bereich in überschaubarere Bereiche unterteilt wird. Es ist ein erweiterter Binärbaum, aber anstelle von zwei untergeordneten Knoten gibt es vier.
In den Bildern unten ist jedes Bild eine visuelle Darstellung des 2D-Raums und die roten Quadrate repräsentieren Objekte. Für die Zwecke dieses Artikels werden Unterknoten wie folgt entgegen dem Uhrzeigersinn gekennzeichnet:
Ein Quadtree beginnt als einzelner Knoten. Objekte, die zum Quadtree hinzugefügt werden, werden dem einzelnen Knoten hinzugefügt.
Wenn dem Quadtree weitere Objekte hinzugefügt werden, wird dieser schließlich in vier Unterknoten aufgeteilt. Jedes Objekt wird dann in einen dieser Unterknoten eingefügt, je nachdem, wo es sich im 2D-Raum befindet. Jedes Objekt, das nicht vollständig in die Begrenzung eines Knotens passt, wird im übergeordneten Knoten platziert.
Jeder Unterknoten kann weiter unterteilen, wenn weitere Objekte hinzugefügt werden.
Wie Sie sehen, enthält jeder Knoten nur wenige Objekte. Wir wissen also, dass zum Beispiel die Objekte im oberen linken Knoten nicht mit den Objekten im unteren rechten Knoten kollidieren können, so dass wir keinen kostspieligen Kollisionserkennungsalgorithmus zwischen solchen Paaren ausführen müssen.
Sehen Sie sich dieses JavaScript-Beispiel an, um einen Quadtree in Aktion zu sehen.
Die Implementierung eines Quadtrees ist ziemlich einfach. Der folgende Code ist in Java geschrieben. Dieselben Techniken können jedoch für die meisten anderen Programmiersprachen verwendet werden. Ich werde nach jedem Code-Snippet einen Kommentar abgeben.
Wir beginnen mit der Erstellung der Quadtree-Hauptklasse. Unten ist der Code für Quadtree.java.
öffentliche Klasse Quadtree private int MAX_OBJECTS = 10; private int MAX_LEVELS = 5; private int-Ebene; private Listenobjekte; private Rechteckgrenzen; private Quadtree [] Knoten; / * * Konstruktor * / public Quadtree (int pLevel, Rectangle pBounds) level = pLevel; objects = new ArrayList (); Grenzen = pBounds; Knoten = neuer Quadtree [4];
Das Quadtree Klasse ist unkompliziert. MAX_OBJECTS legt fest, wie viele Objekte ein Knoten enthalten kann, bevor er sich teilt und MAX_LEVELS Definiert den Unterknoten der tiefsten Ebene. Niveau ist die aktuelle Knotenebene (0 ist der oberste Knoten), Grenzen stellt den 2D-Raum dar, den der Knoten einnimmt, und Knoten sind die vier Unterknoten.
In diesem Beispiel sind die Objekte, die der Quadtree enthalten soll Rechtecke, Aber für Ihren eigenen Quadtree kann es sein, was Sie wollen.
Als Nächstes implementieren wir die fünf Methoden eines Quadtrees: klar, Teilt, getIndex, einfügen, und abrufen.
/ * * Löscht den 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;
Das klar Die Methode löscht den Quadtree, indem alle Objekte rekursiv von allen Knoten gelöscht werden.
/ * * Teilt den Knoten in 4 Unterknoten. * / 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 (); Knoten [0] = neuer Quadtree (Level + 1, neues Rechteck (x + SubWidth, y, SubWidth, SubHeight)); Knoten [1] = neuer Quadtree (Level + 1, neues Rechteck (x, y, subWidth, subHeight)); Knoten [2] = neuer Quadtree (Level + 1, neues Rechteck (x, y + subHeight, subWidth, subHeight)); Knoten [3] = neuer Quadtree (Level + 1, neues Rechteck (x + SubWidth, y + SubHeight, SubWidth, SubHeight));
Das Teilt Die Methode teilt den Knoten in vier Unterknoten auf, indem er den Knoten in vier gleiche Teile teilt und die vier Unterknoten mit den neuen Grenzen initialisiert.
/ * * Bestimmen Sie, zu welchem Knoten das Objekt gehört. -1 bedeutet, dass * object nicht vollständig in einen untergeordneten Knoten passt und Teil * des übergeordneten Knotens ist * / private int getIndex (Rechteck pRect) int index = -1; double verticalMidpoint = bounds.getX () + (bounds.getWidth () / 2); double horizontalMidpoint = bounds.getY () + (bounds.getHeight () / 2); // Objekt kann vollständig in die oberen Quadranten passen. Boolean topQuadrant = (pRect.getY () < horizontalMidpoint && pRect.getY() + pRect.getHeight() < horizontalMidpoint); // Object can completely fit within the bottom quadrants boolean bottomQuadrant = (pRect.getY() > horizontalMidpoint); // Das Objekt kann vollständig in die linken Quadranten passen, wenn (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; Rückgabeindex;
Das getIndex method ist eine Hilfsfunktion des Quadtrees. Er bestimmt, wo ein Objekt in den Quadtree gehört, indem er bestimmt, in welchen Knoten das Objekt passen kann.
/ * * Füge das Objekt in den Quadtree ein. Wenn der Knoten * die Kapazität überschreitet, teilt er alle * Objekte auf und fügt sie den entsprechenden Knoten hinzu. * / public void insert (Rechteck pRect) if (node [0]! = null) int index = getIndex (pRect); if (index! = -1) node [index] .insert (pRect); Rückkehr; 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++;
Das einfügen Methode ist, wo alles zusammenkommt. Die Methode ermittelt zuerst, ob der Knoten über untergeordnete Knoten verfügt, und versucht, das Objekt dort hinzuzufügen. Wenn keine untergeordneten Knoten vorhanden sind oder das Objekt nicht in einen untergeordneten Knoten passt, wird das Objekt dem übergeordneten Knoten hinzugefügt.
Nachdem das Objekt hinzugefügt wurde, bestimmt es, ob der Knoten aufgeteilt werden muss, indem geprüft wird, ob die aktuelle Anzahl von Objekten die maximal zulässige Anzahl von Objekten überschreitet. Durch das Aufteilen fügt der Knoten ein beliebiges Objekt ein, das in einen untergeordneten Knoten passt, um es dem untergeordneten Knoten hinzuzufügen. Andernfalls bleibt das Objekt im übergeordneten Knoten.
/ * * Gibt alle Objekte zurück, die mit dem angegebenen Objekt kollidieren könnten. * / Public Liste abrufen (Liste returnObjects, Rectangle pRect) int index = getIndex (pRect); if (index! = -1 && node [0]! = null) node [index] .retrieve (returnObjects, pRect); returnObjects.addAll (Objekte); return returnObjects;
Die letzte Methode des Quadtree ist die abrufen Methode. Es gibt alle Objekte in allen Knoten zurück, mit denen das gegebene Objekt möglicherweise kollidieren könnte. Diese Methode hilft, die Anzahl der Paare zu verringern, gegen die die Kollision geprüft wird.
Jetzt, da wir einen voll funktionsfähigen Quadtree haben, ist es an der Zeit, ihn zu verwenden, um die für die Kollisionserkennung erforderliche Prüfung zu reduzieren.
In einem typischen Spiel erstellen Sie zunächst den Quadtree und passieren die Bildschirmgrenzen.
Quadtree Quad = neuer Quadtree (0, neues Rechteck (0,0,600,600));
Bei jedem Frame fügen Sie alle Objekte in den Quadtree ein, indem Sie zuerst den Quadtree löschen und dann die einfügen Methode für jedes Objekt.
quad.clear (); für (int i = 0; i < allObjects.size(); i++) quad.insert(allObjects.get(i));
Nachdem Sie alle Objekte eingefügt haben, gehen Sie jedes Objekt durch und rufen eine Liste von Objekten ab, mit denen es möglicherweise kollidiert. Sie werden dann mit einem Kollisionserkennungsalgorithmus nach Kollisionen zwischen jedem Objekt in der Liste und dem Ausgangsobjekt suchen.
Liste 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
Hinweis: Kollisionserkennungsalgorithmen gehen über den Rahmen dieses Tutorials hinaus. In diesem Artikel finden Sie ein Beispiel.
Die Kollisionserkennung kann teuer sein und die Leistung Ihres Spiels beeinträchtigen. Mit Quadtrees können Sie die Kollisionserkennung beschleunigen und Ihr Spiel mit Höchstgeschwindigkeit laufen lassen.
zusammenhängende Posts
Accentsconagua