Irrgarten

Ein Irrgarten ist ein Netz von Wegen mit Verzweigungen. In mathematischer Hinsicht handelt es sich also um einen Graph:

• die Orte, von denen mehrere Wege wegführen oder zu denen mehrere Wege hinführen, sind die Knoten des Graphs.
• Wege, die zwei Orte unmittelbar verbinden, entsprechen den Kanten des Graphs.

Ein Irrgarten dient der Unterhaltung: Aufgrund der Verzweigungen ist der Pfad von einem vorgegebenen Anfangsort zu einem Zielort nicht offensichtlich. Deshalb bietet es dem Betrachter (im Falle eines Bildes eines Irrgartens) oder dem Besucher (im Falle einer tatsächlichen Gartenanlage) eine Herausforderung, diesen Pfad zu finden.

Irrgärten können algorithmisch erzeugt werden. Es gibt dafür mehrere Möglichkeiten. Eine Möglichkeit ist der Algorithmus nach J. B. Kruskal:

• Erzeuge für jeden Ort des Irrgartens eine korrespondierende Menge, in der sich nur der Ort befindet.
• Erzeuge eine Liste aller möglichen Wände zwischen jeweils zwei Orten, in zufälliger Reihenfolge.
• Nun wird die Liste der Wände der Reihe nach untersucht: Wenn die Orte auf beiden Seiten der Wand zu unterschiedlichen Mengen gehören, dann wird die Wand durch einen Durchgang ersetzt und die beiden Mengen werden vereinigt. Anderenfalls bleibt die Wand bestehen.

Dieser Algorithmus basiert auf Kruskals Algorithmus für Minimum Cost Spanning Trees:

• Bei den Orten handelt es sich um die Knoten eines Graphs (siehe Graph).
• Die Kanten des Graphs sind die potentiellen Wände oder Durchgänge zwischen den Räumen.
• Den Kanten werden zufällige und unterschiedliche Kosten zugeordnet.
• Eine Kante, die nicht in den aufspannenden Baum aufgenommen wird, entspricht einer Wand des Irrgartens. Eine Kante, die Teil des aufspannenden Baums ist, stellt einen Durchgang im Irrgarten dar.


Download

Das ausführbare Programm zum Erzeugen und Lösen von Irrgärten befindet sich in der unten verlinkten Datei Maze.jar. Die Quelltexte sind ebenfalls in die JAR-Datei eingepackt.


Link

http://en.wikipedia.org/wiki/Maze_generation_algorithm


Maze.jar

Anlage

Abbildung: Beispiel für einen Irrgarten.