Mit Lenna im Irrgarten

oder bildgestützte Labyrinthgenerierung

 Ja, lange nichts mehr geschrieben. Ich versuche es erst gar nicht mit einer Entschuldigung ... der Stress, die Motivation, das Leben im Allgemeinen.

Das "Hauptprojekt" ist nicht tot. Es ruht bis ich mal wieder mehr Zeit am Stück habe. Bis dahin ein kleiner Zwischenpost.

Benötigt: Ein Labyrinth

Nicht fragen. Es gibt Tage, an denen braucht man einfach einen Irrgarten. Als programmier-affiner Mensch will und vor allem muss man in solchen Momenten das Rad neu erfinden. Zumindest nachdem man mit üblichen Verfahren (Prim's & Co.) zur Labyrinthgenerierung herum experimentiert hat. Mir persönlich waren die Ergebnisse einfach zu langweilig.

Zu erschaffen: Ein Labyrinth

In dieser Not kam mir der Gedanke, den Irrgarten auf Basis eines Vorgabebildes  zu erzeugen. Man nehme also beispielsweise das Bild einer schönen Frau (ganz kanonisch natürlich), drücke auf einen Knopf und schon hat man einen Irrgarten ... wie im realen Leben halt. Ein Labyrinth sei der Vollständigkeit als ein verzweigtes, verwinkeltes Wegesystem definiert; grob formal ein Graph mit Knoten an den Abzweigungen. Eine mögliche Darstellungsform wären z.B, Schwarz/Weiß-Bilder, bei den benachbarte weiße Pixel Gänge symbolisieren, benachbarte schwarze Pixel entsprächen Wänden.

Der Algorithmus

Ausgangsmaterial ist ein Farbbild. Dieses wird auf eine Größe des Labyrinthes skaliert und in ein Grauwertbild konvertiert. Der umgesetzte Algorithmus nutzt für ersteres eine bilineare Skalierung und für letzteres die recht gebräuchliche Formel, dass sich der resultierende Grauwert pro Pixel aus der Wichtung 21% Rot + 71% Grün + 7% Blau ergibt. Andere Resampling-Methoden oder Farbkonversionen sind sicherlich auch ausprobierenswert. In der Praxis hat sich diese Kombination allerdings für die gegeben Bilddaten als hinreichend erwiesen.

Man kann das zu erzeugende Labyrinth nun als S/W-Approximation dieses Grauwertbildes begreifen. Um hier ein möglichst gute Annäherung zu erreichen, sollte man die S/W-Pixel gegenüber dem Original so wählen, dass die Differenz zwischen den beiden minimal ist.

Ein Irrgarten besteht initial komplett aus Wänden (= schwarz). Von einem gegebenen Startpunkt aus (oBdA nehmen wir die Mitte des Bildes), den wir als Gang (= weiß) definieren, können wir uns jetzt zu den direkten vier Nachbarn bewegen ... wenn dort ebenfalls ein Gang wäre. Wir bewegen uns in Zweierschritten. Wir verlängern unsere Gänge also immer im zwei Einheiten. Welchen Weg nehmen wir vom Ausgangspunkt also? Gemäß der Vorgabe möglichst wenig Schaden gegenüber dem Originalbild anzurichten, den Weg, deren zugeordnete Grauwertpixel am wenigstens von Weiß verschieden sind. Da jeweils zwei Pixel pro Richtung betroffen sind, wird die Summe aus beiden gebildet. Um zum Ausdruck zu bringen, dass der Schaden am direkten Nachbarn wichtiger ist, als am übernächsten, werden die beiden noch mit einer Wichtung versehen. In der Umsetzung wurde das Verhältnis 4:1 gewählt, was allerdings nur ein heuristisches Wert ist, der sich in der Praxis als gut herausgestellt hat.

Ggf. würde sich eine Untersuchung lohnen, ob ein größerer Lookahead als zwei Pixel das Ergebnis signifikant verbessern würde.

Nachdem man sich für eine der vier Richtungen entschieden hat, werden die beiden betroffenen Pixel auf weiß gesetzt. Dieses Verfahren könnte man jetzt rekursiv solange fortsetzen, bis man in eine Situation kommt, in der jeder weiterer Schritt eine Wand in Richtung es existenten Ganges öffnen würde. Von dieser Postion aus könnte man dann den bereits gegrabenen Gang wieder zurücklaufen (Backtracking), bis man wieder an eine Stelle kommt, an der man erneut die Wahl hat, sich für eine weitere Richtung zu entscheiden.

Dieser dem Depth-first Search-Algorithmus nahestehende Lösungsansatz hat sich in der Praxis als unbrachbar erwiesen, den er läuft in seinen letzten Stufen in Pixel-Nachbarschaftskonstellation, in denen eigentlich alle Schwarz nach Weiß Umwandelungen zu zu großen Schaden führen.

Stattdessen wurde ein globaler Ansatz gewählt. Nachdem man den Gang erweitert hat, werden nicht nur die neuen Nachbarn als potentielle Kandidaten für die nächsten Abzweigungen gehandelt, sondern ebenfalls die verbliebenen Kandidaten der Vorrunde. Der nächste Durchstich wird nun aus dieser erweiterten Liste ermittelt. Diese Minimumsbestimmung lässt sich effizient mit einem binären Heap abbilden. Das Gesamtverfahren wird dann iterativ solange wiederholt, bis keine weiteren Kandidaten in der Heap-Struktur abgelegt werden und diese sich somit leert. Eine weitere Heuristik hat sich indes als hilfreich erwiesen: Hat man Kandidaten, die potentiell den gleichen Schaden anrichten würden, sind die zu bevorzugen, die Teil eines bereits längeren Ganges sind. Der erzielte Effekt ist somit die Erzeugung längerer Gänge. Geschieht dies nicht, weißt das resultierende Bild verstärkt  "kammartige"-Endregionen mit sehr kurzen Gängen auf, die ästhetisch einen eher unbefriedigenden Eindruck hinterlassen.

Soweit die graue bzw. schwarz/weiße Theorie. Die in Go geschriebene Implementation findet sich als Freie Software auf Bitbucket. Hier ist insbesondere die Variante maze-area.go von Interesse.