Algorithmus zur Labyrinthgenerierung - Maze generation algorithm

Maze Generation Algorithmen sind automatisierte Verfahren für die Erstellung von Labyrinthen .

Dieses Labyrinth, das durch eine modifizierte Version von Prims Algorithmus erzeugt wird , unten.

Graphentheoriebasierte Methoden

Animation einer graphentheoriebasierten Methode (randomisierte Tiefensuche)

Ein Labyrinth kann erzeugt werden, indem man mit einer vorbestimmten Anordnung von Zellen beginnt (meistens ein rechteckiges Gitter, aber andere Anordnungen sind möglich) mit Wandstellen dazwischen. Diese vorgegebene Anordnung kann als zusammenhängender Graph betrachtet werden, wobei die Kanten mögliche Wandstellen darstellen und die Knoten Zellen darstellen. Der Zweck des Labyrinth-Erzeugungsalgorithmus kann dann darin betrachtet werden, einen Untergraphen zu erstellen, in dem es schwierig ist, eine Route zwischen zwei bestimmten Knoten zu finden.

Wenn der Teilgraph nicht verbunden ist , gibt es Bereiche des Graphen, die verschwendet werden, weil sie nicht zum Suchraum beitragen. Wenn der Graph Schleifen enthält, können mehrere Pfade zwischen den ausgewählten Knoten bestehen. Aus diesem Grund wird die Labyrinth-Generierung oft als die Generierung eines zufälligen Spannbaums betrachtet . Schleifen, die naive Labyrinthlöser verwirren können, können eingeführt werden, indem im Verlauf des Algorithmus zufällige Kanten zum Ergebnis hinzugefügt werden.

Die Animation zeigt die Schritte zur Erzeugung des Labyrinths für einen Graphen, der sich nicht auf einem rechteckigen Gitter befindet. Zuerst erstellt der Computer einen zufälligen planaren Graphen G, der in Blau dargestellt ist, und seinen dualen F, der in Gelb dargestellt ist. Zweitens durchquert der Computer F unter Verwendung eines ausgewählten Algorithmus, beispielsweise einer Tiefensuche, wobei der Pfad rot eingefärbt wird. Wenn während der Durchquerung eine rote Kante eine blaue Kante kreuzt, wird die blaue Kante entfernt. Schließlich, wenn alle Ecken von F besucht wurden, wird F gelöscht und zwei Kanten von G, eine für den Eingang und eine für den Ausgang, werden entfernt.

Randomisierte Tiefensuche

Animation des Generators mit Tiefensuche

Dieser Algorithmus, auch als "rekursiver Backtracker"-Algorithmus bekannt, ist eine randomisierte Version des Tiefensuchalgorithmus .

Dieser Ansatz wird häufig mit einem Stapel implementiert und ist eine der einfachsten Möglichkeiten, ein Labyrinth mit einem Computer zu erstellen. Betrachten Sie den Platz für ein Labyrinth als ein großes Gitter von Zellen (wie ein großes Schachbrett), wobei jede Zelle mit vier Wänden beginnt. Ausgehend von einer zufälligen Zelle wählt der Computer dann eine zufällige Nachbarzelle aus, die noch nicht besucht wurde. Der Computer entfernt die Wand zwischen den beiden Zellen und markiert die neue Zelle als besucht und fügt sie dem Stapel hinzu, um das Zurückverfolgen zu erleichtern. Der Computer setzt diesen Prozess fort, wobei eine Zelle, die keine unbesuchten Nachbarn hat, als Sackgasse betrachtet wird. Wenn es sich in einer Sackgasse befindet, läuft es durch den Pfad zurück, bis es eine Zelle mit einem nicht besuchten Nachbarn erreicht, und setzt die Pfaderzeugung fort, indem es diese neue, nicht besuchte Zelle besucht (eine neue Kreuzung erzeugt). Dieser Vorgang wird fortgesetzt, bis jede Zelle besucht wurde, wodurch der Computer bis zur Anfangszelle zurückverfolgt wird. Wir können sicher sein, dass jede Zelle besucht wird.

