Wie soll ich die Datenstruktur für ein dynamisches Labyrinth mit unbegrenzter Größe erstellen?

43

Ich bin mir nicht sicher, ob "Labyrinth" der richtige Begriff ist. Grundsätzlich starten Benutzer in einer Single Roommit 4 Türen (N, S, E und W). Sie können in jede Richtung gehen, und jeder nachfolgende Raum enthält einen anderen Raum mit 1 bis 4 Türen, die zu anderen Räumen führen.

Das "Labyrinth" soll unbegrenzt groß sein und wachsen, wenn Sie Räume verschieben. Es ist eine begrenzte Anzahl Roomsverfügbar, die verfügbare Anzahl ist jedoch dynamisch und kann sich ändern.

Mein Problem ist, dass ich mir nicht sicher bin, welche Datenstruktur für diese Art von Muster am besten geeignet ist

Ich habe zuerst darüber nachgedacht, nur ein [X] [X] -Array von RoomObjekten zu verwenden, aber ich würde das wirklich lieber vermeiden, da das Ding in jede Richtung wachsen soll und nur Räume gebaut werden sollten, die "besucht" werden.

Der andere Gedanke war, dass jede RoomKlasse 4 verknüpfte RoomEigenschaften für N, S, E und W enthält und nur mit der vorherigen verknüpft ist Room, aber das Problem dabei ist, dass ich nicht weiß, wie ich identifizieren kann, ob ein Benutzer einen Raum betritt, der hat einen angrenzenden Raum schon "gebaut"

Zum Beispiel,

--- --- ----------
| | | |
   Start 5 4
| | | |
--- --- --- ---
--- --- ---------- --- ---
| | | | | |
| 1 2 3
| | | | | |
--- --- --- --- ----------

Wenn der Benutzer von Start> 1> 2> 3> 4> 5 wechselt, muss Room# 5 wissen, dass W den Startraum enthält, S Raum # 2 ist und in diesem Fall nicht verfügbar sein sollte und N entweder a sein kann Neu Roomoder eine Mauer (nichts).

Vielleicht brauche ich eine Mischung aus dem Array und den verbundenen Räumen, oder vielleicht sehe ich das einfach falsch.

Gibt es eine bessere Möglichkeit, die Datenstruktur für diese Art von "Labyrinth" zu erstellen? Oder bin ich mit meinem aktuellen Denkprozess auf dem richtigen Weg und vermisse nur ein paar Informationen?

(Falls Sie interessiert sind, ist das Projekt ein Spiel, das Munchkin Quest sehr ähnlich ist. )

Rachel
quelle
Ich glaube nicht, dass irgendein Array funktionieren würde, da die Räume in eine beliebige Richtung wachsen würden ... Wenn Sie also bei [0,0] beginnen und sich nach links bewegen? es würde versuchen [-1, 0].
Paul
@Paul Hänge eine Zeile / Spalte an, verschiebe alle Array-Daten und verschiebe dann auch alle Player-Positionen, um sie an das neue Map-Array anzupassen. Langsam und kann schwierig sein, je nachdem, wie viel verschoben werden muss, aber möglich. Trotzdem ist Bubblewraps Antwort viel besser.
Izkata
Ich liege wahrscheinlich falsch, aber wäre das auf GameDev.SE nicht besser dran?
Dynamische
1
@Dynamic Dies ist eine Frage zur Datenstruktur, daher passt sie genau hierher.
Izkata,

Antworten:

44

Geben Sie die Raumkoordinaten an (Start wäre (0,0)) und speichern Sie jeden generierten Raum in einem Wörterbuch / einer Hashmap nach Koordinaten.

Es ist ganz einfach, die benachbarten Koordinaten für jeden Raum zu bestimmen, mit denen Sie überprüfen können, ob bereits ein Raum vorhanden ist. Sie können Nullwerte einfügen, um Stellen darzustellen, an denen bereits festgestellt wurde, dass kein Raum vorhanden ist. (oder wenn das nicht möglich ist, bin ich mir nicht sicher, ob atm ein separates Wörterbuch / eine separate Hasmap für Koordinaten ist, die keinen Raum enthalten)

