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.