© alphaspirit, 123RF

Labyrinthe faszinierten schon die alten Griechen. Um schnellstmöglich aus einem solchen Irrgarten herauszufinden, bemüht Mike Schilli seine Go-Programmierkünste.

In Europa sollen Irrgärten ab dem 15. Jahrhundert in Mode gekommen sein, meist auf herrschaftlichen Gütern, auf denen sich Gäste in durch hohe Hecken unterteilten Gartenanlagen verirren durften. Verschlungene Pfade, die teilweise sogar im Kreis führen und auf denen es gilt, von einem Startpunkt aus zu einem Endpunkt zu gelangen, lassen sich aber auch auf Papier zeichnen oder im Computer simulieren. Programme stellen das Wegesystem intern meist als Graphen dar, auf dessen Kanten der virtuelle Gast sich von einem Knoten zum nächsten hangelt, Sackgassen verwirft, aus Endlosschleifen aussteigt und irgendwann am Zielknoten ankommt.

Die rechnergestützte Behandlung von Labyrinthen teilt sich in zwei Aufgaben: das Erzeugen von Irrgärten und deren möglichst effektives Durchschreiten mittels eines Lösungsprogramms (Solver). Man sollte es nicht für möglich halten, aber auf Amazon findet sich tatsächlich ein Buch zum Thema “Labyrinthe für Programmierer” [1]. Dessen Kindle-Version ist zwar wegen Font-Problemen gründlich misslungen, aber die Papierausgabe zeigt einige nützliche Verfahren zum Erstellen und Lösen von Labyrinthen.

Von Zelle zu Zelle

Ein Labyrinth besteht aus einer Matrix von M x N Zellen, wobei in Abbildung 1 jeweils rote Pfeile bestimmen, in welche Richtung ein Wanderer sie verlassen darf. Diese Optionen bestimmen dann die eingezeichneten Wände, die eine Zelle von ihren Nachbarn trennt.

Abbildung 1: Ein rechnergeneriertes 5×4-Labyrinth samt der erlaubten Richtungswechsel von Zelle zu Zelle.

So bestimmt die Startzelle an den Koordinaten (0, 0), dass aus ihr nur ein Weg in Ostrichtung herausführt. Daraus schließt der Algorithmus zum Zeichnen des Labyrinths, dass die Ostwand fehlt, und zeichnet die Südmauer dick ein. Die erlaubten Richtungswechsel definiert das Programm später als North, South, East und West. Gibt eine Zelle East an, muss die rechts von ihr liegende logischerweise mindestens West sagen, da der Wanderer das Labyrinth in beiden Richtungen beschreiten darf.

Die rechnerinterne Darstellung des Labyrinths als Graph zeigt Abbildung 2. Vom Startknoten (0, 0) führt nur ein Weg weg, und zwar zum Knoten (0, 1), der rechts vom Startknoten liegt. Bei der ersten Koordinate handelt es sich also um den Y-Wert, der die Zeile bestimmt, beim zweiten um den X-Wert für die Spalte – analog dazu, wie Programme üblicherweise Matrizen speichern.

Abbildung 2: Ein Labyrinth als Graph: Die Zellen als Knoten, erlaubte Wege als Kanten.

package main
import (
  "fmt"
  "math/rand"
  "time"
)
const (
  North = 1 << iota
  South
  West
  East
)
type Cell struct {
  X, Y     int
  Options  int
  Visited  bool
  Solution bool
}
type Maze struct {
  Cells  [][]Cell
  Width  int
  Height int
  Start  *Cell
  Finish *Cell
}
var Turns = []int{North, South, West, East}
func main() {
  width := 5
  height := 4
  rand.Seed(time.Now().UnixNano())
  maze := newMaze(width, height)
  maze.Start = &maze.Cells[0][0]
  maze.Finish = &maze.Cells[height-1][width-1]
  makeMaze(maze)
  solution := maze.Solve()
  for _, step := range solution {
    step.Solution = true
  }
  fmt.Print(maze.toString())
}

