Program 3 - Maze Traversal

Due: March 21, 2001, 11AM by email

This programming assignment will give you practise with stacks, recursion, and graphical user interfaces.

The assignment is to write a program that does maze traversal. First, you need to design a data structure to represent the maze. For example, a two dimensional array, with squares either empty or blocked, is one simple alternative, but feel free to design another. (Whichever alternative you use, your program should prompt the user to input the size of the maze first however, for example, 20 rows by 25 columns). Secondly, your program should traverse the maze. (You can use either explicit stacks, or recursion, in your traversal algorithm). The goal is to start from the maze entrance, and make it to the maze exit. You will have to keep track of the places already visited, to prevent infinite loops.

Finally, the graphical user interface should first draw the maze, then draw each step you take in searching for a path through the maze. If you have to backtrack, you might draw the return path in a different color. You might consider drawing the final path in yet a different color, to distinguish it from the attempted paths. Note that to make it visible to the eye, you will have to slow down drawing in your program. (There are several ways to do this - send email if you need help with this). For the graphical display, I leave it up to you to use either an applet, or a Frame to do the graphics.

This assignment is purposely leaving the algorithm choice to you. Don't be afraid to send email asking for help.