CIT 594, Assignment 6: Maze Running
Purposes of this assignment:
In this assignment, you are to find your way out of a maze. I supply the GUI and the maze, while you write only the code required to escape the maze.
This is a somewhat unusual maze. It consists of an n by m array of "cells." If A and B are adjacent cells, you may or may not be able to go from A to B, and independently, you may or may not be able to go from B to A. From a cell along the edge of the table, you may or may not be able to escape to "outside" the maze. In the GUI (shown below), a gray arrow between cells indicates that you may go in the direction indicated by the arrow. The red dot indicates your starting position. In the second picture, the black arrows show a successful path.
Figure 1. A maze to be solved.
Figure 2. The same maze, solved.
Mazes are randomly generated, and there is usually an escape path. However, some mazes will be impossible to escape. In that event, your program should report failure after it has tried all possible paths.
To keep from going in circles, you need to keep track of the places where you
have been. If you enter a cell that you have previously explored, you should
immediately backtrack out of it. A requirement of the assignment is that you
Collection of some kind (other than a
to keep track of the places you have been, in order to avoid very long searches
(or infinite loops). The choice of
Collection is up to you.
The provided code:
I am providing three Java classes,
CrazyMaze (the GUI),
(which does the actual work), and
Position (a location in the maze).
You are not allowed to modify these classes. You should provide:
A class named
public Wanderer(Maze maze),and
public boolean solve()
CrazyMaze GUI will create a random maze, create a new
and ask the
Wanderer to solve the maze. That's all you should need
to know about the GUI.
Here's the jar file.
The second class,
Maze, provides a small number of methods for
you to use. You may be surprised at how limited these methods are. In particular,
you are not responsible for keeping track of your own row and column position
in the maze (and you shouldn't try to do so). You will find that these methods
are sufficient for your programming task, and the relative lack of information
should help to prevent you from being tempted to do all sorts of complicated
and unnecessary bookkeeping. With just these operations, you can concentrate
on the backtracking algorithm itself (and on the use of a Collection to keep
track of where you have already been).
Here is the interface. First, there are some direction constants:
You can use either the
WEST set of directions, or the
LEFT set of directions, whichever you find
more natural. You can even mix them, though this would not be in good taste.
Here are the methods you can use:
boolean canMove(int direction)
void move(int direction)
Use these as instance methods of your
maze (which was passed in
to your constructor as a parameter); that is, you would say
The program as it currently exists has an annoying flicker on larger mazes. I'm working on that problem, and you can expect to see a new version of the code shortly. However, I will not be changing the contract (unless someone points out a serious error in it), so none of my changes should affect you.
This assignment is due by midnight, Thursday, February 28. Do all your work in a single folder (directory), jar that directory, and submit it via Blackboard.