Wie kann ich das langsame Laden großer Level beschleunigen?

7

Ich habe einen Ebenenlader erstellt, der in einem XML-Format gespeicherte Ebenen lädt. Dies bedeutet, dass ich einen XML-Parser verwende, um die Ebenen zu lesen. Es funktioniert, aber das Laden etwas größerer Level dauert zu lange. Jetzt suche ich nach einer Möglichkeit, das Laden zu beschleunigen. Ich muss nicht die gesamte Datei auf einmal laden, da der Player ohnehin nicht die gesamte Karte sehen kann. Ein teilweises Laden wäre also in Ordnung.

Ich dachte an einen kachelbasierten Lademechanismus, bei dem mehrere Teile der Karte vorhanden sind und der Lader nur den Teil / die Kachel lädt, auf dem der Benutzer steht. Aber ich bin mir nicht sicher, ob das eine gute Idee ist.

Vaillancourt
quelle
12
45 Sekunden ist sehr langsam, um eine Datei zu laden. Wie groß ist diese Datei genau?
user253751
3
Was ist das für ein Spiel und was ist in den Levels gespeichert? Ich konnte sehen, dass verschiedene Ansätze für verschiedene Arten von Spielen besser funktionieren
phflack
1
Das Übersetzen von Werten ist eine teure Operation (da alles , was Sie laden, von einer Zeichenfolge in ihren tatsächlichen Binärwert übersetzt werden muss). Haben Sie darüber nachgedacht, stattdessen Binärdateien zu verwenden? Dies hat auch den zusätzlichen Vorteil, dass es dem Spieler schwer fällt, Änderungen an der Datei vorzunehmen (aber angesichts der entsprechenden Fähigkeiten und Anstrengungen nicht unmöglich)
Flater
In welcher Sprache arbeitest du? XML-Parser unterscheiden sich stark in ihrer Geschwindigkeit. Daher kann es so einfach sein, Ihren Parser gegen einen schnelleren auszutauschen.
Jack Aidley
Das Problem ist nicht das XML an sich. Das Problem liegt in Ihrem Entwicklungsprozess , der die Auswirkungen von Architektur- und Implementierungsentscheidungen auf die Leistung viel zu spät untersucht. Die nächste Mal, stellen Sie ein Leistungsbudget früh , eine Performance - Test - Suite baut früh , und tut Performance - Tests der vorgeschlagenen Subsysteme wie Serialisierung Motoren früh , so dass Sie nicht immer wieder in diesem Chaos zu tun bekommen.
Eric Lippert

Antworten:

26

Zunächst sollten Sie messen, wo genau der Engpass liegt, damit Sie keine Zeit damit verschwenden, Dinge zu verbessern, die bereits gut genug sind. Der Engpass könnte einer der folgenden sein:

  • Lesen der XML-Datei von der Festplatte
  • Ihr XML-Parser analysiert es
  • Ihr Code, der die Ausgabe des XML-Parsers interpretiert und in Ihre internen Datenstrukturen konvertiert
  • Das Laden verwandter Assets (Kartenkacheln usw.)
  • Initialisierung des Spiels

In Ihrer Frage wird jedoch speziell das teilweise Laden von Kartenteilen erwähnt. Nehmen wir für diese Antwort an, Sie haben Ihren Code profiliert und festgestellt, dass das Lesen und / oder Parsen der XML-Datei das Problem ist und dass das teilweise Laden tatsächlich die naheliegendste Lösung für Ihr Problem ist.

Bei XML-basierten Dateiformaten ist dies normalerweise nicht möglich. Ein DOM-basierter XML-Parser muss das gesamte XML-Dokument analysieren und validieren, bevor Sie Daten daraus extrahieren können. Ein SAX-basierter XML-Parser muss mindestens alles bis zu dem Knoten lesen, den Sie suchen. Wenn Sie also ein teilweises Laden zulassen möchten, müssen Sie das XML-basierte Format aufgeben und Ihr eigenes Binärdateiformat erfinden, in dem Map Chunks an bekannten Dateipositionen beginnen, zu denen Sie selektiv wechseln können seek, ohne die Daten dazwischen lesen zu müssen.

Wenn Sie XML weiterhin verwenden möchten, können Sie jeden Kartenblock als separate XML-Datei speichern.