Luftpolsterfolie
quelle
2
Stellen Sie sicher, dass jedes Raumobjekt Nord-Ost-Süd-West-Informationen zu anderen Raumobjekten enthält, sodass Sie sowohl das Wörterbuch / die Hashmap als auch die Himmelsrichtungen des Raums verwenden können, um durch das Labyrinth zu navigieren (manchmal möchten Sie mit absoluten Koordinaten und suchen) Manchmal möchten Sie wissen, was nördlich von Raumobjekt X) liegt.
Neil
2
@Paul Ich denke, die Idee ist, ein Raumwörterbuch zu erstellen, und beim Erstellen eines neuen Raumes Roomnach benachbarten Räumen im Wörterbuch zu suchen und deren Links zum RoomObjekt hinzuzufügen, bevor neue Räume zu den verbleibenden Seiten hinzugefügt werden. Das einzige Mal, dass die Wörterbuchsuche ausgeführt wird, ist das Erstellen eines neuen RoomObjekts, nicht das Rooms
Rachel,
7
Es gibt keinen Grund zu speichern Links zu anderen Räumen innerhalb eines RoomObjekts überhaupt. Wenn Sie im Raum sind (x,y)und nach Norden reisen möchten, suchen Sie den Raum (x,y+1)im Wörterbuch und erstellen ihn, falls er nicht vorhanden ist. Wörterbuchsuchen sind sehr schnell O(1).
Karl Bielefeldt
3
@KarlBielefeldt: Der Raum @ (x,y+1)kann existieren, aber von (x,y)Norden aus nicht befahrbar sein . Das heißt, eine Kante darf nicht direkt von (x,y)nach gehen (x,y+1).
Steven Evers
2
Ihr macht das kompliziert. Dies ist im Grunde dasselbe wie ein Array. Sie suchen es jedoch in einem Wörterbuch und nicht in einem zweidimensionalen Array. Alle Probleme, denen Sie mit einem Array begegnen, sind ebenfalls vorhanden ... aber er wollte trotzdem ein Array verwenden.
user606723
15

In den meisten Fällen klingt das, was Sie beschreiben, wie ein Diagramm. Angesichts einiger Ihrer Anforderungen (dem wachsenden Aspekt) würde ich wahrscheinlich eine Adjazenzliste als Implementierung auswählen (die andere übliche Option wäre eine Adjazenzmatrix ).

Ich bin nicht sicher, welche Sprache Sie verwenden, aber ein gutes Tutorial / eine gute Erklärung mit Implementierungsdetails für ein Diagramm, das mit einer Adjazenzliste in .NET implementiert wurde, finden Sie hier .

Steven Evers
quelle
1
Nicht sicher, ob ein Diagramm ausreicht, um dies zu beschreiben, da N / E / S / W nicht wirklich Teil des Diagrammkonzepts sind. es gibt nur verbunden und möglicherweise in / out.
Edward Strange
3
@ CrazyEddie: Denken Sie daran, dass die / a-Datenstruktur nicht direkt einer bestimmten Domäne zugeordnet werden soll (das ist in der Tat ihr Vorteil). In diesem speziellen Beispiel wäre das Diagramm gerichtet, und die Kanten können einfach mit einer Aufzählung versehen werden.
Steven Evers
Die Anmerkung könnte das Ost-West-, Nord-Süd-Verhältnis sogar trivial durchsetzen. Dies würde die Probleme beseitigen, von Raum A nach Raum B nach Westen und dann von Raum B nach Raum C (anstelle von Raum A) nach Osten zu gehen, da eine schlechte Verbindung besteht.
Peter Smith
3
Nehmen wir an, wir wollten einen Raum einrichten, der von einem Zauberer bewohnt wird, der sich selbst schützt, indem er den Spieler zehn Felder in eine zufällige Richtung teleportiert. Das Auffinden dieses Punktes in einer Diagramm-basierten Datenstruktur wäre sehr kostspielig, insbesondere wenn dieser Raum nicht vorhanden wäre und Sie alle Räume generieren müssten, die diesen Raum mit einem anderen Raum im Diagramm verbinden (da die Struktur keine Mehrfachnennungen zulässt, voneinander getrennte Abschnitte des Dungeons).
Mark Booth
2
@MarkBooth aber dann haben wir die Anforderungen geändert, nein?
Joshua Drake
9

Ein paar Gedanken zur Implementierung (ich habe an Carcassonne gedacht, das eine Reihe anderer herausfordernder Aspekte beim Erstellen der Matrix hat - es war sogar eine Interviewfrage, die mir einmal gestellt wurde).

Es gibt einige Fragen, die an diese Struktur gestellt werden:

  1. Gibt es ein Zimmer bei X, Y?
  2. Gibt es einen Raum [N / S / E / W] für den leeren Platz X, Y?

Das Problem mit einfachen Listen und Grafiken

