Description
"You are in a maze of twisty little passages, all alike."
-Adventure
Mazes are a classic staple of adventure games. To have variety across replays and to devalue strategy guides, mazes are a good place to add randomness, and many algorithms exist to generate them. Most maze algorithms generate perfect mazes, which have every open area within the maze connected without loops. It is relatively straightforward to create loops in most perfect maze algorithms, by carving additional passages between already connected grids after completion of the perfect maze.
Many procedural dungeon generation techniques use maze algorithms as the basis of level design as the properties of perfect mazes are useful for ensuring efficient use of space in a grid or voxel based data structure and connectedness between elements in the level. However, perfect mazes can be less interesting to navigate through than imperfect mazes, because there is only one correct path through a level.
Code Example
One method for generation, the Growing Tree algorithm, starts with a single cut square in a grid of squares, and a list of exposed squares adjacent to the cut square. Each step an exposed square is selected. If it is exposed on only one side then cutting it will not form a loop - so it is cut, removed from the list, and any newly exposed squares are added to the list. If it cannot be cut, then it becomes a wall and is removed from the exposed list. This step is repeated until it cannot be repeated, that is, until the exposed list becomes empty.
If the order of items added to the list is preserved then the shape of the maze can be varied by where in the list the next cell is selected from. If only the most recent items are used then the maze will be generated "depth first" and will consist of long passages with few branches. If the oldest entry is used then passages are likely to be short with many branches.
See growingtree.py, a python implementation of this algorithm. Sample output:
..#...#..##.#.##.#.#.#.#...#.##...#.#.#.
#.#.####.........#.......###....###.....
..#..#.#.####.##...#####.....##.#.#.##.#
#.#.##......#.#..#.....##.#.##.......#..
.....##.##.####.##.#.###########.#######
.#.#.....#.#.#####.#...#.#.#.#.###....#.
####.#####.....#.#######.#...#.#.##.###.
.........##.##.....#.#.#.#.###.#.....#..
#####.#.###.###.####.#.......#.#.#####.#
#.#...###.#...#.#.##...#####.....#......
....#...#.##.##......####.########.#####
###.#.###..#.#######.................##.
....#.....##......#..#####.###########..
.#.###.#.########.##.....#...........#.#
.###.#.####.##..#.#..#.###.##.###.####..
##......#......####.##...#.#....#......#
...#.##...#.#####...##.#.#.##.###.#.####
##.#..#.#.#.....#.#..#####.#....#.#.#...
...##.#.#.##.####.##.....#.#.#.####...##
.#.#..#.#..#....#.#..#.#.#.#.#....#.#...
PCG Wiki References
External Links
- Simple maze on RogueBasin
- Think Labyrinth: Maze Algorithms - Discusses different classifications of mazes, example images, and algorithms to generate them.
- Maze - Wikipedia article on Mazes.
- Maze generation algorithms - Wikipedia article on algorithms to generate mazes.
- "Algorithm" is Not a Four-Letter Word - Presentation explaining algorithms to generate mazes