Wie haben sie das gemacht: Millionen Fliesen in Terraria

45

Ich habe eine Spiel-Engine entwickelt, die Terraria ähnelt , hauptsächlich als Herausforderung, und obwohl ich das meiste herausgefunden habe, kann ich nicht wirklich meinen Kopf darum legen, wie sie mit den Millionen von interagierbaren / erntbaren Kacheln umgeht Das Spiel hat auf einmal. Wenn ich in meiner Engine ungefähr 500.000 Kacheln erstelle , was 1/20 der in Terraria möglichen Kacheln entspricht, sinkt die Framerate von 60 auf ungefähr 20, obwohl ich immer noch nur die Kacheln in der Ansicht rendere. Wohlgemerkt, ich mache nichts mit den Kacheln, sondern behalte sie nur in Erinnerung.

Update : Code hinzugefügt, um zu zeigen, wie ich Dinge mache.

Dies ist Teil einer Klasse, die die Kacheln handhabt und zeichnet. Ich vermute, der Täter ist der "foreach" -Teil, der alles durchläuft, sogar leere Indizes.

...
    public void Draw(SpriteBatch spriteBatch, GameTime gameTime)
    {
        foreach (Tile tile in this.Tiles)
        {
            if (tile != null)
            {
                if (tile.Position.X < -this.Offset.X + 32)
                    continue;
                if (tile.Position.X > -this.Offset.X + 1024 - 48)
                    continue;
                if (tile.Position.Y < -this.Offset.Y + 32)
                    continue;
                if (tile.Position.Y > -this.Offset.Y + 768 - 48)
                    continue;
                tile.Draw(spriteBatch, gameTime);
            }
        }
    }
...

Hier ist auch die Tile.Draw-Methode, die auch ein Update verträgt, da jede Kachel vier Aufrufe der SpriteBatch.Draw-Methode verwendet. Dies ist Teil meines Autotiling-Systems, was bedeutet, dass jede Ecke in Abhängigkeit von benachbarten Kacheln gezeichnet wird. texture_ * sind Rechtecke, die bei der Levelerstellung einmal gesetzt werden, nicht bei jedem Update.

...
    public virtual void Draw(SpriteBatch spriteBatch, GameTime gameTime)
    {
        if (this.type == TileType.TileSet)
        {
            spriteBatch.Draw(this.texture, this.realm.Offset + this.Position, texture_tl, this.BlendColor);
            spriteBatch.Draw(this.texture, this.realm.Offset + this.Position + new Vector2(8, 0), texture_tr, this.BlendColor);
            spriteBatch.Draw(this.texture, this.realm.Offset + this.Position + new Vector2(0, 8), texture_bl, this.BlendColor);
            spriteBatch.Draw(this.texture, this.realm.Offset + this.Position + new Vector2(8, 8), texture_br, this.BlendColor);
        }
    }
...

Jede Kritik oder Anregung zu meinem Code ist willkommen.

Update : Lösung hinzugefügt.

Hier ist die letzte Level.Draw-Methode. Die Level.TileAt-Methode überprüft einfach die eingegebenen Werte, um OutOfRange-Ausnahmen zu vermeiden.

...
    public void Draw(SpriteBatch spriteBatch, GameTime gameTime)
    {
        Int32 startx = (Int32)Math.Floor((-this.Offset.X - 32) / 16);
        Int32 endx = (Int32)Math.Ceiling((-this.Offset.X + 1024 + 32) / 16);
        Int32 starty = (Int32)Math.Floor((-this.Offset.Y - 32) / 16);
        Int32 endy = (Int32)Math.Ceiling((-this.Offset.Y + 768 + 32) / 16);

        for (Int32 x = startx; x < endx; x += 1)
        {
            for (Int32 y = starty; y < endy; y += 1)
            {
                Tile tile = this.TileAt(x, y);
                if (tile != null)
                    tile.Draw(spriteBatch, gameTime);

            }
        }
    }
