Maze Generation Algorithms
Alexandre Rousseau
Overview
Creating mazes programmatically is easy. Many algorithms exist that will help you do just that. Here are some of them.
Binary Tree
Possibly the simplest of all, the binary tree algorithm works like this:
Before you begin, choose one direction from each of the North-South and East-West axes, say, North and East. Then, starting at the southwest corner of the maze, choose one of those two directions at random for each cell. The chosen direction represents the side of the cell from which an exit will be carved, all other sides being solid. Apply this to all cells except for the following:
- Northermost (top row of the maze) cells all have an exit to the East.
- Easternmost (right column of the maze) cells all have an exit to the East.
This algorithm works fast and is simple to implement. Here's the code to generate the data behind the view:
function binaryTree(rows, cols){ return _.map(_.range(rows), function(row, i){ return _.map(_.range(cols), function(col, j){ if (row == 0) { return (col+1 < cols) ? 'top e' : 'null'; } else if (col+1 == cols) { return 'right n'; } else { return Math.random() < 0.5 ? 'n' : 'e'; } }); }); }
And from that, we get this maze:
This algorithm has one major flaw: the data it generates is skewed diagonally — towards the northeast, in our case. This results in the creation of corridors along each axis limit — again in our case, at the rightmost column and top row — of the rendered maze. To avoid such undesirables, other, more complex, algorithms are needed.
Sidewinder
Coming soon
The sidewinder algorithm works like this:
Using this code:
// TODO
We get, say, that:
[ [1,2,3,4,5,6], [1,2,3,4,5,6], [1,2,3,4,5,6], [1,2,3,4,5,6], [1,2,3,4,5,6] ]
And from that, we generate this:
As you can see,