The purpose of this document is to provide an architecture-level view of the code which you have been provided as part of the MazeRunner assignment. You should also look at the Javadoc code posted here. Best of luck with the assignment!
The Maze class represents a maze consisting of a rectangular grid of MazeCell objects. Each Maze instance stores information such as the width and height of the maze, the MazeCell instance at each location in the maze, the location of the start, and the location of the donut. The MazeCell is the basic building block of the Maze. Each MazeCell has the ability to return its position within a Maze and information about the walls surrounding it. We use an enumeration type Direction to refer to the four cardinal directions. For example, you can ask a MazeCell object if it has a wall on its north side by calling cell.isWall(Direction.NORTH).
Each MazeCell also has a "state" (unvisited, visit in progress, visited, on solution path) defined using the enumeration CellState. The CellState information is used both to keep track of whether each MazeCell has been processed by the algorithm yet, and also by the visualizer to display the state of a MazeCell. If updated appropriately by a MazeRunner, this CellState information can be used by the visualizer to display the MazeRunner's progress through the Maze.
Each MazeCell also includes an Object reference extraInfo, which means that maze runners may store some extra information in each MazeCell while running. Because extraInfo is an Object, the extra information can be of any type. In RandomMazeRunner, we use the extraInfo field to store a link to the next node in the solution path.
To generate a Maze, the MazeFactory
inner class defines a static method to parse and construct a Maze from an input file. Static methods of
a class may be called without needing to instantiate an instance of the class.
The Maze input format is a
picture of the maze. There is also some header information at the front that
gives the dimensions of the maze (width, then height). In the maze, '-'
and '|' are used for walls, ' ' for rooms and unblocked passages, '+'
for the corners of the rooms, '*' for the start, and 'O'
for the donut. For example, the following is a legal maze:
7 5
+-+-+-+-+-+-+-+
|*| | | | |
+ +-+ + + +-+ +
| | | |
+ + + +-+ +-+ +
| | | | |
+ +-+-+ +-+-+ +
| | |
+-+ + +-+-+ +-+
| | O|
+-+-+-+-+-+-+-+
The Maze class also provides two iterator classes. As the name suggests, iterators are often used to iterate over a range of objects: if an iterator points to one element in a range, then it is possible to increment it so that it points to the next element. Iterators are central to generic programming because they are an interface between containers and algorithms: algorithms typically take iterators as arguments, so a container need only provide a way to access its elements using iterators. This makes it possible to write a generic algorithm that operates on many different kinds of containers, even containers as different as a vector and a priority queue. The Maze's iterators are descended from Java's built-in Iterator interface. The MazeIterator iterates through the cells of a Maze. The NeighborIterator iterates over the neighbors of a particular MazeCell.
The MazeRunner interface represents a "runner" that solves a maze using some search algorithm. You should implement this interface to solve the maze with BFS, DFS, and BestFS. The interface defines a single method solveMaze, which takes a Maze to solve and a PrintWriter object on which to print the solution. The RandomMazeRunner discussed below is an example of a MazeRunner.
To help you get started with the MazeRunner interface, we have provided some example code. The RandomMazeRunner class, which is descended from the abstract MazeRunner, randomly walks through a Maze. At each MazeCell, it randomly chooses to visit a neighbor of that cell. Since the RandomMazeRunner maintains no information about whether a cell has been visited, a RandomMazeRunner may visit the same set of cells indefinitely.
The RandomMazeRunner utilizes a nested class called SolutionPathInfo to build a "linked list" of Mazes from the start node to the end node. As the RandomMazeRunner goes from node to node, it sets the SolutionPathInfo's next reference/pointer. When the RandomMazeRunner has reached the exit room, it iterates through the linked SolutionPathInfo (starting from the start node) and sets the CellState to onSolutionPath. This allows the code to print out the solution path and the visualizer to color nodes on the solution path differently.The Maze architecture includes some built-in support for visualization of the maze runners. Both Maze and MazeCell implement the Listener design pattern, in which "listeners" (classes implementing the MazeChangeListener interface) may register with an instance of Maze. Registered listeners receive information about "events" - for example, when a MazeCell changes its CellState. It is important that your implementations of MazeRunner properly update the CellState, so that any listeners receive the correct events.
The MazeTracer class is an example of a MazeChangeListener. The MazeTracer prints out each cell state change as it occurs, making it a useful tool for debugging your code. You can enable the tracer by using the "-t" option when you run MazeRunnerLauncher.