In this lab you will design a Java applet to navigate a maze. We model the maze as a grid of squares. The grid has r rows and c columns. The maze in the picure below has r=10 rows and c=10 columns.
The white squares are squares you may occupy or move to. The black squares are walls or obstacles. The green square is the start of the maze, and the red square is the end of the maze.
In Java we represent the maze as a two-dimensional array of integers:
The colored squares of the pictured maze correspond to the following integer values in the maze array:
| maze[r][c] = -1 | black square |
| maze[r][c] = 0 | white square |
| maze[r][c] = 1 | green square (START) |
| maze[r][c] = 2 | red square (END) |
The START square is at array position maze[1][1]. The END square is at position maze[8][8].
We can move in at most four possible directions from any occupied square -- north, south, east or west. If we are currently in position maze[r][c], then the following array positions correspond to the possible directions of movement:
| maze[r-1][c] | North |
| maze[r+1][c] | South |
| maze[r][c-1] | West |
| maze[r][c+1] | East |
Here is an example of a fully functional maze applet:
Clicking the Solve button will compute the path through the maze from start to finish. The blue squares represent this path. The gray squares represent "dead-end" paths that your algorithm computed. Depending on the order in which you choose directions, your implementation may visit different dead-end paths than the one above. The output area shows the squares visited by the algorithm and the final path through the maze.
You will be given an almost complete version of the Maze.java code for the above applet. You need to fill in the code for the subroutine to solve the maze:
The first line of code (showPosition( r, c, depth );) will generate the recursion trace in the output text area so you can see what your subroutine is doing. You should leave that line of code where it is and put all your code below as indicated.
You don't need to change any other code in the program!
Create a subdirectory of your public_html/cps001 directory to store your applet files for this lab. Access the P: drive from My Computer on your desktop. Open the folder for your public_html directory. Open the folder for the cps001 directory you just made. Create a new folder titled Lab8.
Create an HTML document for your applet. Start GNU Emacs. Go to File->Open and open a new file in your Lab8 directory named Maze.html. Type in the complete HTML page for your applet. In the applet tag set width = 350 and height = 600.
Save your Maze.html file.
Download or copy the file Maze.java to your Lab8 directory.
Open Maze.java in Emacs.
From your prelab you should see that navigating a maze from start to end can be solved recursively. Before writing any code, think about the following:
What are your base cases??
What are your recursive cases??
You need to keep track of squares you have already visited. This keeps you from going backwards and from wandering around the maze forever. There is a two-dimensional array of boolean values for you to use to do this:
Initially all values are set to false. When you move to a square, you should first check if you have been there already. If you haven't, you should mark the square as visited. What happens if you move to a square you have already visited??
If maze[r][c] == 2 then you are at the END square and you have (hopefully!) solved the maze. When you move to a square you should check if this is the end square, and if so set the boolean value endSquare == true. Once you reach the end square, you don't want to continue searching the maze!!
The integer variable depth is used to keep track of the depth of the decision tree of the maze, or in other words the number of steps you are from the start square. The depth increases by one when you move to a new (previously unvisited) square. The depth decreases by one when you move to a square you have visited already. You need to set these values appropriately.