Zonierung von Bereichen auf einer großen Kachelkarte sowie von Dungeons

Mein Spiel hat eine Karte wie die von Minecraft, so wie sie pseudoinfinit und zufällig generiert ist. Und groß. Angenommen, der Benutzer hat eine 1000x1000-Zone (hier 2D) erkundet, das sind also 1.000.000 Kacheln.

Offensichtlich werde ich nicht in der Lage sein, alles im Speicher zu speichern. Ich möchte auch nicht einfach alles aus einem 10er-Plättchen oder einem beliebigen Radius ignorieren - beide werden nicht aktualisiert (alle NPCs, vielleicht reaktive Plättchen) und ich müsste mit unangenehmen Positionen wie 1382,12918 arbeiten.

Wenn ich es also in Blöcke oder Zonen oder was auch immer von 64x64-Kacheln aufteilen würde, müsste ich die Position jeder Kachel und jedes Objekts wie folgt speichern:

Chunk a, b. Positioniere x, y.

Aber was ist, wenn ich Dungeons und ähnliches in meiner Karte haben möchte? Also ein einzelnes Plättchen, das zu einem 40-stöckigen Dungeon mit einer Fläche von jeweils 40 x 40 führt. Ich kann diese nicht genau in derselben Karte speichern.

Und da ist die Gedächtnisseite; Wie viel könnte ich möglicherweise gleichzeitig vernünftigerweise im Speicher speichern? Ich könnte ganz einfach Kacheln nach ID erstellen und dort das normale 2D-Array haben. Oder gibt es eine effektivere Lösung als eine Datendatei mit Kacheltypen ? Also für eine 64x64 ... das wird nur 20K oder was auch immer sein. Ich möchte, dass so viel Umgebung wie möglich für das realistischste Update geladen wird. Aber ich weiß nicht, welche Art von Grenzen ich erreichen kann, ohne das Gedächtnis zu belasten.

Obwohl ich dem Gefühl zustimme: "Mach dir keine Sorgen, es sei denn, es ist ein bewährtes Problem", denke ich, dass es sich lohnt, frühzeitig darüber nachzudenken: Das Nachrüsten einer Lösung ist viel schmerzhafter. Und ja, nur das Aktualisieren von Kacheln in der Nähe ist der richtige Weg. Die effiziente Speicherung und Adressierbarkeit von Elementen in Ihrer Spielwelt ist jedoch aus Leistungsgründen sehr wichtig.

Was Sie hier wirklich denken, ist ein spärlicher Datensatz: etwas, bei dem die potenziellen Indizes groß (oder unbegrenzt) sind, aber nur ein kleiner Teil tatsächlich verwendet wird. Der entscheidende Punkt ist, dass Sie nicht genau wissen, welcher Anteil verwendet wird.

Die Standardlösung für ein Problem mit spärlichen Datensätzen besteht darin, den Index / die Adressierbarkeit vom tatsächlichen Datenspeicher zu trennen. Wenn das Kachelobjekt also teuer ist, lagern Sie es in kompakter Form (z. B. in einem flachen Array). Lassen Sie es jedoch über ein billigeres Objekt indizieren. In seiner einfachsten Form kann dies eine 2D- (oder 3D-) Matrix sein, die Sie leicht nach Koordinaten indizieren können, aber jedes Element in der Matrix ist einfach ein Index. Sie verwenden diesen Index dann, um den tatsächlichen Kachelinhalt in einem separaten, kompakten Array nachzuschlagen. Wenn der Kachelinhalt noch nicht vorhanden ist, fügen Sie ihn am Ende des Arrays hinzu und speichern Sie den Index in der 3D-Matrix.

Die Lösung wird komplexer, wenn Sie das Löschen von Inhalten unterstützen möchten (da dies zur Fragmentierung des Inhaltsarrays führt) und wenn Ihr Kachelinhalt billig ist, dann das zusätzliche Gewicht des Index (32-Bit- oder 64-Bit-Indizes) wird wahrscheinlich die Einsparungen überwältigen, wenn nicht jede einzelne potenzielle Kachel gespeichert wird. Es ist auch eine zusätzliche Suche, die Ihre Cache-Leistung beeinträchtigt.

Sie können noch mehr Speichereffizienz erzielen, indem Sie zusätzliche Indirektionsebenen einführen. Angenommen, Sie organisieren Ihre Kacheln in Blöcke, und Blöcke haben eine Granularität von 64 x 64 x 64. Bei einem Plättchen mit 125, 1, 132 wissen Sie, dass es in Chunk (1,0,2) gehört. Sie haben also eine Welt, die aus einem kompakten Chunk-Array und einer Matrix von Chunk-Indizes besteht (-1, wenn der Chunk nicht existiert). Der Inhalt jedes Blocks (falls vorhanden) besteht aus einer 64 x 64 x 64-Matrix von Kachelindizes (-1, wenn die Kachel noch nicht vorhanden ist) und einem kompakten Array verwendeter Kacheln. Auf diese Weise brennen Sie nicht viele Kachelindizes für Chunks, die nie verwendet werden. Wenn Sie diesem Ansatz folgen und sinnvolle Zahlen für die Chunk-Granularität auswählen, können Sie Ihr Universum massiv skalieren und Ihre Speichernutzung unter Kontrolle halten. Eigentlich, wenn Sie Ihre Chunks 32x32x32 machen,

Sie können auch hinterhältige Tricks ausführen, z. B. das höherwertige Bit Ihrer Chunk- oder Kachelindizes verwenden, um etwas Besonderes zu bedeuten. Wenn für einen Eintrag in der Kachelmatrix das oberste Bit gesetzt ist, bedeuten die unteren 31 Bits keinen Kachelindex, sondern einen Warp-Index oder ähnliches, und Sie können dies in einer separat gepflegten Liste nachschlagen um die Koordinaten herauszufinden, zu denen es führt.

Warum können Sie nicht eine Million Kacheln im Speicher speichern? Sogar mein Telefon hat 256 MB RAM; eine Million leere Kacheln werden was sein, 4-32MB?