Maze generator with DFS
Tags: algorithms, javascript, svelte, dfs
Published: 2021-05-29 21:11:57

---
title: Maze generator with DFS
published: true
description: dfs algorithms utilization
tags: #algorithm #js #svelte #dfs
cover_image: https://raw.githubusercontent.com/ziskand/maze-by-dfs/28d776ce2631630da0c60843beda84fdad668463/maze_generation.gif
---

## Motivation

**Maze** or in other term _labyrinth_ followed by [_wiki_](https://en.wikipedia.org/wiki/Maze) 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](https://dev.to/ziskand/bfs-dfs-tree-traversing-7-min-recap-53ic) 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](https://en.wikipedia.org/wiki/Tree_%28data_structure%29) 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()](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set) and collected each place we visit there _(and of course anything within this Set should not be reused again)_

## Pseudo Code
```js
	// ------ //
	// 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)
```js
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
```js
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
```js
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)_](https://svelte.dev/repl/024443a95cda4464bbc49ee979dac776?version=3.38.2)
Additionally if you want to tweak the code locally - the [**source**](https://github.com/ziskand/maze-by-dfs) is available in github.