JS Tutorial: Labyrinth Generator - Rekursive Backtracker Algorithm

in #deutsch6 years ago

bild2.png

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:

animation (0).gif

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!

Sort:  
Nachdem Dein Beitrag gelesen worden ist hat ein Kurator des German-Steem-Bootcamp entschieden, ihn mit einem Upvote über ein paar Cent zu belohnen
Aktueller Kurator ist @greece-lover
Loading...



This post has been voted on by the steemstem curation team and voting trail.

There is more to SteemSTEM than just writing posts, check here for some more tips on being a community member. You can also join our discord here to get to know the rest of the community!

@resteemator is a new bot casting votes for its followers. Follow @resteemator and vote this comment to increase your chance to be voted in the future!

Coin Marketplace

STEEM 0.17
TRX 0.15
JST 0.028
BTC 62102.06
ETH 2415.08
USDT 1.00
SBD 2.49