Our Specification

To meet the above requirements, the program will have the following features:

1. It will start as a standalone GUI application written in Java using the standard edition of JDK 1.3
2. The program uses Java AWT and Swing libraries to implement the GUI. It does not use any third party graphical packages
3. The GUI has a panel on which the maze will be displayed. The panel can be updated whole on a request of one of the traversing algorithms, or just a single cell of the maze can be updated, also on request of one of the traversing algorithms.
4. Maze will be displayed on the panel using color-coding:
1. green for the cells that have not been visited by the algorithm yet
2. red for the cells that are currently considered as the ones on the path to the solution
3. gray for the cells that have been visited by the traversing algorithm but abandoned as cells on the path to the solution
4. the walls between cells will be black lines
5. The GUI will have several buttons: New, Clear, Depth-First, Breadth-First and A*.
1. Clicking on New button will triger new maze generation
2. Clicking on Clear button will clear the current maze – reset all the cells to green
3. Clicking on Depth-First, Breadth-First or A* will trigger the corresponding traversal algorithm
6. The GUI will have a slider to determine the speed of animation. The user will be able to choose several values between “fast” and “slow” for traversal animation
7. The GUI will have a “Setup” menu, in which the user can choose the “set size” option for the maze. In this case, the program will open a dialog that will enable the user to enter new maze dimensions

Analysis and Design

The program requires graphical animation of the maze. We will apply the Model-View-Controller (MVC) pattern to the overall architecture of the program. We will use a variation of the MVC pattern that decomposes the overall system into two subsystems: the model and the view-controller

The model consists of the maze object and the various algorithms that connect/traverse the maze.

The view contains the GUI components and the graphical display of the maze.

The controller sets up the appropriate wiring between the model and the view. It uses event handlers to respond to user input and notifies the model and the view to update accordingly. The controller uses a multithreading to enable animation of the algorithms while the algorithms are performing.

We now describe the two subsystems.

Model

We represent the maze by an abstract class called Maze. A Maze object holds the data structure for maze cells and the walls between the cells. It has declarations of methods for changing and querying the properties of a maze: dimensions, cell status, existance of walls between cells, starting and ending points for traversal A concrete class that extends Maze should implement the data structures that will hold the maze cell and wall information and implement the abstract methods from Maze. On the abstract level, the maze is conceptually a two-dimensional array of cells. A concrete implementation has to provide this interface, but the actual data structure design in a concrete implementation is arbitrary.

Maze also has a generateNewMaze method that implements the Factory pattern. This method returns a new instance of the current implementation of a concrete Maze. As of this writing, this Factory method returns a new instance of RandomMaze, a rudimentary (and extremely inefficient) prototype of a random-generated maze. During your software integration, you should change this factory method to return your concrete implementation of the maze.

Maze also provides a mechanism for animation of maze traversal using thread synchronization. All of the methods involved in thread synchronization have already been implemented by us in the abstract Maze class.

Class Status provides constants for the cells in the maze. Cells can be NotVisited, OnPath or Abandoned.

We represent the different maze algorithms with a Strategy pattern. This pattern is defined by the abstract class Strategy. The only method in Strategy is execute(Maze maze), which performs an algorithm on the maze. Concrete classes that extend the Strategy should implement this method to perform the corresponding algorithm on the maze. For example, we have provided a concrete strategy Clear, which iterates through all the cells in the maze and sets their status to Status.NotVisited. Clear.execute is an excellent example of the only interaction that the model has with the View-Controller: to trigger “animated” color change of a cell in the maze it is sufficient to call the refreshAndRepaint method in the MazeWindow class.

Strategy also has several Singleton fields: DFS, BFS, AStar, MazeGen and Clear – these singletons correspond to concrete strategies that have yet to be implemented. As of this writing, they are all initialized to an instance of the Clear strategy, they should be initialized to corresponding concrete implementations of Strategy when the implementations are finished.

View-Controller

The controller and view class is called MazeWindow. This class implements all the interaction between the maze and the user, and presents to the user an animated view of the algorithm that traverses or generates the maze. MazeWindow is a subclass of a Swing class JFrame. It implements the buttons, menus and and the slider using the standard Swing components. It uses the AWT event dispatching mechanism to assotiate user actions with actions performed on the Maze.

A large portion of the code for MazeWindow is automatically generated by JBuilder using a graphical design system. The important fields and methods of the MazeWindow class are:

• maze - a reference to the Maze implementation for which this View and Control is set up.
• ROWS, COLS – current values of the maze dimensions. They are set to 50 and 50 by default
• xStart, yStart, xEnd, yEnd – the coordinates (in pixels) of the part of the MazeWindow on which the maze is drawn
• PAUSE_MS – the amount of time (in miliseconds) that the control will stop the execution of a maze algorithm to update the graphics.
• paint – the method that draws the complete maze on the panel. This method queries the maze to find out the status of the cells and walls and draws them accordingly
• {NewMaze, ClearMaze, DepthFirst, BreadthFirst, AStar, SetSize}_actionPerformed – the methods to which the events in the GUI are dispatched. These methods perform the requested operation by setting the correct Strategy singleton in the Maze and manipulating the thread execution process.
• refreshAndRepaint – a method for repainting a single cell in the maze. This method stops the Strategy execution process for PAUSE_MS miliseconds and repaints the requested cell. This (and maybe a call to repaint() which repaints the whole frame without pausing the execution) should be the only point of interaction where your code in the Model calls the code in the View-Controller.

Class SizeDialog implements the pop-up dialog that asks the user for new maze dimensions.

Class MainWindow is the main program class. This class should be specified when the program is run.

You can find all the source code here.