Maze generator with DFS

Motivation

Maze or in other term labyrinth followed by wiki definition:

A maze is a path or collection of paths, typically from an entrance to a goal.

We want to use our knowledge from BFS + DFS recap and figure out a way to apply DFS algorithm in maze generation.

Basic Idea

There are multiple approaches to generate different kinds of labyrinth. Each solution has it's unique requirements and different methodology in algorithm's implementation.

In our case we want to find a way to "transform" an empty space to a valid maze.
Let's try to break down what we just said into requirements.

Valid maze:
- maze should have well defined border (width and height will be just enough for us)
- our maze should have entrance and goal (connected by generated path)
- path generation logic should not be applied outside of the predefined border
- the path (entrance -> goal) should not be boring...

Now when we finally have some basic requirements let's figure out how to match DFS algorithm (that works with tree structured data-sets) and our tree data-set.

Question: Hmmm... hold on a second! We don't have any tree structured data-set, all we have is an empty space... and what are we searching exactly - we remember that DFS is meant for searching, right?

Answer: Well it's partially correct...
We kind of reversing initial purpose of the algorithm - since we don't search for any particular thing, but instead we benefit DFS's approach of reaching the deepest node whenever possible and exploring all valid children of the current place...

The logic is quite simple - if i sit in the middle of a class i have four other students around me (front, back, left and right). If i switch places with the studen on my right side suddenly i have 3 new students sitting around me, now if i switch places again... got it, right?
The result of successful execution will be tree structured data-set of all visited places or in other words - labyrinth path.

Digging Deeper into the details:
Let's figure out a way to treat provided empty space as a world where DFS can be completely functional.
Remember that our requirement to empty space was it's high & width? It comes handy if we want to divide our empty-space into something DFS can handle.

Let's define a logical variable step step = 10 - this variable will help us with multiple calculations.
Now we can claim that our empty-space with height=100 and width=100 can be interpreted as walkable space or in other terms - 10 steps from border to border.
Great! It means that in order to navigate from one point to another we can use steps, for example:

navigate right move: from(x, y) -> to(x + step, y)
navigate left move: from(x, y) -> to(x - step, y)

Now when we have a "walkable" space - we can apply our DFS and discover all possible steps that we can walk to.

Every performed step should be "marked" as visited so we wont enter the infinite loop...
For that purpose we will use Set() and collected each place we visit there (and of course anything within this Set should not be reused again)

Pseudo Code

    // ------ //
    // preset //
    // ------ //

    // empty field for maze generation
    space = {height: 100, width: 100}
    // navigation mean
    step = 10;
    // navigation space limits
    minLimit = 0
    maxLimit = space.Max - step // assuming that width = height

    // initial place - to start maze generation
    firstPlace = (50, 50)

    // --------- //
    // algorithm //
    // --------- //

    // initial step of storing first node - tree root
    collection = stack.push(firstPlace)

    // initialize iteration loop
    do:
        place = stack.pop()
        if place has neighbors:
            checkPotentialNeighbors([up, right, down, left]):
            shuffle([up, right, down, left])  // <-- shuffle result to achive "turn right turn left" effect
            for neighbor in [right, down, up, left]:
                if neigbout <= maxLimit && neighbour >= minLimit:
                    if neighbor not in visitedPlacesSet:
                        stack.push(neighbor)
                        visitedPlacesSet.add(neighbor)
    // termination condition
    while stack not empty

Code Snippet

Maze Generation - (DFS)

import Stack from "./Stack.js";
import Cell from "./Cell.js";   
import Config from  "./Config.js"

const shuffle = (a) => {
    for (let i = a.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [a[i], a[j]] = [a[j], a[i]];
    }
    return a;
};

const DFS = async ({ root }, dataPoints) => {
        const stack = new Stack();
        const visitedNodes = new Set();

        // add enterance & exit nodes
        const enterance = new Cell(Config.minPosition, Config.minPosition);
        const exit = new Cell(Config.maxPosition, Config.maxPosition);
        visitedNodes.add(enterance);
        visitedNodes.add(exit);
        // Svelte store - (reactive observer)
        await dataPoints.update((visited) => (visited = [...visited, enterance]));
        await dataPoints.update((visited) => (visited = [...visited, exit]));

        let node;

        if (!root) {
            return;
        }

        stack.push(root);

        while (stack.size() > 0) {
            node = stack.pop();

            // find all valid children of the node
            let nodeChildren = [];
            // first child
            if (node.y - Config.step <= Config.maxPosition
                    && node.y - Config.step >= Config.minPosition) {
                nodeChildren.push(new Cell(node.x, node.y - Config.step));
            }
            // second child
            if (node.x + Config.step <= Config.maxPosition 
                    && node.x + Config.step >= Config.minPosition) {
                nodeChildren.push(new Cell(node.x + Config.step, node.y));
            }
            // third child
            if (node.x - Config.step >= Config.minPosition 
                    && node.x - Config.step <= Config.maxPosition) {
                nodeChildren.push(new Cell(node.x - Config.step, node.y));
            }
            // fourth child
            if (node.y + Config.step >= Config.minPosition 
                    && node.y + Config.step <= Config.maxPosition) {
                nodeChildren.push(new Cell(node.x, node.y + Config.step));
            }

            let validChildren = nodeChildren.filter(
                (cell) => !visitedNodes.has(JSON.stringify(cell))
            );

            shuffle([...validChildren]).forEach((cell) => {
                if (!visitedNodes.has(JSON.stringify(cell))) {
                    stack.push(cell);
                    visitedNodes.add(JSON.stringify(cell));
                }
            });

            if (validChildren.length !== 0) {
                // Svelte store - (reactive observer)
                await dataPoints.update((visited) => (visited = [...visited, node]));
            }
        }
    };

Cell - logical containner to carry the location data

class Cell {
    constructor(x, y) {
        this.recX = x;
        this.recY = y;
    };

    get x() {
        return this.recX;
    }

    get y() {
        return this.recY;
    }
}

Stack - interface implementation of [push, pop size] functionality

class Stack {
    constructor() {
        this.items = new Array();
    }

    push(item) {
        this.items.push(item);
    }

    pop() {
        return this.items.pop();
    }

    size() {
        return this.items.length;
    }
}

Example

Live example with all the snippets from above is available on DFS Maze Generator (Svelte REPL)
Additionally if you want to tweak the code locally - the source is available in github.

Blog

Maze generator with DFS

Yigal Ziskand

Motivation

Basic Idea

Pseudo Code

Code Snippet

Example

Join Our Newsletter. No Spam, Only the good stuff.

Related