Wie erstelle ich ein Labyrinth mit JavaScript?
Durch Zufall bin ich irgendwann mal auf diesen BASIC-Einzeiler gestoßen, mit dem sich eine Art Pseudo-Labyrinth erstellen lässt. Ich habe versucht, das in Plain JavaScript halbwegs kompakt nachzubauen. Dabei kann man kaum übersehen, dass es sich keineswegs um ein richtiges Labyrinth handelt, sondern eher um eine zufällige Anordnung von Strichen ohne Lösungsweg. Also habe ich mich gefragt, wie schwer es wohl sein kann, ein Labyrinth programmatisch und vor allem kompakt zu erzeugen. Dazu gibt es zwar eine Menge Lösungsansätze, mein Ziel ist aber, die Herangehensweise zu beschreiben. Und da wir ja gerade alle zuhause abhängen, ist diese kleine Anleitung entstanden.
Vorbereitung
Der aus meiner Sicht einfachste Ansatz ist es, eine Fläche mit schon gesetzten Wänden möglichst chaotisch zu durchpflügen. Wir brauchen also erstmal eine Fläche mit x * y Zellen, die jeweils mit Wänden voneinandern getrennt sind. In JavaScript sieht das folgendermaßen aus:
function createBlankMaze() {
var rowIndex, colIndex;
var table = document.createElement("table");
var tbody = document.createElement("tbody");
for (rowIndex = 1; rowIndex <= mazeHeight; rowIndex++) {
var row = document.createElement("tr");
for (colIndex = 1; colIndex <= mazeWidth; colIndex++) {
var col = document.createElement("td");
if (rowIndex == 1 && colIndex == 1 ) {
col.style.backgroundColor = "rgb(244,0,0)";
col.setAttribute("type", "start");
} else if (rowIndex == mazeHeight && colIndex == mazeWidth) {
col.style.backgroundColor = "rgb(0,244,0)";
col.setAttribute("type", "finish");
} else {
col.style.backgroundColor = "rgb(255,255,255)";
}
col.setAttribute("id", "cell_" + rowIndex + "_" + colIndex);
row.appendChild(col);
}
tbody.appendChild(row);
}
table.appendChild(tbody);
document.getElementById("maze_container").appendChild(table);
}
Wir erzeugen also eine Tabelle mit 10 Zeilen und 10 Spalten und packen Sie am Ende in ein div mit der Id maze_container. Die “Wände” habe ich für jede Zelle mit CSS definiert:
table td {
border: 1px #000000 solid;
}
Der Eingang in rot befindet sich immer oben links, der Ausgang ist grün und unten rechts. Nun werden wir uns in einer Schleife vom Startfeld in Richtung Ziel bewegen. Mit jedem Schleifendurchlauf bewegen wir uns ein Feld weiter. Daraus entsteht erstmal ein Lösungsweg. Danach müssen natürlich noch die restlichen Felder bearbeitet werden. Dazu werden wir vom Lösungsweg aus Abzweige erzeugen. Los gehts.
Schritt 1: Der simpelste Lösungsweg
Um erstmal eine Schleife als Grundlage zu erhalten, beginnen wir mit einem sehr simplen Lösungsweg. Der geht ganz einfach 9 Felder nach rechts und 9 Felder nach unten. Wir nutzen dazu einfach eine Liste mit Anweisungen:
var exits = ["right", "right", "right", "right", "right", "right", "right", "right", "right", "bottom", "bottom", "bottom", "bottom", "bottom", "bottom", "bottom", "bottom", "bottom"];
(Warum nicht 10, sondern 9? Sobald wir uns auf dem letzen Feld befinden, müssen wir uns nicht weiter bewegen.)
In einer Schleife gehen wir nun diese Liste durch und bewegen unseren Zähler entsprechend eine Zelle nach rechts oder unten:
var currentCell;
var rowIndex = 1;
var colIndex = 1;
for (exitIndex = 0; exitIndex < exits.length; exitIndex++) {
switch(exits[exitIndex]) {
case "right":
colIndex = colIndex + 1;
break;
case "bottom":
rowIndex = rowIndex + 1;
break;
}
currentCell = document.getElementById("cell_" + rowIndex + "_" + colIndex);
currentCell.style.backgroundColor = "#f00000";
}
Hier werden noch keine Wände entfernt, sondern erstmal nur der Weg nachgezeichnet, um eine Idee für den Algorithmus zu bekommen. Und so sieht das aus:
Schritt 2: Einen Funken Abwechslung
Ein wenig Abwechslung erhalten wir, wenn wir uns einfach abwechselnd nach unten und rechts bewegen. Dazu füllen wir die Liste mit den Ausgängen einfach in einer Schleife:
var exits = [];
for (exit = 1; exit <= mazeWidth - 1; exit++) {
exits.push("right");
exits.push("bottom");
}
Das war es schon. Das Ergebnis sieht folgendermaßen aus:
Schritt 3: Die Wände einreißen
Nun sorgen wir dafür, dass tatsächlich ein Weg vom Start zum Ziel entsteht. Dazu werden einfach die Rahmen unten bzw. rechts entfernt, sobald wir uns in die entsprechende Richtung bewegen. Unsere Hauptschleife wird also etwas aufgebohrt.
var currentCell = document.getElementById("cell_1_1");
for (exitIndex = 0; exitIndex < exits.length; exitIndex++) {
exit = exits[exitIndex];
currentCell.style["border-"+exit] = "none";
switch(exit) {
case "right":
colIndex = colIndex + 1;
break;
case "bottom":
rowIndex = rowIndex + 1;
break;
}
currentCell = document.getElementById("cell_" + rowIndex + "_" + colIndex);
currentCell.style.backgroundColor = "#f00000";
switch(exit) {
case "right":
currentCell.style["border-left"] = "none";
break;
case "bottom":
currentCell.style["border-top"] = "none";
break;
}
lastExit = exit;
}
Noch bevor die Schleife startet, legen wir fest, in welcher Zelle wir uns befinden. Nur so können wir den Rahmen entsprechend unseres Ausgangs entfernen. Dazu wird einfach die CSS-Eigenschaft auf “none” gesetzt. Außerdem entfernen wir in der nächsten Zelle jeweils den gegenüberliegenden Rahmen. Wenn wir die vorherige Zelle also nach rechts verlassen haben, müssen wir in der darauffolgenden Zelle den Rahmen links entfernen.
Außerdem muss die Schleife für die Erstellung unserer Ausgänge angepasst werden:
for (exit = 1; exit < mazeWidth; exit++) {
exits.push("right");
exits.push("bottom");
}
Nun reichen uns nicht mehr nur 9 Schritte nach unten und rechts. Da wir nun für jedes Feld den unteren bzw. rechten Rahmen entfernen, müssen wir insgesamt 10 Felder in jede Richtung berücksichtigen. Das Ergebnis ist jetzt tatsächlich schon ein Irrgarten. Allerdings ein ziemlich einfacher:
Schritt 4: Noch mehr Abwechslung
Der nächste Schritt ist naheliegend: Wir durchlaufen nicht einfach die Liste möglicher Ausgänge, sondern entscheiden zufällig, welcher Ausgang als nächstes kommt. Dazu muss die Schleifenbedinung allerdings etwas angepasst werden.
for (loop = 0; loop < (mazeWidth + mazeHeight - 2); loop++) {
exitIndex = Math.floor(Math.random() * exits.length);
exit = exits[exitIndex];
exits.splice(exitIndex, 1);
currentCell.style["border-"+exit] = "none";
switch(exit) {
case "right":
colIndex = colIndex + 1;
break;
case "bottom":
rowIndex = rowIndex + 1;
break;
}
currentCell = document.getElementById("cell_" + rowIndex + "_" + colIndex);
currentCell.style.backgroundColor = "#f00000";
switch(exit) {
case "right":
currentCell.style["border-left"] = "none";
break;
case "bottom":
currentCell.style["border-top"] = "none";
break;
}
lastExit = exit;
}
Die ersten drei Zeilen innerhalb der Zeile sind hier von Bedeutung. Zuerst wird der nächste Ausgang per Zufall bestimmt und in der Variable exit abgelegt. Danach wird dieser Eintrag auch aus der Liste möglicher Ausgänge entfernt. Das ist wichtig, da wir uns ja z.B. nicht mehr als 10 mal nach rechts bewegen können. Außerdem erzeugen wir so eine Art Gewichtung, die sich bei jedem Durchlauf verändert. Würden wir einfach nur per Zufall zwischen rechts und unten entscheiden, wäre das Ergebnis im Moment vielleicht ähnlich. Aber sobald wir auch die Richtungen oben und links dazu nehmen, ist das Ergebnis weitaus chaotischer.
Das Ergebnis ist immer noch recht banal, aber sieht schon etwas mehr nach Labyrinth aus:
Schritt 5: Mehr Bewegungsfreiheit
Bisher haben wir uns nur nach rechts und unten bewegt. Nun wollen wir uns auch nach links und oben bewegen. Dazu noch mal eine wichtige Grundannahme: Wir müssen uns 9 mal nach rechts und unten bewegen, um zum Ziel zu kommen. Erst wenn wir uns ein mal nach rechts bewegt haben, können wir uns dafür ein mal nach linsk bewegen. Das gleiche gilt für oben und unten. Da ich nun vier Bewegungsfreiheiten haben, muss die Schleifenbedingung erneut angepasst werden. Diesmal können wir ja theoretisch jedes der 100 Felder belegen. Außerdem muss ich nun zusätzliche Rahmen entfernen.
while (loop < ((mazeWidth * mazeHeight) - 1)) {
exitIndex = Math.floor(Math.random() * exits.length);
exit = exits[exitIndex];
exits.splice(exitIndex, 1);
currentCell.style["border-"+exit] = "none";
switch(exit) {
case "right":
colIndex = colIndex + 1;
exits.push("left");
break;
case "bottom":
rowIndex = rowIndex + 1;
exits.push("top");
break;
case "left":
colIndex = colIndex - 1;
exits.push("right");
break;
case "top":
rowIndex = rowIndex - 1;
exits.push("bottom");
break;
}
currentCell = document.getElementById("cell_" + rowIndex + "_" + colIndex);
currentCell.style.backgroundColor = "#f00000";
switch(exit) {
case "right":
currentCell.style["border-left"] = "none";
break;
case "bottom":
currentCell.style["border-top"] = "none";
break;
case "left":
currentCell.style["border-right"] = "none";
break;
case "top":
currentCell.style["border-bottom"] = "none";
break;
}
lastExit = exit;
loop++;
}
In der ersten _Switch-_Anweisung gibt es außerdem eine wichtige Anweisung. Wenn der nächste Ausgang nach rechts geht, ergänze ich die Liste möglicher Ausgänge um einen Ausgang nach links (analog natürlich für die anderen Richtungen):
exits.push("left");
Und wie sieht das Ergebnis aus?
Ich würde sagen: Bescheiden. Das Problem ist, dass wir uns nach links bewegen, nachdem wir uns gerade erst nach rechts bewegt haben. Genauso dürfen wir uns nicht nach oben und gleich danach wieder nach unten bewegen.
Wir müssen also etwas nachbessern. Wenn wir uns nun in z.B. der Zelle mit den Koordinaten x = 4 und y = 4 befinden, prüfen wir, ob die drei benachbarten Zellen bereits belegt sind (Hintergrundfarbe ist rot). Ist z.B. die rechte Nachbarzelle belegt, dürfen wir uns nicht nach rechts bewegen.
Auch die Liste möglicher Ausgänge wird etwas anders organisiert:
var validExits = ["right", "bottom", "left", "top"];
var remainingExits = {"right": mazeWidth, "bottom": mazeHeight, "left": 0, "top": 0};
var nextExits = [];
Das Array validExits ist eine globale, nicht veränderbare Liste aller möglichen Ausgänge. Mit remainingExits führen wir ein Objekt ein, dass die Anzahl möglicher bzw. erforderlicher Ausgänge protokolliert. Und nextExits ist das Array, das bei jedem Schleifendurchlauf die möglichen Ausgänge anzeigt. Die überarbeitete Schleife sieht nun so aus:
while (loop < ((mazeWidth * mazeHeight) - 1)) {
nextExits = [];
for (i = 0; i < validExits.length; i++) {
switch(validExits[i]) {
case "right":
nextPossibleCell = document.getElementById("cell_" + rowIndex + "_" + (colIndex + 1));
break;
case "left":
nextPossibleCell = document.getElementById("cell_" + rowIndex + "_" + (colIndex - 1));
break;
case "bottom":
nextPossibleCell = document.getElementById("cell_" + (rowIndex + 1) + "_" + colIndex);
break;
case "top":
nextPossibleCell = document.getElementById("cell_" + (rowIndex - 1) + "_" + colIndex);
break;
}
if (nextPossibleCell == null || nextPossibleCell.style.backgroundColor != "rgb(240, 0, 0)") {
for (t = 0; t < remainingExits[validExits[i]]; t++) {
nextExits.push(validExits[i]);
}
}
}
exitIndex = Math.floor(Math.random() * nextExits.length);
exit = nextExits[exitIndex];
currentCell.style["border-"+exit] = "none";
switch(exit) {
case "right":
colIndex = colIndex + 1;
remainingExits.left++;
remainingExits.right--;
break;
case "bottom":
rowIndex = rowIndex + 1;
remainingExits.top++;
remainingExits.bottom--;
break;
case "left":
colIndex = colIndex - 1;
remainingExits.left--;
remainingExits.right++;
break;
case "top":
rowIndex = rowIndex - 1;
remainingExits.top--;
remainingExits.bottom++;
break;
}
currentCell = document.getElementById("cell_" + rowIndex + "_" + colIndex);
switch(exit) {
case "right":
currentCell.style["border-left"] = "none";
break;
case "bottom":
currentCell.style["border-top"] = "none";
break;
case "left":
currentCell.style["border-right"] = "none";
break;
case "top":
currentCell.style["border-bottom"] = "none";
break;
}
if (rowIndex == mazeHeight && colIndex == mazeWidth) {
break;
}
currentCell.style.backgroundColor = "#f00000";
lastExit = exit;
loop++;
}
Hier wede ich noch mal ein paar Besonderheiten erläutern: Gleich zu Beginn der Schleife durchlaufen wir alle gültigen Ausgänge um so zu den nächsten möglichen Zellen zu kommen (nextPossibleCell). Nur wenn diese Zelle überhaupt existiert (wir uns also nicht am Rand des Irrgarten befinden) und nicht belegt ist (Hintergrundfarbe ist nicht rot), kann die entsprechende Bewegungsrichtung verwendet werden:
[...]
nextExits.push(validExits[i]);
[...]
Danach folgt wieder die Zufallsbestimmung des nächsten Ausgangs. Die Protokollierung der restlichen Ausgänge erfolgt nun etwas anders, am Beispiel von Ausgang “rechts”:
[...]
remainingExits.left++;
remainingExits.right--;
[...]
Der Rest der Schleife bleibt unverändert. Und tatsächlich: Der Irrgarten sieht weitaus schöner aus:
Allerdings fehlt immer noch eine offensichtliche Kleinigkeit: Wir erreichen das Ziel nicht.
Schritt 6: Das Sackgassenproblem
Wir erzeugen eine Sackgasse. Der Weg aus der Sackgasse sieht folgendermaßen aus: Wir müssen uns zurück bewegen. Bei jeder Zelle prüfen wir die möglichen Ausgänge und nehmen einfach einen anderen. Die bereits belegten Zellen bleiben weiterhin belegt.
Da wir nun in den Schleifenablauf eingreifen, führen wir eine Sicherung ein. So vermeiden wir, dass die Schleife z.B. unendlich läuft.
Außerdem führen wir ein weiteres Array lastExits ein, dass den aktuellen Weg protokolliert (das nennt sich übrigens recursive backtracker algorithmus) Gleich der Beginn der Schleife prüft nun erstmal unser Sicherungsnetz:
while (loop < ((mazeWidth * mazeHeight) - 1)) {
loopFuse++;
if (loopFuse >= maxLoops) {break;}
[...]
Danach prüfen wir wie gehabt, welche Ausgänge noch nicht belegt sind. Und dann, bevor wir per Zufall den nächsten Ausgang bestimmen, bauen wir unsere Sackgassen-Schutz-Funktion ein:
[...]
if (nextExits.length == 0) {
lastCells.splice(lastCells.length - 1, 1);
console.log("Sackgasse. Einen Schritt zurück:");
rowIndex = lastCells[lastCells.length - 1][0];
colIndex = lastCells[lastCells.length - 1][1];
currentCell = document.getElementById("cell_" + rowIndex + "_" + colIndex);
continue;
}
exitIndex = Math.floor(Math.random() * nextExits.length);
[...]
Wenn wir uns in einer Sackgasse befinden, entfernen wir einfach die letzte Zelle aus lastCells und setzen den Zeige auf die Zelle davor. Dann verlassen wir den Schleifendurchlauf mit continue. Weiter unten müssen wir natürlich auch dafür sorgen, dass die jeweils aktuelle Zelle zu lastCells hinzugefügt wird:
[...]
lastCells.push([rowIndex, colIndex]);
currentCell = document.getElementById("cell_" + rowIndex + "_" + colIndex);
[...]
Ganz am Ende der Schleife prüfen wir außerdem noch, ob wir uns vielleicht schon am Ziel befinden, um dann die Schleife zu verlassen:
[...]
if (rowIndex == mazeHeight && colIndex == mazeWidth) {
break;
}
currentCell.style.backgroundColor = "#f00000";
loop++;
}
Das Ergebnis überzeugt: Wir erzeugen nun einen verzweigten Weg, der nicht nur nach rechts und unten geht, sondern sogar Sackgassen enthält:
Schritt 7: Noch mehr Sackgassen!
Wie bekommen wir noch mehr Sackgassen in unser Labyrinth? Indem wir die echte Route abgehen und einfach von jeder Zelle aus eine neue Route starten? Ja. Das war auch mein erster Gedanke. Allerdings ist die aktuelle Zielroute oft von Sackgassen umgeben. Wenn wir diesen Weg wählen, könnten also weiterhin einige Felder unbearbeitet bleiben. Deshalb werden wir ziemlich schroff einfach jedes belegte Feld als Startpunkt für einen Abzweig nutzen. Das Erzeugen der Abzweigungen kommt natürlich ohne die Sackgassen-Schutz-Funktion aus.
Dazu müssen wir erstmal die aktuelle Logik in eine Funktion packen, die jetzt drei Parameter erwartet:
startAtRow = 1;
startAtCol = 1;
addRoute(startARow, statrtAtCol, false);
Die Funktion addRoute sieht folgendermaßen aus. False bedeutet also, dass wir keinen Abzeig sondern erstmal die korrekte Route zum Ziel erzeugen wollen.
function addRoute(startAtRow, startAtCol, createDetour) {
var validExits = ["right", "bottom", "left", "top"];
var remainingExits = {"right": mazeWidth, "bottom": mazeHeight, "left": 0, "top": 0};
var nextExits = [];
var lastCells= [];
var rowIndex = startAtRow;
var colIndex = startAtCol;
var currentCell = document.getElementById("cell_" + rowIndex + "_" + colIndex);
var exit;
var lastExit;
var exitIndex;
var loop = 0;
var loopFuse = 0;
var maxLoops = 4 * mazeWidth * mazeHeight;
var nextPossibleCell;
while (loop < ((mazeWidth * mazeHeight) - 1)) {
loopFuse++;
if (loopFuse >= maxLoops) {break;}
nextExits = [];
for (i = 0; i < validExits.length; i++) {
switch(validExits[i]) {
case "right":
nextPossibleCell = document.getElementById("cell_" + rowIndex + "_" + (colIndex + 1));
break;
case "left":
nextPossibleCell = document.getElementById("cell_" + rowIndex + "_" + (colIndex - 1));
break;
case "bottom":
nextPossibleCell = document.getElementById("cell_" + (rowIndex + 1) + "_" + colIndex);
break;
case "top":
nextPossibleCell = document.getElementById("cell_" + (rowIndex - 1) + "_" + colIndex);
break;
}
if (nextPossibleCell != null) {
if (nextPossibleCell.getAttribute("occupied") != "true") {
for (t = 0; t < remainingExits[validExits[i]]; t++) {
nextExits.push(validExits[i]);
}
}
}
}
if (nextExits.length == 0) {
if (createDetour == true) {
if (colIndex == mazeWidth) {
rowIndex++;
colIndex = 1;
} else {
colIndex++;
}
currentCell = document.getElementById("cell_" + rowIndex + "_" + colIndex);
continue;
} else {
lastCells.splice(lastCells.length - 1, 1);
rowIndex = lastCells[lastCells.length - 1][0];
colIndex = lastCells[lastCells.length - 1][1];
currentCell = document.getElementById("cell_" + rowIndex + "_" + colIndex);
continue;
}
}
exitIndex = Math.floor(Math.random() * nextExits.length);
exit = nextExits[exitIndex];
if (createDetour == false) {
currentCell.style["border-"+exit] = "none";
} else {
if (!(exit == "right" && colIndex == mazeWidth - 1 && rowIndex == mazeHeight) &&
!(exit == "bottom" && colIndex == mazeWidth && rowIndex == mazeHeight - 1) ) {
currentCell.style["border-"+exit] = "none";
}
}
switch(exit) {
case "right":
colIndex = colIndex + 1;
remainingExits.left++;
remainingExits.right--;
break;
case "bottom":
rowIndex = rowIndex + 1;
remainingExits.top++;
remainingExits.bottom--;
break;
case "left":
colIndex = colIndex - 1;
remainingExits.left--;
remainingExits.right++;
break;
case "top":
rowIndex = rowIndex - 1;
remainingExits.top--;
remainingExits.bottom++;
break;
}
lastCells.push([rowIndex, colIndex]);
currentCell = document.getElementById("cell_" + rowIndex + "_" + colIndex);
switch(exit) {
case "right":
currentCell.style["border-left"] = "none";
break;
case "bottom":
currentCell.style["border-top"] = "none";
break;
case "left":
currentCell.style["border-right"] = "none";
break;
case "top":
currentCell.style["border-bottom"] = "none";
break;
}
if (rowIndex == mazeHeight && colIndex == mazeWidth) {
break;
}
currentCell.style.backgroundColor = backgroundColorRoute;
currentCell.setAttribute("occupied", "true");
lastExit = exit;
loop++;
}
}
An der Funktionalität hat sich hier nicht viel geändert: Wir prüfen zuerst, welche Ausgänge von der aktuellen Zelle aus möglich sind. Direkt danach allerdings müssen wir, wenn es keine weiteren Ausgänge gibt, die Funktion verlassen - wir wollen ja diesmal explizit Sackgassen erzeugen:
if (createDetour == true) {
return false;
[...]
Weiter unten gibt es eine weitere Besonderheit: Wenn wir den Abzweig erzeugen, darf dieser natürlich nicht “aus Versehen” zum Ziel führen. Wir prüfen also, ob wir uns direkt neben der Zielzelle befinden. In dem Fall wird der Rahmen nicht entfernt:
[...]
if (!(exit == "right" && colIndex == mazeWidth - 1 && rowIndex == mazeHeight) &&
!(exit == "bottom" && colIndex == mazeWidth && rowIndex == mazeHeight - 1) ) {
currentCell.style["border-"+exit] = "none";
}
[...]
Ganz am Ende der Schleife wird außerdem das Attribut occupied der Zelle auf true gesetzt. So müssen wir nicht mehr mit der Hintergrundfarbe arbeiten, um belegte Zellen zu erkennen:
[...]
currentCell.setAttribute("occupied", "true");
[...]
Nun kommen wir zum Erzeugen der Abzweige. Wie schon angekündigt, durchlaufen wir einfach die Zellen, die bereits belegt (occupied == true) sind, um von dort aus unsere bewährte Routenerstellung - jedoch ohne Sackgassen-Schutz-Funktion, zu starten:
for (n = 1; n < (mazeWidth * mazeHeight) - 1; n++) {
var currentCell = document.getElementById("cell_" + startAtRow + "_" + startAtCol);
if (currentCell.getAttribute("occupied") == "true") {
addRoute(startAtRow, startAtCol, true);
}
if (startAtCol == mazeWidth) {
startAtRow++;
startAtCol = 1;
} else {
startAtCol++;
}
}
Et voila: Ein Irrgarten:
Und auch wenn der Algorithmus teilweise etwas stumpf gestaltet ist, kann sich die Performance sehen lassen. Ein Labyrinth mit der Kantenlänge 100 x 100 dauert nur wenige Sekunden:
Natürlich gibt es an der einen oder anderen Stelle noch Optimierungspotential. Ich hab die ganze Logik noch mit einer Navigation und einer Stopp-Uhr ausgestattet. So sieht das ganze dann als Zeitvertreib für die Quarantäne aus: https://nickyreinert.github.io/maze/