Anton's Blog: Mazes

Ever since I was a kid, playing on my 16KB TI-99/4A, I've loved creating randomly-generated mazes on the computer. I started with square rooms, then I worked up to triangular rooms, then hexagonal rooms. It was only recently that I realized a very simple algorithm for solving mazes without recursion.

I present here simple algorithms for creating and solving mazes, with illustrations. Although presented for square mazes, the algorithms can be adapted to any regularly or even irregularly tiled regions, and 3-D mazes.

Generation Algorithm

We generate this maze using a "random walk" through the maze space, skipping visited locations (rooms). If/when we get stuck, we look from left-to-right, top-to-bottom (and back) for visited locations with unvisited adjacent locations.

Set up a 2-dimensional array with the dimensions of the desired maze. Initialize each array element as a cell with no doors.

Here we have visualized an example 5-by-5 array of cells; each cell has no doors.

Pick a random element in the array.

Step A. Examine each adjacent location; if the adjacent location has no doors, add it to a list of potential new locations.

Choose a random new location from the list.

Add a door from the current location to the new location, and vice versa.

Move to the new location.

Return to Step A.

If the list of potential new locations is empty, we are in a "dead end."

Choose a new location, moving left to right, top to bottom, and repeating at the top. Skip any unvisited locations. Return to Step A.

When all the locations in the array are visited, we are done.

Solution algorithm

The resulting maze has a dendrite topology. If we set the start and end locations of the maze to have doors leading outside the array, we can solve the maze by repeatedly eliminating all "dead ends" (locations with only one door) from the array.

First, set the start and end locations to have doors leading outside the array.

Step B. Moving from left-to-right, top-to-bottom, find a dead end.

Step C. Seal the one door from the dead end. The dead end leads to only one location; seal the corresponding door in that location, and move to that location.