...
William Mariager
quelle
2
Sind Sie absolut sicher, dass Sie nur das rendern, was in der Ansicht der Kamera dargestellt wird?
Cooper
5
Die Framerate sinkt von 60 auf 20 fps, nur wegen des zugewiesenen Speichers? Es ist sehr unwahrscheinlich, dass etwas nicht stimmt. Um welche Plattform handelt es sich? Verschiebt das System den virtuellen Speicher auf die Festplatte?
Maik Semder
6
@Drackir In diesem Fall würde ich sagen, es ist falsch, wenn es überhaupt eine Kachelklasse gibt, ein Array mit Ganzzahlen geeigneter Länge, und wenn es eine halbe Million Objekte gibt, ist OO-Overhead kein Witz. Ich nehme an, dass es möglich ist, mit Objekten zu tun, aber worum geht es? Ein Integer-Array ist kinderleicht zu handhaben.
aaaaaaaaaaa
3
Autsch! Durchlaufen aller Kacheln und Aufrufen Zeichnen Sie vier Mal auf jedes Kacheln, das angezeigt wird . Hier sind definitiv einige Verbesserungen möglich ...
thedaian
11
Sie brauchen nicht die ganze Partitionierung, über die weiter unten gesprochen wird, um nur das zu rendern, was gerade angezeigt wird. Es ist eine Tilemap. Es ist bereits in ein reguläres Raster unterteilt. Berechnen Sie einfach die Kachel oben links und unten rechts und zeichnen Sie alles in dieses Rechteck.
Blecki

Antworten:

56

Durchlaufen Sie beim Rendern alle 500.000 Kacheln? Wenn ja, wird das wahrscheinlich einen Teil Ihrer Probleme verursachen. Wenn Sie beim Rendern eine halbe Million Kacheln durchlaufen und eine halbe Million Kacheln, wenn Sie die 'Update'-Häkchen auf ihnen ausführen, durchlaufen Sie eine Million Kacheln pro Frame.

Offensichtlich gibt es Möglichkeiten, dies zu umgehen. Sie können Ihre Aktualisierungsticks auch beim Rendern ausführen und so die Hälfte der Zeit sparen, die Sie für das Durchlaufen all dieser Kacheln aufgewendet haben. Aber das verbindet Ihren Rendering-Code und Ihren Update-Code zu einer Funktion und ist im Allgemeinen eine SCHLECHTE IDEE .

Sie können die Kacheln auf dem Bildschirm verfolgen und diese nur durchlaufen (und rendern). Abhängig von der Größe Ihrer Kacheln und der Bildschirmgröße kann dies leicht die Anzahl der Kacheln verringern, die Sie durchlaufen müssen, und das spart einiges an Verarbeitungszeit.

Schließlich, und vielleicht ist die beste Option (die meisten großen Weltspiele tun dies), Ihr Terrain in Regionen aufzuteilen. Teilen Sie die Welt in Teile von beispielsweise 512 x 512 Kacheln auf und laden / entladen Sie die Regionen, wenn der Spieler sich einer Region nähert oder sich dieser nähert. Dies erspart es Ihnen auch, weit entfernte Kacheln durchlaufen zu müssen, um irgendeine Art von 'Update'-Tick durchzuführen.

(Wenn Ihre Engine keine Art von Update-Tick für Kacheln durchführt, können Sie den Teil dieser Antworten, in dem diese erwähnt werden, natürlich ignorieren.)

