Maze generation algorithm

The creation of mazes by algorithms is fairly simple. Ineffective computer algorithms take a grid of the desired size (rectilinear n-dimensional block if you prefer) and then recursively remove walls from randomly chosen cells that make up the grid using a depth-first search algorithm. Walls are only removed to connect cells if they are not already connected by a different path, which requires a futher process to check. This will create a perfect maze, that is one containing no unconnected space.

Here is a sensible maze generation algorithm, which generated the maze to the right. For the source code for a Java applet that generated the maze using the algorithm, click on the maze.

Start with a grid. Randomly select a square of the grid, mark it as part of the maze. Mark the neighbouring squares as next to the maze, store their locations in a list. While there are still squares in the list of squares next to the maze, randomly choose one from the list, remove it from the list, and connect it to the maze, by removing a wall between it and the maze. Mark it as part of the maze. Then mark all squares next to it as next to the maze, if they aren't already marked or part of the maze, adding them to the list. Once the list is empty, the maze is complete.

In mazes generated by that algorithm, it will typically be relatively easy to find the way to the square that was first picked at the beginning of the algorithm, since most paths lead to or from there, but hard to find the way out.

External link

• Making Mephistophelean Mazes, 1995 webpage with source code (http://www.pmms.cam.ac.uk/~gjm11/programs/maze/)

This article is a stub. You can help Wikipedia by fixing it.