Maze Generator & Solver

Labyrinthgeneratoren erstellen mithilfe verschiedener Algorithmen zufällige, lösbare Labyrinthe, wobei jeder Algorithmus Labyrinthe mit unverwechselbaren visuellen Merkmalen und unterschiedlichem Lösungsschwierigkeitsgrad erzeugt. Dies ist sowohl ein Werkzeug als auch ein Rätsel – der Spieler kann neue Labyrinthe beliebiger Größe generieren und versuchen, diese zu lösen, oder die Generierungs- und Lösungsalgorithmen in Echtzeit bei der Arbeit beobachten. Das Verständnis der verschiedenen Generierungsalgorithmen fügt eine pädagogische Dimension hinzu, da jede Methode Labyrinthe mit einzigartigen Eigenschaften erzeugt: lange Gänge, viele Sackgassen, viele Verzweigungen oder flussartige Muster.

Regeln

1. Wähle eine Labyrinthgröße (Breite und Höhe) sowie einen Generierungsalgorithmus aus.
2. Generiere das Labyrinth. Das Ergebnis ist immer ein perfektes Labyrinth: genau ein Weg zwischen zwei beliebigen Zellen, keine Schleifen und keine unerreichbaren Bereiche.
3. Lösen Sie das Labyrinth, indem Sie den Weg vom Start (in der Regel oben links) zum Ziel (in der Regel unten rechts) finden.
4. Beobachten Sie optional Schritt für Schritt die Animation des Generierungs- oder Lösungsalgorithmus.
5. Vergleichen Sie verschiedene Algorithmen, um zu sehen, wie sie sich auf den Schwierigkeitsgrad und das Erscheinungsbild des Labyrinths auswirken.

Generierungsalgorithmen

• Rekursiver Backtracker (DFS): Beginnt bei einer zufälligen Zelle, bahnt einen Weg zu einer zufälligen, noch nicht besuchten Nachbarzelle und kehrt zurück, wenn er feststeckt. Erzeugt lange, gewundene Gänge mit relativ wenigen Abzweigungen. Erzeugt Labyrinthe, die organisch wirken und mäßig schwer zu lösen sind.
• Prims Algorithmus: Verwaltet eine Grenze aus Wandkandidaten und wählt zufällig Wände zum Entfernen aus, wodurch das Labyrinth wie ein Baum nach außen wächst. Erzeugt Labyrinthe mit kürzeren Sackgassen und mehr Verzweigungen, was zu einem buschigeren Erscheinungsbild führt.
• Kruskal-Algorithmus: Entfernt zufällig Wände zwischen Zellen in verschiedenen zusammenhängenden Komponenten, bis das gesamte Raster verbunden ist. Erzeugt sehr gleichmäßige Labyrinthe ohne erkennbare Tendenz oder Muster.
• Rekursive Teilung: Beginnt mit einem leeren Raster und fügt rekursiv Wände mit Durchgängen aus einer einzigen Zelle hinzu. Erzeugt Labyrinthe mit langen, geraden Wänden und einem charakteristischen schraffierten Erscheinungsbild. Sind tendenziell leichter zu lösen.
• Aldous-Broder-Algorithmus: Ein Zufallsweg, der Durchgänge zu noch nicht besuchten Zellen schafft. Erzeugt vollkommen gleichmäßige Labyrinthe (jedes mögliche Labyrinth ist gleich wahrscheinlich), ist jedoch bei großen Gittern sehr langsam.
• Wilsons Algorithmus: Verwendet zufällige Wanderungen mit Schleifenlöschung, um gleichmäßige Spanning-Tree-Labyrinthe zu erzeugen. Mathematisch elegant und liefert unverzerrte Ergebnisse, allerdings mit variabler Generierungszeit.
• Eller-Algorithmus: Erzeugt das Labyrinth zeilenweise unter Verwendung von Set-Tracking. Speichereffizient und kann unendlich lange Labyrinthe erzeugen, da nur die aktuelle Zeile gespeichert werden muss.
• Binärbaum: Jede Zelle ist entweder mit ihrem nördlichen oder östlichen Nachbarn verbunden (zufällig ausgewählt). Extrem schnell und einfach, erzeugt jedoch eine merkliche diagonale Verzerrung. Jedes Labyrinth weist entlang zweier Kanten klare Korridore auf.

