Day 29 of my "build a small game a day, from nothing" run. A maze is two classic graph algorithms hiding inside a drawing: one to build it, one to escape it. Carve with a randomised depth-first search, solve with a breadth-first search, and the whole thing fits in about 120 lines of vanilla JS.
Play it (LOOK / UNDERSTAND / BUILD tabs) here: https://dev48v.infy.uk/game/day29-maze.html
A maze is a graph wearing walls
Strip away the pixels and a maze is a grid graph: every cell is a node, and there's a potential edge between each pair of adjacent cells. Building the maze is deciding which of those potential edges become open passages and which stay blocked. Solving it is a plain shortest-path search on the passages that survived.
I store the whole thing as one 2-D array where each cell holds four bits — one per wall (north, east, south, west):
const N_=1, E_=2, S_=4, W_=8; // one bit per wall
let cells = Array.from({length:N}, () => Array(N).fill(15));
// 15 = 1111 = all four walls up (a solid, uncarved cell)
The one subtlety: the wall between two cells belongs to both of them. My north wall is my neighbour's south wall. So carving a passage means clearing a bit on this cell and the matching bit on the neighbour, or the two cells disagree about whether they're connected.
Carving: randomised DFS (the recursive backtracker)
The recursive-backtracker is just depth-first search with the neighbour order shuffled. Keep an explicit stack. Peek at the top cell; if it has any unvisited neighbours, pick one at random, knock down the wall between them, mark it visited, and push it — you've dived one step deeper. If it has none, it's a dead end: pop it and carry on from the cell beneath. That pop is the backtrack.
function carve(rand){
const seen = Array.from({length:N}, () => Array(N).fill(false));
const stack = [[0,0]]; seen[0][0] = true;
while (stack.length){
const [r,c] = stack[stack.length-1]; // peek the top
const opts = DIRS.filter(d => {
const nr=r+d.dr, nc=c+d.dc;
return inB(nr,nc) && !seen[nr][nc]; }); // unvisited neighbours
if (!opts.length){ stack.pop(); continue; } // dead end -> backtrack
const d = opts[(rand()*opts.length)|0]; // pick one at random
const nr=r+d.dr, nc=c+d.dc;
cells[r][c] &= ~d.bit; cells[nr][nc] &= ~d.opp; // carve both sides
seen[nr][nc] = true; stack.push([nr,nc]);
}
}
Because you never revisit a cell, you add exactly one passage per newly visited cell, so you end with exactly cells − 1 passages. That number matters: a graph that touches every node and has exactly nodes − 1 edges is a spanning tree. A spanning tree of the grid is precisely a perfect maze — every cell reachable, no loops, no closed-off rooms, and exactly one path between any two cells.
DFS also gives the maze its look. Because it commits to a direction and keeps going until it physically can't, you get long, snaking corridors and long dead ends — a high "river" factor. Prim's and Kruskal's carve the same kind of spanning tree but look bushier, because they grow from many fronts at once instead of one deep, greedy dive.
Solving: BFS finds the shortest path for free
Every step in a maze costs the same, so the graph is unweighted, and on an unweighted graph BFS returns a shortest path. It expands in rings — all cells one step from the entrance, then two, then three — using a FIFO queue. The first time the exit comes off that queue, it's been reached by the fewest possible steps.
function solve(){
const seen = Array.from({length:N}, () => Array(N).fill(false));
const parent = Array.from({length:N}, () => Array(N).fill(null));
const queue = [[0,0]]; seen[0][0] = true;
while (queue.length){
const [r,c] = queue.shift(); // FIFO -> explore in rings
if (r===N-1 && c===N-1) break; // exit reached (shortest)
for (const d of DIRS){
if (cells[r][c] & d.bit) continue; // wall in the way -> blocked
const nr=r+d.dr, nc=c+d.dc;
if (!seen[nr][nc]){ seen[nr][nc]=true; parent[nr][nc]=[r,c]; queue.push([nr,nc]); }
}
}
return parent; // walk this back from the exit to get the route
}
The parent map is the payoff. When the exit pops, you don't have a path yet — you have a tree of "who reached me". Walk from the exit parent-to-parent back to the start and reverse it, and that chain is the shortest route.
Why not Dijkstra or A*?
Because the graph is evenly weighted, they'd give the same answer for more work. Dijkstra generalises BFS to edges with different costs (it needs a priority queue); A* adds a heuristic — say, the straight-line distance to the exit — so it explores fewer cells on huge grids. They earn their keep when steps have costs, or the map is enormous. For an even-cost maze, BFS is the simplest tool that's already optimal. Use the least machinery the problem allows.
The takeaway
Both halves are linear in the number of cells: the carve visits each cell once, and BFS touches each cell and its handful of edges once. A 100×100 maze is 10,000 cells and still solves instantly. I verified the carve on 40 different mazes — every one had exactly cells − 1 passages, was fully connected, had no loops, and BFS returned a path whose length matched an independent shortest-distance check.
Vanilla JS, no libraries, runs offline — and you can walk the maze yourself with the arrow keys. Tomorrow: Reversi — flip your opponent's discs by bracketing them, against a minimax AI.
Top comments (0)