# Computer Generated Mazes

The following mazes were computer generated using a path digging algorithm. The generator maintains a list of all of the cells that have been added to the maze. At each step, it chooses one of the previous cells and randomly adds one of its unvisited neighbors to the maze. If a neighboring cell contains a perpendicular hallway followed by an empty cell, then this cell is also a valid choice to be added, replacing the hallway with a crossover cell. 9/10 of the time, the chosen previous cell is the last one that was added to the maze allowing the algorithm to construct longer paths without branching than if the previous cell were chosen completely randomly. Furthermore, the neighboring cell that is in the same direction as the last choosen neighbor is given a higher priority to encourage the creation of straight hallways that allow for crossovers. The direction of the crossover is based on the parity of the cell coordinates.

The mazes are output in Postscript, rendered with anti-aliasing using gv, and then screen captured. More recently, I'm rendering the mazes using POV-Ray.

Eventually, I'd like to find an algorithm that can create the non-tree like mazes that make up my three sheet weave mazes.

16x21 maze 1

16x21 maze 2

32x42 maze 1

32x42 maze 2

32x42 maze 4

32x42 maze 8

48x63 maze 1

48x63 maze 2

64x84 maze 1

64x84 maze 2

32x42 loop maze 1 -- joins dead-ends to a randomly chosen second neighboring cell. uses a lower initial branching probability.

Raytraced 7x5 maze 2

Raytraced 21x16 maze 1 -- start and end from the middles of the top and bottom edges. Click for 800x600 image (500k).

Raytraced 25x25 maze 4 -- start and end from the middles of the top and bottom edges. The second close-up uses a smaller railing size. Click for 800x600 images (900k, 750k, and 800k).

## Links to other people's maze pages

Beautiful mazes by Andrea Gilbert at www.clickmazes.com. Largely based on patterns. Hand-made.

Walter D. Pullen has a great description of maze generating algoritms at www.astrolog.org.

The incremental maze builder from the Obfuscated C Contest entry by John Tromp.

Jill Britton has a whole collection of mathematical pattern pages, including topic 14 on mazes.