Das Hauptprogramm in Listing 1 legt mit »newMaze()« in Zeile 37 ein neues Labyrinthmodell an. Es folgt die Definition von Ein- und Ausgang mit den Zellen ganz links oben und rechts unten. »makeMaze()« in Zeile 41 wirft den Zufallsgenerator an und baut die Mauern ein. Der Aufruf von »Solve()« in Zeile 43 findet einen Weg vom Ein- zum Ausgang. Zurück kommt ein Array-Slice von Zellen, die auf diesem Weg durchschritten wurden. Die For-Schleife ab Zeile 45 markiert sie in der internen Darstellung, die »Print()« in Zeile 47 ins Terminal schreibt.

Die restlichen, in Listing 2 zusammengefassten Funktionen helfen sowohl dem Generator als auch später dem Solver beim Abarbeiten der Zellen. So hat jede Zelle ein Feld »Visited«, das Algorithmen auf »true« setzen, falls sie sie schon bearbeitet haben. Die Funktion »Reset()« ab Zeile 8 setzt alle Felder der Matrix nach getaner Arbeit wieder zurück auf den ursprünglichen Zustand.

Die Funktion »Neighbors()« ab Zeile 32 gibt alle direkten Nachbarn einer Zelle in allen vier Himmelsrichtungen als Array-Slice von Pointern auf »Cell«-Typen zurück. »Move()« ab Zeile 44 schreitet ausgehend von einer gegebenen Zelle in die angegebene Himmelsrichtung und gibt einen Pointer auf die Zielzelle zurück. Landet der Sprung außerhalb des Matrix-Universums, kommt ein Fehler zurück.

package main
import (
    "errors"
    "math/rand"
)
func newMaze(width int, height int) *Maze {
  var cells [][]Cell
  for y := 0; y < height; y++ {
    row := make([]Cell, width)
    for x := 0; x < width; x++ {
      row[x].X = x
      row[x].Y = y
    }
    cells = append(cells, row)
  }
  return &Maze{
    Width:  width,
    Height: height,
    Cells:  cells}
}
func (maze *Maze) Reset() {
  for x := 0; x < maze.Width; x++ {
    for y := 0; y < maze.Height; y++ {
      maze.Cells[y][x].Visited = false
    }
  }
}
func (maze Maze) Neighbors(cell *Cell) []*Cell {
  neighbors := []*Cell{}
  for _, direction := range Turns {
    tcell, err := maze.Move(cell, direction)
    if err != nil || tcell.Visited {
      continue
    }
    neighbors = append(neighbors, tcell)
  }
  return neighbors
}
func (maze Maze) Move(cell *Cell, turn int) (*Cell, error) {
  var dx, dy int
  switch turn {
  case North:
    dy = -1
  case South:
    dy = 1
  case West:
    dx = -1
  case East:
    dx = 1
  }
  if cell.X+dx > maze.Width-1 ||
    cell.X+dx < 0 ||
    cell.Y+dy > maze.Height-1 ||
    cell.Y+dy < 0 {
    return cell, errors.New("Stepped outside")
  }
  return &maze.Cells[cell.Y+dy][cell.X+dx], nil
}
func makeMaze(maze *Maze) {
  stack := []*Cell{}
  maze.Start.Options = East
  stack = append(stack, maze.Start)
  for len(stack) > 0 {
    lastIdx := len(stack) - 1
    cur := stack[lastIdx]
    stack = stack[:lastIdx]
    ncells := maze.Neighbors(cur)
    if len(ncells) > 0 {
      stack = append(stack, cur)
      idx := rand.Intn(len(ncells))
      rcell := ncells[idx]
      rcell.Visited = true
      cellConnect(cur, rcell)
      stack = append(stack, rcell)
    }
  }
}
func cellConnect(c1 *Cell, c2 *Cell) {
  if c1.X == c2.X {
    if c1.Y < c2.Y {
      c1.Options |= South
      c2.Options |= North
    } else {
      c1.Options |= North
      c2.Options |= South
    }
  }
  if c1.Y == c2.Y {
    if c1.X < c2.X {
      c1.Options |= East
      c2.Options |= West
    } else {
      c1.Options |= West
      c2.Options |= East
    }
  }
}

Abbildung 3 zeigt drei aufeinanderfolgende Aufrufe des aus den Listings generierten Binaries »maze«. Der Algorithmus erzeugt jedes Mal ein anderes Labyrinth, und immer findet der Solver einen Weg vom Ein- zum Ausgang.

