GUI Maze Solver

Objectives

• Demonstrate code re-use and multi-file programming
• Use OOP techiques including inheritance and composition
• Use multithreading
• Use data structures to solve a problem - specifically ArrayList and Stack

Overview

• We have already covered object-oriented programming and data structures.
• We have discussed and briefly used multithreading and GUI programming.
• Today we attempt to consolidate and build on what we have previously done.
• The goal for the day is to extend someone's maze creator program to make a graphical maze solver.
• You already have to create a maze solver using graph techniques for one of your assignments, so we will use a different algorithm today - one that is better suited for a visual display of walking a maze.

Prerequisite

You should use your source files from the maze creation assignment: Board.java, Cell.java, Direction.java, and Maze1.java. If you do not have them completed, then you can download compiled versions of those classes here: GUIMazeBaseClasses.zip. Just extract the class files into the same directory where you will be creating your graphical maze solver. The graphical maze solver must be named: GUIMaze.java

Source files (classes)

• Direction: Provides support for named directions (N,E,S,W) - unchanged
• Cell: Keeps track of and supports the individual aspects of a "maze room" (a cell) - unchanged
• Board: Keeps track of and supports the grouping of cells that comprise the maze - unchanged
• Maze1: Builds and displays a random maze using Direction, Cell, and Board - minor modifications
• MazeCell: Keeps track of the way a cell is displayed in the GUI - NEW
• GUIMaze: Creates the GUI and solves the maze using a GUI - NEW
• SolverThread: The thread that solves the maze (contained within GUIMaze) - NEW

Maze1 changes

• Add code to support a delay argument for the command line. This will control how fast the solution displays.
• Add code to call the GUI maze solver.

MazeCell

This will be a subclass of JLabel with additional support for coloring the cell and showing borders where there are walls present. It should get a reference to the Cell object it represents to set up the borders - but it does not need to retain that reference.

GUIMaze

This is the workhorse of today's project. It has to create the GUI interface and it also contains the thread that will be used to solve the maze. The suggested API is listed below:

• public GUIMaze(Board b): constructor
• public GUIMaze(Board b, int delay): constructor
• public MazeCell getCell(int row, int column): returns a specific cell from the GUI maze
• public void createAndShowGUI(): creates the GUI and makes it visible

GUIMaze GUI mockup

Solver class and algorithm

This class should have two constructors (one default and one which accepts a delay time). It should implement Runnable (act as a thread) with the run method using the following algorithm:

set all cells to unvisited
set the start cell to visited, color it as a terminal cell, and push it onto the stack
set solved to false
while not solved do the following
    get a list of the unvisited connected neighbors of the top cell on the stack
    if the list is empty then
        pop the cell from the stack and color it plain (not part of solution)
    otherwise
        pick one of the neighbors at random from the list
        push it onto the stack
        if it is not the start or end cell then
            color it as part of the solution
            set it to visited
        if it is the end cell then set solved to true
    delay