Wie oben angegeben, beinhaltet dieser Algorithmus eine tiefe Rekursion, die bei einigen Computerarchitekturen zu Stapelüberlaufproblemen führen kann. Der Algorithmus kann in eine Schleife umgewandelt werden, indem Rückverfolgungsinformationen im Labyrinth selbst gespeichert werden. Dies bietet auch eine schnelle Möglichkeit, eine Lösung anzuzeigen, indem Sie an einem beliebigen Punkt beginnen und zum Anfang zurückgehen.

Horizontaler Durchgangs-Bias

Labyrinthe, die mit einer Tiefensuche erstellt werden, haben einen geringen Verzweigungsfaktor und enthalten viele lange Korridore, da der Algorithmus jeden Zweig so weit wie möglich durchsucht, bevor er zurückverfolgt.

Rekursive Implementierung

Randomisierte Tiefensuche auf einem hexagonalen Raster

Der Tiefensuchalgorithmus der Labyrinthgenerierung wird häufig mit Backtracking implementiert . Dies kann mit einer folgenden rekursiven Routine beschrieben werden:

  1. Gegeben eine aktuelle Zelle als Parameter,
  2. Markiere die aktuelle Zelle als besucht
  3. Während die aktuelle Zelle unbesuchte Nachbarzellen enthält
    1. Wählen Sie einen der nicht besuchten Nachbarn
    2. Entfernen Sie die Wand zwischen der aktuellen Zelle und der ausgewählten Zelle
    3. Rufen Sie die Routine rekursiv für eine ausgewählte Zelle auf

die einmal für jede Anfangszelle im Bereich aufgerufen wird.

Iterative Implementierung

Ein Nachteil des ersten Ansatzes ist eine große Rekursionstiefe – im schlimmsten Fall muss die Routine möglicherweise für jede Zelle des verarbeiteten Bereichs wiederholt werden, was in vielen Umgebungen die maximale Rekursionsstapeltiefe überschreiten kann. Als Lösung kann die gleiche Backtracking-Methode mit einem expliziten Stack implementiert werden , der normalerweise ohne Schaden viel größer werden darf.

  1. Wählen Sie die Ausgangszelle aus, markieren Sie sie als besucht und schieben Sie sie auf den Stapel
  2. Solange der Stapel nicht leer ist
    1. Pop eine Zelle aus dem Stapel und mache sie zu einer aktuellen Zelle
    2. Wenn die aktuelle Zelle Nachbarn hat, die nicht besucht wurden
      1. Schieben Sie die aktuelle Zelle auf den Stack
      2. Wählen Sie einen der nicht besuchten Nachbarn
      3. Entfernen Sie die Wand zwischen der aktuellen Zelle und der ausgewählten Zelle
      4. Markieren Sie die ausgewählte Zelle als besucht und schieben Sie sie auf den Stapel

Randomisierter Kruskal-Algorithmus

Eine Animation zum Erzeugen eines 30 x 20-Labyrinths mit dem Kruskal-Algorithmus.

Dieser Algorithmus ist eine randomisierte Version des Kruskal-Algorithmus .

  1. Erstellen Sie eine Liste aller Wände und erstellen Sie für jede Zelle einen Satz, der jeweils nur diese eine Zelle enthält.
  2. Für jede Wand in zufälliger Reihenfolge:
    1. Wenn die durch diese Wand geteilten Zellen zu unterschiedlichen Mengen gehören:
      1. Entfernen Sie die aktuelle Wand.
      2. Verbinde die Sätze der ehemals geteilten Zellen.

Es gibt mehrere Datenstrukturen, die verwendet werden können, um die Gruppen von Zellen zu modellieren. Eine effiziente Implementierung, die eine disjunkte Mengendatenstruktur verwendet, kann jede Vereinigungs- und Suchoperation an zwei Mengen in nahezu konstanter amortisierter Zeit (insbesondere Zeit; für jeden plausiblen Wert von ) ausführen , sodass die Laufzeit dieses Algorithmus im Wesentlichen proportional zur Zahl ist der Wände, die dem Labyrinth zur Verfügung stehen.

