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!
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. The 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 vector 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. 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.
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.
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 a nested (as opposed to an inner) class in Java, similar to the CellState in MazeCell. Note that, unlike their abstract Maze and MazeCell ancestors, the SquareCellMaze and SquareCell classes are aware of, and dependent on, each other.
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 (width, then height). In the maze, '-'
and '|' are used for walls, ' ' for rooms and unblocked passages, '+'
for the corners of the rooms, '*' for the entrance, and 'O'
for the donut. For example, the following is a legal maze:
7 5 +-+-+-+-+-+-+-+ |*| | | | | + +-+ + + +-+ + | | | | + + + +-+ +-+ + | | | | | + +-+-+ +-+-+ + | | | +-+ + +-+-+ +-+ | | O| +-+-+-+-+-+-+-+
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. The SquareCellMazeIterator iterates through
the cells of a SquareCellMaze. The NeighborIterator iterates over the neighbours of a particular SquareCell.
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 nested
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 code to print out
the solution path and the visualizer to color nodes
on the solution path differently.