Effiziente kachelbasierte Kollisionserkennung für viele Quadrate?

9

Derzeit arbeite ich an meiner eigenen Version eines auf Kacheln basierenden Spiels (denke an Terraria, aber weniger fantastisch (ich denke, das ist ein Wort? Tut mir leid, wenn es nicht so ist)).

Jedenfalls funktioniert derzeit die Kollisionserkennung (sogar für Eckfälle!), Was für mich ein großer Schritt war. Es ist äußerst erfreulich zu sehen, wie ein Sprite nicht durch einen Block läuft. Aber dann hatte ich die Idee, ein Benchmarking durchzuführen. Schlechte Idee.

1.000 Quadrate, kein Problem. 10.000 Quadrate für 3 Zeichen waren etwas verzögert. 100.000 Felder (wirklich riesige Karte) für 3 Charaktere waren nicht spielbar.

Ich habe das Problem, dass ich nicht einmal die Blöcke berücksichtigen möchte, die zu weit vom Spieler, den Charakteren, Gegenständen usw. entfernt sind, aber ich möchte diese nicht ständig aus dem Speicher laden.

Hier ist mein bisheriger Algorithmus, zögern Sie nicht zu kritisieren.

foreach (Block in level)
{
    if (distance from block to player > a specified amount)
        ignore this block;
    else
    {
        get the intersection depth between the two bounding boxes
        if (depth of intersection != Zero-vector)
        {
            check y size vs x size
            resolve on smallest axis
        }
    }
}

Wie Sie feststellen werden, wächst die Reihenfolge dieses Algorithmus um N Blöcke, wenn die Levelgröße größer wird. Ich möchte nicht einmal Blöcke berücksichtigen, die nicht einmal in der Nähe des Spielers sind.

Ich denke, vielleicht verwenden Sie ein (0,0) bis (mapWidth, mapHeight) Doppelarray von Blöcken anstelle einer Liste und berechnen eine Gefahrenzone in Abhängigkeit von der Position der Person, z. B. wenn die Position des Spielers bei (10, 20) liegt. es wird von (0, 10) bis (20, 30) oder so weiter aussehen.

Alle Gedanken und Überlegungen sind großartig, danke.

Ross
quelle
1
Und willkommen bei stackexchange! :-) Vergessen Sie nicht, die FAQ zu lesen, wenn Sie nicht wissen, wie das gesamte QS- und Reputationssystem funktioniert.
David Gouveia
Sicherlich sind diese Kacheln größer als 16 x 16 Pixel, bei 1920 x 1080 sind das 8.100 Kacheln. Sicher wissen Sie, wo sich die beweglichen Objekte befinden, und Sie können nur Kacheln im Raster überprüfen, die sich möglicherweise in Reichweite befinden (wenn eine 160 * 160 ist und sich die Mitte in Kachel (12,12) befindet, müssen Sie nur zwischen Kacheln (6) prüfen , 6) und (18,18) für insgesamt ~ 150 mögliche Kacheln.). Sicherlich fallen Fliesen unter Schwerkraft nur herunter, und Sie müssen nur nach der nächsten Fliese darunter suchen.
DampeS8N
Denken Sie, dass 16x16 zu klein ist? Es wäre nicht schwer für mich, die Größe der Fliesen zu ändern, da alles, was sich auf die Breite / Höhe bezieht, eine statische Konstante ist. Alles, was ich tun müsste, ist, sie in Paint.NET zu vergrößern, was schön ist, weil es mehr Details hinzufügt.
Ross
Würde es Ihnen etwas ausmachen, Ihren Kollisionscode zu teilen? : /
Asche999

Antworten:

7

Ja, du denkst richtig. Sie sollten ein 2D-Array von Kacheln verwenden, da Sie damit Kacheln nach Position indizieren können.

Block[,] level = new Block[width, height];

Und da der Spieler nur mit den umgebenden Plättchen kollidieren kann, ist die Anzahl der Kollisionsprüfungen, die Sie durchführen müssen, sehr gering. Dies hängt natürlich von der Größe des Spielers ab. Das Platformer-Beispiel macht es so:

int leftTile = (int)Math.Floor((float)characterBounds.Left / tileWidth);
int rightTile = (int)Math.Ceiling(((float)characterBounds.Right / tileWidth)) - 1;
int topTile = (int)Math.Floor((float)characterBounds.Top / tileHeight);
int bottomTile = (int)Math.Ceiling(((float)characterBounds.Bottom / tileHeight)) - 1;

for (int y = topTile; y <= bottomTile; ++y)
{
    for (int x = leftTile; x <= rightTile; ++x)
    {
        // Handle collisions with the tile level[x,y] just like you were doing!
    }
}

Überprüfen Sie das Beispiel, wenn Sie immer noch Probleme haben.