Abbildung 3: Drei verschiedene 5×4-Labyrinthe mit Pfaden vom Start links oben zum Ziel rechts unten.

Entstehungsweg

Wie entsteht nun so ein rechnergenerierter Irrgarten? Die meisten Algorithmen dafür entstanden schon vor über 50 Jahren [2], Wikipedia listet die bekanntesten auf [3]. Für diesen Snapshot kommt das iterative Verfahren zum Einsatz.

Listing 1 definiert dazu in Zeile 23 ein Labyrinth vom Typ »Maze« mit einem zweidimensionalen Array-Slice von Zellen vom Typ »Cell«. Außer den Dimensionen der Zellenmatrix speichert die Struktur auch noch den Start- und den Endpunkt des gesuchten Lösungswegs.

Die Zellen des Labyrinths wiederum bestehen gemäß ihrer Definition ab Zeile 16 aus den X/Y-Koordinaten der Zelle, den Pfadoptionen sowie Markern dafür, ob der Algorithmus sie schon abgehandelt hat und ob sie einen Teil des Pfads zur Lösung bilden.

Am Startpunkt beginnend, arbeitet sich das Programm zu benachbarten Zellen vor und wechselt dabei zufallsbedingt immer wieder die Richtung. Manövriert es sich in eine Sackgasse hinein, in der es keine bisher nicht besuchten Zellen als Nachbarn mehr findet, macht es sich auf die Suche nach neuen Kandidaten, die an bereits vorher durchschrittenen Zellen hängen. Alle noch abzuarbeitenden Zellen schiebt »makeMaze()« in Listing 2 auf einen Stack, von wo es sie später abholt, die Zellennachbarn abklappert und dort nach neuen Kandidaten sucht.

Dabei knöpft sich Zeile 83 einen zufälligen Nachbarn der zuletzt untersuchten Zelle vor, reißt mit »cellConnect()« die trennende Mauer zu ihm ein und erlaubt anschließend über die Zellenvariable »Options« Verbindungen in der jeweiligen Himmelsrichtung. Dabei erfahren beide Zellen der Richtung entsprechende Änderungen. Um zum Beispiel eine Verbindung zwischen zwei übereinanderliegenden Zellen einzurichten, erhält die untere Zelle die Option »North« als gangbaren Weg, die obere die Option »South«.

Komplizierter Pop

Um in Go das letzte Element von einem Array-Slice zu entfernen und in einer Variablen abzulegen, wie ab Zeile 75 in Listing 2, sind erstaunlich viele Schritte nötig. Skriptsprachen wie Python machen das ratzfatz mit »pop()«.

Go besteht jedoch darauf, erst den letzten Index des Arrays anzusprechen (»len(slice)-1«) und den dortigen Wert abzuholen. Anschließend gilt es, das Teil-Slice von den Indexnummern »0« bis »len(slice)-1« (ausschließlich, also ohne das letzte Element) wieder der Slice-Variablen zuzuweisen (Listing 3). Dank Gos interner Slice-Arithmetik, die nur Pointer verschiebt, aber keine Elemente umkopiert, ist das Ganze sehr effizient – aber im Programmcode nicht ganz einfach zu lesen.

last = slice[len(slice)-1]
slice = slice[:len(slice)-1]

Effizient geodert

Um eine Reihe von Optionen effizient in einer Integer-Variablen ablegen zu können, definiert Listing 1 die Himmelsrichtungen als Konstanten. Das Schlüsselwort »iota« mit dem Operator »<<« in Zeile 10 setzt die Werte der Konstanten »North«, »South«, »West« und »East« als Zweierpotenzen, also auf die Werte »1«, »2«, »4« und »8«.

Das ermöglicht, eine Variable (wie etwa »Options«) durch binäres Odern auf mehrere dieser Werte zu setzen. Soll eine Zelle zum Beispiel Übergänge sowohl nach Norden als auch nach Osten zulassen, stellt das Programm deren Wert auf »1 | 8« ein – also 9. Will es später testen, ob Norden eine Option darstellt, prüft es »Option & 8«, was immer dann ungleich null ist, falls vorher eine 8 hineingeodert wurde.

Kommissar Zufall

