Program 4 - Maze Traversal

Due: April 29, 2002,  email to etutor by midnight


This programming assignment will give you practise with 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.  The difficulty is in keeping track of the maze locations already visited, to prevent infinite loops.

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 should draw over the path in a different color. 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 and can't find it on the Java API web site). Design and details of the graphical display are left up to you and and your imagination. You can use either an applet, or a JFrame to do the graphics.