Make Maze

<< DuckyLove | FinalProjectsTrailIndex | Perspective Floor >>

Various interactive mazes could be made. This one just constructs a maze using the Recursive backtracker algorithm described here

For a visual demonstration of the algorithm, Click here

This will make a new maze on a mouse click. To see it in action, click here

Cell.java

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Rectangle;
import java.util.ArrayList;

/**
 * @author Chris Thiel, OFMCap 
 * @version 16 May 2012
 */

public class Cell 
{
	public static final int GAP=10, SIZE=40, LEFT=40, TOP=60;
	public static final int NORTH=0, SOUTH=1, EAST=2, WEST=3;

	private int visits, row, col;
	private boolean[] wall;
	private Rectangle box;

	public Cell(int r, int c)
	{
		visits=-1;
		row=r;
		col=c;
		wall=new boolean[4];
		box = new Rectangle (LEFT+col*(SIZE+GAP), TOP+row*(SIZE+GAP), SIZE, SIZE);
		for (int i=0;i<4;i++)
			wall[i]=true;
	}
	/**
	 * 
	 * @return a random neighboring Cell, or null if all neighbors have been visited
	 */
	public Cell randomNeighbor(Cell[][] m){
		ArrayList<Cell> n = new ArrayList<Cell>();
		//NORTH
		if (row>0 && m[row-1][col].getVisits()<0)
			n.add(m[row-1][col]);
		//SOUTH
		if (row<m.length-1 && m[row+1][col].getVisits()<0)
			n.add(m[row+1][col]);
		//WEST
		if (col>0 && m[row][col-1].getVisits()<0)
			n.add(m[row][col-1]);
		//EAST
		if (col<m[0].length-1 && m[row][col+1].getVisits()<0)
			n.add(m[row][col+1]);
		if (n.size()<1)
			return null;
		return n.get((int)(n.size()*Math.random()));
	}
	public void draw(Graphics g, Color c)
	{
		Color oldColor=g.getColor();
		g.setColor(c);

		if (visits==1)
			g.setColor(Color.GREEN);
		if (visits>1)
			g.setColor(Color.RED);

		g.fillRect(box.x, box.y, box.width, box.height);
		if (!wall[SOUTH])
			g.fillRect(box.x, box.y+SIZE, box.width, GAP);
		if (!wall[EAST])
			g.fillRect(box.x+SIZE, box.y, GAP, box.width);

		g.setColor(oldColor);
	}
	public Rectangle getBox(){return box;}
	public int getRow(){return row;}
	public int getCol(){return col;}
	public int getVisits(){return visits;}
	public void setVisits(int i){visits=i;}
	public void incVisits(){visits++;}
	public void setWall(int direction, boolean value){
		wall[direction]=value;
	}
	/**
	 * removes the walls between this cell and the other cell
	 * @param other
	 */
	public void removeWall(Cell other) {
		if (other.getRow()>row){//other cell is below this one
			this.setWall(SOUTH, false);
			other.setWall(NORTH, false);
		}
		if (other.getRow()<row){//other cell is above this one
			this.setWall(NORTH, false);
			other.setWall(SOUTH, false);
		}
		if (other.getCol()>col){//other cell is east of this one
			this.setWall(EAST, false);
			other.setWall(WEST, false);
		}
		if (other.getCol()<col){//other cell is west this one
			this.setWall(WEST, false);
			other.setWall(EAST, false);
		}


	}
}

MazeMaker.java


import java.applet.Applet;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Image;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.util.ArrayList;

/**
 * @author Chris Thiel, OFMCap 
 * @version 16 May 2012
 */

public class MakeMaze extends Applet implements MouseListener
{
	public static final int ROWS=10, COLS=14;
	public static final int WIDTH=800, HEIGHT=600;
	private Cell[][] m;
	String message="Making Maze";
	private Image imgBuffer;
    private Graphics gBuffer;

	public void init()
	{
		imgBuffer = createImage(WIDTH,HEIGHT);
        gBuffer = imgBuffer.getGraphics();
        message="Making First Maze";
		makeMaze();
		message="First Maze done.";
		this.addMouseListener(this);
	}
	public void makeMaze()
	{
		m = new Cell[ROWS][COLS];
		for (int r=0;r<ROWS;r++)
			for(int c=0;c<COLS;c++)
				m[r][c]=new Cell(r,c);Cell currentCell=m[ROWS-1][0];
		currentCell.incVisits();
		ArrayList<Cell> stack=new ArrayList<Cell>();
		while (unvisitedCells()){
			Cell choice=currentCell.randomNeighbor(m);
			if (choice!=null){
				stack.add(0, currentCell);
				currentCell.removeWall(choice);
				currentCell=choice;
				currentCell.incVisits();
			}else{
				stack.remove(0);
				currentCell=stack.get(0);
			}
			repaint();
		}
	}
	private boolean unvisitedCells(){
		int r=0;
		while(r<ROWS){
			int c=0;
			while(c<COLS)
				if(m[r][c].getVisits()<0){
					return true;
				}else{
					c++;
				}
			r++;
		}
		return false;
	}
	public void paint(Graphics g)
	{
		gBuffer.setColor(Color.WHITE);
		gBuffer.fillRect(0, 0, WIDTH, HEIGHT);
		gBuffer.setColor(Color.BLACK);
		gBuffer.drawString(message, 20, 20);
		gBuffer.fillRect(Cell.LEFT-Cell.GAP, Cell.TOP-Cell.GAP, 
				COLS*(Cell.SIZE+Cell.GAP)+Cell.GAP, ROWS*(Cell.SIZE+Cell.GAP)+Cell.GAP);
		for (int r=0;r<ROWS;r++)
			for(int c=0;c<COLS;c++)
				m[r][c].draw(gBuffer, Color.YELLOW);
		g.drawImage(imgBuffer,0,0,this);
	}
	public void update(Graphics g)
    {
        paint(g); 
    }
	@Override
	public void mouseClicked(MouseEvent e) {}
	@Override
	public void mouseEntered(MouseEvent e) {}
	@Override
	public void mouseExited(MouseEvent e) {}
	@Override
	public void mousePressed(MouseEvent e) {}
	@Override
	public void mouseReleased(MouseEvent e) {
		message="Making new Maze";
		makeMaze();
		message="Maze Done";
		repaint();
	}

}