Implementieren eines zufällig generierten Labyrinths mit Prims Algorithmus

8

Ich versuche ein zufällig generiertes Labyrinth mit dem Prim-Algorithmus zu implementieren.

Ich möchte, dass mein Labyrinth so aussieht:

aber die Labyrinthe, die ich aus meinem Programm erzeuge, sehen so aus:

Ich bin gerade dabei, die fett hervorgehobenen Schritte korrekt umzusetzen:

  
  1. Beginne mit einem Gitter voller Wände.
    2.   
  2. Wähle eine Zelle aus und markiere sie als Teil des Labyrinths. Fügen Sie die Wände der Zelle zur Wandliste hinzu.
    3.   
  3. Es gibt zwar Wände in der Liste:      
    • ** 1. Wählen Sie eine zufällige Wand aus der Liste. Wenn die Zelle auf der gegenüberliegenden Seite noch nicht im Labyrinth ist:      
        1. Mache die Wand zu einem Durchgang und markiere die Zelle auf der gegenüberliegenden Seite als Teil des Labyrinths. **
          2.   
        •   
        1. Fügen Sie die benachbarten Wände der Zelle zur Wandliste hinzu.
          2.   
        •   
      •   
      1. Entfernen Sie die Wand von der Liste.
        2.   
      •   
    4.   

von diesen Artikel über die Labyrinthgeneration

Wie kann ich feststellen, ob eine Zelle ein gültiger Kandidat für die Wandliste ist? Ich möchte meinen Algorithmus so ändern, dass er ein korrektes Labyrinth erzeugt. Irgendwelche Ideen, die mir helfen würden, mein Problem zu lösen, würden geschätzt werden.

    
donth77 20.04.2015, 05:13
quelle

6 Antworten

8

Die Beschreibung im Wikipedia-Artikel verdient wirklich eine Verbesserung.

Der erste verwirrende Teil des Artikels ist, dass die Beschreibung des randomisierten Prim-Algorithmus die angenommene Datenstruktur des Algorithmus nicht näher erläutert. So werden Sätze wie "entgegengesetzte Zelle" verwirrend.

Grundsätzlich gibt es zwei Hauptansätze, die "Labyrinth-Generator-Programmierer" wählen können:

  1. Zellen haben Wände oder Durchgänge zu ihren 4 Nachbarn. Die Informationen über Wände / Passagen werden gespeichert und manipuliert.
  2. Zellen können entweder blockiert (Wände) oder Passagen sein, ohne zusätzliche Verbindungsinformationen zu speichern.

Je nachdem, welches Modell (1) oder (2) der Leser beim Lesen der Beschreibung des Algorithmus vor Augen hat, verstehen sie ihn oder verstehen ihn nicht.

Ich persönlich bevorzuge es, Zellen entweder als Wände oder als Passagen zu verwenden, anstatt mit dedizierten Passage- / Wandinformationen herumzuspielen.

Dann haben die "Grenz" -Patches einen Abstand von 2 (statt 1) ​​von einer Passage. Ein zufälliges Grenzgebiet von der Liste der Grenzgebiete wird ausgewählt und mit einem zufälligen benachbarten Durchgang (in Entfernung 2) verbunden, indem auch die Zelle zwischen dem Grenzgebiet und dem benachbarten Durchgang eine Passage gemacht wird.

Hier meine F # Implementierung von wie es aussieht:

%Vor%

Ein resultierendes Labyrinth kann dann so aussehen:

Hier ein Versuch, meine Lösung im wikipedia "Algorithmus" Stil zu beschreiben:

  
  1. Ein Gitter besteht aus einem zweidimensionalen Array von Zellen.
    2.   
  2. Eine Zelle hat 2 Zustände: Blockiert oder Passage.
    3.   
  3. Beginnen Sie mit einem Gitter voller Zellen im Status Blocked.
    4.   
  4. Wählen Sie eine zufällige Zelle, setzen Sie sie auf "Passage" und berechnen Sie ihre Grenzzellen.   Eine Grenzzelle einer Zelle ist eine Zelle mit Abstand 2 im Zustand Blockiert und innerhalb des Gitters.
    5.   
  5. Während die Liste der Grenzzellen nicht leer ist:      
    1. Wähle eine zufällige Grenzzelle aus der Liste der Grenzzellen.
      2.   
    2. Lassen Nachbarn (borderCell) = Alle Zellen in der Entfernung 2 in State Passage.   Wählen Sie einen zufälligen Nachbarn und verbinden Sie die Grenzzelle mit dem Nachbarn, indem Sie die Zelle dazwischen setzen, um die Passage zu markieren.   Berechnen Sie die Grenzzellen der gewählten Grenzzelle und fügen Sie sie der Grenzliste hinzu.   Entferne die gewählte Grenzzelle aus der Liste der Grenzzellen.
      3.   
    6.   
    
BitTickler 20.04.2015, 21:41
quelle
3

Eine einfache Java-Implementierung des Prim-Algorithmus:

%Vor%

Eine Beispielausgabe von new Maze(20,20).toString() ist:

%Vor%     
MT0 22.04.2015 22:45
quelle
2

