Introduction

Chances are, you’ve once wanted to make a progam for generating or solving mazes. There are dozens of maze algorithms. In my opinion, Kruskal’s algorithm is the simplest for generating mazes.
I made a demo of this at /projects/kruskal.

Animation of maze generation
The colored cells are the open cells.

“Perfect” maze

A maze without any loops and without any inaccessible areas is called a perfect maze. From any point, there is one and only one path to any other point, provided you do not retrace your steps. In other words, there is exactly one solution. A perfect maze can also be described as a spanning tree over all the open cells of a maze.

Psuedocode

generateMaze(n) function:

  1. Create a maze of size n × n
  2. Open every other cell in every other row (in a grid)
  3. Calculate numIterations = (n - 1) * (n + 3) / 4
  4. For var i = 0 to numIterations:
    • iterateKruskal()

iterateKruskal() function:

  1. Get a random** closed cell’s (wall) x and y coordinates
  2. Get the two surrounding open cells (A and B) to the wall.
  3. Check if A and B belong to the same group
    • If yes, open the wall
    • (If no, do nothing this time)
function generateMaze(size) {
	let maze = makeEmpty2DArray(size);
	openEveryOtherCell(maze);
	const numIterations = (size - 1) * (size + 3) / 4;
	for (let i = 0; i < numIterations; i++) {
		iterateKruskal();
	}
}

function iterateKruskal() {
	let wall = getRandomOpenCell();
	let [cell1, cell2] = getSurroundingOpenCells(wall);
	if (cell1.group !== cell2.group) {
		openCell(wall); // connect the two groups
	}
}

The functions look like this:

function loop() {
	if(iterateKruskal()) {
		isDone = true;
	}
	if(isDone) {
		window.cancelAnimationFrame(loop);
		return;
	}
	window.requestAnimationFrame(loop);
}
function iterateKruskal() {
	// these next few lines are a way to get the coordinates of a random wall
	let cellA = getRandomLocation(); // one of the original open cells as {x, y}
	let dir = getRandomMovement(); // either (0, ±1) or (±1, 0)

	// coordinates of the wall
	let wall = {
		x: cellA.x + dir.x,
		y: cellA.y + dir.y
	};

	// if wall is already open, redo the algorithm
	if (!isOpen(wall)) {
		return iterateKruskal();
	}

	// coordinates of another open cell next to the wall
	let cellB = {
		x: wall.x + dir.x,
		y: wall.y + dir.y
	};

	// if cellB is out of the grid area, redo the algorithm
	if(isOutOfBounds(cellB)) {
		return iterateKruskal();
	}

	let cellSetA = getHue(cellA.x, cellA.y);
	let cellSetB = getHue(cellB.x, cellB.y);

	// if both cells are already part of the same group, redo the algorithm
	if (cellSetA === cellSetB) {
		return iterateKruskal();
	}

	openCell(wall);

	//
	let abundantHue = renumber(cellSetA, cellSetB);

	setHue(wall, abundantHue);
	drawSquare(wall, hueToColor(abundantHue));

	colors[abundantHue]++;
}
Example of one iteration of Kruskal's algorithm, depicting how cellA, cellB, and the wall are chosen.
Example of one iteration of Kruskal's algorithm, with cellA and dir randomly chosen.
// a function that renumbers all the cells with the less common hue
// to the more common hue and returns the abundantHue
function renumber(hue1, hue2) {
	let abundantHue = (colors[hue1] > colors[hue2]) ? hue1 : hue2;
	let overridenHue = (abundantHue === hue1) ? hue2 : hue1;

	let abundantColor = hueToColor(abundantHue);
	for (let i = 0; i < size; i++) {
		for (let j = 0; j < size; j++) {
			if(getHue(i, j) === overridenHue) {
				setHue(i, j, abundantHue);
				drawSquare(i, j, abundantColor);
			}
		}
	}
	colors[abundantHue] += colors[overridenHue];
	return abundantHue;
}

Vertical/horizontal passage bias

Kruskal’s algorithm tends to produce mazes with a high branching factor which means there are many short dead ends as opposed to long corridors.

The horizontal passageways are colored red and the vertical are colored blue. There are many more blue than red squares.

Visualization of a vertically biased maze, with the horizontal passageways colored red and the vertical colored blue. There are many more blue than red squares.
Left: maze with a vertical passage bias. Right: same maze but with the opened former-walls color coded.

A simple way to add in a specific horizontal or vertical bias is to change the function that determines the location of a wall. horBias is a number from -0.5 (vertical bias) to 0.5 (horizontal bias).

function getRandomMovement() {
	const rand = Math.random();
	const bias = 0.5 + horBias;
	if(rand < bias / 2) { // left
		return {x: -1, y: 0};
	} else if(rand < bias) { // right
		return {x: 1, y: 0};
	} else if(rand < (1 - bias) / 2 + bias) { // up
		return {x: 0, y: -1};
	} else { // down
		return {x: 0, y: 1};
	}
}

Sample trace

The colored cells represent the “open” cells and the white cells are the walls.

Trace of the generation of a 7x7 maze.
Iterations of a 7x7 maze constructed with Kruskal's algorithm.