Hallo und herzlich willkommen zum Tutorial, welches euch zeigt, wie ihr in JavaScript eure eigenen Labyrinthe erzeugen könnt. Zur Generierung dieser werden wir heute auf den Randomized Prim's algorithm zurückgreifen.

Für den Fall der Fälle, dass dich der "Recursive Backtracker" Algorithmus zur Generierung von Labyrinthen auch interessiert, habe ich hier bereits einen Blogartikel darüber verfasst.

Der Algorithmus:

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

• Starte mit einen Koordinatensystem voller Wände
• Nehme eine Zelle, markiere Sie als Pfad
• Nehme die Nachbarzellen, welche vom Typ her eine Wand sind und füge Sie einer Liste hinzu.
• Solange es Einträge in der Liste gibt
  • Nehme einen zufälligen Eintrag der Liste
  • Wenn nur eine Nachbarzelle dieser Zelle eine Wand ist,
    • Markiere diese Zelle als Pfad
    • Füge die Nachbarzellen, welche vom Typ her eine Wand sind, der Liste hinzu
  • Entferne diese Zelle von der Liste

---

Vorbereitungen:

Koordinatensystem

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

// Starte mit einen Koordinatensystem voller Wände
var gridsize = 20;
var cells = [];
   for (var i = 0; i < gridsize; i++) {
        for (var j = 0; j < gridsize; j++) {
            cells.push(cell(i, j, true));
        }
  }

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 müssen nach Vorgabe des Algorithmus nur folgende Eigenschaft besitzen:

• Information, ob eine Zelle eine Wand darstellen soll oder nicht

Weitere Informationen fügen wir dem Zellenobjekt hinzu, um damit besser arbeiten zu können:

• Information, wie Hoch & Breit eine Zelle ist
• Schlüssel zur Objektidentifizierung
• X / Y Koordinate der Zelle

Wir generieren unsere Zellenobjekte mit Hilfe eines sogenannten Objekkonstruktors:

function cell(x, y, isWall) {
    var newcell = {
        "x": x,
        "y": y,
        "key" : "x" + x + "y" + y,
        "isWall" : isWall
    };
    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 Zelle, markiere Sie als Pfad

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 unseren ersten Pfad markieren.

function randomPrimMaze() {
    // Pick a cell, mark it as part of the maze
    var initialCell = randomItem(cells);
    initialCell.isWall = false;

---

Als nächstes folgt folgende Anweisung:

Nehme die Nachbarzellen welche eine Wand sind und füge Sie einer Liste hinzu.

Dafür benötigen wir eine Funktion, welche uns die Nachbarzellen der aktuellen Zelle zur Verfügung stellt. Wir wollen unser Zellenobjekt erweitern, sodass dieses uns die Information zur Verfügung stellen kann.

Zunächst implementieren wir eine Hilfsfunktion, welche uns die direkten Nachbarn der Zelle zur Verfügung stellt.

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 nun alle Nachbarzellen zurückgeben, welche vom Typ her eine Wand darstellen.

    // nachbarzellen zurückgeben, welche vom typ her selbst eine wand sind
    newcell.giveWallNeighbors = function () {
        var neighbors = newcell.giveNeighborKeys();
        var wallNeighbors = [];
        for (var i = 0; i < neighbors.length; i++) {
            var key = neighbors[i];
            if (cells[giveIndexByKey(cells, key)].isWall == true) {
                wallNeighbors.push(key);
            }
        }
        return wallNeighbors;
    }

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;
}

Nun können wir die Zellen der Liste hinzufügen

    // Add the walls of the cell to the wall list.
    var wallNeighbors = initialCell.giveWallNeighbors();
    while (wallNeighbors.length) {
        walls.push(wallNeighbors.shift());
    }

---

Als nächstes kommt folgende Anweisung:

Solange es Einträge in der Liste gibt
Nehme einen zufälligen Eintrag der Liste

while (walls.length > 0) {
        // Pick a random wall from the list. 
        var randomWallKey = randomItem(walls);
        var randomWall = cells[giveIndexByKey(cells, randomWallKey)];

gefolgt von folgender Anweisung:

Wenn nur eine Nachbarzelle dieser Zelle eine Wand ist,

Dafür vergleichen wir die Anzahl der maximalen Nachbarn mit der Anzahl der Nachbarn, welche vom Typ her eine Wand sind.

if (randomWall.giveNeighborKeys().length - 1 == randomWall.giveWallNeighbors().length) {}

• Markiere diese Zelle als Pfad & füge die Nachbarzellen dieser Zelle der Liste hinzu

// Make the wall a passage
randomWall.isWall = false;
// mark the unvisited cell as part of the maze.
var wallNeighbors = randomWall.giveWallNeighbors();
// add neighbors to list
while (wallNeighbors.length) {
    walls.push(wallNeighbors.shift());
}

Nun müssen wir die verarbeitete Zelle nur noch von der Liste entfernen. Dafür identifizieren wir zunächst den Index des Eintrags und entfernen diesen dann mit Hilfe der Funktion "splice".

var randomWallWallsIndex = walls.indexOf(randomWallKey);
// Remove the wall from the list
walls.splice(randomWallWallsIndex, 1);

---

Visualisierung des Algorithmus:

Die zufällig auserwählte Zelle wird blau dargestellt. Die Zellen, welche vom Typ her eine Wand sind, zeichnen wir schwarz. Einträge, welche keine Wand sind, sollen grau dargestellt werden. Ein Ausführen des Algorithmus mit Zeichnen des jeweiligen Zustandes ergibt folgendes Animation:

---

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!