Spiele - Labyrinth zeichnen mit Excel

Erzeugung eines Labyrinths

Methoden zum Finden des Weges durch ein Labyrinth sind oft beschrieben worden. In diesem Beitrag geht es um die Erzeugung eines Labyrinths.

Algorithmus von Wilson

Der Algorithmus von Wilson erzeugt ein Labyrinth durch eine Folge von Zufallspfaden, bei denen Schleifen eliminert werden. Ausgehend von einer zufällig ausgweählten Zelle, wird zunächst ein Zufallspfad erzeugt, dessen schlussendliche Länge gleich der Summe von Höhe und Breite des Bereichs ist. Dieser Pfad wird nun als das Labyrinth betrachtet.

Nun wird, ausgehend von einer Zelle, die nicht zum Labyrinth gehört, ein neuer Zufallspfad gestartet und fortgesetzt, bis er

1. auf sich selber trifft. In diesem Fall liegt eine Schlaufe vor, die entfernt wird. Von der gekreuzten Zelle aus wird der Pfad dann fortgeführt
2. auf das Labyrinth trifft. In diesem Fall wird der Pfad zum Labyrinth hinzugefügt

Neue Pfade werden gestartet, bis das Labyrinth alle Zellen im Zeichenbereich umfasst.

Demovideo

Das Video zeigt die Erzeugung eines Labyrinths mit dem VBA-Modul der Excel-Arbeitsmappe, das für diesen Zweck entwickelt wurde