Hallo und herzlich willkommen zum Tutorial, welches euch zeigt, wie ihr in JavaScript eure eigenen Labyrinthe erzeugen könnt. Zur Generierung dieser werden wir auf den Recursive Backtracker Algorithm zurückgreifen.

Der Algorithmus:

Zunächst wollen wir einmal auf den Algorithmus eingehen und ihn anschließend nachprogrammieren. Es folgt eine freie Übersetzung des unter Wikipedia referenzierten Algorithmus:

• Nehme eine zufällige Zelle und mache diese zur aktuellen Zelle. Markiere sie anschließend als besucht.
• Solange es unbesuchte Zellen gibt
  • Falls die aktuelle Zelle unbesuchte Nachbarn hat
    • Selektiere eine Zelle der Nachbarzellen per Zufall
    • Füge die aktuelle Zelle dem Stack hinzu
    • Entferne die Wand zwischen der aktuellen & selektierten Zelle
    • Mache aus der selektierten Zelle die aktuelle Zelle & markiere sie als besucht.
  • Falls der Stack nicht leer ist
    • Entferne ein Element vom Stack und mache es zur aktuellen Zelle.

---

Vorbereitungen:

Koordinatensystem

Wir werden unsere Zellen mit Hilfe eines Koordinatensystems abbilden. Dabei wollen wir dieses frei Dimensionieren können.

var gridsize = 20;
var cells = [];
for (var i = 0; i < gridsize; i++) {
    for (var j = 0; j < gridsize; j++) {
        cells.push(cell(i, j));
    }
}

Die variable gridsize bestimmt, wie viele Zeilen(y) und Spalten(x) es gibt. Für die jeweilige Zelle wird ein Zellenobjekt im Zellenarray cells gespeichert.

Im Codebeispiel würden aktuell 400 Zellen generiert, welche bei der Erstellung des Labyrinths berücksichtigt werden müssten.

---

Zellengenerierung

Unsere Zellen werden nach Vorgabe des Algorithmus mindestens folgende Eigenschaften besitzen:

• Zustand, ob eine Zelle besucht worden ist oder nicht
• Information, welche Zellwände eingerissen wurden

Weitere Informationen fügen wir der Zelle hinzu:

• Information, wie Hoch & Breit eine Zelle ist
• Schlüssel zur Objektidentifizierung

Wir generieren unsere Zellenobjekte mit Hilfe eines sogenannten Objekkonstruktors:

function cell(x, y) {
    var newcell = {
        "x": x,
        "y": y,
        "wall": [true, true, true, true], // top right left bottom
        "visited": false,
        "key" : "x" + x + "y" + y
    };
    return newcell;
}

---

Umsetzung des Algorithmus

Nun da wir alle Vorkehrungen getroffen haben, ist es an der Reihe den Algorithmus schritt für Schritt umzusetzen.

Nehme eine zufällige Zelle und mache diese zur aktuellen Zelle. Markiere sie anschließend als besucht.

Wir benötigen eine Funktion, welche uns ein zufälliges Element eines Arrays zurückgibt.

// give random item from array
function randomItem(array) {
    return array[Math.floor(Math.random() * array.length)];
}

Nun können wir diese als besucht markieren und Sie zu unserer aktuellen Zelle machen.