David Gouveia
quelle
Dies ist ein sehr netter kleiner Algorithmus, von dem ich noch nicht einmal gehört habe (ich hätte es tun sollen, aber ich behaupte Unwissenheit). Danke!
Ross
@ Ross Wirklich? Sie wären überrascht, wie ähnlich Ihre Lösung der Probe ist. :-) Abzüglich des Listenteils ist alles andere ziemlich identisch (Begrenzungsrahmen kreuzen, Schnitttiefe ermitteln, Auflösung auf kleinster Achse).
David Gouveia
1
Oh Mann, ich habe es nur angeschaut. >. <Ich wünschte, ich wüsste das vor 2 Tagen !! Nun, ich bin neu bei XNA, aber ich habe mich mit 2D-Grafiken beschäftigt (nur OpenGL, nicht sehr viel Spielprogrammierung). Ich denke, ich sollte zuerst mehr Ressourcen überprüfen, bevor ich mit dem Codieren anfange.
Ross
1

Ich denke meine Antwort wäre deine Antwort! ;-);

Wenn Sie Spielerposition (und -größe) haben, können Sie Indizes der umgebenden Kacheln berechnen (die die einzigen sind, die im Detail überprüft werden). Auf diese Weise sollte es unerheblich sein, wie groß Ihre Karte ist. Es hängt nur von der tatsächlichen Größe Ihres Spielers ab, sodass mehr potenzielle Kacheln überprüft werden müssen.

Vielleicht lesen Sie das Tutorial über Kollisionen bei riemers.net, wenn Sie es noch nicht getan haben.

Prinz Charles
quelle
Ich habe von Riemer gehört, bin aber nie zum Schauen gekommen, danke!
Ross
1

Wenn Sie mit einer großen Anzahl von Kollisionen arbeiten, möchten Sie normalerweise eine erweiterte Struktur verwenden , z. B. einen Quadtree oder eine Hashmap, um nach diesen Kollisionen zu suchen.

Da Kacheln statisch sind, würde ich die Verwendung eines Quadtree empfehlen. Ein Quad-Baum besteht aus Quads. Jedes Quad besteht aus vier Rechtecken und jedes dieser Rechtecke sind Quads. Dies wird rekursiv bis zu einer bestimmten Größe fortgesetzt. Jedes Quad kann eine Liste von Kacheln enthalten, die sich in diesem Bereich des Bildschirms befinden. Auf diese Weise können Sie nach Kollisionen suchen

  1. Beschränken Sie die Kontrollen auf diejenigen in unmittelbarer Nähe
  2. Beschränken Sie Überprüfungen nur auf Objekte, die sich bewegen

Wenn Sie nicht einmal Kacheln außerhalb des Bildschirms betrachten möchten, können Sie so etwas tun

public bool CheckCollision(myPosition) {
    if(quadNodes.Count > 0) {
        // This is not a leaf, keep checking
        foreach(Quad node in quadNodes) {
            if(node.Position is insideViewport && nearPlayer)
                // Continue recursion
            }
        }
    }
    else {
        // This is a leaf, do checks
        foreach(Tile tile in tileList) {
            if(collision)
                return true;
        }
        return false;
    }
}
Mike Cluck
quelle
Hmm, ich habe von Octrees in der 3D-Kollisionserkennung gehört, aber noch nie eine erweiterte Datenstruktur für die 2D-Kollisionserkennung gesehen. Vielen Dank!
Ross
1
Da sein Spiel (unter der Annahme von Terraria) aus gleichmäßig verteilten Plättchen besteht, wäre die Verwendung eines Gitters viel einfacher und schneller als ein Quadtree. Ein Quadtree funktioniert besser für komplexere Welten, in denen ein Gitter schwer zu passen wäre und alles eine beliebige Größe hat.
David Gouveia
1
Sie haben Recht, wenn es sich um ein rein gitterbasiertes Spiel handelt, bis hin zu den Charaktergrößen. Ich weiß, dass es in Terraria auch Monster gibt, die nicht ohne weiteres in ein Rasterformat passen. Ich ging davon aus, dass die Grundwelt aus Kacheln besteht, aber andere Objekte wären anders und sie könnten sie in einer ähnlichen Struktur speichern, um zu vermeiden, dass eine andere gebaut wird. Ich nehme an, sie könnten ein Gitter für Kacheln verwenden als eine andere Struktur (falls erforderlich) für andere beliebige Objekte.
Mike Cluck
1
Das wollte ich vorschlagen :) Das Gitter sollte verwendet werden, um Kollisionen mit dem Gelände zu behandeln, während ein Quadtree verwendet werden könnte, um Kollisionen zwischen Objekten zu behandeln.
David Gouveia
Wahr. Im Moment hat jeder Begrenzungsrahmen 2 ^ Leistungsabmessungen. Dies erleichtert mir die Kollisionserkennung erheblich. Ein Raster würde vorerst meinen Bedürfnissen entsprechen.
Ross