Quad Trees / Grid Based Collision - Logik in die Tat umsetzen

Zuallererst habe ich nur eine kurze Zeit lang meine eigene Spielelogik geschrieben, also entschuldige ich mich, wenn dies unkompliziert erscheint.

Ich habe viel über Quad-Bäume und gitterbasierte Kollisionserkennung gelesen. Ich verstehe die Logik - prüfe grundsätzlich nicht auf Kollisionen, es sei denn, Objekte sind im Grunde genommen in der Nähe. Es wird aber nie erwähnt, wie die das tatsächlich ausführen.

Ich habe ein paar mögliche Methoden im Kopf, bin mir aber nicht sicher, welche die beste ist

Allgemeiner Kollisionstest - keine Optimierung

for(var i:int = 0; i < objects.length; i++){
        //find object A
        var objectA = objects[i];

        for(var j:int = i + 1; j < objects.length; j++){
            //find object B
            var objectB = objects[j];

            if(objectA.collidesWith(objectB){

               //handle collision logic
              }
        }

Nachbarn speichern (Methode 1) Aber was ist, wenn wir die Kollisionen optimieren möchten, um nur Objekte zu überprüfen, die sich in der Nähe befinden. Durchlaufen wir immer noch alle Objekte oder erstellen wir ein Array mit Near-Objekten, die überprüft werden sollen?

var objects:Array = new Array();
    var neighbours:Array = new Array();

    for(var i:int = 0; i < objects.length; i++){
        //find object A
        var objectA = objects[i];

        for(var j:int = i + 1; j < objects.length; j++){
            //find object B
            var objectB = objects[j];

            if(objectA.isNear(objectB){

               neighbours.push(objectA, objectB);
              }
        }

    }

    //somewhere else
    for(i:int = 0; i < neighbours.length; i++){
        //only check neighbours

        for(j:int = i + 1; j < neighbours.length; j++){

            if(objectA.collidesWith(objectB){

               //handle collision logic
              }
        }
    }

Schleifen Sie alle Objekte, aber überprüfen Sie nur die Nachbarn auf Kollision (Methode 3). Die andere Möglichkeit besteht darin, dass Sie immer noch alles durchlaufen, aber prüfen Sie, ob sich die Objekte in der Nähe befinden, bevor Sie die Kollision testen.

for(var i:int = 0; i < objects.length; i++){
        //find object A
        var objectA = objects[i];

        for(var j:int = i + 1; j < objects.length; j++){
            //find object B
            var objectB = objects[j];

            if(objectA.isNear(objectB){
               //they are near - check collision!
               if(objectA.collidesWith(objectB){

               //handle collision logic
              }
            }
        }

    }

Objekte in Kacheldaten speichern (Methode 3) Bei Verwendung eines Kachelsystems ist eine andere Option zulässig. Speichern Sie die Objekte, die sich auf einer bestimmten Kachel befinden, in den Kacheldaten. Überprüfen Sie, auf welcher Kachel sich das Objekt befindet. Die umgebenden Kacheln enthalten alle Objekte, mit denen es kollidieren könnte:

var ObjectA;

for(var i:int = 0; i < 4; i ++){
//check 4 surrounding tiles from object A

   if(Object.currentTile + surroundingTile[i] CONTAINS collidable object){
   //check collision!
    if(objectA.collidesWith(surroundingTile.object){

    //handle collision logic
     }

}
}

Ich versuche immer, die reale Welt als Beispiel zu betrachten. Wenn ich Elemente mit derselben Farbe vergleichen möchte, erscheint es unlogisch, alle Elemente zu überprüfen, auch wenn sie nicht mit der Farbe übereinstimmen (Methode 2, überprüfen Sie jedes Element). Ich würde wahrscheinlich die Gegenstände mit der gleichen Farbe (Objekte, die nahe beieinander liegen) sammeln und diese prüfen (Methode 1), anstatt alles zu überprüfen.

Dies ist kein angemessener Vergleich, da sich die Elemente in der Kollisionsprüfung ständig bewegen, sodass die Reihenfolge vertauscht wird. Das verwirrt mich.

Wäre es effizienter, jedes Element zu überprüfen und so die Belastung durch die Erzeugung einer Reihe von Nachbarn zu verringern?

Oder ist es effizienter, Nachbarn zu finden, um nicht so viele Objekte durchlaufen zu müssen, um die Kollision zu überprüfen?

Das Ändern der Daten auf jeder Kachel scheint ebenfalls sehr intensiv zu sein, daher bin ich mir nicht sicher, ob das eine gute Idee ist.

Ich habe über ein Tower Defense-Spiel nachgedacht, bei dem der Tower Objekte erkennen muss, die sich in Reichweite befinden, bevor er auf sie schießt. Und es scheint einfach albern, alle Gegenstände zu überprüfen, während manchmal überhaupt keine Gegenstände in der Nähe sind.

Ich entschuldige mich für den langen Beitrag und habe immer Probleme, mich selbst zu erklären!

Sie müssen die Anzahl der tatsächlichen Kollisionsprüfungen reduzieren. Ja klar, ich weiß. Gehen wir also näher darauf ein:

Ihr erster Kollisionsprüfungsalgorithmus ohne Optimierung: Wie viele Prüfungen werden in einem Durchgang durchgeführt? Wenn n die Anzahl der Objekte ist, handelt es sich um n * (n-1) Prüfungen. Bei vielen Objekten (> 100) ist dies furchtbar langsam.

Die Überprüfungsmethode Ihres Nachbarn wird nicht viel schneller sein. Wenn Ihre Objekte nicht statisch sind und sich viel bewegen, müssen Sie diese Liste der Nachbarn für jedes Objekt jedes Mal in Ihrer Spielrunde erstellen. Dies ist tatsächlich schlechter als der erste Algorithmus, da Sie n * (n-1) ausführen, um die Nachbarliste zu erstellen, und dann für jedes Objekt prüfen, ob es mit einem seiner Nachbarn kollidiert.

Sie müssen Ihren Spielraum partitionieren. Nehmen wir an, Ihr Spielraum ist 400x400 Pixel breit. Sie können dies in 4 Unterfelder mit einer Größe von jeweils 200 x 200 unterteilen und für jedes Objekt überprüfen, in welches der Unterfelder es gehört (ein Objekt kann sich in mehr als einem Unterfeld befinden). Dann müssen Sie nur noch prüfen, ob die Objekte in jedem Unterraum mit anderen Objekten im selben Unterraum kollidieren.

Die Laufzeitkosten betragen also: n für die Erstellung der 4-Unterraum-Liste + (n / 4) * ((n-1) / 4), was viel besser ist als die vorherigen Laufzeitkosten. Dies kann durch Verkleinern der Teilräume (z. B. 50x50) weiter verringert werden.

Unser Algorithmus sieht nun ungefähr so ​​aus:

for each (object in objects)
  check into which subspace the object belongs

for each (subspace in subspaces)
  for each (object in subspace)
    check object for collision with other objects in same subspace

Dies ähnelt in gewisser Weise Ihrer Kacheldatenidee. Die Unterabstände müssen jedoch nicht die gleiche Größe wie die Kacheln haben.

Wir können einen letzten Schritt tun, um dies mit einem Quadtree weiter zu optimieren. Sei k die Anzahl der Teilräume. Um die Spaces-Objektlisten zu erstellen, führen wir k * n Prüfungen durch, die zu einer Vielzahl von Überprüfungen führen, ob Ihre Spielwelt groß wird.

Um diese Kosten zu senken, verwenden wir einen Quadtree. Ein Quadtree ist ein weiterer Weg, um unseren Spielraum aufzuteilen. Anstatt unseren 400x400-Raum in 64 50x50-Teilräume zu unterteilen und für jedes Objekt zu überprüfen, in welchem ​​der 64 Teilräume es sich derzeit befindet, wird der Spielraum in 4 Teilräume unterteilt, die halb so groß sind wie der Spielraum (200x200), die wiederum unterteilt sind in kleinere Subspaces (100x100), die wiederum in 50x50 Subspaces unterteilt sind. Das ist unser Quadtree.

Wenn wir nun wissen wollen, in welchen 50x50-Unterraum ein Objekt gehört, prüfen wir, in welchen der 200x200-Unterräume es gehört. Dann gehen wir eine Ebene tiefer in unseren Quadtree und vergleichen die 4 100x100 Subspaces, die sich in dem gerade gefundenen 200x200 Subspace befinden. Dies wird wiederholt, bis wir wissen, in welchen 50x50-Unterraum das Objekt gehört. Wie viele Kontrollen waren nun notwendig? 4 für jede Ebene des Quadtrees (Denken Sie daran, dass sich ein Objekt am Rand von zwei Unterbereichen befinden kann). Wir benötigen also 4 * 3 Prüfungen, um ein Objekt dem richtigen 50x50-Unterraum zuzuweisen. Viel besser als 64 Schecks.

Unser Quadtree-Algorithmus benötigt also 4 * 3 * n Prüfungen, um die Unterraumlisten zu erstellen, und dann so etwas wie k * (n / k) Prüfungen, um die Kollisionen jedes Objekts zu überprüfen.