Es spielt keine Rolle, ob die Liste der Wände anfänglich randomisiert ist oder ob eine Wand zufällig aus einer nicht zufälligen Liste ausgewählt wird, beide Wege sind genauso einfach zu codieren.

Da der Effekt dieses Algorithmus darin besteht, einen minimalen Spannbaum aus einem Graphen mit gleich gewichteten Kanten zu erzeugen, neigt er dazu, regelmäßige Muster zu erzeugen, die ziemlich einfach zu lösen sind.

Randomisierter Prim-Algorithmus

Eine Animation zum Erstellen eines 30 x 20-Labyrinths mit dem Algorithmus von Prim.

Dieser Algorithmus ist eine randomisierte Version des Algorithmus von Prim .

  1. Beginnen Sie mit einem Gitter voller Wände.
  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. Während es Wände in der Liste gibt:
    1. Wählen Sie eine zufällige Wand aus der Liste aus. Wenn nur eine der Zellen besucht wird, die die Wand teilt, dann:
      1. Machen Sie die Wand zu einem Durchgang und markieren Sie die nicht besuchte Zelle als Teil des Labyrinths.
      2. Fügen Sie die benachbarten Wände der Zelle zur Wandliste hinzu.
    2. Entfernen Sie die Wand aus der Liste.

Beachten Sie, dass das einfache Ausführen klassischer Prims auf einem Graphen mit zufälligen Kantengewichten Labyrinthe erzeugen würde, die stilistisch identisch mit denen von Kruskal sind, da es sich bei beiden um minimale Spannbaumalgorithmen handelt. Stattdessen führt dieser Algorithmus eine stilistische Variation ein, da die Kanten näher am Startpunkt ein geringeres effektives Gewicht haben.

Geänderte Version

Obwohl der klassische Prim-Algorithmus eine Liste von Kanten führt, könnten wir für die Labyrinth-Generierung stattdessen eine Liste benachbarter Zellen führen. Wenn die zufällig ausgewählte Zelle mehrere Kanten hat, die sie mit dem bestehenden Labyrinth verbinden, wählen Sie zufällig eine dieser Kanten aus. Dies wird dazu neigen, etwas mehr zu verzweigen als die obige Edge-basierte Version.

Vereinfachte Version

Der Algorithmus kann noch weiter vereinfacht werden, indem Zellen zufällig ausgewählt werden, die an bereits besuchte Zellen angrenzen, anstatt die Gewichte aller Zellen oder Kanten zu verfolgen.

Es wird normalerweise relativ einfach sein, den Weg zur Startzelle zu finden, aber schwer, den Weg woanders zu finden.

Wilsons Algorithmus

Hauptartikel: Loop-gelöschter Random Walk

Alle oben genannten Algorithmen haben verschiedene Arten von Verzerrungen: Die Tiefensuche ist auf lange Korridore ausgerichtet, während die Algorithmen von Kruskal/Prim auf viele kurze Sackgassen ausgerichtet sind. Wilsons Algorithmus hingegen erzeugt eine unverzerrte Stichprobe aus der gleichmäßigen Verteilung über alle Labyrinthe unter Verwendung von schleifengelöschten Random Walks .

Wir beginnen den Algorithmus, indem wir das Labyrinth mit einer willkürlich ausgewählten Zelle initialisieren. Dann beginnen wir mit einer willkürlich gewählten neuen Zelle und führen einen Random Walk durch, bis wir eine bereits im Labyrinth befindliche Zelle erreichen. Wenn der Random Walk jedoch zu irgendeinem Zeitpunkt seinen eigenen Pfad erreicht und eine Schleife bildet, löschen wir die Schleife aus dem Pfad bevor Sie fortfahren. Wenn der Pfad das Labyrinth erreicht, fügen wir ihn dem Labyrinth hinzu. Dann führen wir einen weiteren schleifengelöschten Random Walk von einer anderen willkürlichen Startzelle aus durch, bis alle Zellen gefüllt sind.

