I love the aesthetics of mazes. They have an organized chaos to them. The same goes for labyrinths, though they are technically different since a labyrinth is traditionally supposed to have a single path to the center with no dead ends or forks. They are less about getting lost and more about finding your way. Also minotaurs.

## The algorithm

After digging into various maze generation algorithms, the randomized depth-first search seemed like the simplest to implement in real time. The algorithm could be described as:

- Pick a cell (I’m using the top-right corner, but you could also pick a random cell)
- Pick a random neighbor of the current cell
- Connect the current cell to the neighbor
- Make the neighbor the current cell
- Repeat until there are no unvisited cells

Whenever a cell does not have any unvisited neighbors, you have to backtrack to a previous cell with unvisited neighbors. This requires building up a stack of cells that have been visited but not yet fully explored.

## A single SVG path

Let’s go ahead and dig into the code before I get too far ahead of myself. In the HTML, there is simply an inline `svg`

with a single `path`

for our maze drawing, as well as `rect`

for the outside walls.

```
<svg class="maze" xmlns="http://www.w3.org/2000/svg">
<path d="" />
<rect x="0" y="0" width="100%" height="100%" />
</svg>
<style>
svg.maze path,
svg.maze rect {
fill: none;
stroke: currentColor;
}
svg.maze path {
stroke-width: 0.15;
}
svg.maze rect {
stroke-width: 0.3;
}
</style>
```

I am setting the `stroke-width`

to `0.15`

. Technically, what looks like walls in the final maze are actually the corridors, but the aesthetic is the same. Please don’t tell anyone that my maze is a lie.

## The JavaScript

The `runMaze`

function starts by setting the `viewBox`

of the SVG to the size of the element, so I end up with a grid of 16x16 cells that can cover the entire SVG.

```
async function runMaze() {
const svg = document.querySelector('svg.maze');
const CELL_SIZE = 16;
const w = Math.ceil(svg.scrollWidth / CELL_SIZE);
const h = Math.ceil(svg.scrollHeight / CELL_SIZE);
svg.setAttribute('viewBox', `0 0 ${w} ${h}`);
```

The next thing it does is instantiate the stack with the starting cell. I am representing a cell as an array like `[2,3]`

. There is also a `Set`

to keep track of which cells have been visited. Since arrays are passed by reference, I have to convert the cell to a string before adding it to the set. If I were to call `visited.has([2,3])`

, for example, it would always return `false`

for the same reason that `[2,3] === [2,3]`

is false.

```
const start = [w, 0];
const stack = [start];
const visited = new Set([start.join(',')]);
```

To begin drawing the maze, the `path`

is updated to begin drawing at the starting cell. For the sake of keeping the article concise, I am leaving out some code that resets the maze whenever the SVG is resized.

```
const path = svg.firstElementChild;
path.setAttribute('d', `M${start[0]},${start[1]}`);
```

Whenever we have to backtrack up the stack, we do not want to connect the last drawn cell to the next, so I have a `moveNext`

flag that will be set to `true`

whenever we backtrack.

`let moveNext = false;`

Now we can start the main loop. The loop will continue until the stack is empty. The last cell in the stack is the current cell.

```
while (stack.length > 0) {
const cell = stack[stack.length - 1];
const neighbor = getRandomNeighbor(cell, visited, w, h);
```

The `getRandomNeighbor`

function will return a random unvisited neighbor of the current cell. If there are no unvisited neighbors, it will return `null`

.

```
function getRandomNeighbor(cell, visited, w, h) {
const neighbors = getNeighbors(cell, visited, w, h);
if (neighbors.length === 0) return null;
return neighbors[Math.floor(Math.random() * neighbors.length)];
}
function getNeighbors(cell, visited, w, h) {
let neighbors = [];
const [x, y] = cell;
if (x > 0) neighbors.push([x - 1, y]);
if (x < w) neighbors.push([x + 1, y]);
if (y > 0) neighbors.push([x, y - 1]);
if (y < h) neighbors.push([x, y + 1]);
neighbors = neighbors.filter((n) => !visited.has(n.join(',')));
return neighbors;
}
```

Back in our loop, once we have a neighbor, we add it to the stack and mark it as visited. We also draw our SVG path to the cell and ensure `moveNext`

is false.

```
if (neighbor) {
stack.push(neighbor);
visited.add(neighbor.join(','));
appendToPath(path, neighbor, moveNext);
moveNext = false;
```

The `appendToPath`

function appends the cell to the path’s `d`

attribute. If `moveNext`

is true, it will append an `M`

command to move to the cell. Otherwise, it will append an `L`

command to draw a line to the cell.

```
function appendToPath(path, cell, isMove) {
const d = path.getAttribute('d');
path.setAttribute('d', d + ` ${isMove ? 'M' : 'L'}${cell[0]},${cell[1]}`);
}
```

If there are no neighbors, we have to backtrack. We pop the last cell off the stack and set `moveNext`

to true.

```
} else {
stack.pop();
moveNext = true;
}
}
}
```

If you were to put it all together, you would now have a function that instantly generates a maze!

## Final touches

However, I wanted to have the maze draw slowly over time. I did this by adding a `requestAnimationFrame`

promise to the loop. I also added a counter that would only call `requestAnimationFrame`

every 3 iterations. This way, the maze would be generated in real time, but it would not be too slow.

Here is the full `runMaze`

function:

```
async function runMaze() {
const svg = document.querySelector('svg.maze');
const CELL_SIZE = 16;
const w = Math.ceil(svg.scrollWidth / CELL_SIZE);
const h = Math.ceil(svg.scrollHeight / CELL_SIZE);
svg.setAttribute('viewBox', `0 0 ${w} ${h}`);
const start = [w, 0];
const stack = [start];
const visited = new Set([start.join(',')]);
const path = svg.querySelector('path');
path.setAttribute('d', `M${start[0]},${start[1]}`);
let moveNext = false;
let i = 0;
while (stack.length > 0 && i / w < 60) {
const cell = stack[stack.length - 1];
const neighbor = getRandomNeighbor(cell, visited, w, h);
if (neighbor) {
stack.push(neighbor);
visited.add(neighbor.join(','));
appendToPath(path, neighbor, moveNext);
moveNext = false;
if (i % 3 === 0) await new Promise(requestAnimationFrame);
} else {
stack.pop();
moveNext = true;
}
i++;
}
}
```

## Webmentions

Kurau :tokyo: reposted this.