function recursiveBacktrackerMaze() {
    // make decision of initial cell
    var initialCell = randomItem(cells);
    var currentCell = initialCell;
    initialCell.visited = true;

---

Als nächstes müssen wir uns um folgende Anweisung kümmern:

Solange es unbesuchte Zellen gibt

Dafür benötigen wir eine Teilmenge unseres Zellenarrays. Und zwar brauchen wir die Zellen, welche als Status" visited = false" haben. Dafür implementieren wir folgende Hilfsfunktion:

function giveUnvisitedCells() {
    var ucells = [];
    for (var i = 0; i < cells.length; i++) {
        if (cells[i].visited == false) {
            ucells.push(cells[i]);
        }
    }
    return ucells;
}

---

Nun da wir immer auf die unbesuchten Zellen zugreifen können, müssen wir uns laut der nächsten Anweisung auch um unbesuchte Nachbarn der Zelle kümmern.

Falls die aktuelle Zelle unbesuchte Nachbarn hat

Dafür implementieren wir 2 Hilfsfunktionen. Zum einen erweitern wir das Zellenobjekt, sodass dieses uns seine direkten Nachbarn zurückgeben kann.

newcell.giveNeighborKeys = function () {
        var array = [];
        // left
        if (x - 1 >= 0) {
            array.push("x" + (x - 1) + "y" + y);
        }
        // right
        if (x + 1 < gridsize) {
            array.push("x" + (x + 1) + "y" + y);
        }
        // up
        if (y - 1 >= 0) {
            array.push("x" + x + "y" + (y - 1));
        }
        // down
        if (y + 1 < gridsize) {
            array.push("x" + x + "y" + (y + 1));
        }
        return array;
    };

Mit Hilfe dieser Funktion wollen wir uns dann alle Zellen zurückgeben, welche nicht besucht worden sind.

    newcell.giveUnvisitedNeighbors = function () {
        var neighbors = newcell.giveNeighborKeys();
        var unvisitedKeys = [];
        for (var i = 0; i < neighbors.length; i++) {
            var key = neighbors[i];
            if (cells[giveIndexByKey(cells, key)].visited == false) {
                unvisitedKeys.push(key);
            }
        }
        return unvisitedKeys;
    };

Dabei generieren wir immer die Schlüssel des zu findenden Objektes.

Um für den generierten Objektschlüssel das passende Objekt zu finden, müssen wir alle Objekte unseres Zellenarrays mit den generierten Schlüssel vergleichen.

function giveIndexByKey(array, key) {
    for (var i = 0; i < array.length; i++) {
        if (array[i].key == key) {
            return i;
        }
    }
    return -1;
}

---

Der Rest des Algorithmus liegt auf der Hand:

Selektiere eine Zelle der Nachbarzellen per Zufall
- Füge die aktuelle Zelle dem Stack hinzu
- Entferne die Wand zwischen der aktuellen & selektierten Zelle
- Mache aus der selektierten Zelle die aktuelle Zelle & markiere sie als besucht.

var unvisitedNeighborKeys = currentCell.giveUnvisitedNeighbors();
        // Falls die aktuelle Zelle unbesuchte Nachbarn hat
        if (unvisitedNeighborKeys.length > 0) {
            // Selektiere eine Zelle der Nachbarzellen per Zufall
            var randomNeighborKey = randomItem(unvisitedNeighborKeys);
            // Füge die aktuelle Zelle dem Stack hinzu
            keysStack.push(currentCell);
            // Entferne die Wand zwischen der aktuellen & selektierten Zelle
            removeWall(currentCell, randomNeighborKey);
            // Mache aus der selektierten Zelle die aktuelle Zelle & markiere sie als besucht.
            currentCell = cells[giveIndexByKey(cells, randomNeighborKey)];
            currentCell.visited = true;
        }

Sollten wir aber keine Nachbarzellen haben, müssen wir auf unseren Stack zurückgreifen

Falls der Stack nicht leer ist
Entferne ein Element vom Stack und mache es zur aktuellen Zelle.

Dadurch ergibt sich dann eine else-if Anweisung

...
} else if (keysStack.length > 0) {
            currentCell = keysStack.pop();
}

Damit sind wir auch schon fertig.

---

Das Ergebnis:

Wenn wir uns nun Schritt für Schritt des Algorithmus anschauen, wird deutlich, warum dieser als "Backtracker" Algorithmus bezeichnet wird. Die aktuelle Zelle wird durch die blaue Zelle dargestellt. Die nicht besuchte Zellen sind rot. Bereits besuchte Zellen sind grün. Dadurch ergibt sich folgendes Bild:

Gegen Ende der Animation sieht man, wie der Algorightmus den bereits gegangenen Weg zurückgeht, bis er eine nicht besuchte Zelle findet, um diese Anschließend als besucht zu markieren. Daher auch der Name "Backtracker Algorithmus".

---

Für die Nerds unter euch hier auch nochmal ein Fiddlelink.

Vielen Dank fürs lesen, falls Ihr irgendwelche Fragen oder Verbesserungsvorschläge haben solltet, lasst es mich bitte in den Kommentaren wissen :)

Wünsche euch allen eine schöne restliche Woche!