JTF > Demo Gallery > assignments > MazeMaker

 
This assignment involves working with mazes constructed on a rectangular grid. The more conventional part of the assignment is solving an existing maze, which can be done using a variety of algorithms such as the right-hand rule (which fails if the maze contains loops), recursive backtracking, or nondeterministic exploration in parallel. The sample applet, however, also supports automatic maze generation using the following algorithm, which ensures that any pair of squares is connected by a single unique path.

  1. Imagine that the maze consists of a two dimensional array of “rooms”, each of which can be “painted” in some color. Start off by painting each of the rooms white.

  2. Iterate through each of the walls of the maze in a random order. At each step, look at the colors of the room on each side of the wall and perform one of the following operations:

Processing the walls in a completely random order tends to give rise to very easy mazes in which the start and finish squares are connected by a path that doesn't meander very much. Starting with walls that are far away from the start and finish squares generates much more interesting mazes.

This assignment is adapted from an immigration project for summer interns at DEC’s Systems Research Center, which was developed by Greg Nelson in the 1980s.