Beim zufälligen Auswählen von Elementen aus einem Array-Slice wie in Zeile 83 von Listing 2 gilt es, aufzupassen wie ein Luchs, damit der Zugriff auch wirklich zufällig erfolgt und nicht etwa manche Elemente bevorzugt erscheinen. Die Funktion »Intn(x)« aus dem Standardpaket math/rand liefert dazu gleichverteilte Zufallswerte in Form einer Ganzzahl zwischen »0« einschließlich und dem Integerwert »x« ausschließlich.

Im Codestück aus Listing 4 liefert »len(slice)« die Anzahl der Elemente im Array; der Index des letzten Elements liegt aber um eins niedriger. Also liefert der Zufallsgenerator gleichverteilte Indexwerte zwischen 0 und »len(slice)-1«, jeweils einschließlich – genau das vom Doktor verordnete Medikament zur Auswahl eines zufälligen Array-Elements.

idx := rand.Intn(len(slice))
randElement := slice[idx]

Was passiert, wenn der Zufallsgenerator keine rein zufälligen Werte ausspuckt, sondern in eine Richtung tendiert, also Vorlieben hat (Bias), zeigt Abbildung 4: Öde Labyrinthe, die kein Mensch je anpacken würde – aber der Computer macht natürlich trotzdem einen guten Job.

Abbildung 4: Ein defekter Zufallsgenerator mit Vorlieben generiert nur langweilige Labyrinthe.

Damit der Generator nicht bei jedem erneuten Programmlauf dasselbe Labyrinth generiert, muss »main()« ihn auf einen Wert initialisieren, der sich von Aufruf zu Aufruf unterscheidet. Zeile 36 in Listing 1 setzt ihn deswegen mittels »rand.Seed()« auf die aktuelle Uhrzeit in Nanosekunden, die auf ein relativ breites Spektrum streut.

Reise ohne Ziel?

Dass der Algorithmus zum Generieren nur den Startpunkt erhält und scheinbar keinen Endpunkt des Labyrinths braucht, liegt daran, dass das Verfahren Wege generiert, auf denen der Wanderer alle Punkte des Irrgartens erreichen kann. Das Verfahren stellt sicher, dass keinerlei abgeschottete Sektionen entstehen. Insofern ist garantiert, dass der Solver später jeden wahlfrei definierten Endpunkt erreicht.

Endlosschleifen beherrscht er ebenfalls nicht, da er niemals auf bereits vorher beschrittene Wege einbiegt. Wer solche Irrgärten möchte, findet eine breite Palette weiterer Algorithmen, die sich ebenfalls einfach implementieren lassen.

Malstunde

Um das Labyrinth auf den Bildschirm zu bringen, kann das Programm entweder eine Grafikbibliothek bemühen oder im einfachsten Fall Zeichen per ASCII-Art ins Terminal schreiben. Da einzelne Zellen im Labyrinth ihre Mauern mit den Nachbarzellen teilen, brauchen sie sich nicht um die Darstellung aller ihrer vier Wände zu bemühen: Es genügen zwei, den Rest erledigen die nördlichen und westlichen Nachbarn.

Der Algorithmus zum Malen des Labyrinths muss also wie in Listing 5 von links nach rechts und von oben nach unten durch die Zellen der internen Darstellung iterieren. Er zieht bei jeder Zelle unten eine Wand ein, es sei denn, die Zelle steht in Richtung »South« offen, und zeichnet rechts eine Wand, falls »East« keine Option ist. Liegt eine Zelle am Rand des Labyrinths – also ganz links, rechts, oben oder unten –, bringt der Algorithmus in diesen Richtungen ebenfalls Mauern an.

package main
func (maze Maze) toString() string {
  output := ""
  for x := 0; x < maze.Width; x++ {
    output += "+---"
  }
  output += "+\n"
  for y := 0; y < maze.Height; y++ {
    upper := "|"
    lower := "+"
    for x := 0; x < maze.Width; x++ {
      wall := "|"
      if (maze.Cells[y][x].Options & East) != 0 {
        wall = " "
      }
      sol := " "
      if maze.Cells[y][x].Solution {
        sol = "o"
      }
      upper += " " + sol + " " + wall
      wall = "---"
      if (maze.Cells[y][x].Options & South) != 0 {
        wall = "   "
      }
      lower += wall + "+"
    }
    output += upper + "\n"
    output += lower + "\n"
  }
  return output
}

