🔲 Labyrinth-Generator & -Löser

Die Rastergröße legt sowohl Breite als auch Höhe des quadratischen Labyrinths fest, von 5×5 bis 60×60 Zellen, sodass die Gesamtzellenzahl das Quadrat dieses Werts ist. Die Geschwindigkeit ist einem Schritte-pro-Bild-Zeitplan zugeordnet (1, 1, 2, 4, 8, 15, 30, 60, 150, 500), womit du das Schnitzen auf ein Kriechen verlangsamen oder ein großes Labyrinth fast sofort fertigstellen kannst.

Ein perfektes Labyrinth ist vollständig verbunden und enthält keine Schleifen, sodass es genau eine Route zwischen einem beliebigen Zellenpaar gibt. In der Graphentheorie ist es ein Spannbaum des Rastergraphen: Jede Zelle ist erreichbar, und das Entfernen eines Durchgangs würde das Labyrinth trennen.

Wilsons Algorithmus verwendet schleifenfreie Zufallsbewegungen: Er läuft zufällig von einer unbesuchten Zelle, bis er auf das bestehende Labyrinth trifft, und löscht dabei entstandene Schleifen. Dieses Verfahren wählt gleichverteilt zufällig aus allen möglichen Spannbäumen, sodass jedes Labyrinth dieser Größe gleich wahrscheinlich ist. David Wilson veröffentlichte es 1996.

Er beginnt an einer Zelle, markiert sie als besucht und bewegt sich wiederholt zu einem zufälligen unbesuchten Nachbarn, wobei die Wand zwischen ihnen entfernt und die Zelle auf einen Stapel gelegt wird. Hat eine Zelle keine unbesuchten Nachbarn, geht er zurück, indem er vom Stapel nimmt. Diese Tiefensuche erzeugt die langen, schlängelnden Gänge, die für DFS-Labyrinthe typisch sind.

Jede Zelle enthält eine 1-Byte-Bitmaske, deren Bits offene Durchgänge nach Norden, Osten, Süden und Westen darstellen (Werte 1, 2, 4 und 8). Das Entfernen einer Wand setzt das entsprechende Bit in beiden benachbarten Zellen. Der Renderer liest diese Bits, um verbindende Brücken zwischen Zellen zu zeichnen, und der Löser liest sie, um zu wissen, welche Züge erlaubt sind.

Ja. Jeder Algorithmus ist originalgetreu umgesetzt: DFS mit explizitem Stapel, Prims mit zufälliger Front, Kruskals mit gemischter Kantenliste und Union-Find-Konnektivität und Wilsons mit echten schleifenfreien Zufallsbewegungen. Der BFS-Löser ist eine Standard-Kürzeste-Wege-Suche, sodass die hervorgehobene Route für ein perfektes Labyrinth immer optimal ist.

Kruskals Algorithmus mischt alle Wände und betrachtet sie nacheinander, wobei eine Wand nur entfernt wird, wenn die beiden dadurch getrennten Zellen zu unterschiedlichen Regionen gehören. Eine Union-Find-Struktur (disjunkte Mengen) verfolgt, welche Zellen bereits verbunden sind, sodass der Algorithmus beim Zusammenführen des Rasters zu einem einzigen Baum Schleifen vermeiden kann.

Sie erscheinen bei der Erzeugung von Videospiel-Levels und Dungeons, in prozeduralen Content-Tools und als klassische Lehrbeispiele für Graphentraversierung und Spannbäume. Dieselben Ideen erstrecken sich auf Robotik und Netzwerk-Routing, wo das Finden verbundener, schleifenfreier Pfade durch einen Raum wesentlich ist.