Labyrinth

So funktioniert das Script

Zwei klassische Verfahren stecken hier nebeneinander: eines, das ein Labyrinth erzeugt, und eines, das den kürzesten Weg darin findet. Beide gehören zum Grundwerkzeug der Informatik.

const stapel = [{ x: 1, y: 1 }];
gitter[1][1] = false;
while (stapel.length > 0) {
  const jetzt = stapel[stapel.length - 1];
  …
  if (nachbarn.length === 0) { stapel.pop(); continue; }
  …
  stapel.push(ziel2);
}

Das ist das rekursive Zurückverfolgen — hier bewusst mit einem eigenen Stapel statt mit echter Rekursion geschrieben. Der Grund: Bei einem großen Labyrinth würde die Rekursion tausende Ebenen tief gehen und den Aufrufspeicher des Browsers sprengen. Der Stapel als Array kann beliebig wachsen.

Der Ablauf ist einfach: Vom obersten Feld des Stapels aus wird eine zufällige unbesuchte Nachbarzelle gesucht. Gibt es eine, wird die Wand dazwischen eingerissen und die neue Zelle auf den Stapel gelegt. Gibt es keine, wird die aktuelle Zelle vom Stapel genommen — man geht also den eigenen Weg zurück, bis wieder etwas zu tun ist.

[[0, -2], [0, 2], [-2, 0], [2, 0]]
…
gitter[(jetzt.y + ziel2.y) / 2][(jetzt.x + ziel2.x) / 2] = false;

Der Kunstgriff steckt in den Zweierschritten. Das Raster enthält abwechselnd Zellen und Wände: Ungerade Positionen sind Zellen, gerade sind Wände. Nachbarzellen liegen deshalb zwei Felder entfernt, und die Wand dazwischen ist genau der Mittelwert der beiden Positionen. Ein Labyrinth mit 12 × 12 Zellen braucht so ein Raster von 25 × 25 Feldern.

Weil jede Zelle genau einmal besucht wird und immer nur eine Wand zu einer unbesuchten Zelle fällt, kann kein Rundweg entstehen. Daher ist das Ergebnis immer lösbar, und zwischen je zwei Punkten gibt es genau einen Weg.

let rand = [spieler];
while (rand.length > 0) {
  const naechste = [];
  for (const punkt of rand) { … }
  rand = naechste;
}

Die Wegsuche ist eine Breitensuche: Sie betrachtet zuerst alle Felder in einem Schritt Entfernung, dann alle in zwei Schritten, und so fort. Weil sie in Ringen nach außen wächst, ist der erste gefundene Weg zum Ziel garantiert der kürzeste. Eine Tiefensuche fände zwar auch einen Weg, aber irgendeinen.

vorgaenger[schluessel(nx, ny)] = punkt;
…
while (jetzt) {
  pfad.push(jetzt);
  jetzt = vorgaenger[schluessel(jetzt.x, jetzt.y)];
}
return pfad.reverse();

Damit am Ende nicht nur die Länge, sondern der Weg selbst herauskommt, merkt sich die Suche für jedes erreichte Feld, von wo aus es erreicht wurde. Ist das Ziel gefunden, hangelt man sich an diesen Vorgängern rückwärts bis zum Start und dreht die Liste um. Dasselbe Verfahren steckt in jedem Routenplaner.

stift.fillRect(x * kante, y * kante, kante + 0.5, kante + 0.5);

Die halbe zusätzliche Kantenlänge ist kein Versehen: Bei krummen Feldgrößen bleiben zwischen benachbarten Rechtecken sonst haarfeine helle Linien stehen, weil der Browser auf Bildpunkte rundet. Die winzige Überlappung schließt sie. Ein Kniff, den man beim Zeichnen von Rastern immer wieder braucht.

Zum Anpassen: Für Labyrinthe mit Rundwegen reißt ihr nach dem Bau zufällig noch ein paar Wände ein — dann versagt die Rechte-Hand-Regel, und das Labyrinth wird kniffliger. Andere Bauverfahren erzeugen ganz andere Charaktere: Der Algorithmus von Prim liefert kurze, verzweigte Gänge, das hier verwendete Zurückverfolgen dagegen lange, gewundene — deshalb fühlen sich diese Labyrinthe wie ein Irrgarten an und nicht wie ein Schwamm.