Recursive Division Maze Generation

Recursive Division Algorithm

This is a fast algorithm that differs from other maze generating routines in that it builds walls, rather than breaking through them.

1. Choose an area to be divided (highlighted in blue). Initially, the only available area will be the entire board.
2. 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.
3. Choose a random location in the wall to build a single gap. This ensures the maze will be fully connected.
4. 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.
5. The process ends when no areas remain with width and height greater than 1.

This algorithm can be easily modified to change the overall appearance or size of the maze.

About the Applet

This applet was created using JavaScript and the P5 library. No other libraries/dependencies are required. If you are having trouble viewing the applet, be sure JavaScript is enabled in your browser. Click here for instructions. Internet Explorer is not recommended for this applet.

This applet was last updated July 2019.