Dieses Verfahren bleibt unabhängig davon, welche Methode wir verwenden, um die Startzellen willkürlich auszuwählen. Wir könnten also der Einfachheit halber immer die erste ungefüllte Zelle in (sagen wir) von links nach rechts und von oben nach unten geordneter Reihenfolge auswählen.

Aldous-Broder-Algorithmus

Der Aldous-Broder-Algorithmus erzeugt auch gleichförmige Spannbäume.

  1. Wählen Sie eine zufällige Zelle als aktuelle Zelle aus und markieren Sie sie als besucht.
  2. Während es unbesuchte Zellen gibt:
    1. Wählen Sie einen zufälligen Nachbarn.
    2. Wenn der gewählte Nachbar nicht besucht wurde:
      1. Entfernen Sie die Wand zwischen der aktuellen Zelle und dem ausgewählten Nachbarn.
      2. Markieren Sie den gewählten Nachbarn als besucht.
    3. Machen Sie den ausgewählten Nachbarn zur aktuellen Zelle.

Rekursive Divisionsmethode

Illustration der rekursiven Division
Originalkammer Teilung durch zwei Wände Löcher in Wänden weiter unterteilen... abgeschlossen
Schritt 1
Schritt 2
Schritt 3
Schritt 4
Schritt 5

Labyrinthe können mit rekursiver Division erstellt werden , einem Algorithmus, der wie folgt funktioniert: Beginnen Sie mit dem Raum des Labyrinths ohne Wände. Nennen Sie dies eine Kammer. Teilen Sie die Kammer mit einer zufällig positionierten Wand (oder mehreren Wänden), wobei jede Wand eine zufällig positionierte Durchgangsöffnung darin enthält. Wiederholen Sie dann den Vorgang rekursiv an den Unterkammern, bis alle Kammern die Mindestgröße haben. Diese Methode führt zu Labyrinthen mit langen geraden Wänden, die ihren Raum durchqueren, wodurch es einfacher ist, zu erkennen, welche Bereiche vermieden werden sollten.

Rekursive Labyrinth-Generierung

Bauen Sie beispielsweise in einem rechteckigen Labyrinth an zufälligen Punkten zwei Wände, die senkrecht zueinander stehen. Diese beiden Wände teilen die große Kammer in vier kleinere Kammern, die durch vier Wände getrennt sind. Wählen Sie zufällig drei der vier Wände aus und öffnen Sie an einer zufälligen Stelle in jeder der drei ein eine Zelle breites Loch. Fahren Sie auf diese Weise rekursiv fort, bis jede Kammer eine Breite von einer Zelle in eine der beiden Richtungen hat.

Einfache Algorithmen

3D-Version des Algorithmus von Prim. Vertikale Ebenen sind von unten nach oben mit 1 bis 4 gekennzeichnet. Treppen nach oben sind mit "/" gekennzeichnet; Treppen nach unten mit "\" und Treppen nach oben und unten mit "x". Der Quellcode ist in der Bildbeschreibung enthalten.

Es gibt andere Algorithmen, die nur genügend Speicher benötigen, um eine Zeile eines 2D-Labyrinths oder eine Ebene eines 3D-Labyrinths zu speichern. Der Algorithmus von Eller verhindert Schleifen, indem er speichert, welche Zellen in der aktuellen Zeile durch Zellen in den vorherigen Zeilen verbunden sind, und entfernt niemals Wände zwischen zwei bereits verbundenen Zellen. Der Sidewinder-Algorithmus beginnt mit einer offenen Passage entlang der gesamten oberen Reihe, und die nachfolgenden Reihen bestehen aus kürzeren horizontalen Passagen mit einer Verbindung zu der Passage darüber. Der Sidewinder-Algorithmus ist trivial von unten nach oben zu lösen, da er keine Sackgassen nach oben hat. Bei einer gegebenen Startbreite erzeugen beide Algorithmen perfekte Labyrinthe von unbegrenzter Höhe.

