###
V22.102:Honors Data Structures

Spring 2000

Assignment IV

Second program: maze traversal.
Due: Wednesday March. 8

The purpose of this assignment is to implement a nice graphic interface to
the maze search program described in the text, pp 339 and following. Full
algorithm is fgure 9.15, p 346. The assignment involves array and stack
manipulations.

a) Read the algorithm carefully, and make sure you understand how it works.
Then, describe precisely what needs to be changed (new declarations, new
data structures) to make this into a 3-dimensional maze traversal program.
In particular, how are the variables Offset and Option affected? If the
maze is of size N by N by N, what is the maximum time complexity of the
algorithm?

b) Maze generation: to test our program, we want to generate random mazes.
If we stick to rectangular mazes where the paths are only horizontal or
vertical, we can generate a maze by carving random straight lines into it.
We generate two random numbers; one to specify a row (or column) and one to
specify the length of the path. To generate a random number, we use the
function Math.random (), defined in class Math (in Java.Lang). A call to
this function generates a real number in the range 0.0 to 1.0. To obtain an
integer in the range 0 to N, write:

int val = (int) (N * Math.random ());

Choose a reasonable size maze, say 20 by 20, carve random paths into it, and
display the result. Simplest is to print an array of zeroes and ones (you can
do this for the first tests) but afterwards we want a pleasant display in an
applet, for example.

c) The maze should be a rectangular array of geometric primitives, squares
or circles. For example, the points corresponding to walls may be dark circles,
and the points corresponding to paths might be left blank. As the algorithm
tries different paths, the places that have been explored should be in a
different color. When the algorithm succeeds, the full path should be somehow
highlighted in a different color.

d) The user interface asks the user if he wants to continue the simulation.
If yes, the program generates a new random maze and runs the algorithm on it.
Optional: the interface may ask for the desired dimensions of the maze.