Effizientes Auslesen von Off-Screen-Objekten auf einer 2D-Karte von oben nach unten

8

Ich weiß, dass Effizienz der Schlüssel zur Spielprogrammierung ist, und ich habe einige Erfahrungen mit dem Rendern einer "Karte" früher gemacht, aber wahrscheinlich nicht auf die beste Weise.

Für ein 2D-TopDown-Spiel: (Rendern Sie einfach die Texturen / Kacheln der Welt, sonst nichts)

Angenommen, Sie haben eine Karte von 1000 x 1000 (Kacheln oder was auch immer). Wenn sich die Kachel nicht in der Ansicht der Kamera befindet, sollte sie nicht gerendert werden - so einfach ist das. Sie müssen keine Kachel rendern, die nicht angezeigt wird. Da Ihre Karte jedoch 1000 x 1000 Objekte enthält oder weniger, möchten Sie wahrscheinlich nicht alle 1000 * 1000 Kacheln durchlaufen, um zu sehen, ob sie gerendert werden sollen oder nicht.

Frage: Wie lässt sich diese Effizienz am besten umsetzen? Damit es "schnell / schneller" bestimmen kann, welche Kacheln gerendert werden sollen?

Außerdem baue ich mein Spiel nicht um Kacheln, die mit einem SpriteBatch gerendert wurden, sodass es keine Rechtecke gibt. Die Formen können unterschiedliche Größen haben und mehrere Punkte haben, z. B. ein gekrümmtes Objekt mit 10 Punkten und eine Textur innerhalb dieser Form.

Frage: Wie stellen Sie fest, ob sich diese Art von Objekten "in" der Ansicht der Kamera befindet?

Mit einem 48x48-Rechteck ist das ganz einfach. Sehen Sie nur, ob sich X + Breite oder Y + Höhe in der Ansicht der Kamera befindet. Anders mit mehreren Punkten.

Einfach ausgedrückt, wie Sie den Code und die Daten effizient verwalten können, um nicht gleichzeitig eine Million Objekte durchlaufen / durchlaufen zu müssen.

Deukalion
quelle

Antworten:

6

Wie für komplexe Objekte Ich denke , der beste Weg , nur um sie zu umgebenden Rechtecken zu reduzieren ist, und prüfen Sie, ob das Rechteck innerhalb des Ansichtsfensters ist. Selbst wenn Sie eine Textur rendern, die (aufgrund ihrer Form) nicht sichtbar ist, ist sie wahrscheinlich schneller als ein komplexerer Erkennungsalgorithmus.

Um große Karten effizient zu handhaben, sollten Sie Ihre Karte in größerem Maßstab unterteilen, z. B. 10 x 10. Dann überprüfen Sie Ihre Ansichtsfenster-Kreuzung. Im schlimmsten Fall trifft es 4 dieser 'Regionen', was zu (100x100) * 4 = 40K Objekten führt. Dies ist ein vereinfachtes Beispiel. Für eine reale Verwendung sollten Sie die Quadtree-Struktur in Betracht ziehen, die für solche Unterteilungen und die Kollisionserkennung besonders effizient ist (die Sichtbarkeitsprüfung des Ansichtsfensters ist im Grunde eine Kollisionsprüfung zwischen Ansichtsfenster und Sprite).

Petr Abdulin
quelle
Die Verwendung eines Quadtree für Kartenkacheln ist ein wenig übertrieben ... da Sie nur die richtigen Indizes der Kacheln berechnen können, die gerendert werden müssen. Außerdem sind Regionen einfacher, und ich würde empfehlen, sie für die erste Optimierungsrunde zu verwenden. Es wird später helfen, Quadtrees zu verstehen und zu verwenden :) +1.
Liosan
@Liosan Es ist nicht klar, ob diese 'Kacheln' die gleiche Größe haben, sonst wäre die Lösung natürlich ziemlich trivial.
Petr Abdulin
Sie haben Recht, Deukalion schrieb sogar einen Kommentar zu einer anderen Antwort: "Und eine Kachel hat nicht immer genau die gleiche Größe."
Liosan
Funktioniert QuadTree überhaupt mit etwas anderem als exakten Regionsgrößen? Jeder Bereich sollte keine Rechteckgröße haben, da das Objekt innerhalb des Rechtecks ​​nicht so ist, dass es kein Rechteck bildet. Es handelt sich also NICHT um ein gerendertes 1024 x 1024 Pixel-Raster, dessen Form möglicherweise sehr orthodox ist.
Deukalion
Nun, ich denke nein (ich habe selbst keine Quadtrees verwendet), aber das spielt keine Rolle, wenn Sie alles in den umgebenden Rechteckbereich einfügen können. Wenn quadtree aus irgendeinem Grund nicht für Ihre Aufgabe geeignet ist, müssen Sie höchstwahrscheinlich einen ähnlichen Ansatz verwenden.
Petr Abdulin
3

