Ich schreibe ein Spiel von Dynamic Labyrinth, in dem sich nach jeder Zeit die Struktur des Labyrinths ändert (Einige Türen werden geschlossen und einige Türen werden sich öffnen. Etwas wie Triwazard in HP4). Kann mir jemand sagen, welche Datenstruktur am besten geeignet ist, dies darzustellen?
Wird das Labyrinth ein rechteckiges Gitter sein? Etwas anderes?
Es hängt auch davon ab, wie viel von der Karte nützliche Informationen (Pässe oder Objekte) enthalten wird.
Wenn es ein rechteckiges Gitter ist und die meisten Gitterquadrate ETWAS enthalten, ist eine gute Datenstruktur ein 2D-Array (Array von Arrays), wobei jedes Element des Arrays 1 Zeile repräsentiert, wobei jedes Element des inneren Arrays 1 Zelle repräsentiert Diese Zeile, bei der es sich um ein Objekt handelt, das Daten enthält, die sich auf diese Zelle beziehen (welche Nachbarzellen können verschoben werden, was enthält die Zelle, ist ein Zeichen darauf).
Wenn jedoch das Labyrinth kein Rechteck ist, ODER wenn die Mehrheit der Zellen in einem großen Labyrinth tatsächlich keine nützlichen In-Elemente enthält (z. B. nicht passierbare Blöcke), ist eine gute Datenstruktur ein Graph.
Jede Ecke des Graphen ist eine Zelle, die passierbar ist. Kanten stellen die Zellenpaare dar, zwischen denen Sie sich bewegen können (Sie können es zu einem gerichteten Diagramm machen, wenn einige Türen nur in eine Richtung zeigen). Jede Ecke / Zelle ist ein Objekt, das Informationen über diese Zelle enthält (z. B. ihre Position im physischen Labyrinth, das gezeichnet werden soll usw.).
Der Array-of-arrays-Strukturvorteil ist, dass es SEHR einfach ist, es zu zeichnen, und ziemlich direkt zur Verarbeitung (irgendeine Bewegung ist gerade in / de-crement eines Indexes). Das Hinzufügen / Entfernen von Wänden ist so einfach wie das Ändern von Daten in den Arrayelementen zweier benachbarter Zellen.
Der Graphenstrukturvorteil besteht darin, dass er viel weniger Platz einnimmt, wenn die Labyrinthdurchgänge sehr spärlich sind (z. B. nur 1/100 des Felds besteht); es ist die einzige Struktur, die eine zufällige (z. B. nicht rechteckige) Geometrie darstellen kann, und die Verarbeitung ist ziemlich einfach. Das Hinzufügen / Entfernen von Wänden ist einfach, da es nur eine Kante zu einer Grafik hinzufügt.
Tags und Links data-structures maze