A seaswine. A mythical creature in Carta Marina

A Maze Generator

Mazes are fascinating. Few symbols combine extremes in a manner such as a maze; one side attracts our desire to understand what’s rational, another the confusion we experience, when we don’t know if the answer nor if an answer is at hand, at all.

Algorithms for generating mazes are equally fascinating. This post fixate maze generation by use of the Depth-first Search (DFS) algorithm. Depth-first search is used to traverse any graph-like data structure. Therefore, it can be used for solving mazes as well as generating them.

Whilst the Breadth-first Search begins at a ‘root’, and thereafter simultaneously traverse its surrounding nodes, level by level, the DFS algorithm begin by following a branch from a ‘root’ to its end, traverse back to follow another unvisited set of nodes/branch.

I’ve constructed a Maze Generator, following the DFS pseudo code available at Wikipedia. This is a sample output from my Node.js bash environment:

Show me the code?

Origins. An empty ‘map’

Let’s begin by generating an empty ‘map’ of arbitrary size. Each ‘visitable’ cell should at first be surrounded by unvisitable cells - walls.

For now, we’ll make no attempt to use images/tiles and will settle with ASCII-blocks. ░ will represent a walkable cell, ▓ a wall. We always want the maze to be of uneven size for matters of convenience; it so much easier to not have to bother about the walls surrounding the maze as such. The way we’ll create an array will be influenced by the excellent Dr. Axel Rauschmayer. See his post Creating and filling an Array of arbitrary lengths in JavaScript

function newMap(W,H) {

  /* if the the width or height 
   * is a even number, we'll make it uneven
   */
  W % 2 !== 1 && W++;
  H % 2 !== 1 && H++;

  /* here the index, not the value (undefined), is 
   * interesting and what's used to create the 2d array.
   * If either i or j is is even a wall is created, 
   * otherwise a walkable cell.
   */
  return Array.from({length: H}, (_, i) =>
    Array.from({length: W}, (__, j) =>
    i % 2 === 0 || j % 2 === 0
      ? '▓'
      : '░'
    )
  );
}
/*
 * We also need a simple function for drawing our maze.
 */
function renderMap (maze) {
  return maze
  .forEach(col => console.log(
      col.join().replace(/,/g, '')
    ));
}
renderMap(newMap(40,20))

In a Node.js environment this would output:

$ node printMap.js

▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓░▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓

(There are other ways to create (n) dimensional arrays. You could use a for-loop or the fill method of Array…)

An visual explanation of what will happen

The DFS algorithm operates as a graph. How we can move between nodes (and what counts as a node; here each element in the 2d array) determine its structure. This maze will only use straight angles (90 degrees) and therefore there are four possible directions (up, right, down, left), ways of moving between one node and another.

Say this is the first node, positioned at a random x/y in a 2d array of unknown size: