0 Spicy Yoghurt | Last updated: 20 November 2026 | Algorithm tutorial
Build a maze generator in JavaScript
Learn how maze generation algorithms work by building a maze generator in JavaScript. Watch depth-first search, Prim's algorithm, Kruskal's algorithm and five others build a maze step by step. Then add loops to the maze and find the way out. You'll also turn your maze into a little game you can play in your browser.
Every algorithm in this tutorial makes a maze, but each one makes a different kind. Some dig long, winding corridors, others leave lots of short dead ends, and one of them builds walls instead of knocking them down. Pick an algorithm in the demo below and watch it work. When the maze is done, the text above it shows how many of the cells are dead ends: cells you can only leave the way you came in.
What is a perfect maze?
Each maze in this tutorial starts as a grid of square cells, with a wall on every side of every cell. To turn a grid like that into a maze, you knock down some of the walls, so you can walk from one cell into the next. Knock down too few, and you can't reach parts of the grid. Knock down too many, and you get a big empty room.
Most maze generation algorithms make a perfect maze. In a perfect maze, you can reach every cell, and there's exactly one path between any two cells. There are no loops and no closed-off areas. Click or tap two cells in the demo below to see the only path between them:
Now switch the demo to Tree. It draws a line from the middle of every cell through each gap in its walls. Those lines branch out to every cell, but they never come back together, just like the branches of a tree.
In math, a tree like that is called a spanning tree: a tree that reaches every cell of the grid. Every perfect maze is a spanning tree, and every algorithm in this tutorial builds one, each in its own way. That's why their mazes look so different.
Store the maze in a grid
Before you can build a maze, you need a way to store it. Store every cell as an object with its position and its four walls. true means the wall is still standing:
function createGrid(columns, rows) {
let grid = [];
for (let y = 0; y < rows; y++) {
let row = [];
for (let x = 0; x < columns; x++) {
row.push({
x: x,
y: y,
top: true,
right: true,
bottom: true,
left: true
});
}
grid.push(row);
}
return grid;
}The grid is an array of rows, and each row is an array of cells. So grid[y][x] gives you the cell in column x of row y.
A wall between two cells belongs to both of them: the right wall of one cell is the left wall of the cell next to it. So to knock down a wall, you change both cells. The directions array helps with that. For each side of a cell, it holds the step to the neighbor on that side and the name of the wall on that side. opposite is the name of the same wall, as seen from the neighbor:
const directions = [
{x: 0, y: -1, wall: 'top', opposite: 'bottom'},
{x: 1, y: 0, wall: 'right', opposite: 'left'},
{x: 0, y: 1, wall: 'bottom', opposite: 'top'},
{x: -1, y: 0, wall: 'left', opposite: 'right'}
];
function getNeighbors(grid, cell) {
let neighbors = [];
for (let direction of directions) {
let x = cell.x + direction.x;
let y = cell.y + direction.y;
let inside =
x >= 0 && x < grid[0].length &&
y >= 0 && y < grid.length;
if (inside) {
neighbors.push(grid[y][x]);
}
}
return neighbors;
}
function getDirection(a, b) {
return directions.find(function (direction) {
return a.x + direction.x == b.x &&
a.y + direction.y == b.y;
});
}
function removeWall(a, b) {
let direction = getDirection(a, b);
a[direction.wall] = false;
b[direction.opposite] = false;
}On the canvas, y increases as you go down, so row 0 is the top row, and a step of -1 in y goes one row up. getNeighbors() returns the cells next to a cell, but only the ones inside the grid. A cell in a corner has two neighbors, and a cell along the edge has three. getDirection() works out which side of cell a touches cell b, and removeWall() uses it to knock down the wall between them, on both sides.
To draw the maze, draw a line for every wall that's still standing. size is the width of a cell in pixels:
function drawMaze(context, grid, size) {
context.strokeStyle = '#303030';
context.lineWidth = 2;
context.lineCap = 'square';
context.beginPath();
for (let row of grid) {
for (let cell of row) {
let x = cell.x * size;
let y = cell.y * size;
if (cell.top) {
context.moveTo(x, y);
context.lineTo(x + size, y);
}
if (cell.right) {
context.moveTo(x + size, y);
context.lineTo(x + size, y + size);
}
if (cell.bottom) {
context.moveTo(x, y + size);
context.lineTo(x + size, y + size);
}
if (cell.left) {
context.moveTo(x, y);
context.lineTo(x, y + size);
}
}
}
context.stroke();
}A wall between two cells gets drawn twice, once for each cell. That's no problem: the second line lands exactly on top of the first. All the walls are added to the same canvas path, so stroke() only has to draw once. lineCap = 'square' makes every line a little longer at both ends, so the walls meet neatly at the corners. If drawing lines like this is new to you, the tutorial about drawing on the HTML5 canvas explains moveTo() and lineTo().
Click or tap a wall in the demo below to knock it down or put it back. Each cell shows its place in the grid as [y][x]: first the row, then the column. The code shows the two cells on either side of the wall you clicked:
// grid[1][2]
{x: 2, y: 1, top: false, right: false, bottom: true, left: true}
// grid[1][3]
{x: 3, y: 1, top: false, right: true, bottom: true, left: false}This isn't the only way to store a maze. The tutorial on pathfinding in JavaScript uses a grid where a wall takes up a whole cell. That's handy for a game level, and at the end of this tutorial, you'll turn your maze into one. But while you build a maze, walls between cells are easier to work with: every cell is a place you can walk through, and every wall is something you can knock down.
Start with the binary tree algorithm
The simplest maze algorithm doesn't even look at the rest of the maze. Go through the cells one by one, and for each cell, knock down either its top wall or its right wall, at random. That's the binary tree algorithm:
function getRandomItem(array) {
return array[Math.floor(Math.random() * array.length)];
}
function binaryTree(grid) {
for (let row of grid) {
for (let cell of row) {
let options = [];
if (cell.y > 0) {
options.push(grid[cell.y - 1][cell.x]);
}
if (cell.x < row.length - 1) {
options.push(row[cell.x + 1]);
}
if (options.length > 0) {
removeWall(cell, getRandomItem(options));
}
}
}
}The tutorial on random numbers in JavaScript explains how getRandomItem() works, along with lots of other ways to use randomness in a game. options holds the neighbor above and the neighbor to the right. A cell in the top row has no neighbor above it, and a cell in the rightmost column has nothing to its right, so they only get one option. The cell in the top-right corner gets none at all.
That's a maze in a handful of lines. So what's the catch? In the demo below, the red cell is the cell the algorithm is working on, and the gray cells are the ones it hasn't reached yet. Watch it a few times:
The top row is one long, straight corridor, and so is the rightmost column. Every cell in the top row can only open to the right, and every cell in the rightmost column can only open upward.
From any cell, you can reach the top-right corner by going only up or right, because every cell has an opening either above it or to its right. So if you start in the bottom-left corner and only go up or right, you'll never take a wrong turn on the way to the top-right corner. A pattern like that is called a bias, and most maze algorithms have one. The binary tree algorithm just has a very strong one.
Sidewinder, a variation on the binary tree algorithm, fixes half of the problem. It goes through each row from left to right and keeps track of a run: a group of cells side by side. At every cell, it flips a coin. On heads, it knocks down the wall to the right, so the run gets longer. On tails, it closes the run: it picks a random cell from the run, knocks down its top wall, and starts a new run. In the top row, it doesn't flip a coin: it always knocks down the wall to the right, because there's no cell above to open into. And at the right edge, it always closes the run, because there's no cell to the right:
function sidewinder(grid) {
for (let row of grid) {
let run = [];
for (let cell of row) {
run.push(cell);
let atRightEdge = cell.x == row.length - 1;
let atTop = cell.y == 0;
if (atRightEdge || (!atTop && Math.random() < 0.5)) {
// Close the run: knock down a top wall in the run
if (!atTop) {
let member = getRandomItem(run);
removeWall(member, grid[member.y - 1][member.x]);
}
run = [];
} else {
removeWall(cell, row[cell.x + 1]);
}
}
}
}Switch the demo above to Sidewinder. The long corridor down the right side is gone, because a run can now open upward from any of its cells. But the top row is still one long corridor.
Carve long corridors with depth-first search
The maze algorithm most people know is depth-first search, often called the recursive backtracker. Start in a random cell and dig a tunnel to a random neighbor you haven't visited yet. Keep digging until you get stuck. Then go back along your tunnel, one cell at a time, until you find a cell with a neighbor you haven't visited, and keep digging from there. When you're all the way back at the start, you've visited every cell:
function getUnvisitedNeighbors(grid, cell) {
return getNeighbors(grid, cell).filter(function (neighbor) {
return !neighbor.visited;
});
}
function depthFirstSearch(grid) {
let start = getRandomItem(getRandomItem(grid));
start.visited = true;
let stack = [start];
while (stack.length > 0) {
let cell = stack[stack.length - 1];
let unvisited = getUnvisitedNeighbors(grid, cell);
if (unvisited.length == 0) {
// A dead end: go back one step along your tunnel
stack.pop();
continue;
}
let next = getRandomItem(unvisited);
removeWall(cell, next);
next.visited = true;
stack.push(next);
}
}getRandomItem(getRandomItem(grid)) first picks a random row, and then a random cell in that row. The cells from createGrid() don't have a visited property yet, and a property that doesn't exist counts as false in !neighbor.visited. The stack array is your tunnel. push() adds a cell to the end of it when you dig, and pop() takes the last cell off when you go back.
In the demo below, the red cell digs, and the light red cells are the tunnel on the stack:
Depth-first search keeps digging the same tunnel for as long as it can, so it makes long, winding corridors with few branches. Only about 10% of the cells end up as dead ends, and the path from one corner to the opposite corner is long. The tutorial on pathfinding uses it too, to generate random mazes on a grid where the walls are whole cells.
You can also write depth-first search with a function that calls itself for every neighbor. That's where the name recursive backtracker comes from. But on a big grid, that version can crash, as you'll see in the questions at the end of this tutorial. The version with an array as the stack doesn't have that problem.
Grow a maze with Prim's algorithm
Prim's algorithm grows the maze from a single cell. It keeps a frontier: a list of all the cells right next to the maze. Over and over, it takes a random cell from the frontier and connects it to a random neighbor that's already part of the maze. The new cell is now part of the maze too, so its own neighbors join the frontier:
function addToFrontier(grid, cell, frontier) {
for (let neighbor of getUnvisitedNeighbors(grid, cell)) {
if (!frontier.includes(neighbor)) {
frontier.push(neighbor);
}
}
}
function prim(grid) {
let start = getRandomItem(getRandomItem(grid));
start.visited = true;
let frontier = [];
addToFrontier(grid, start, frontier);
while (frontier.length > 0) {
// Take a random cell out of the frontier
let index = Math.floor(Math.random() * frontier.length);
let cell = frontier.splice(index, 1)[0];
// Connect it to a random neighbor that's already in the maze
let neighbors = getNeighbors(grid, cell);
let inMaze = neighbors.filter(function (neighbor) {
return neighbor.visited;
});
removeWall(cell, getRandomItem(inMaze));
cell.visited = true;
addToFrontier(grid, cell, frontier);
}
}visited means the cell is part of the maze. splice(index, 1) removes one item from the array and returns it in a new array, so [0] gives you the cell itself. The orange cells in the demo below are the frontier:
Every cell in the frontier is equally likely to be picked next, so the maze grows in all directions at once, like a stain spreading out. The result is the opposite of depth-first search: short paths, lots of branches, and lots of short dead ends. About 35% of the cells end up as dead ends. You'll see the word frontier again in the tutorial on pathfinding, where it's the list of cells the search looks at next.
The original Prim's algorithm finds the cheapest way to connect all the points in a network, like the shortest way to run cables between a few houses. The version for mazes is simpler: every wall costs the same to knock down, so it picks a random cell from the frontier.
Remove random walls with Kruskal's algorithm
Kruskal's algorithm looks at walls instead of cells. Put every wall between two cells in a list, in a random order. Then go through the list. If the cells on either side of a wall aren't connected yet, knock the wall down. If they're already connected, leave the wall standing, because there's a path between them, and a second one would make a loop.
So how do you know if two cells are connected? Put every cell in a group of its own. Each time you knock down a wall, join the groups of the two cells into one. Two cells are connected if they're in the same group.
A quick way to keep track of the groups is a disjoint-set structure, also called union-find. Every cell points to a parent. Follow the parents until you reach a cell that points to itself: that's the root of the group. Two cells are in the same group if they have the same root. To join two groups, let the root of one group point to the root of the other:
function findRoot(cell) {
while (cell.parent != cell) {
cell = cell.parent;
}
return cell;
}
function kruskal(grid) {
// Every wall between two cells, and every cell in a group of its own
let walls = [];
for (let row of grid) {
for (let cell of row) {
cell.parent = cell;
if (cell.x > 0) {
walls.push([row[cell.x - 1], cell]);
}
if (cell.y > 0) {
walls.push([grid[cell.y - 1][cell.x], cell]);
}
}
}
shuffle(walls);
for (let [a, b] of walls) {
let rootA = findRoot(a);
let rootB = findRoot(b);
if (rootA != rootB) {
removeWall(a, b);
rootB.parent = rootA;
}
}
}Each wall in the list is an array with the two cells on either side of it. for (let [a, b] of walls) goes through the walls one by one and puts the two cells of each wall in a and b. Every cell adds the wall to its left and the wall above it, so every wall is in the list exactly once. shuffle() puts the walls in a random order. It's the Fisher-Yates shuffle from the tutorial on random numbers in JavaScript. It shuffles the array in place and also returns it, which comes in handy later on.
The red line in the demo below is the wall the algorithm is looking at. Switch the demo to Groups to see each group in its own color. At first, every cell has its own color. Each wall that comes down merges two colors into one, until the whole maze is a single color:
Kruskal's algorithm doesn't have a strong style of its own. The maze grows in little patches all over the grid at once, and about 30% of the cells end up as dead ends.
Take a random walk with Aldous-Broder and Wilson's algorithms
Most of the algorithms so far give their mazes a style of their own: a bias, even if it's only a slight one. Sometimes, you don't want any style at all. Instead, you want a maze picked at random from all the mazes that fit in your grid, each one equally likely. Such a maze is called a uniform spanning tree. Two algorithms in this tutorial make one, and they both use a random walk: a walk where every step goes to a random neighbor.
The Aldous-Broder algorithm is the simpler of the two. Start in a random cell and walk around at random. Every time you step into a cell you haven't visited yet, knock down the wall you came through. Stop when you've visited every cell:
function aldousBroder(grid) {
let cell = getRandomItem(getRandomItem(grid));
cell.visited = true;
let unvisited = grid.length * grid[0].length - 1;
while (unvisited > 0) {
let next = getRandomItem(getNeighbors(grid, cell));
if (!next.visited) {
removeWall(cell, next);
next.visited = true;
unvisited--;
}
cell = next;
}
}unvisited starts at the number of cells minus one, because the start cell is already part of the maze. Aldous-Broder is simple, but slow. At the start, nearly every step finds a new cell. But near the end, the walk wanders around the maze for ages before it stumbles onto the last few cells.
Wilson's algorithm walks the other way: not from the maze into new cells, but from a new cell to the maze. Start by adding one random cell to the maze. Then pick a cell that's not in the maze yet, and walk at random until you reach the maze. Your walk probably crossed itself a few times. Loops in the walk would become loops in the maze, so erase them, and add what's left of the walk to the maze. Repeat that from every cell that's still not in the maze.
Erasing the loops sounds hard, but there's a neat trick. During the walk, cell.exit remembers which neighbor you stepped to the last time you left the cell. When you go around in a loop and leave a cell again, the new exit replaces the old one. So when you follow the exits from the start, you skip every loop:
function wilson(grid) {
let cells = grid.flat();
getRandomItem(cells).visited = true;
for (let start of cells) {
// Walk at random until you reach the maze, and remember
// the last way out of every cell you pass
let cell = start;
while (!cell.visited) {
cell.exit = getRandomItem(getNeighbors(grid, cell));
cell = cell.exit;
}
// Follow the exits from the start:
// that's the walk without its loops
cell = start;
while (!cell.visited) {
removeWall(cell, cell.exit);
cell.visited = true;
cell = cell.exit;
}
}
}grid.flat() puts all the rows one after another in a single array, so you can go through all the cells with a single loop. A cell that's already in the maze when its turn comes skips both while loops. Here, visited means the cell is part of the maze, just like in Prim's algorithm. The walk itself doesn't mark the cells it passes through. In the demo below, the blue line is the walk, and you can see the loops disappear as the walk crosses itself:
Wilson's algorithm starts slowly, because the first walk has to find a maze of just one cell. After that, the maze is a bigger target, and the walks get shorter and shorter. Aldous-Broder is the other way around: fast at the start, and slow at the end. Both give you exactly the same kind of maze, with about 29% dead ends.
Build an endless maze row by row with Eller's algorithm
Depth-first search, Prim's, Kruskal's and the two random-walk algorithms all need the whole grid in memory. Eller's algorithm only looks at one row at a time, like Sidewinder, but without its bias. So it can make a maze that never ends, like a level in an endless runner. It keeps track of groups of connected cells, called sets, just as Kruskal's algorithm does. Every row goes through three steps:
- Put every cell in a set - A cell with an opening to the row above is already in the same set as the cell above it. Each of the other cells gets a new set of its own.
- Join cells side by side - Go along the row, and for each pair of neighbors in different sets, decide at random whether to knock down the wall between them. If you do, both sets become one.
- Open the way down - Knock down at least one bottom wall in every set, so no set gets cut off from the rest of the maze.
In the last row, step 2 joins every pair of neighbors that are still in different sets, and there's no step 3:
function mergeSets(row, from, to) {
for (let cell of row) {
if (cell.set == from) {
cell.set = to;
}
}
}
function eller(grid) {
let nextSet = 1;
for (let y = 0; y < grid.length; y++) {
let row = grid[y];
let lastRow = y == grid.length - 1;
// A cell that isn't open to the row above gets a new set
for (let cell of row) {
if (!cell.set) {
cell.set = nextSet;
nextSet++;
}
}
// Join neighbors from different sets: at random,
// or always in the last row
for (let x = 0; x < row.length - 1; x++) {
let a = row[x];
let b = row[x + 1];
if (a.set != b.set && (lastRow || Math.random() < 0.5)) {
removeWall(a, b);
mergeSets(row, b.set, a.set);
}
}
if (lastRow) {
break;
}
// Every set goes down at least once
let setsDown = [];
for (let cell of shuffle(row.slice())) {
if (!setsDown.includes(cell.set) || Math.random() < 0.3) {
setsDown.push(cell.set);
let below = grid[y + 1][cell.x];
removeWall(cell, below);
below.set = cell.set;
}
}
}
}The sets are numbered from 1, so !cell.set is only true for a cell that doesn't have a set yet. Step 3 goes through a shuffled copy of the row: row.slice() copies it, so the row itself stays in order. The first cell of each set in the shuffled copy always goes down. After that, each of the other cells in that set has a 30% chance to go down too. The cell below joins the set of the cell above it, so in the next row, step 1 skips it.
The code above makes a maze of a fixed size. For an endless maze, only keep the current row and the next one, and skip the step for the last row. That's what the demo below does. Cells in the same set have the same color:
Like Kruskal's algorithm, Eller's algorithm joins random groups wherever they happen to meet, without favoring any direction. So their mazes look a lot alike, with about the same percentage of dead ends, a bit under 30%.
Split the grid into chambers with recursive division
Every algorithm so far starts with all the walls and knocks some of them down. Recursive division works the other way around. It starts with an empty grid, with only the walls around the edge. Then it builds a wall straight across the grid, from one side to the other, and leaves one gap in it. That splits the grid into two chambers. After that, the algorithm does the same thing in each chamber, until every chamber is only one cell wide or one cell high. addWall() is removeWall() with true instead of false:
function recursiveDivision(grid) {
// Start without any walls, except around the edge
for (let row of grid) {
for (let cell of row) {
cell.top = cell.y == 0;
cell.right = cell.x == row.length - 1;
cell.bottom = cell.y == grid.length - 1;
cell.left = cell.x == 0;
}
}
divide(grid, 0, 0, grid[0].length, grid.length);
}
function divide(grid, x, y, width, height) {
if (width < 2 || height < 2) {
return;
}
if (width < height || (width == height && Math.random() < 0.5)) {
// A wall below row wallY, with a gap in column gapX
let wallY = y + Math.floor(Math.random() * (height - 1));
let gapX = x + Math.floor(Math.random() * width);
for (let i = x; i < x + width; i++) {
if (i != gapX) {
addWall(grid[wallY][i], grid[wallY + 1][i]);
}
}
divide(grid, x, y, width, wallY - y + 1);
divide(grid, x, wallY + 1, width, y + height - wallY - 1);
} else {
// A wall to the right of column wallX, with a gap in row gapY
let wallX = x + Math.floor(Math.random() * (width - 1));
let gapY = y + Math.floor(Math.random() * height);
for (let i = y; i < y + height; i++) {
if (i != gapY) {
addWall(grid[i][wallX], grid[i][wallX + 1]);
}
}
divide(grid, x, y, wallX - x + 1, height);
divide(grid, wallX + 1, y, x + width - wallX - 1, height);
}
}divide() gets a chamber: its top-left cell at (x, y), and its width and height in cells. It splits a wide chamber with a wall from top to bottom, and a tall chamber with a wall from left to right, so the chambers don't get too long and thin. wallY is the last row of the top part, so the top part is wallY - y + 1 rows high, and the bottom part gets the rest. Then divide() calls itself on each of the two parts. That's where the word recursive in the name comes from. In the demo below, the light blue area is the chamber that's being split:
The walls in these mazes are easy to spot: long and straight, with a gap somewhere along each one. That gives the mazes a blocky look. With recursive division, you can also add rooms: stop splitting a chamber once it's small enough, and you have an open room with one or more doors.
Which maze algorithm should you use?
So which one is the best? That depends on the maze you want. In the race below, all eight algorithms build a maze at the same time, on grids of the same size. Sidewinder doesn't get its own maze in the race, because it's a variation on the binary tree algorithm. Under each maze, you can see two numbers: the percentage of cells that are dead ends, and the length of the longest path in the maze, in cells:
The numbers change a little with every race, but the differences remain. The mazes in the race are 14 by 10 cells. On a bigger grid of 30 by 30 cells, the differences are even clearer. There, the longest path in the maze is about 460 cells long with depth-first search, and only about 90 with Prim's algorithm. Here's what each algorithm is good for:
- Binary tree and Sidewinder - The simplest and the fastest, and they only need to look at one row at a time. Use them when you don't mind the bias, or when you like how it looks.
- Depth-first search - Long, winding corridors and few dead ends. Use it when you want a long walk from the entrance to the exit. It's also one of the easiest to write.
- Prim's algorithm - Lots of short dead ends, and the paths through the maze stay short. Use it when you want a maze full of choices, where the way out is never far.
- Kruskal's algorithm - No strong style of its own. A good all-around choice, and fun to watch, because it works on the whole grid at once.
- Aldous-Broder and Wilson's algorithms - Every possible maze is equally likely, with no style at all. Use Wilson's when you want a fair maze, for example in a puzzle.
- Eller's algorithm - One row at a time, so the maze can go on forever. Use it for a level in an endless runner.
- Recursive division - Long, straight walls and a blocky look. Use it when you want rooms, or a maze that looks like the floor plan of a building.
Speed hardly matters. On a grid of 30 by 30 cells, each algorithm takes a millisecond or less. Only Aldous-Broder slows down on a big grid, because of all the wandering at the end.
Add loops to your maze
A perfect maze has exactly one path between any two cells. That's great for a puzzle, but in a game, it can feel limiting. An enemy that chases you through a perfect maze always takes the same corridor as you, so you can never get around it. Loops give you a choice of routes.
A simple way to add loops is to get rid of dead ends. A dead end is a cell with three walls. Knock down one of them, and the dead end turns into a passage, with a loop somewhere around it. If one of the neighbors behind those walls is a dead end too, pick that one, so you get rid of two dead ends at once:
function countWalls(cell) {
return directions.filter(function (direction) {
return cell[direction.wall];
}).length;
}
function removeDeadEnds(grid, chance) {
for (let row of grid) {
for (let cell of row) {
if (countWalls(cell) != 3 || Math.random() >= chance) {
continue;
}
// The neighbors behind a wall, preferably other dead ends
let neighbors = getNeighbors(grid, cell);
let closed = neighbors.filter(function (neighbor) {
return cell[getDirection(cell, neighbor).wall];
});
let deadEnds = closed.filter(function (neighbor) {
return countWalls(neighbor) == 3;
});
let options = deadEnds.length > 0 ? deadEnds : closed;
removeWall(cell, getRandomItem(options));
}
}
}chance is how likely each dead end is to be opened up, from 0 to 1. A maze without any dead ends is called a braid maze. In the demo below, the dead ends are red. Try the options, and see how the maze opens up:
The maze in the demo comes from depth-first search, which already leaves few dead ends. Even so, removing all of them changes it completely. For a person, a maze with loops is often harder, not easier: you can walk in circles without noticing.
Find the way out of a maze
A maze needs a way out, so how do you find it? In the demos below, the way out is a goal cell, like the bottom-right corner.
The oldest trick is the wall follower. Put your right hand on the wall and keep walking, without ever letting go. At every cell, turn right if you can. If you can't, go straight, and if that's blocked too, turn left. At a dead end, turn around:
function followWall(grid, start, goal) {
let cell = start;
let facing = 1;
let path = [cell];
while (cell != goal) {
// Turn right if you can, else go straight,
// else turn left, else turn around
for (let turn of [1, 0, 3, 2]) {
let direction = directions[(facing + turn) % 4];
if (!cell[direction.wall]) {
facing = (facing + turn) % 4;
cell = grid[cell.y + direction.y][cell.x + direction.x];
path.push(cell);
break;
}
}
}
return path;
}facing is the direction you're walking in, as an index into directions. It starts at 1, which means you're facing right. The directions go around clockwise, from top to right to bottom to left, so adding 1 turns right, 3 turns left and 2 turns around. % 4 keeps the index between 0 and 3.
A perfect maze has no loops, so all its walls are connected to the outer wall and form a single piece. Keep one hand on the wall, and you'll pass every cell, so sooner or later you'll reach the goal.
The wall follower can take a long detour, though, because it walks into every dead end along the way. And in a maze with loops, it can fail. If the goal is in the middle, your hand may be on a wall that goes around in a loop. Then you'll walk in circles forever.
There are two other ways to solve a maze:
- Dead-end filling - Fill every dead end, as if you poured concrete into it. A cell next to a filled dead end can become a dead end itself, so fill that one too, and keep going. Leave the start and the goal alone. When there are no dead ends left, the cells that are still open are the path. In a maze with loops, dead-end filling leaves open every route that's part of a loop, so you may still have to choose between them.
- Breadth-first search - Use it to find the shortest path, even in a maze with loops. It explores the maze in rings around the start, so the first time it reaches the goal, it's taken the shortest route. The tutorial on pathfinding in JavaScript explains it step by step, along with Dijkstra's algorithm and A*.
Try all three ways in the demo below, from the green dot in the top-left corner to the red dot in the bottom-right corner:
At the end, the demo also draws the shortest path, so you can compare it with the route the wall follower took.
Turn your maze into a level you can play
For a game, it's often easier if each wall takes up a whole square, like in the pathfinding tutorial. Then every square of your level is either a wall or a floor, and you can draw each one with a tile from a sprite sheet.
To convert your maze, start with a level that's all walls. A maze of 5 by 3 cells becomes a level of 11 by 7 squares: twice as many columns and rows, plus one of each. Every cell of the maze becomes an open square in an odd row and an odd column, and every wall you knocked down opens the square in between:
function toLevel(grid) {
let level = [];
for (let y = 0; y < grid.length * 2 + 1; y++) {
level.push(new Array(grid[0].length * 2 + 1).fill('#'));
}
for (let row of grid) {
for (let cell of row) {
let x = cell.x * 2 + 1;
let y = cell.y * 2 + 1;
level[y][x] = '.';
if (!cell.right) {
level[y][x + 1] = '.';
}
if (!cell.bottom) {
level[y + 1][x] = '.';
}
}
}
return level.map(function (row) {
return row.join('');
});
}You only have to look at the right and bottom walls. The top wall of a cell is the bottom wall of the cell above it, and that cell already took care of it. The result is an array of strings, with a # for a wall and a dot for an open square, like this maze of 5 by 3 cells:
[
'###########',
'#.........#',
'#.###.###.#',
'#...#...#.#',
'###.###.#.#',
'#.....#.#.#',
'###########'
]That's exactly the format of the levels in the tutorial on pathfinding, so you can use the code from that tutorial to send enemies after the player.
In the demo below, the maze is a level you can play. Click or tap the maze first. Then use the arrow keys or swipe to guide the little mouse to the cheese. Each key press moves the mouse one square, if there's no wall in the way. A swipe makes it keep running until it reaches a wall or a side passage. The tutorial on keyboard, mouse and touch controls shows how to listen for key presses and how to detect a swipe.
Every new maze comes from depth-first search, with the mouse in the top-left corner and the cheese in the bottom-right corner. Depth-first search makes the longest paths, so the way to the cheese is never short.
Common questions about maze generation
What's the difference between a maze and a labyrinth?
In everyday English, people use both words for the same thing. Strictly speaking, a labyrinth has a single path that winds from the entrance to the center, without any choices, so you can't get lost in it. A maze has branches and dead ends. Every algorithm in this tutorial makes a maze.
Why does my maze generator crash on a big grid?
Chances are it's a recursive version of depth-first search, a function that calls itself for every cell it digs into. Every call waits until the next one is done, and the browser can only keep so many waiting calls at once. On a big grid, the tunnel can get thousands of cells long, and the browser stops with the error Maximum call stack size exceeded. Use an array as the stack instead, like the code in this tutorial does. An array can hold millions of cells.
How do I get the same maze every time?
Use a seeded random number generator instead of Math.random(). With the same seed, you get the same random numbers, and so the same maze. That's handy for a maze of the day, or to let players share a maze by its seed. The tutorial on random numbers in JavaScript has a small generator with a seed, called Mulberry32.
How do I make a maze harder?
First of all, make it bigger. Then pick an algorithm with lots of dead ends, like Prim's, so there are more wrong turns to take. A few loops make it harder too, because the wall follower can stop working and it's easy to go around in circles. And put the start and the exit far apart.
Here's how to find the two cells that are farthest apart in a perfect maze. Run breadth-first search from any cell and find the cell that's farthest from it. That cell is one end of the longest path. Then run breadth-first search again from that cell: the cell that's farthest from it is the other end.
Can I make a hexagonal or circular maze?
Yes. Most algorithms in this tutorial only need to know the neighbors of a cell. On a grid of hexagons, a cell has six neighbors instead of four. A circular maze has rings of cells, and the outer rings have more cells than the inner ones. Depth-first search, Aldous-Broder, Prim's, Kruskal's and Wilson's algorithms all work the same way on both kinds of grid. You mainly have to rewrite createGrid(), getNeighbors(), removeWall() and the drawing code. Binary tree, Sidewinder, Eller's algorithm and recursive division need rows and columns, so they're harder to adapt.
How do I add rooms to a maze?
Place a few rooms on the grid first: knock down the walls inside each room, and mark its cells as visited. Then fill the space between the rooms with depth-first search, starting from a cell outside them. Start a new search in every part of the grid that's still unvisited. Knock down a wall here and there to connect every room and every part of the maze to the rest. Finally, remove some dead ends, so fewer corridors lead nowhere. Bob Nystrom explains this way of making a dungeon in his article Rooms and Mazes.
Can a cellular automaton make a maze?
Sort of. Conway's Game of Life has a variation called Maze, where a dead cell comes to life with exactly 3 living neighbors, and a living cell survives with 1 to 5. It grows into patterns that look like a maze, but they aren't perfect mazes: some parts are closed off, and others have loops. You can try it in the tutorial on Conway's Game of Life in JavaScript.
Example code: a maze generator
Here's an example page that puts the basics from this tutorial together in a single HTML file. It generates a maze with depth-first search and draws it on a canvas. Use the arrow keys or WASD to guide the mouse to the cheese, and when you get there, a new maze appears. The image of the mouse comes from spicyyoghurt.com. Copy all of the code below into a new .html file and open that file in your browser:
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Maze Generation Tutorial | Spicy Yoghurt</title>
</head>
<body>
<h1>Maze generation tutorial by Spicy Yoghurt</h1>
<p>
Click the maze, then use the arrow keys or WASD
to guide the mouse to the cheese.
</p>
<canvas
id="canvas"
width="750"
height="400"
tabindex="0"
style="border:1px solid lightgray;"
>
Your browser does not support the HTML5 canvas tag.
</canvas>
<script>
'use strict';
const columns = 24;
const rows = 12;
const size = 30;
const directions = [
{x: 0, y: -1, wall: 'top', opposite: 'bottom'},
{x: 1, y: 0, wall: 'right', opposite: 'left'},
{x: 0, y: 1, wall: 'bottom', opposite: 'top'},
{x: -1, y: 0, wall: 'left', opposite: 'right'}
];
// The keys for up, right, down and left,
// in the same order as directions
const arrowKeys = [
'ArrowUp', 'ArrowRight', 'ArrowDown', 'ArrowLeft'
];
const wasdKeys = ['KeyW', 'KeyD', 'KeyS', 'KeyA'];
let canvas;
let context;
let grid;
let mouse;
let cheese;
let mouseImage = new Image();
window.onload = init;
function init() {
canvas = document.getElementById('canvas');
context = canvas.getContext('2d');
canvas.addEventListener('keydown', onKeyDown);
canvas.focus();
mouseImage.onload = draw;
mouseImage.src =
'https://spicyyoghurt.com/img/tutorials/javascript/' +
'mouse-sprite-sheet.png';
newMaze();
}
function newMaze() {
grid = createGrid(columns, rows);
depthFirstSearch(grid);
mouse = {x: 0, y: 0, facing: 1};
cheese = {x: columns - 1, y: rows - 1};
draw();
}
function createGrid(columns, rows) {
let grid = [];
for (let y = 0; y < rows; y++) {
let row = [];
for (let x = 0; x < columns; x++) {
row.push({
x: x,
y: y,
top: true,
right: true,
bottom: true,
left: true
});
}
grid.push(row);
}
return grid;
}
function getNeighbors(grid, cell) {
let neighbors = [];
for (let direction of directions) {
let x = cell.x + direction.x;
let y = cell.y + direction.y;
let inside =
x >= 0 && x < grid[0].length &&
y >= 0 && y < grid.length;
if (inside) {
neighbors.push(grid[y][x]);
}
}
return neighbors;
}
function getDirection(a, b) {
return directions.find(function (direction) {
return a.x + direction.x == b.x &&
a.y + direction.y == b.y;
});
}
function removeWall(a, b) {
let direction = getDirection(a, b);
a[direction.wall] = false;
b[direction.opposite] = false;
}
function getRandomItem(array) {
return array[Math.floor(Math.random() * array.length)];
}
function getUnvisitedNeighbors(grid, cell) {
return getNeighbors(grid, cell).filter(function (neighbor) {
return !neighbor.visited;
});
}
function depthFirstSearch(grid) {
let start = getRandomItem(getRandomItem(grid));
start.visited = true;
let stack = [start];
while (stack.length > 0) {
let cell = stack[stack.length - 1];
let unvisited = getUnvisitedNeighbors(grid, cell);
if (unvisited.length == 0) {
// A dead end: go back one step along your tunnel
stack.pop();
continue;
}
let next = getRandomItem(unvisited);
removeWall(cell, next);
next.visited = true;
stack.push(next);
}
}
function onKeyDown(event) {
let index = arrowKeys.indexOf(event.code);
if (index == -1) {
index = wasdKeys.indexOf(event.code);
}
if (index == -1) {
return;
}
// Keep the arrow keys from scrolling the page
event.preventDefault();
let direction = directions[index];
mouse.facing = index;
// Only move if there's no wall in the way
if (!grid[mouse.y][mouse.x][direction.wall]) {
mouse.x += direction.x;
mouse.y += direction.y;
}
if (mouse.x == cheese.x && mouse.y == cheese.y) {
newMaze();
} else {
draw();
}
}
function draw() {
context.clearRect(0, 0, canvas.width, canvas.height);
context.save();
// Center the maze, so the outer walls aren't cut off
context.translate(
(canvas.width - columns * size) / 2,
(canvas.height - rows * size) / 2
);
drawMaze(context, grid, size);
drawCheese();
drawMouse();
context.restore();
}
function drawMaze(context, grid, size) {
context.strokeStyle = '#303030';
context.lineWidth = 2;
context.lineCap = 'square';
context.beginPath();
for (let row of grid) {
for (let cell of row) {
let x = cell.x * size;
let y = cell.y * size;
if (cell.top) {
context.moveTo(x, y);
context.lineTo(x + size, y);
}
if (cell.right) {
context.moveTo(x + size, y);
context.lineTo(x + size, y + size);
}
if (cell.bottom) {
context.moveTo(x, y + size);
context.lineTo(x + size, y + size);
}
if (cell.left) {
context.moveTo(x, y);
context.lineTo(x, y + size);
}
}
}
context.stroke();
}
function drawCheese() {
let x = cheese.x * size + size / 2;
let y = cheese.y * size + size / 2;
context.fillStyle = '#ffcf51';
context.beginPath();
context.moveTo(x - 9, y + 7);
context.lineTo(x + 9, y + 7);
context.lineTo(x + 9, y - 2);
context.lineTo(x + 3, y - 8);
context.closePath();
context.fill();
}
function drawMouse() {
let x = mouse.x * size + size / 2;
let y = mouse.y * size + size / 2;
if (!mouseImage.complete || mouseImage.naturalWidth == 0) {
// No image yet: draw a gray circle instead
context.fillStyle = '#8a9a9e';
context.beginPath();
context.arc(x, y, size / 3, 0, Math.PI * 2);
context.fill();
return;
}
// The mouse sprite faces right, so it needs no turn
// when mouse.facing is 1. Each entry in directions is
// a quarter turn clockwise from the one before it.
context.save();
context.translate(x, y);
context.rotate((mouse.facing - 1) * Math.PI / 2);
// The first frame of the third row: the mouse standing still
context.drawImage(
mouseImage,
0, 256, 128, 128,
-size * 0.8, -size * 0.8, size * 1.6, size * 1.6
);
context.restore();
}
</script>
</body>
</html>To try another algorithm, copy its function from this tutorial, and call that function in newMaze() instead of depthFirstSearch(). Some algorithms use other functions as well, so copy those too:
- Prim's algorithm - Uses addToFrontier().
- Kruskal's algorithm - Uses findRoot() and shuffle().
- Eller's algorithm - Uses mergeSets() and shuffle().
- Recursive division - Uses divide() and addWall().
You'll find shuffle() in the tutorial on random numbers in JavaScript. For addWall(), copy removeWall(), rename the copy to addWall() and change false to true.
To add loops, copy countWalls() and removeDeadEnds() too, and call removeDeadEnds(grid, 0.5) right after the maze algorithm.
Conclusion
Every maze generation algorithm in this tutorial builds a spanning tree through a grid of cells, and the way it builds that tree gives the maze its style. Depth-first search digs long corridors, Prim's algorithm grows a bushy maze with lots of dead ends, and Kruskal's algorithm joins groups of cells. Wilson's algorithm makes every possible maze equally likely, Eller's algorithm can go on forever, and recursive division builds walls instead of knocking them down. You've also learned how to add loops, how to find the way out, and how to turn a maze into a level for your game.
That's all for now. If you have any questions, feel free to ask them in the comment section. Made a maze with an algorithm that's not in this tutorial? Tell us about it in the comments. You can download the example code here.
Comments
Thanks! We've received your comment. We check every comment by hand before it appears, so this can take a few days.

No comments yet. Be the first to leave one!