Die Schwierigkeit bei einfachen Listen besteht darin, dass man die Struktur durchgehen muss, um zu testen, ob etwas an einem bestimmten Ort platziert werden kann. Das System benötigt eine Möglichkeit, auf einen beliebigen Ort O (1) zuzugreifen.

Erwägen:

1 2 3 ? 4
5 . . * 6
7 8 9 A B

Um die Information über den möglichen Ort '?' Zu finden, muss man bei 3 den ganzen Weg herumlaufen, um zu 4 zu gelangen mit einem "Sprung 1" (zusätzliche Informationen) erfordert noch Spaziergänge, wenn die Nachbarschaft von "*" von 6 oder A gefunden wird.

Einfache, große Arrays

Es ist eine begrenzte Anzahl von Zimmern verfügbar

Wenn dies keine große Zahl ist, erstellen Sie einfach ein 2N x 2N-Array und belassen Sie es dort. Ein 100 x 100-Array besteht aus "nur" 10.000 Zeigern und 50 Objekten. Indizieren Sie direkt in das Array.

Dies könnte auf nur NxN reduziert werden, wenn Aktivitäten außerhalb der Grenzen das Array verschieben, um immer innerhalb der Beschränkungen zu bleiben. Wenn zum Beispiel ein Raum hinzugefügt werden soll, der unter dem Array liegt, muss das Raster jedes Element um eine Position verschieben, damit kein Unterlauf mehr auftritt. Zu diesem Zeitpunkt würde die Größe der Welt für 50 Räume 2500 Zeiger und 50 Objekte betragen.

Sparse Arrays und Matrizen

Um dies optimal zu erstellen, untersuchen Sie ein spärliches Array, in dem die meisten Elemente 0 oder null sind. Für zwei Dimensionen ist dies als spärliche Matrix bekannt . Viele Programmiersprachen haben verschiedene Bibliotheken, um mit dieser Struktur zu arbeiten. Wenn sich die Bibliothek auf ganze Zahlen beschränkt, kann man diese ganze Zahl als Index für ein festes Array von Räumen verwenden.

Mein bevorzugter Ansatz wäre, die Räume als Struktur zu haben (Zeiger auf benachbarte Räume und Koordinaten) und den Raum auch einen Zeiger von einer Hash-Tabelle zu haben, die auf Koordinaten gehasht ist. In dieser Situation würde man die Hash-Tabelle abfragen, um zu fragen, welcher Raum [N / S / E / W] von einem Nullraum ist. Dies ist übrigens das 'DOK'-Format zum Speichern einer dünnen Matrix.

Gemeinschaft
quelle
1
Eine gute Antwort, wie Bubblewrap jedoch vorschlägt, ist ein Wörterbuch mit einem Positionstupel als Schlüssel eine vernünftige Struktur, um eine dünne Matrix zu implementieren.
Mark Booth
2

Wie wäre es damit..

Geben Sie jeder Zelle einen Link zu jedem ihrer Nachbarn. Geben Sie jeder Zelle einen Namen (dh "0/0", "-10/0" (Angenommen, Sie beginnen bei 0,0)). Fügen Sie ein HashSet mit allen Namen hinzu. Wenn Sie versuchen, in eine andere Zelle zu wechseln, überprüfen Sie einfach, ob der Nachbar noch nicht im HashSet vorhanden ist.

Wenn Sie eine Öffnung für einen anderen Raum erstellen, bedeutet dies auch, dass die Räume vorhanden sind? Sie erstellen also einen Link zu einem leeren Raum ohne Links zu einem Raum. Wahrscheinlich möchten Sie auch die neuen Zimmernachbarn überprüfen. Wenn einer existiert und sich zu Ihrem neuen Raum öffnen würde, fügen Sie diesem Raum eine Tür hinzu.

   Empty   
   (0,1)        

---    ---            ----------
|        |            |        |
    0,0       1,0        2,0       Empty
|        |            |        |   (3,0)
---    --- ---------- ---    ---
|        | |        | |        |
|   0,-1      1,-1       2,-1      Empty
|        | |        | |        |   (3,-1)
---    --- ---    --- ----------

   Empty     Empty   
  (0,-2)    (1,-2)

HashSet = {0 | 0, 1 | 0, 2 | 0, 3 | 0, 0 | -1, 1 | -1 ...} 1,0: W = 0,0 / Tür; 1,0: N = 1,1 / leer; E = 2,0 / Tür; S = 1, -1 / Wand

Sie müssten auch sicherstellen, dass Sie jedem neuen Raum mindestens eine nicht angrenzende (zu einem anderen Raum gehörende) Tür geben, damit das Labyrinth in diese Richtung wachsen kann.

