## DEV Community is a community of 696,672 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Maze generator with DFS

Yigal Ziskand
Hopeless Technology Geek

## 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?

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}
step = 10;
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)
// 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);
// 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);
}
});

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.