CompSci 18S - Spring 2008 - Solving a Maze (Recursion)
Classwork 13 (10 pts)
April 14, 2008
For group work, please turn in one sheet of paper with all the names
of those who participated in your group.
Problem
We will address solving a maze using a Maze class.
The maze is a 2D structure with walls and blank areas (no walls) where you
can walk, with a wall all
the way around the complete structure. There is a starting position
inside the maze and there is a pile of gold that needs to be found.
We will use a 2-D array of Colors to store the maze, here are the instance
variables of the class.
<![CDATA[
// the maze data
private Color[][] myMaze;
// starting point of the solution
private Point myStart;
// true if the gold has been found, false otherwise
private boolean isSolved;
]]>
Yellow - Gold
Green - Wall
Black - blank
Magenta - Start
Blue - path , show part of path that has been checked.
And in code we will use contants to refer to them.
<![CDATA[
// colors that represent different states of the maze
public static final Color WALL = Color.GREEN;
public static final Color BLANK = Color.BLACK;
public static final Color PATH = Color.BLUE;
public static final Color GOLD = Color.YELLOW;
public static final Color MARKER = Color.MAGENTA;
]]>
Problem
Assume the maze has already been inialized. Your task is solve the maze
using recursion. You will stay on the blank areas and as you check a
square on the
path, you should change it's color to Blue.
Do not worry about painting the maze. If you change a color in the maze,
then it should automatically be painted for you.
<![CDATA[
public void solve ()
{
isSolved = false;
myMaze[myStart.x][myStart.y] = BLANK;
solveRecursively(myStart.x, myStart.y);
}
private void solveRecursively (int row, int col)
{
]]>
Coding
You can download 18SMaze from the 18S snarf site. You will need to
write the one method solveRecursively in the Maze class, which has been
started for you.