Versuchen Sie, die Wände zu Beginn der Prozedur mit eindeutig zufälligen Gewichten zu versehen. Diese Liste der Gewichte wird sich nie ändern. Wenn Sie Ihre nächste Wand aus der Liste der verfügbaren Wände auswählen, wählen Sie die Wand mit minimalem Gewicht.

    
Edward Doolittle 20.04.2015 05:35
quelle
2

Ihre Lösung sieht nicht sehr falsch aus. Insbesondere ist es ein Labyrinth, und (wenn Sie nicht diagonal gehen können) gibt es einen einzigartigen Weg von jedem (offenen) Standort zum anderen (offenen) Ort. Das einzige Problem mit dem scheint der Stil zu sein.

Wenn Sie das "richtige" Labyrinth, das Sie gepostet haben, ohne den äußeren Rand betrachten und die Zelle oben links als (0,0) betrachten, können Sie beobachten, dass sich die Durchgänge und Wände in einem gewissen Sinne abwechseln. Jede Zelle, in der beide Koordinaten gerade sind, muss eine Passage sein, und jede Zelle, in der beide Koordinaten ungerade sind, muss eine Wand sein. Die einzigen Zellen, in denen Sie die Wahl haben, sind die, bei denen eine Koordinate gerade und die andere ungerade ist.

Lassen Sie eine Zelle (x,y) in der Mitte des Feldes, wo beide Koordinaten gerade sind, angegeben werden. Diese Zelle muss eine Passage sein. Die Zellen (x-1,y) , (x+1,y) , (x,y-1) und (x,y+1) sind die potentiellen Wände, die sie umgeben, und die Zellen (x-2,y) , (x+2,y) , (x,y-2) und (x,y+2) die Quadrate auf den Gegenteilen davon Wände jeweils.

Mit dieser Information können Sie einfach Ihren Algorithmus implementieren, mit der zusätzlichen Anforderung, dass Sie in Schritt 2 eine Zelle auswählen müssen, in der beide Koordinaten gerade sind.

    
Hoopje 20.04.2015 21:31
quelle
1

Die einfache Antwort auf Ihre Frage ist, dass Sie beim Hinzufügen einer Kante prüfen müssen, ob die Kante eine Wand entfernt, die der letzte Nachbar einer benachbarten Wand ist.

Dies verhindert, dass Wände nur durch die Ecke verbunden werden.

    
kpie 22.04.2015 00:17
quelle
1

Ich selbst habe mir etwas ganz anderes einfallen lassen, bevor ich das Thema überhaupt recherchiert habe. Sehen Sie, wenn Sie denken, dass es ein hilfreicher Ansatz ist.

Vor langer Zeit, als ich IBM PC Character Graphics (Glyphen, die Teil der Code-Seite sind) gesehen habe, dachte ich darüber nach, Labyrinthe auf diese Weise zu erstellen. Mein Ansatz hat zwei Phasen:

  1. Erzeugen eines Labyrinths in einem Array von Ganzzahlen, wobei die bitcodierten Werte 1-15 verwendet werden, um Richtungen anzuzeigen, die in jeder Zelle des Labyrinths offen sind
  2. Rendering in eine sichtbare Form. Also sind die Wände keine Rolle, bis ich das Labyrinth zeige.

Jede Zelle beginnt mit 0 (nicht ausgewählt) und dann kann jedes der 4 Bits (1 = nach rechts, 2 = nach unten, 4 = links, 8 = nach oben) eingeschaltet werden. Naiv, können Sie einfach eine zufällige Zahl von 1-15 in jeder Zelle wählen, außer für fünf Dinge:

  1. Beginnen Sie damit, eine "Wand" aus Fluren und Ecken um das gesamte Array zu ziehen und lassen Sie an zwei Punkten einen Durchgang. Dies ist der einfachste Weg, mit den Randbedingungen umzugehen.
  2. Gewichten Sie die Wahlmöglichkeiten so, dass Sackgassen selten sind und gerade oder Eckkorridore sind üblich, volle Kreuzungen selten.
  3. Ordne die einzelnen Zellen den bereits vorhandenen zu: Wenn eine benachbarte Zelle das entsprechende Bit On hat (1 Bit in der Zelle auf der linken Seite usw.), wird das Bit in dieser Zelle aktiviert, und wenn dies der Fall ist Aus, zwinge es in diese Zelle.
  4. Finden Sie einen Weg, um sicherzustellen, dass der Anfang und das Ende verbunden sind (weitere Forschung erforderlich hier).
  5. Manage, um alle Zellen zu füllen und keine Leerstellen zu erzeugen (mehr Forschung erforderlich).

Hier ist eine Darstellung des "rohen" Arrays in Form von Zeichengrafiken:

%Vor%

Beim Rendern des Ergebnisses zeige ich jede Zelle mit einem 3x4 Raster von Zeichengrafiken an. Hier ist ein Beispiel:

%Vor%

Sehen Sie, was Sie mit dieser Methode tun können. (Eine andere Wahl der Schriftart lässt es besser aussehen als hier, die Zeilen verbinden sich nahtlos - müssen natürlich Monospace sein).

    
user4624979 27.08.2015 14:45
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset android.support.design.widget.FloatingActionButton Durch die Implementierung von FAB wird die Bildgröße reduziert