Philipp
quelle
Hallo, danke für deine Antwort! Ich bin sicher, dass es mit dem Laden von XML zusammenhängt und ich möchte wirklich XML verwenden. Die Sache ist, dass die Datei selbst in 45 Sekunden oder relativ schnell geladen wird. Das Lesen der analysierten Daten und das Einfügen in ein Array dauert jedoch 12 Minuten oder viel länger. Ich würde also eine Möglichkeit brauchen, nur die Daten zu lesen, die ich brauche, dann wären diejenigen, die 45 Sekunden beginnen und dann ungefähr weitere 2 Minuten, ungefähr. Aber wenn ich jeden Knoten auf die richtigen x- und y-Koordinaten überprüfen muss, könnte ich auch einfach die gesamte Datei laden,
..... also brauche ich eine Möglichkeit, nur die Knoten mit dem x und y innerhalb des Bereichs zu lesen. Ich denke, es sollte möglich sein, da es eine kurze Zeit dauert, bis der Parser die Datei intern analysiert. Kennen Sie einen Weg, dies zu tun, ohne separate Dateien zu haben?
@ appmaker1358 Ist die von der XML-Parser-Bibliothek benötigte Zeit in den 45 Sekunden oder 12 Minuten enthalten?
Philipp
1
Um Philipps Teile als separate Dateien zu speichern, verfolgt Minecraft diesen Ansatz. Ein Mittelweg wäre, 2 Unterteilungsebenen zu haben. Eine Regionsdatei, die Daten für 9 Chunks enthält. Sie würden eine Regionsdatei in den Speicher laden und die Chunks nach Bedarf basierend auf dem Player-Standort analysieren und laden. Auf diese Weise werden höchstens 4 Regions-XML gleichzeitig geladen (Spieler steht an der Regionsecke)
Stephan
3
@ appmaker1358 Ich denke, wir brauchen mehr Informationen darüber, wie Ihre XML-Datei strukturiert ist. Bitte fügen Sie diese Informationen der Frage hinzu. Geben Sie auch an, inwieweit Sie das XML-Format bei Bedarf ändern können / möchten.
Philipp
7

Obwohl XML für praktisch alles und auch für Anwendungen mit hohem Volumen und geringer Latenz verwendet wird, ist es für fast alles ein miserables Format, insbesondere für Anwendungen mit zeitlichen Einschränkungen, einschließlich Spielen (außer möglicherweise zum Speichern) die Einstellungen des Spiels). Selbst für Live-Daten ist ein einfaches Format mit binären Tags, das im Grunde dasselbe wie XML tut und nur nicht von Menschen lesbar ist (z. B. ein 16-Bit-Knotentyp, 32-Bit-Länge, gefolgt von Inhalten), um ein Vielfaches schneller zu lesen und schreibe.

XML ist verlockend, weil es für Menschen lesbar ist und Sie nicht mehr Tools als einen Texteditor benötigen, um eine XML-Datei zu schreiben. Es ist jedoch auch zu ausführlich, verarbeitet mehrere Datentypen (Binärdaten, große Mengen von Zahlen usw.) nicht so gut und die Verarbeitung dauert sehr unleserlich.
Sie können das Parsen erheblich beschleunigen, indem Sie einen anderen Parser verwenden. Es gibt viele Alternativen (Rapidxml, Pugixml, was auch immer), die jedoch nicht das allgemeine Problem lösen, dass das Format zu ausführlich und für den Menschen lesbar ist.

Während es akzeptabel und nicht allzu ungewöhnlich ist, XML in der eigenen Produktionspipeline zu verwenden (obwohl die meisten Leute lieber JSON oder YAML verwenden würden), gibt es normalerweise ein maßgeschneidertes Tool, das während des Erstellungsprozesses ausgeführt wird und Ihre XML-Dateien konvertiert zu einem proprietären Binärformat, das idealerweise (nicht unbedingt, aber idealerweise) einfach geladen oder so wie es ist speicherabgebildet werden kann. Kein Parsen, nur Speicherzuordnung und Setzen eines Zeigers.
Dasselbe Tool (oder ein ähnliches Tool) liest normalerweise auch andere Daten ein, z. B. Texturen, die in einer Vielzahl von Formaten gespeichert sind, die möglicherweise nicht trivial zu analysieren sind, und fügt sie in gewisser Weise in eine binäre Spieldatei ein So können sie einfach einsatzbereit zugeordnet werden.
Mit dem richtigen Format sollte das Laden eher 0,45 Sekunden als 45 Sekunden betragen.