thedaian
quelle
5
Der Regionsteil scheint interessant zu sein, wenn ich mich recht entsinne, so funktioniert Minecraft. Es funktioniert jedoch nicht mit der Entwicklung des Terrains in Terraria, auch wenn Sie sich nicht in der Nähe befinden, wie z. B. Gras ausbreiten, Kakteen wachsen und dergleichen. Bearbeiten : Es sei denn, sie wenden die seit der letzten Aktivierung der Region verstrichene Zeit an und führen dann alle Änderungen durch, die in diesem Zeitraum vorgenommen worden wären. Das könnte tatsächlich funktionieren.
William Mariager
2
Minecraft verwendet definitiv Regionen (und die späteren Ultima-Spiele haben es getan, und ich bin mir ziemlich sicher, dass viele der Bethesda-Spiele dies tun). Ich bin mir nicht so sicher, wie Terraria mit dem Gelände umgeht, aber sie wenden wahrscheinlich entweder die verstrichene Zeit auf eine "neue" Region an oder sie speichern die gesamte Karte im Speicher. Letzteres würde eine hohe RAM-Auslastung erfordern, aber die meisten modernen Computer könnten damit umgehen. Möglicherweise gibt es auch andere Optionen, die nicht erwähnt wurden.
Thedaian
2
@MindWorX: Es würde nicht immer funktionieren, alle Aktualisierungen beim Neuladen durchzuführen. Nehmen wir an, Sie haben eine ganze Menge unfruchtbaren Gebiets und dann Gras. Du gehst ewig weg und gehst dann auf das Gras zu. Wenn der Block mit dem Gras geladen wird, holt er auf und breitet sich in diesem Block aus, aber er breitet sich nicht in die näheren Blöcke aus, die bereits geladen sind. Solche Dinge verlaufen jedoch VIEL langsamer als das Spiel - überprüfen Sie nur eine kleine Teilmenge der Kacheln in einem Aktualisierungszyklus, und Sie können entferntes Terrain live machen, ohne das System zu laden.
Loren Pechtel
1
Als Alternative (oder Ergänzung) zum "Aufholen", wenn sich eine Region dem Spieler nähert, können Sie stattdessen eine separate Simulation durchführen lassen, die jede entfernte Region durchläuft und diese langsamer aktualisiert. Sie können entweder für jeden Frame Zeit reservieren oder ihn in einem separaten Thread ausführen lassen. So können Sie beispielsweise die Region, in der sich der Player befindet, sowie die 6 angrenzenden Regionen in jedem Frame aktualisieren, aber auch 1 oder 2 zusätzliche Regionen aktualisieren.
Lewis Wakeford
1
Für alle, die sich fragen, speichert Terraria seine gesamten Kacheldaten in einem 2D-Array (maximale Größe 8400x2400). Anschließend können Sie mithilfe einer einfachen Mathematik entscheiden, welcher Abschnitt der Kacheln gerendert werden soll.
FrenchyNZ
4

Ich sehe hier einen großen Fehler, der durch keine der Antworten behoben wird. Natürlich sollten Sie niemals mehr Kacheln zeichnen und iterieren, als Sie benötigen. Weniger offensichtlich ist, wie Sie die Kacheln tatsächlich definieren. Wie ich sehen kann, hast du eine Kachelklasse gemacht, das habe ich immer auch gemacht, aber es ist ein großer Fehler. Sie haben wahrscheinlich alle möglichen Funktionen in dieser Klasse und das verursacht eine Menge unnötiger Verarbeitung.

Sie sollten nur wiederholen, was für die Verarbeitung wirklich erforderlich ist. Überlegen Sie sich also, was Sie für die Fliesen tatsächlich benötigen. Zum Zeichnen brauchst du nur eine Textur, aber du willst nicht über ein tatsächliches Bild iterieren, da diese groß zu verarbeiten sind. Sie könnten einfach ein int [,] oder sogar ein vorzeichenloses Byte [,] erstellen (wenn Sie nicht mehr als 255 Kacheltexturen erwarten). Alles, was Sie tun müssen, ist über diese kleinen Arrays zu iterieren und eine switch- oder if-Anweisung zu verwenden, um die Textur zu zeichnen.

Was müssen Sie also aktualisieren? Der Typ, die Gesundheit und der Schaden scheinen ausreichend. All dies kann in Bytes gespeichert werden. Warum also nicht eine Struktur wie diese für die Update-Schleife erstellen:

struct TileUpdate
{
public byte health;
public byte type;
public byte damage;
}

Sie können den Typ auch zum Zeichnen der Kachel verwenden. Sie können also dieses Element von der Struktur trennen (ein eigenes Array erstellen), damit Sie nicht über die unnötigen Gesundheits- und Schadensfelder in der Zeichenschleife iterieren. Zum Aktualisieren sollten Sie einen größeren Bereich als nur Ihren Bildschirm berücksichtigen, damit sich die Spielwelt lebendiger anfühlt (Einheiten ändern ihre Position außerhalb des Bildschirms). Zum Zeichnen von Dingen benötigen Sie jedoch nur die sichtbaren Kacheln.