Die meisten Algorithmen zur Labyrinthgenerierung erfordern die Aufrechterhaltung von Beziehungen zwischen Zellen darin, um sicherzustellen, dass das Endergebnis lösbar ist. Gültige einfach verbundene Labyrinthe können jedoch erzeugt werden, indem man sich unabhängig auf jede Zelle konzentriert. Ein Binärbaum-Labyrinth ist ein orthogonales Standard-Labyrinth, bei dem jede Zelle immer eine Passage nach oben oder nach links hat, aber nie beides. Um ein binäres Baumlabyrinth zu erstellen, werfen Sie für jede Zelle eine Münze, um zu entscheiden, ob eine Passage nach oben oder nach links hinzugefügt werden soll. Wählen Sie immer dieselbe Richtung für Zellen an der Grenze, und das Endergebnis ist ein gültiges einfach verbundenes Labyrinth, das wie ein binärer Baum aussieht , mit der oberen linken Ecke als Wurzel. Wie bei Sidewinder hat das Binärbaum-Labyrinth keine Sackgassen in Richtungen der Voreingenommenheit.

Eine verwandte Form des Werfens einer Münze für jede Zelle besteht darin, ein Bild mit einer zufälligen Mischung aus Schrägstrich- und Backslash-Zeichen zu erstellen. Dabei entsteht kein gültiges einfach zusammenhängendes Labyrinth, sondern eine Auswahl geschlossener Schleifen und einseitiger Passagen. (Das Handbuch für den Commodore 64 stellt ein BASIC-Programm vor, das diesen Algorithmus verwendet, jedoch stattdessen PETSCII- Grafikzeichen mit diagonalen Linien verwendet, um ein glatteres grafisches Erscheinungsbild zu erzielen.)

Algorithmen für zellulare Automaten

Bestimmte Arten von zellulären Automaten können verwendet werden, um Labyrinthe zu erzeugen. Zwei bekannte zelluläre Automaten, Maze und Mazectric, haben die Regelstrings B3/S12345 und B3/S1234. Bei ersteren bedeutet dies, dass Zellen von einer Generation zur nächsten überleben, wenn sie mindestens einen und höchstens fünf Nachbarn haben . Bei letzteren bedeutet dies, dass Zellen überleben, wenn sie ein bis vier Nachbarn haben. Hat eine Zelle genau drei Nachbarn, wird sie geboren. Es ähnelt Conways Spiel des Lebens darin, dass Muster, bei denen in keiner Generation eine lebende Zelle neben 1, 4 oder 5 anderen lebenden Zellen liegt, sich genauso verhalten werden. Bei großen Mustern verhält es sich jedoch ganz anders als Life.

Für ein zufälliges Startmuster entwickeln sich diese labyrinth-erzeugenden zellulären Automaten zu komplexen Labyrinthen mit klar definierten Wänden, die Korridore umreißen. Mazecetric, das die Regel B3/S1234 hat, hat die Tendenz, im Vergleich zu Maze mit der Regel B3/S12345 längere und geradere Korridore zu erzeugen. Da diese Regeln für zellulare Automaten deterministisch sind , wird jedes erzeugte Labyrinth durch sein zufälliges Startmuster eindeutig bestimmt. Dies ist ein erheblicher Nachteil, da die Labyrinthe dazu neigen, relativ vorhersehbar zu sein.

Wie einige der oben beschriebenen graphentheoriebasierten Verfahren erzeugen diese zellulären Automaten typischerweise Labyrinthe aus einem einzigen Startmuster; Daher wird es normalerweise relativ einfach sein, den Weg zur Startzelle zu finden, aber schwieriger, den Weg woanders zu finden.

Siehe auch

Verweise

Externe Links