Damon
quelle
Obwohl diese Antwort richtig ist, denke ich, dass es wichtig ist zu betonen, dass dies nur eine konstante Verbesserung des Faktors ergibt. Dies ist wahrscheinlich ausreichend für den Anwendungsfall von appmaker1358. da es die Ladezeit von 45s auf etwas überschaubares reduzieren würde. Wenn die Ladezeit der Level-Map jedoch 450 Sekunden betragen würde (z. B. in einer Open World-Einstellung), würde dieser Ansatz nicht ausreichen, und die ursprüngliche Idee der Aufteilung in Blöcke wäre erforderlich. Beachten Sie, dass sich diese Ideen ergänzen. Die verschiedenen Chunks können sogar Teil derselben Datei sein, wenn sie in einem parse-freien Binärformat mit expliziten Elementlängen vorliegen.
Thierry
1
@ Thierry: In der Tat. Das Schöne an einem Binärformat (ohne Text), in dem Sie explizite Längen von allem haben, ist, dass Sie nur Daten im Wert von Gigabyte überspringen können, wenn Sie anhand der Länge wissen, dass das gewünschte Material vorhanden ist. XML kann das nicht bereitstellen. Angenommen, der Adressraum ist groß genug (wir befinden uns noch nicht ganz im 32-Bit-Is-History-Land, aber hoffentlich bald), können Sie sogar nur eine einzelne Datei mit GB-Größe zuordnen und den VM-Manager die Arbeit erledigen lassen. Wenn Sie Seiten einige Frames berühren, bevor Sie tatsächlich darauf zugreifen (Arbeitsthread), damit der Hauptthread nie einen Fehler sieht, funktioniert dies besser, als man hoffen würde.
Damon
Wenn Sie gelegentlich mit einem kleinen "Schluckauf" leben können, müssen Sie sich nicht einmal darum kümmern, Seiten zu berühren. Einfach abbilden und vergessen.
Damon
Wir haben fast 100-fache Geschwindigkeitsverbesserungen festgestellt, indem wir einfach die Parser (von Python auf C) gewechselt haben, bei denen es sich um extrem niedrig hängende Früchte handelte (ein anderes Modul importieren, 3 Codezeilen ändern). In diesem Benchmark war XML fast doppelt so hoch (+ 84%) ) so ausführlich wie JSON beim Speichern derselben Daten. Eine Reduzierung auf binär würde zu noch besseren Ergebnissen führen. Ich brauche ungefähr so ​​viel Zeit, um Dateien mit einer Größe von 4 GB auf die Festplatte zu laden und zu analysieren (~ 21 GB, sobald sie in Python im RAM geladen sind) ...
TemporalWolf
5

Es gibt eine Reihe von Faktoren, um dieses Problem anzugehen, obwohl Sie auf dem richtigen Weg sind.

Einzellast

Der erste Ansatz besteht, wie Sie bereits versucht haben, darin, alles auf einmal zu laden. Dadurch stehen Ihre gesamte Ladezeit und Datei-E / A im Vordergrund. Wie Sie bereits bemerkt haben, kann Ihre anfängliche Ladezeit mit zunehmender Kartengröße für den Benutzer ärgerlich werden. Dadurch wird auch eine Obergrenze für Ihre maximale Weltgröße erstellt, die auf dem minimal erforderlichen Speicher der Zielplattform basiert.

Es gibt zwei andere Möglichkeiten, wie ich damit umgehen kann: Sie können die Welt aufteilen und sie vom Bildschirm laden, wenn sich der Player ihnen nähert (Laden des Streams); und Sie können Ladezonen haben.

Zonen laden