Wenn Sie die obige Struktur beibehalten, werden nur 3 Bytes pro Kachel benötigt. Aus Speicher- und Speichergründen ist dies also ideal. Für die Verarbeitungsgeschwindigkeit spielt es keine Rolle, ob Sie int oder byte oder sogar long int verwenden, wenn Sie ein 64-Bit-System haben.

Madmenyo
quelle
1
Ja, spätere Iterationen meiner Engine haben sich dazu entwickelt, dies zu nutzen. Hauptsächlich, um den Speicherverbrauch zu reduzieren und die Geschwindigkeit zu erhöhen. ByRef-Typen sind im Vergleich zu einem mit ByVal-Strukturen gefüllten Array langsam. Trotzdem ist es gut, dass Sie dies zur Antwort hinzugefügt haben.
William Mariager
1
Ja, ich bin darauf gestoßen, als ich nach zufälligen Algorithmen gesucht habe. Sie haben sofort bemerkt, dass Sie Ihre eigene Kachelklasse in Ihrem Code verwendet haben. Es ist ein sehr häufiger Fehler, wenn Sie neu sind. Schön, dass Sie noch aktiv sind, seit Sie dies vor 2 Jahren gepostet haben.
Madmenyo
3
Du brauchst weder healthnoch damage. Sie können einen kleinen Puffer mit den zuletzt ausgewählten Plättchenpositionen und den jeweiligen Schäden aufbewahren. Wenn ein neues Plättchen ausgewählt wird und der Puffer voll ist, rollen Sie das älteste Plättchen ab, bevor Sie das neue Plättchen hinzufügen. Dies begrenzt die Anzahl der Kacheln, die Sie gleichzeitig abbauen können, aber es gibt trotzdem eine Grenze (ungefähr #players * pick_tile_size). Sie können diese Liste pro Spieler behalten, wenn dies einfacher ist. Größe ist wichtig für Geschwindigkeit; Kleinere Größe bedeutet mehr Kacheln in jeder CPU-Cacheline.
Sean Middleditch
@ SeanMiddleditch Sie haben Recht, aber das war nicht der Punkt. Der Punkt war, anzuhalten und zu überlegen, was Sie tatsächlich benötigen, um die Kacheln auf dem Bildschirm zu zeichnen und Ihre Berechnungen durchzuführen. Da das OP eine ganze Klasse verwendete, habe ich ein einfaches Beispiel angefertigt, das einen großen Beitrag zum Lernfortschritt leistet. Schalte jetzt mein Thema für die Pixeldichte frei, du bist offensichtlich ein Programmierer, der versucht, diese Frage mit dem Auge eines CG-Künstlers zu betrachten. Da diese Seite ist auch für CG für Spiele afaik.
Madmenyo
2

Es gibt verschiedene Codierungstechniken, die Sie verwenden können.

RLE: Sie beginnen also mit einer Koordinate (x, y) und zählen dann, wie viele gleiche Kacheln nebeneinander (in Längsrichtung) entlang einer der Achsen existieren. Beispiel: (1,1,10,5) würde bedeuten, dass ab der Koordinate 1,1 10 Kacheln des Kacheltyps 5 nebeneinander liegen.

Das massive Array (Bitmap): Jedes Element des Arrays enthält den Kacheltyp, der sich in diesem Bereich befindet.

EDIT: Ich bin gerade auf diese hervorragende Frage gestoßen: Zufällige Seed-Funktion für die Kartengenerierung?

Der Perlin-Geräuschgenerator scheint eine gute Antwort zu sein.

Sam Axe
quelle
Ich bin mir nicht sicher, ob Sie die gestellte Frage beantworten, da Sie über Codierung (und Perlin-Rauschen) sprechen und die Frage sich anscheinend mit Leistungsproblemen befasst.
thedaian
1
Wenn Sie die richtige Codierung (wie Perlin-Rauschen) verwenden, können Sie sich nicht darum kümmern, alle diese Kacheln gleichzeitig im Speicher zu halten. Stattdessen bitten Sie Ihren Encoder (Rauschgenerator), Ihnen mitzuteilen, was an einer bestimmten Koordinate angezeigt werden soll. Hier besteht ein Gleichgewicht zwischen CPU-Zyklen und Speichernutzung, und ein Rauschgenerator kann bei diesem Balanceakt helfen.
Sam Axe
2
Das Problem hierbei ist, dass, wenn Sie ein Spiel erstellen, mit dem Benutzer das Terrain irgendwie ändern können, die Verwendung eines Geräuschgenerators zum "Speichern" dieser Informationen nicht funktioniert. Außerdem ist die Erzeugung von Rauschen ziemlich teuer, ebenso wie die meisten Codierungstechniken. Es ist besser, CPU-Zyklen für das eigentliche Gameplay (Physik, Kollisionen, Beleuchtung usw.) zu sparen. Perlin-Rauschen eignet sich hervorragend für die Geländegenerierung, und die Codierung ist gut für das Speichern auf der Festplatte.
thedaian
Sehr gute Idee, aber wie bei Thedaian wird das Terrain vom Benutzer interagiert, was bedeutet, dass ich keine Informationen mathematisch abrufen kann. Ich werde mir sowieso das Perlin-Rauschen ansehen, um das Grundgelände zu erzeugen.
William Mariager
1

Sie sollten die Tilemap wahrscheinlich wie bereits vorgeschlagen partitionieren. Zum Beispiel mit Quadtree-Struktur , um eventuelle Verarbeitungen (z. B. einfaches Durchschleifen) der unnötigen (nicht sichtbaren) Kacheln zu vermeiden. Auf diese Weise verarbeiten Sie nur das, was möglicherweise verarbeitet werden muss, und eine Vergrößerung des Datasets (Kachelzuordnung) verursacht keine praktischen Leistungseinbußen. Vorausgesetzt natürlich, der Baum ist gut ausbalanciert.

Ich möchte nicht langweilig klingen, indem ich das "Alte" wiederhole, aber wenn Sie optimieren, denken Sie immer daran, die von Ihrer Toolchain / Ihrem Compiler unterstützten Optimierungen zu verwenden, und experimentieren Sie ein wenig damit. Und ja, vorzeitige Optimierung ist die Wurzel allen Übels. Vertrauen Sie Ihrem Compiler, er weiß es in den meisten Fällen besser als Sie, aber immer, immerMessen Sie zweimal und verlassen Sie sich niemals auf Schätzungen. Es geht nicht darum, den schnellsten Algorithmus schnell zu implementieren, solange Sie nicht wissen, wo sich der tatsächliche Engpass befindet. Aus diesem Grund sollten Sie einen Profiler verwenden, um die langsamsten (heißen) Pfade des Codes zu finden und sich darauf zu konzentrieren, sie zu beseitigen (oder zu optimieren). Niedrige Kenntnisse der Zielarchitektur sind häufig erforderlich, um das gesamte Hardwareangebot auszuschöpfen. Untersuchen Sie daher die CPU-Caches und erfahren Sie, was ein Branch Predictor ist. Sehen Sie, was Ihr Profiler Ihnen über Cache / Branch Hits / Misses sagt. Und wie die Verwendung einer Baumdatenstruktur zeigt, ist es besser, intelligente Datenstrukturen und dumme Algorithmen zu haben, als umgekehrt. Daten stehen an erster Stelle, wenn es um Leistung geht. :)

