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.

"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]++;
}

// 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, indicating a significant bias towards vertical passageways.

One of the simpler ways 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.