Brian Gordon

Maze generation

This Python script can generate mazes of arbitrary size and output them as png images using pypng. It can generate a 1000x1000 pixel maze in about 1 second on my hardware.

To generate the maze, Prim's algorithm is applied to a randomly-weighted lattice graph to produce a minimum-cost spanning tree. Alternatively, the program can generate a random spanning tree; this mode is faster and uses much less memory.

After the spanning tree has been constructed, this pattern is followed to produce the output image. Interestingly, this type of maze can be solved using a flood-fill algorithm on the walls. Several examples are given at the bottom of the page. The solution paths lie between the red and blue components of each maze.

This script only requires the pypng library, which is included as png.py in the zip distribution. If png.py is in the same directory as mazes.py then it will work fine.

$ python mazes.py -h
usage: mazes.py [-h] [--prims | --random] -s size size [-o filename]

Generate a maze with one of two algorithms.

optional arguments:
  -h, --help    show this help message and exit
  --prims       Use Prim's algorithm
  --random      Produce a random spanning tree
  -s size size  The maze's size, width then height in cells
  -o filename