zxcdw
quelle
+1 für "vorzeitige Optimierung ist die Wurzel allen Übels" Ich bin schuld daran :(
Thedaian
16
-1 ein Quadtree? Etwas überfordert? Wenn in einem 2D-Spiel wie diesem alle Kacheln die gleiche Größe haben (was für Terrarien gilt), ist es extrem einfach herauszufinden, welche Kacheln auf dem Bildschirm angezeigt werden - es ist nur die oberste linke Ecke (auf dem Bildschirm) der Kacheln ganz unten rechts.
BlueRaja - Danny Pflughoeft
1

Geht es nicht nur um zu viele Draw Calls? Wenn Sie alle Ihre Kartenkacheln-Texturen in einem einzigen Bild-Kacheln-Atlas platzieren, erfolgt beim Rendern kein Texturwechsel. Und wenn Sie alle Ihre Kacheln in ein einzelnes Netz stapeln, sollte es in einem Ziehungsaufruf gezogen werden.

Über die dynamische Werbung ... Vielleicht ist Quad Tree keine so schlechte Idee. Unter der Annahme, dass Kacheln in Blatt- und Nicht-Blatt-Knoten nur gestapelte Netze von ihren Kindern sind, sollte die Wurzel alle Kacheln enthalten, die in einem Netz gestapelt sind. Das Entfernen einer Kachel erfordert Knotenaktualisierungen (erneutes Batching des Netzes) bis zur Wurzel. Aber auf jeder Baumebene wird nur 1/4 des Netzes re-batched, was nicht so viel sein sollte. 4 * tree_height mesh joins?

Oh, und wenn Sie diesen Baum im Beschneidungsalgorithmus verwenden, werden Sie nicht immer den Stammknoten, sondern einige seiner untergeordneten Knoten rendern, sodass Sie nicht einmal alle Knoten bis zum Stammknoten aktualisieren / neu stapeln müssen, sondern bis zu dem (Nicht-Blatt-) Knoten, den Sie sind Rendering im Moment.

Nur meine Gedanken, kein Code, vielleicht ist es Unsinn.

Ankunft
quelle
0

@arrival ist richtig. Das Problem ist der Ziehungscode. Sie erstellen ein Array von 4 * 3000 + Zeichen- Quad- Befehlen (24000+ Zeichen- Polygon- Befehle) pro Frame. Dann werden diese Befehle verarbeitet und an die GPU weitergeleitet. Das ist ziemlich schlimm.

Es gibt einige Lösungen.

  • Rendern Sie große Blöcke (z. B. Bildschirmgröße) von Kacheln in eine statische Textur und zeichnen Sie sie in einem einzigen Aufruf.
  • Verwenden Sie Shader, um die Kacheln zu zeichnen, ohne die Geometrie für jeden Frame an die GPU zu senden (dh speichern Sie die Kachelzuordnung auf der GPU).
Ark-Kun
quelle
0

Sie müssen die Welt in Regionen aufteilen. Perlin Noise Terrain Generation kann ein gemeinsames Saatgut verwenden, sodass das Saatgut auch dann einen Teil des Noise Algo bildet, wenn die Welt nicht vorgeneriert ist, wodurch das neuere Terrain in die vorhandenen Teile integriert wird. Auf diese Weise müssen Sie nicht mehr als einen kleinen Puffer vor der Ansicht des Spielers gleichzeitig berechnen (einige Bildschirme um den aktuellen herum).

In Bezug auf die Handhabung von Dingen wie Pflanzen, die in Bereichen wachsen, die weit vom aktuellen Bildschirm des Players entfernt sind, können Sie beispielsweise Timer verwenden. Diese Timer durchlaufen beispielsweise Dateien, in denen Informationen über die Pflanzen, ihre Position usw. gespeichert sind. Sie müssen lediglich die Dateien in den Timern lesen / aktualisieren / speichern. Wenn der Player diese Teile der Welt wieder erreicht, liest die Engine die Dateien wie gewohnt ein und zeigt die neueren Anlagendaten auf dem Bildschirm an.

Ich habe diese Technik in einem ähnlichen Spiel verwendet, das ich letztes Jahr für die Ernte und die Landwirtschaft gemacht habe. Der Spieler konnte sich weit von den Feldern entfernen, und bei der Rückkehr waren die Gegenstände aktualisiert worden.

Jason Coombes
quelle
-2

Ich habe darüber nachgedacht, wie ich mit so vielen Zillionen von Blöcken umgehen soll, und das einzige, was mir in den Sinn kommt, ist das Flyweight Design Pattern. Wenn Sie es nicht wissen, empfehle ich Ihnen dringend, darüber zu lesen: Kann beim Speichern und Verarbeiten viel helfen: http://en.wikipedia.org/wiki/Flyweight_pattern

Tiago Frossard
quelle
3
-1 Diese Antwort ist zu allgemein, um nützlich zu sein, und der von Ihnen bereitgestellte Link geht nicht direkt auf dieses spezielle Problem ein. Das Flyweight-Muster ist eine von vielen Möglichkeiten, große Datenmengen effizient zu verwalten. Könnten Sie näher erläutern, wie Sie dieses Muster im speziellen Kontext des Speicherns von Kacheln in einem Terraria-ähnlichen Spiel anwenden würden?
Postgoodism