Recursive Division Maze Generation
Recursive Division AlgorithmThis is a fast algorithm that differs from other maze generating routines in that it builds walls, rather than breaking through them.
- Choose an area to be divided (highlighted in blue). Initially, the only available area will be the entire board.
- Divide the chosen area by constructing a wall though it. The placement of the wall, as well as its direction, is random. However, in this particular implementation of the algorithm, the decision to build a vertical or horizontal wall is weighted based on the shape of the area being divided. In particular, if the area has width w and height h, a random integer from 0 to w+h is chosen. If the value is less than w, the division is vertical. This ensures that a wider area is more likely to be divided by a vertical wall, and a narrow area is more likely to be cut horizontally. This is purely for aesthetics.
- Choose a random location in the wall to build a single gap. This ensures the maze will be fully connected.
- If the divided portions of the area are large enough (width and height greater than 1 cell), they are both added to the stack of eligible areas to divide.
- The process ends when no areas remain with width and height greater than 1.
This applet was last updated July 2019.