Labyrinth
Aus Leo's Wiki
Inhaltsverzeichnis |
Ursprung
Zum Thema Labyrinth liegt schon länger ein unfertiges Progrämmchen auf meiner Platte, das glaub ich entstand, als ich meinte, an diesem Beispiel meinem kleinen Bruder ein wenig Programmieren beibringen zu können. Letztes Wochenende habe ich es nun von C++ nach Java konvertiert und ausgebaut. Im Folgenden möchte ich meine Erkenntnisse teilen.
Wie entsteht ein Labyrinth
Ein Labyrinth entsteht, wenn man in einen Raum mit zwei Türen Wände zieht und dabei niemals Durchgänge zumauert. Um ein Labyrinth mit nur einer eindeutigen Lösung zu erhalten, werden neue Mauerstücke immer an bestehende angebaut. Das macht ein Labyrinth vom Eingang zum Ausgang zwar leichter, ein Labyrinth, aus dem ein "Gefangener" finden muss aber schwerer, da eine einfach Regel wie "immer an der Wand entlang" nicht funktionert, falls man eine Insel umrundet.
Interessant dabei ist, dass man systematisch leichte und schwere Labyrinthe erhalten kann, bzw. ziemlich einfach Labyrinthe erhält, die einer Systematik folgen:
Vom Start zur Mitte zum Ziel
Wenn Wände zufällig an einer beliebigen Wand weiterwachsen, so wachsen alle Wände relativ gleichmäßig auf die zuletzt noch freie Mitte zu. Folglich führt die Lösung dieses Labyrinths auch über die Mitte und es entstehen fast keine Labyrinthe, die auch Wege am Rand enthalten.
Ein Beispiel.
Am Rand entlang zum Ziel
Einzelne Wände am wachsen gänzlich zu hindern um diesen Breitenwuchs zu bremsen ist sicher keine gute Idee, da so evtl. einzelne weiße Flecken entstehen würden. Man kann aber beim Bauen bevorzugt dort weiter bauen, wo man zuletzt gebaut hat. Im Extremfall erhält man eine lange Wand, die den Raum ausfüllt und am Rand einen Weg vom Start zum Ziel lässt.
Ein Beispiel.
Mein Progrämmchen
Da nun im Zuge des debuggens sich herausstellte, dass ich wohl bei meinem ASCII-Labyrinth ein Sonderzeichen falsch übernommen hatte, und ich keinen Bock hatte, weiter mit diesen Sonderzeichen zu hantieren, hab ich mir meine eigenen Bildchen gemalt und hab eine HTML-Ausgabe gebaut. Zu Debug-Zwecken entstand dann auch noch eine Färbung, die angibt, welchen Ursprung und Abstand ein Mauersegment hat. Den Code findet man hier. Und hier ein entsprechendes JavaDoc
Resultate
Wer's genau wissen will
Laut http://www.astrolog.org/labyrnth/algrithm.htm hab ich den Growing-Tree-Algorithm implementiert, allerdings durch die Steuerung, ob in die Tiefe oder in die Breite gebaut wird, trifft die dortige Statistik nicht ganz zu.
Beta
Software ist eigentlich immer Beta. In diesem Fall musste ich auch mal wieder feststellen, dass aus drei Stunden, nach denen dieses Programm Labyrinthe, bzw. Irrgärten (Maze auf englisch) erzeugte, noch tausend kleine Verbesserungen kamen, womit dann bald irgendwie das ganze Wochenende drauf ging.
Final
Ja was fehlt noch? Natürlich unendlich viel (s.o.). Im Moment fehlt mir:
- Auf meiner Homepage einen Irrgartengenerator anbieten zu können
- Weitere Ausgabevariationen
- ASCII
- als ein png
- interaktiv zum drauf zeichnen
- Statistische Anzeige der in [1] gelisteten Parameter
- Inseln
- 1-tiefe Sackgassen verschieben
