Ich schreibe ein Spiel von Dynamic Labyrinth, in dem nach jeder Zeit die Struktur des Labyrinths ändern wird (Einige Türen werden geschlossen und einige Türen werden geöffnet. Etwas wie Triwazard in HP4). Kann mir jemand vorschlagen, welche Datenstruktur am besten dafür geeignet ist?Datenstruktur, um ein Labyrinth darzustellen
Wird das Labyrinth ein rechteckiges Gitter sein? Etwas anderes?
Es hängt auch davon ab, wie viel 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 In dieser Zeile, die ein Objekt ist, das Daten enthält, die zu dieser Zelle gehören (zu welchen Nachbarzellen kann man hinziehen, was enthält die Zelle, ist dort ein Zeichen). Wenn jedoch das Labyrinth kein Rechteck ist, oder wenn eine Mehrheit der Zellen in einem großen Labyrinth tatsächlich keine nützlichen enthält (z. B. nicht passierbare Blöcke), ist eine gute Datenstruktur ein Graph.
Jeder Scheitelpunkt des Diagramms 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). Jeder Vertex/jede Zelle ist ein Objekt, das Informationen über diese Zelle enthält (z. B. ihre Position in dem physischen Labyrinth, das gezeichnet werden soll usw.).
Die Array-of-Arrays Struktur Vorteil ist, dass es sehr einfach ist, es zu zeichnen, und ziemlich geradlinig zu verarbeiten (jede Bewegung ist nur 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 dem Diagramm nur eine Kante hinzufügt.
1) Welche Datenstrukturen haben SIE berücksichtigt? 2) Niemals annehmen, dass die Leute all die kleinen Abkürzungen kennen, die du tust. HP4 ist nicht gerade eine weltweit bekannte Abkürzung für das 4. Buch der Harry Potter Serie. – DVK