Durch das Laden von Zonen können Sie eine maximale Blockgröße finden, die sich positiv auswirkt, und Ihre Welt in nicht größere Teile unterteilen. Wenn der Spieler eine Transitregion (Tür, Höhle, Kartenkante) betritt, findet eine Art Übergangsgrafik oder -animation statt, um den Spieler abzulenken. Die neue Zone wird aus dem Dateisystem geladen, während die alte gespeichert und entladen wird. Dies ist eine Mitte des Straßenansatzes. Sie können zwar Welten haben, die viel größer als die Speicherkapazität des Zielgeräts sind, und alle Ihre E / A-Anstrengungen unternehmen, bevor der Player die Kontrolle erhält. Dies erhöht jedoch die E / A-Operationen gegenüber Ihrem ursprünglichen Ansatz. Dies kann auch die Kontinuität des Spiels beeinträchtigen, was für den Stil Ihres Spiels günstig oder nicht günstig sein kann. Die Final Fantasy-Reihe ist wahrscheinlich die bekannteste für diese Art von Ansatz.

Laden des Streams

Was ich als das bekannteste Beispiel für das Laden von Streams betrachten würde, ist Minecraft. Chunks werden in den Speicher geladen und aus diesem entfernt, wenn sich die Nähe des Players ändert. Wie beim Laden von Zonen wird beim Laden von Streams auch die Obergrenze für die Weltgröße entfernt. Außerdem werden die Unterbrechungen des Ladevorgangs aus der Benutzererfahrung entfernt. Dies ist jedoch der Ansatz mit der höchsten Datei-E / A-Belastung, da Zonen während einer Wiedergabesitzung häufig geladen und aus dem Speicher gelöscht werden können. Es muss auch darauf geachtet werden, eine Zone in einer näheren Nähe zu laden, als sie aus dem Speicher entfernt wurde, um zu verhindern, dass ein Spieler, der wiederholt über eine Blockgrenze läuft, das Spiel bei E / A-Operationen vergräbt. Für 3D-Spiele eine Methode namens Dogleggingwird oft verwendet, wodurch die Sicht des Spielers auf den Bereich, der geladen wird, blockiert wird. Dies hat normalerweise die Form eines Flurs mit einer Kurve, kann aber jedes Hindernis sein, das die Sichtlinie des Spielers blockiert.

Welcher dieser Ansätze für Ihr Spiel am besten geeignet ist, liegt bei Ihnen.

Stephan
quelle
Ich denke, ich möchte Stream laden und habe daher mehrere Teile meiner Welt, aber ich möchte sie in einer einzigen Datei. Da das Parsen der gesamten Datei intern im Parser nur eine kurze Zeit dauert, brauche ich nur eine Möglichkeit, um leicht zu identifizieren, welcher Knoten der Block ist. Ich muss dies tun, ohne jeden Knoten zu überprüfen, da dies die gleiche Zeit in Anspruch nehmen würde, wie das direkte Laden aller Elemente. Könnten Sie dabei helfen?
1
Sie können die Datei entweder in kleinere Segmente Ihrer Welt aufteilen oder Ihre Knoten so strukturieren, dass sie leichter durchsucht werden können. Es ist schwer zu sagen, welches am besten ist, ohne zu sehen, was Sie bereits haben.
Stephan
3

Werfen wir einen Blick auf smart ... was genau ist smart?

Sie geben an, dass Sie XML als Format zum Speichern Ihrer Ebenen verwenden. XML ist ein hierarchisches Format, das in einer Datei gespeichert wird. Somit haben wir 2 Hauptfaktoren, die unsere Ladezeiten beeinflussen:

  1. E / A-Geschwindigkeit: Dies ist eine harte Einschränkung . Sie können die Lese- und Schreibgeschwindigkeit mit Ihrem Code nicht beeinflussen. Zumindest nicht zu viel. Sie können Dinge wie die Prozessor-Cache-Größe usw. verwenden, aber das ist auf niedriger Ebene und auch von Computer zu Computer unterschiedlich.

  2. Ihre XML-Struktur: Hier können Sie wild werden. Sie können entscheiden, wie Sie Dinge speichern und was früher kommt, was später. Sie können sogar damit beginnen, Teile einer Ebene in kleinere Datasets zu gruppieren und diese Datasets dann in Ihrem großen XML-Dokument zu ordnen, wobei die früher benötigten näher am Dateianfang liegen.

Wenn Sie also den zweiten Faktor erweitern, können Sie Ihr Level in einem Format wie dem folgenden speichern:

