MazeFrame.java

import java.util.ArrayList;
import javax.swing.JFrame;

public class MazeFrame
{
	public static void main(String[] args) throws InterruptedException
	{
		int width = 15;
		int height = 10;
		JFrame frame = new JFrame();
		Maze maze = new Maze(width, height);
		ArrayList<Pair<Integer,Integer>> solution = new ArrayList<Pair<Integer,Integer>>();
		MazeComponent mc = new MazeComponent(maze, solution);
		frame.setSize(800,800);
		frame.setTitle("Maze");
		frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		frame.add(mc);
		frame.setVisible(true);
		
		solution.add(new Pair<Integer,Integer>(0,0));
		Thread.sleep(1000);
		solveMaze(solution, mc, maze, 0, 0, 0, 0);
		mc.repaint();
	}
	
	/** Solve Maze: recursively solve the maze
	 * 
	 * @param solution   : The array list solution is needed so that every recursive call,
	 *                     a new (or more) next position can be added or removed.
	 * @param mc         : This is the MazeComponent. We need that only for the purpose of
	 *                     animation. We need to call mc.repaint() every time a new position
	 *                     is added or removed. For example,
	 *                       :
	 *                     solution.add(...);
	 *                     mc.repaint();
	 *                     Thread.sleep(sleepTime);
	 *                       :
	 *                     solution.remove(...);
	 *                     mc.repaint();
	 *                     Thread.sleep(sleepTime);
	 *                       :
	 * @param maze       : The maze data structure to be solved. 
	 * @return a boolean value to previous call to tell the previous call whether a solution is
	 *         found.
	 * @throws InterruptedException: We need this because of our Thread.sleep(50);
	 */
	public static boolean solveMaze(ArrayList<Pair<Integer,Integer>> solution, MazeComponent mc, Maze maze, int lastX, int lastY, int x, int y) throws InterruptedException
	{
		if (!atExit(maze, x, y))
		{
			boolean pathFound = false;
			
			// do not try previously mapped positions!
			// Try north
			if (!maze.isNorthWall(y, x) && (lastX != x || lastY != y - 1))
			{
				Pair<Integer, Integer> newStep = new Pair<Integer, Integer>(y - 1, x);
				solution.add(newStep);
				mc.repaint();
				Thread.sleep(100);
				pathFound = solveMaze(solution, mc, maze, x, y, x, y - 1);
			}
			// Try east
			if (!pathFound && !maze.isEastWall(y, x) && (lastX != x + 1 || lastY != y))
			{
				Pair<Integer, Integer> newStep = new Pair<Integer, Integer>(y, x + 1);
				solution.add(newStep);
				mc.repaint();
				Thread.sleep(100);
				pathFound = solveMaze(solution, mc, maze, x, y, x + 1, y);
			}
			// Try south
			if (!pathFound && !maze.isSouthWall(y, x) && (lastX != x || lastY != y + 1))
			{
				Pair<Integer, Integer> newStep = new Pair<Integer, Integer>(y + 1, x);
				solution.add(newStep);
				mc.repaint();
				Thread.sleep(100);
				pathFound = solveMaze(solution, mc, maze, x, y, x, y + 1);
			}
			// Try west
			if (!pathFound && !maze.isWestWall(y, x) && (lastX != x - 1 || lastY != y))
			{
				Pair<Integer, Integer> newStep = new Pair<Integer, Integer>(y, x - 1);
				solution.add(newStep);
				mc.repaint();
				Thread.sleep(100);
				pathFound = solveMaze(solution, mc, maze, x, y, x - 1, y);
			}
			
			// If no path, remove the last step from solution
			if (!pathFound)
			{
				solution.remove(solution.size() - 1);
				mc.repaint();
				Thread.sleep(100);
				return false;
			}
			else
			{
				return true;
			}
			
		}
		else
		{
			// Path found
			return true;
		}
	}
	
	private static boolean atExit(Maze maze, int x, int y)
	{
		if (x == maze.getWidth() - 1 && y == maze.getHeight() - 1)
		{
			return true;
		}
		else return false;
	}
}