Lösungsalgorithmen

• Wall Follower: Folgt der linken oder rechten Wand. Funktioniert bei allen einfach zusammenhängenden Labyrinthen. Einfach, aber nicht optimal.
• Breiten-First-Suche (BFS): Erkundet alle Zellen in Entfernung N, bevor zur Entfernung N+1 übergegangen wird. Garantiert den kürzesten Weg.
• Tiefen-First-Suche (DFS): Erkundet so tief wie möglich, bevor zurückverfolgt wird. Findet schnell einen Weg (nicht unbedingt den kürzesten).
• A*-Suche: Verwendet eine Heuristik (typischerweise den Manhattan-Abstand zum Ziel), um die Erkundung in Richtung des Ausgangs zu priorisieren. Findet den kürzesten Weg, während weniger Zellen erkundet werden als bei BFS.
• Dead-End-Filling: Identifiziert alle Sackgassen und füllt sie rückwärts bis zur nächsten Kreuzung auf. Der verbleibende, noch nicht gefüllte Weg ist die Lösung.
• Tremaux-Algorithmus: Eine systematische Methode zur Lösung beliebiger Labyrinthe durch Markieren von Durchgängen. Kann von einem Menschen durchgeführt werden, der durch ein physisches Labyrinth geht.

Die mathematische Erforschung von Labyrinthen reicht Jahrhunderte zurück, doch die algorithmische Erzeugung von Labyrinthen begann erst mit dem Aufkommen der Computer. Einer der frühesten bekannten Algorithmen zur Labyrinthgenerierung tauchte in den 1970er Jahren auf, als Hobbyprogrammierer auf frühen Mikrocomputern wie dem Commodore PET und dem Apple II einfache Programme schrieben, um zufällige Labyrinthe auf dem Bildschirm darzustellen. Der „Binary Tree“-Algorithmus gehörte aufgrund seiner extremen Einfachheit zu den ersten, die verwendet wurden – er lässt sich mit nur wenigen Zeilen BASIC umsetzen.

Die formale Untersuchung von Algorithmen zur Labyrinthgenerierung ist eng mit der Graphentheorie verbunden. Ein perfektes Labyrinth (eines mit genau einem Weg zwischen zwei beliebigen Zellen) entspricht mathematisch einem Spannbaum des Gittergraphen. Die verschiedenen Algorithmen zur Labyrinthgenerierung sind tatsächlich unterschiedliche Methoden zur Berechnung zufälliger Spannbäume. Dieser Zusammenhang wurde in den 1990er Jahren formalisiert, als Forscher nachwiesen, dass der Wilson-Algorithmus und der Aldous-Broder-Algorithmus gleichverteilte Spannbäume erzeugen – was bedeutet, dass jedes mögliche Labyrinth mit gleicher Wahrscheinlichkeit generiert wird.

Die Labyrinthgenerierung wurde zu einem festen Bestandteil der Programmierausbildung und der Freizeitinformatik. Bücher wie „Mazes for Programmers“ von Jamis Buck (2015) untersuchen systematisch Dutzende von Labyrinthalgorithmen einschließlich ihrer Implementierungen, und das Thema ist eine gängige Übung in Informatikkursen zur Vermittlung von Graphalgorithmen, Rekursion und Datenstrukturen. Die visuelle Faszination, Algorithmen dabei zuzusehen, wie sie Labyrinthe Schritt für Schritt generieren, macht sie in Tools zur Algorithmusvisualisierung und in Programmier-Tutorials beliebt.

In der Welt der Videospiele ist die prozedurale Labyrinthgenerierung von grundlegender Bedeutung für das Roguelike-Genre, in dem jeder Durchlauf einen zufällig generierten Dungeon bietet. Spiele wie „Rogue“ (1980), „NetHack“ (1987) und moderne Titel wie „Hades“ (2020) und „Dead Cells“ (2018) nutzen Varianten von Algorithmen zur Labyrinthgenerierung, um wiederholbar gestaltete Level-Layouts zu erstellen. Das Gebiet entwickelt sich ständig weiter: Forscher beschäftigen sich mit der 3D-Labyrinthgenerierung, nicht-rechteckigen Gittern (sechseckig, dreieckig, kreisförmig) sowie Generierungsalgorithmen, die Labyrinthe mit bestimmten Schwierigkeitsmerkmalen erzeugen.