<level>
    <name>Dragon Boss</name>
    <par-time>45</par-time>
    <sections>
        <section>
        ...
        </section>
        <section>
        ...
        </section>
        <section>
        ...
        </section>
    </sections>
</level>

Jeder <section>enthält einen Teil des Levels, so dass jeweils einer davon geladen werden kann.

Nachdem wir das Format in etwas Nützlicheres organisiert haben, besteht der nächste Schritt darin, sicherzustellen, dass wir diese Funktion tatsächlich nutzen können. Eine Möglichkeit besteht darin, die gesamte Datei in den Speicher zu laden, sie dann zu zerlegen und die Level-Daten erst nach dem Zerlegen zu analysieren. Auf diese Weise können Sie bei Bedarf zusätzliche Abschnitte laden, ohne die teure Erstellung von Texturen, Physikobjekten und was nicht, bevor Sie sie benötigen.

Wenn Ihre Datei aus irgendeinem seltsamen Grund zu groß ist, um in den Speicher geladen zu werden, können Sie anstelle des wahrscheinlich verwendeten DOM-Parsers einen SAX-Parser verwenden . Der Vorteil eines SAX-Parsers besteht darin, dass er nicht die gesamte Datei analysieren muss, bevor Sie daran arbeiten können. Es liest und verarbeitet auch die Datei, die sich von Natur aus von einem DOM-Parser unterscheidet, so dass das Lesen beider Dateien sowieso gut sein kann.


Ein weiteres Thema, das sich aus Ihren Kommentaren zu anderen Antworten zu ergeben scheint, ist die Organisation Ihrer Daten . Sie sollten sich im Allgemeinen bemühen, Ihre Spiellogik nach Möglichkeit von Ihren Spieldaten zu entkoppeln. Das Laden einer Ebene darf beispielsweise nicht bedeuten, eine Datei von der Disc zu lesen und alles zu erstellen, was in jeder Zeile der Datei beschrieben wird. Es ist möglicherweise besser, die Daten stattdessen in einer speicherinternen Datenstruktur zu speichern und dann nur bei Bedarf daran zu arbeiten.

dot_Sp0T
quelle
1/2: Nur ein Trottel, aber ich persönlich würde Dinge wie "Prozessor-Cache-Größe usw." nennen. Low-Level, nicht High-Level ... Vielleicht werden diese Begriffe an verschiedenen Orten in entgegengesetzter Weise verwendet?
Bendl
@ Bendl Ich denke, ich wollte damit implizieren, dass es am spezifischeren / oberen Ende der Linie besorgniserregend und optimierend ist. Das Ändern auf niedrige Ebene sollte dasselbe implizieren und verständlicher sein, danke
dot_Sp0T
2/2: Das Beispiel, das Sie geben, enthält viele Wiederholungen des Tags <section>. Der Loader muss jedes dieser Tags einzeln in den Speicher laden. Wenn Sie also alle Tags auf ein oder zwei Buchstaben kürzen, wird dies wahrscheinlich zu einer erheblichen Beschleunigung führen, vorausgesetzt, es gibt viele Tags. (Siehe HTML-Tags)
Bendl
@bendl, das diese auf 1 oder 2 Buchstaben verkürzt, kann einen winzigen Einfluss auf die Ladezeiten haben oder auch nicht , aber das Ausschreiben des Wortabschnitts anstelle einer 2-Buchstaben-Zeichenfolge hat erhebliche Auswirkungen auf das Verständnis des Konzepts und die Zuordnung zu etwas, das man bereits kennt
dot_Sp0T
Ich stimme vollkommen zu! Ich meinte nur, dass dies etwas sein sollte, das das OP berücksichtigen sollte, da dies eine sehr billige Möglichkeit ist, (möglicherweise) viel Ladezeit zu verkürzen. Vielleicht sollte es als Kommentar zu der Frage hinterlassen werden, nicht zu Ihrer Antwort.
Bendl
1

Ändern Sie Ihre XML-Datei nicht, wenn Sie ein nützliches Format für Ihre Arbeit finden.

Der Trick besteht darin, die Datei zu behalten, die Sie mögen, aber Ihr Spiel diese Datei nicht direkt verwenden zu lassen. Schreiben Sie eine einfache Routine (die als Teil des Packens des Spiels ausgeführt wird), um Ihr XML in optimale Blockgrößen zu analysieren, die dynamisch geladen werden sollen, und erstellen Sie gleichzeitig einen Index für die Blöcke, die Sie zu Beginn Ihres Spiels in den Speicher laden können.