Dabei besteht, wie man in Abbildung 4 erkennt, jede Zelle aus drei Zeilen und vier Spalten von ASCII-Zeichen. Die unterste Zeile enthält bei einer geschlossenen Südwand den String »”+—“«, ist sie offen, steht dort »”+ “«. Bei einer geschlossenen Ostwand steht in der zweiten Zeile von oben das Pipe-Zeichen »|«, bei einer offenen Wand stattdessen ein Leerzeichen. Um die Nord- und Westwände braucht sich die Zelle, wie gesagt, nicht zu kümmern, das erledigen die Süd- beziehungsweise Ostwände der Nachbarzellen ordnungsgemäß.

Lösungen suchen

Steht das Labyrinth nach dem Aufruf von »makeMaze()« in Zeile 41 von Listing 1 fest, sucht die Funktion »Solve()« in Listing 6 nach einer Lösung, um vom Start- zum Zielpunkt zu gelangen.

package main
func (maze Maze) Solve() []*Cell {
  maze.Reset()
  stack := []*Cell{maze.Start}
  for len(stack) > 0 {
    cur := stack[len(stack)-1]
    cur.Visited = true
    if cur.X == maze.Finish.X &&
       cur.Y == maze.Finish.Y {
      return stack
    }
    var moveto *Cell
    for _, turn := range Turns {
      if (cur.Options & turn) != 0 {
        trycell, err := maze.Move(cur, turn)
        if err == nil && !trycell.Visited {
          moveto = trycell
          break
        }
      }
    }
    if moveto == nil {
      // nowhere to go, backtrack
      stack = stack[:len(stack)-1]
      continue
    }
    stack = append(stack, moveto)
  }
  return stack
}

Der Solver sucht Depth-First, dringt also erst einmal in die Tiefe vor, um mit einem Schnellschuss eine Lösung zu finden. Die Alternative wäre, an jeder Abzweigung alle Möglichkeiten durchzuprobieren, um so am Ende auf dem kürzesten Weg ins Ziel zu gelangen (Breadth-First).

Führen im Labyrinth manche Wege im Kreis, stellt das primitive Solver vor eine Herausforderung, denn sie dürfen sich nicht festfressen, indem sie ewig im Kreis rennen. Unser Solver »Solve()« hingegen wäre gegen das Problem gewappnet, denn er markiert bereits bearbeitete Zellen im Feld »Visited« und würde nie auf die Idee kommen, eine davon nochmals zu behandeln.

Der Solver prescht also vom Startpunkt aus entlang erlaubter Pfade vor, nimmt jeweils die erstbeste Abzweigung, und schiebt die korrespondierende Zelle auf den Stack »stack«. Kommt er zufällig am Zielpunkt vorbei, sagt er die Jagd ab und beendet sich siegreich, mit den auf dem Stack aufgestapelten Zellen als Lösungsweg. Das ist nicht unbedingt der kürzeste Pfad zur Lösung, aber der Algorithmus hat ihn zumindest schnell gefunden.

Kommt er hingegen nicht am Ende des Labyrinths an, sondern an dem einer Sackgasse, muss er sich an seinem eigenen Stack zurückhangeln. Er wandert zurück zu einer vorher genommenen Abzweigung und erforscht von dort einen alternativen Pfad. Auf diese Weise kommt er irgendwann am Ziel vorbei und gibt den bis dahin aufgebauten Stack als Lösungweg zurück an den Aufrufer.

Das Hauptprogramm markiert mit diesen Daten die Zellen entlang des Wegs, indem es jeweils deren Flag »Solution« auf einen wahren Wert setzt. Die Druckfunktion schreibt in solche Zellen ein »o«.

Alles zusammen

Die vier maßgeblichen Listings dieser Ausgabe kompiliert das Kommando aus Listing 7 in ein Binary »maze«, das beim Aufruf ein 5×4-Labyrinth samt Lösung ausspuckt. Die Dimensionen lassen sich leicht über die Werte für »width« und »height« in »main()« verändern, und auch das Ausprobieren unterschiedlicher Algorithmen zum Generieren und Lösen neuer aufregender Labyrinthe sei dem interessierten Bastler nahegelegt. (uba/jlu)

$ go build maze.go print.go solve.go manip.go