Maze Generator

This exhibit generates human-sized mazes.

The maze-generating algorithm is Prim's Minimum Spanning Tree Algorithm. This type of algorithm has many practical applications: its first modern instance, Borůvka's algorithm, was used to design power-line infrastructure for a town in what is now the Czech Republic. My dad worked on a project in the 1980s that used a similar algorithm for radio-networks. They are also used for circuit board design and taxonomy.

To execute the algorithm, we instruct the computer to follow these steps:

1. To begin, choose a random square from the grid. This square turns green.
2. Turn any black rectangle adjacent to the green square blue.
3. Randomly choose one of the blue rectangles.
   1. If both of the squares around it are green, turn this rectangle black and repeat Step 2 with a different blue rectangle.
   2. Otherwise, turn this rectangle and the black neighboring square green and go back to Step 2.

To demonstrate the exhibit I used two projectors to display the maze on the floor. In the demonstration the maze is 10' x 10'. The exhibit could be adapted to any size space. The maze can also be made more complex; say by increasing the number of squares on each side from 6 to a 10.

The code is available here. The live demonstration and video were created with the help of Joshua Challen Ice in Pittsburgh, PA.