Als sehr vereinfachtes Beispiel, wenn Ihre Zeichnungsentfernung 0,9 km beträgt, könnte jede Blockdatei ein Quadrat von 1 km Ihres Weltrasters darstellen.

Ihr Parser teilt Ihre Welt in 1 km² große Blockdateien auf

Lassen Sie den Parser in jeder Blockdatei die Dateinamen der 8 angrenzenden Blockdateien hinzufügen. Auf diese Weise müssen Sie nicht auf den Index klicken, um zu wissen, welche Nachbarn geladen werden sollen. Fügen Sie außerdem die Koordinate oben links und die Koordinate unten rechts des Rasterblocks hinzu, damit Sie leicht testen können, ob sich ein Spieler in diesem Block befindet

Der Parser erstellt dann eine Indexdatei, indem er alle Blöcke durchläuft, in denen der Name der Blockdatei, die Koordinate oben links und die Koordinate unten rechts gespeichert sind

Das Spiel wird geladen, durchsucht den Index, um herauszufinden, in welchem ​​Block sich der Spieler befindet. Lädt die Blockdatei, liest die benachbarte Blockliste aus dieser Blockdatei und lädt auch diese Blöcke. Sie haben jetzt 9 Chunks um Ihren Player geladen. Wenn sich Ihr Spieler durch das Level bewegt und der Standort Ihres Spielers über den aktuellen Block hinausgeht, durchsuchen Sie die anderen geladenen Blöcke nach dem Block, in dem sich der Spieler gerade befindet. Verwenden Sie die Liste der neuen Blöcke des neuen Blocks, um die neu benachbarten Blöcke zu laden und die entladenen zu entladen nicht länger nebeneinander.

Wenn sich der Spieler bewegt (teleportiert) und die geladenen Blöcke durchsucht, um herauszufinden, in welchem ​​er sich befindet, schlägt dies fehl. An diesem Punkt suchen Sie erneut nach dem Index

Insanerob
quelle
0

Dies ignoriert im Grunde die Vorschläge zum Profilieren Ihrer Ladezeit, zum Bewerten der Komplexität des Dateiformats usw. und ich sehe jetzt eine Variante von Stephans Vorschlag für Ladezonen.

Überlegen Sie, ob Sie ein SEHR großes Level hatten - wie es ein MMO getan hätte. Realistisch gesehen würden Sie nicht das Ganze auf einmal laden. Stattdessen würden Sie es in Stücken tun. Oder laden Sie es auf verschiedenen Detailebenen - Details auf niedriger Ebene (und damit wahrscheinlich kleinere Datendateien) für weit entfernte Dinge und nur auf hoher Detailebene in der Nähe des Players.

Der Ansatz wäre also ungefähr so ​​...

  1. Teilen Sie Ihr Level in Abschnitte auf
  2. Modellieren Sie diese Abschnitte auf verschiedenen Detailebenen - von sehr geringen Details, die für den Spieler ausreichen, um sie aus großer Entfernung zu betrachten, bis zu sehr hohen Details, wo sich der Spieler befindet.
  3. Laden Sie nur Abschnitte basierend auf dem erforderlichen Level.
  4. Laden Sie Abschnitte dynamisch (und entladen Sie sie), während sich der Spieler bewegt.

Es wird davon ausgegangen, dass Detailabschnitte auf niedriger Ebene sehr schnell geladen werden und auf hoher Ebene mehr Zeit benötigt wird.

Dies hilft, indem Sie genau das laden können, was Sie benötigen, nicht alles. Sie haben auch die Möglichkeit, die Prozessorlast zu steuern, da Sie keine entfernten Details rendern oder simulieren müssen - nur dort, wo sich der Player befindet.

Es ist eine allgemeine Antwort, aber es könnte für Sie funktionieren. Es ist definitiv ein Ansatz für ein sehr großes Niveau, aber für ein kleines nicht wirklich praktisch. Vielleicht liegen Ihre Bedürfnisse irgendwo dazwischen und es wird helfen.

Tim Holt
quelle