Wenn Sie viele mobile Objekte haben, sollten Sie diese anhand ihrer Koordinaten in einer mehrdimensionalen Baumstruktur speichern. Auf diese Weise können Sie effizient eine Liste aller Objekte abrufen, die sich in einem bestimmten Rechteck befinden. Sie können sie sogar nach ihren x- oder y-Koordinaten sortieren lassen, was für die Zeichnungsreihenfolge wichtig ist, wenn sich Objekt-Sprites überlappen.

Dies ist auch sehr praktisch für die Kollisionserkennung.

Weitere Informationen finden Sie im Wikipedia-Artikel über kd-Bäume .

Wenn 2D-Bäume für Sie zu kompliziert sind, gibt es auch eine einfachere, aber nicht viel weniger effektive Alternative: Speichern Sie die Objekte als untergeordnete Elemente der Kacheln. Wenn Sie ein Objekt verschieben, entfernen Sie es aus der Objektliste der alten Kachel und fügen es in die Objektliste des neuen ein. Wenn Sie die Objekte zeichnen, durchlaufen Sie erneut die Kacheln im Ansichtsfenster und rufen deren Objekte ab. Dann sortieren Sie sie alle nach y-Koordinaten und zeichnen sie.

Philipp
quelle
1

Ich weiß nicht, ob es der beste Weg ist, aber so lerne ich es:

Sie haben eine zweidimensionale Anordnung von "Kacheln"

public Tile tilemap[][];

Wenn Sie die Position der "Kamera" mit einem Vector2 festlegen, rendern Sie nur das, was sich in der Szene befindet. Das große Rechteck ist das, was Sie auf dem Bildschirm sehen können. Es ist nutzlos, den Rest der Szene zu zeichnen.

Jetzt müssen Sie die Offsets abrufen, vorausgesetzt, Ihre Kamera soll sich in der Mitte der Szene befinden:

offsetX = (graphics().width() / 2 - Math.round(cam.Position().X));
offsetX = Math.min(offsetX, 0);
offsetX = Math.max(offsetX, graphics().width() / 2 - mapWidth);
offsetY = (graphics().height()) / 2 - Math.round(cam.getPosition().Y);
offsetY = Math.min(offsetY, 0);
offsetY = Math.max((graphics().height() / 2 - mapHeight), offsetY);

In welchem ​​Teil des Arrays beginnen und enden die sichtbaren Kacheln?

firstTileX = pixelsToTiles(-offsetX);

lastTileX = firstTileX + pixelsToTiles(graphics().width());

firstTileY = pixelsToTiles(-offsetY);

lastTileY = firstTileY + pixelsToTiles(graphics().height());

int pixelsToTiles(int pixels) {
    return (int) Math.floor((float) pixels / Tile.getHeight());
}

und in Ihrer Zeichenmethode durchlaufen Sie einfach den sichtbaren Teil des Arrays:

   for (int x = firstTileX; x < lastTileX; x++) {
        for (int y = firstTileY; y < lastTileY; y++) {
              Vector2 position = new Vector2(tilesToPixelsX(x) + offsetX,
                        tilesToPixelsY(y) + offsetY);
              tilemap[x][y].Draw(surf, position);
        }
    }
riktothepast
quelle
1
Ja, aber Fliesen waren ein Beispiel, um die Dinge zu vereinfachen. Ich habe bereits geschrieben, dass ich den Prozess des Bestimmens verstehe, ob sich ein Objekt bereits in einer "Ansicht" mit Rechteck- / Titelform befindet, nicht mit fortgeschritteneren Formen mit mehreren Punkten. Außerdem suchte ich nach etwas, das mich dazu bringt, bei jeder Update () -Methode in XNA "nicht" alle Kacheln durchzugehen. Wenn ich eine "GROSSE" Karte mit ungefähr 10000 Objekten (Formen von 3 Punkten und mehr) habe, ist dies nicht der richtige Weg. Bei jedem Update muss ich eine Schleife von 10000 Updates und ebenso viele Berechnungen ausführen. Ich benutze keine Fliesen und das ist nicht effizient; Ich war dort.
Deukalion
Und eine Kachel hat nicht immer genau die gleiche Größe, also kann ich das auch nicht. Ich benutze keine Rechtecke.
Deukalion
Einfach ausgedrückt: Ich möchte nur Objekte durchlaufen, die gerendert werden sollen, nicht Objekte, die überhaupt nicht gerendert werden sollten.
Deukalion
@Deukalion Riktothepasts Code durchläuft nur Kacheln, die im Begrenzungsrahmen des Bildschirms angezeigt werden sollen (obwohl dies nicht sehr klar ist). Dieselbe grundlegende Technik kann verwendet werden, um ein beliebiges Rechteck von Kacheln innerhalb eines bestimmten Satzes von Koordinaten zu durchlaufen.
DampeS8N
0

Sie können eine Bitmap haben, die die gesamte Szene darstellt, aber nicht angezeigt wird. Und dann eine angezeigte Bildschirm-Kamera-Bitmap, die nur aus der gesamten Szene zeichnet, aber nur den Teil, der angezeigt werden muss.

mrall
quelle