Purpose of This Document

For many students, this assignment is the first time they have encountered a significantly-sized body of existing code. The purpose of this document is to provide an architecture-level view of the many interacting classes which you have been provided as part of the CSE 326 MazeRunner assignment.

Please note that, in this document, the term "reference" means "an indirect method of accessing data". Java references, C/C++'s pointers, and C++'s references all fulfill this definition. The term "general reference" is a reference to any type; in particular, a "general reference" in Java is a reference to the Java Object type, and a "general reference" in C/C++ is a void*.

Best of luck with the upcoming assignment!

Abstract Maze Classes/Interfaces

The Maze class is an abstract class which defines the interface to a family of descendant Maze classes. In addition to serving as an interface, the Maze class also contains a vector of registered maze change listeners (which are notified whenever the Maze changes its state) and a general reference to a object which may be used (if the programmer chooses) to store additional information related to all instances of Maze descendants. There is no restriction on the type of information which may be stored in the Maze, due to the use of a general reference.

The MazeRunner class is an abstract base class which defines the interfaces to a family of descendant MazeRunner classes. Each of these classes represent a maze-solving algorithm, which is called via the MazeRunner solveMaze() method. There abstract MazeRunner needs only to know about the Maze class.

The MazeCell class is an abstract base class which defines the interface to a family of descendant MazeCell classes. The MazeCell class contains information about each logical "room" in a maze; this includes information such as the possible number of walls for a room, the number of blocked walls, and the state of the cell. As with the Maze class, there is a general reference to an object which the programmer may choose to store additional information about the cell, and a vecetor of maze change listeners. Unlike the Maze class, the MazeCell class has the ability to broadcast MazeCell changes to all its listeners. Note that the abstract Maze and MazeCell are unrelated classes.

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.

The code here is also pretty hairy; feel free to ignore it. Note that the Java SquareCellMazeVisualizer will run on any platform (since it's implemented in Java), whereas the C++ visualizer will only work on a graphical connection with a Unix machine (ie, you must be working at an xterm, or with ReflectionX).


Comments to cse326staff@cs.washington.edu