Within the MazeCell class is the definition of a non-abstract CellState, which enumerates the set of possible states that a MazeCell may be in. In Java, this is accomplished by creating static instances of a CellState class and preventing any other instance of this class from being constructed. In C++, this is accompilshed with the built-in enum construct, which creates a new numerical type. This allows programmers to associate numerical constants with symbolic names in a type-safe manner. The CellState information is used primarily 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.

The SquareCellMaze Implementation of the Maze abstract class

The SquareCellMaze and related classes are concrete implmentations of the abstract classes listed above. The SquareCellMaze classes implements all the Maze class functionality. The underlying representation of the SquareCellMaze is a dynamically-allocated two-dimensional array of SquareCells (dynamically-allocated 2D arrays are not supported in the C++ language, so this is accomplished via the additional Matrix class).

The SquareCell is the basic building block of the SquareCellMaze, and is inherited from the abstract MazeCell class. In addition to implementing the MazeCell functionality, the SquareCell has the ability to return its position within a SquareCellMaze and information about the walls surrounding it. This Direction information is implemented as static instances of an inner class in Java, and as an enum in C++, similar to the CellState in MazeCell. Note that, unlike their abstract Maze and MazeCell ancestors, the SquareCellMaze and SquareCell classes are aware are aware of, and dependant on, eachother.

To generate a SquareCellMaze, the SquareCellMazeFactory class defines static methods to parse and construct a SquareCellMaze from an input file. Static methods of a class may be called without needing to instantiate an instance of the class. The SquareCellMaze input format is a picture of the maze. There is also some header information at the front that gives the dimensions of the maze (height, then width). In the maze, '-' and '|' are used for walls, ' ' for rooms and unblocked passages, '+' for the corners of the rooms, '*' for the entrance, and 'X' for the exit. For example, the following is a legal maze:

      7 5
      +-+-+-+-+-+-+-+
      |*|   | | |   |
      + +-+ + + +-+ +
      |   |   |     |
      + + + +-+ +-+ +
      | |   |     | |
      + +-+-+ +-+-+ +
      |       |     |
      +-+ + +-+-+ +-+
      |   |        X|
      +-+-+-+-+-+-+-+

Lastly, the SquareCellMaze class makes use of two iterator classes. Iterators are a generalization of pointers: they are objects that point to other objects. 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 SquareCellMaze's iterators are descended from Java's built-in Iterator interface or, in C++, from the templated AbstractIterator abstract base class which we have also provided. The SquareCellMazeIterator iterates through the cells of a SquareCellMaze. The NeighborIterator iterates over the neighbours of a particular SquareCell.

Example Code

To help you get started with the MazeRunner homework, we have provided some example code. The RandomMazeRunner class, which is descended from the abstract MazeRunner, randomly walks through a SquareCellMaze. At each SquareCell, 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 the SolutionPathInfo inner class/struct to build a "linked list" of SquareCellMazes 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 visualizer to colour nodes on the solution path differently.

In addition to MazeRunner code, we have also provided an abstract PriorityQueue class, which may be useful when writing heuristic-based MazeRunners.

Visualizers and Other Tools

The MazeChangeListener class defines two methods which its descendants must implement. The cellStateChangeEvent method is used to inform the MazeChangeListener that a change has occured in the CellState of its parameter. The stateChangeEvent is a general method is used to inform the MazeChangeListener that some kind of change has been made.

The SquareCellMazeTracer is a simple implementation of a change listener which can be used for debugging purposes. This listener merely prints all the MazeCells which were modified via the MazeCell's setState method, and may be useful to ensure that your MazeRunner is working correctly.

The SquareCellMazeVisualizer is a complicated implementation of a MazeChangeListener. It is used to graphically display the current state of the maze (and thus is useful for displaying the progress of one's MazeRunner). The appearance SquareCellMaze depends on whether one's MazeRunner sets the CellState correctly. The code here is pretty hairy, so you can probably ignore the inner workings of this class.

In order to graphically display the SquareCellMaze, the SquareCellMazeVisualizer makes use of the MazePanel class, which wraps language-specific calls to graphics packages. Thus, MazePanel is used to wrap Maze-specific calls to Java's native JPanel class or C++'s direct calls to X.