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.
- 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.
- 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:
- If both rooms are white, the rooms are part of a new path. In
this case, remove the wall and paint each of the rooms in some
previously unused color.
- If one room is white, the white room becomes an extension of an
existing path. Remove the wall and paint the white room to match its
neighbor.
- If the rooms are painted in different colors, the wall joins two
path segments. Remove the wall and repaint the entire path on one
chain so that it matches the other.
- If the rooms are painted in the same color, there must already be
a path that joins the two rooms. Removing this wall would create a
second path, so it is essential to leave that wall in place.
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.