Paul
quelle
1

Was Sie entwerfen, klingt sehr nach einem Diagramm.

Eine Grafik des Labyrinths

Diese werden oft als eine Menge von Zuständen Q , ein Anfangszustand q 0Q und einige Übergänge dargestellt Δ dargestellt . Also, ich würde vorschlagen, dass Sie es so speichern.

  • Ein Satz Q : {s, 1, 2, 3, 5, 6}
  • Ein Anfangszustand q 0 : s
  • Eine Karte der Übergangsbeziehungen Δ : {s → 1, s → 5, 1 → 2, 2 → 3, 3 → 4, 4 → 5}

Die meisten vernünftigen Sprachen haben sowohl Karten als auch Mengen.

kba
quelle
0

Sie könnten eine 4-Wege-Linkliste in Betracht ziehen ...

Ich habe zuerst darüber nachgedacht, nur ein [X] [X] -Array von Raumobjekten zu verwenden, aber ich würde das wirklich lieber vermeiden, da das Ding in jede Richtung wachsen soll und nur Räume gebaut werden sollten, die "besucht" werden.

Sie können dafür immer noch ein [] [] verwenden. Das dynamische Wachstum mag langsam sein, besonders wenn es zu Beginn hinzugefügt wird, aber vielleicht nicht so schlimm. Sie sollten sich profilieren, um zu überprüfen. Der Versuch, eine verknüpfte Liste oder Karte zu manipulieren, ist möglicherweise schlimmer und nicht nur gelegentlich, sondern auf konstanter Ebene.

Sie können nur besuchte Räume erstellen, indem Sie die verzögerte Auswertung implementieren. Ein Objekt kann sich an einer Stelle befinden, die einen Raum enthält, und baut diesen Raum erst, wenn room()es aufgerufen wird. Dann gibt es immer wieder dasselbe zurück. Nicht schwer zu machen.

Edward Strange
quelle
1
Könnten Sie das, was Sie unter einer "4-Wege-Linkliste" verstehen, erweitern? Das einzige, was ich finden konnte, war ein CodeProject-Artikel, der sich zu einer Adjazenzliste zusammensetzte.
Steven Evers
0

Das habe ich über das Buch "Erstellen von Abenteuerspielen auf Ihrem Computer" gelernt. Wenn Sie bereit sind, den BASIC-Code zu durchsuchen (das Buch ist so alt), lesen Sie hier:

http://www.atariarchives.org/adventure/chapter1.php

Für die Verknüpfung haben sie ein Array von Räumen, wobei ein Element in jedem Array ein Zeiger auf einen anderen Raum ist, zu dem Sie wechseln können, wobei 0 (ich würde heutzutage -1 verwenden) angibt, dass dies nicht möglich ist Gehen Sie diesen Weg. Zum Beispiel würden Sie eine Raumstruktur erstellen (oder eine Klasse oder was-haben-Sie)

room {
 int north_dir;
 int south_dir;
 int west_dir;
 int east_dir;
 // All other variables and code you care about being attached to the rooms here
}

Dann könnten Sie ein Array oder eine verknüpfte Listenstruktur haben, oder aber Sie möchten Ihre Räume verwalten. Für Arrays (oder C ++ - Vektoren) würde ich diesen Code verwenden, und die Richtungen würden den Index des Raums enthalten, mit dem sie verknüpft sind. Für eine verknüpfte Liste können Sie Zeiger auf den nächsten Raum verwenden.

Wie andere bereits gesagt haben, können Sie dies auch tun, wenn Sie beim Betreten neuer Räume dynamisch neue Räume generieren müssen.

laaph
quelle
0

Versuchen Sie nicht, alle Probleme mit einer einzigen Struktur zu lösen.

Definieren Sie Ihr Raumobjekt, um Dinge über den Raum zu speichern, nicht seine Beziehungen zu anderen Räumen. Dann kann ein 1D-Array, eine Liste usw. beliebig wachsen.

Eine separate Struktur kann "Erreichbarkeit" enthalten - welche Räume sind von dem Raum aus zugänglich, in dem ich mich befinde. Entscheiden Sie dann, ob die transitive Erreichbarkeit eine schnelle Berechnung sein muss oder nicht. Vielleicht möchten Sie eine Brute-Force-Berechnung und einen Cache.

Vermeiden Sie frühzeitige Optimierungen. Verwenden Sie wirklich einfache Strukturen und leicht verständliche Algorithmen, und optimieren Sie dann die verwendeten.

julianisch
quelle