/*
 * Dfs.java
 *
 * Use depth-first search to generate a random rectangular
 * maze.
 * Animate the construction of the maze.
 *
 * written by mike slattery - mar 1999
 */
import java.awt.*;
import java.util.*;
import java.applet.*;

public class Dfs extends Applet implements Runnable
{
	public static final int WTOP = 1;
	public static final int WRGT = 2;
	public static final int WBOT = 4;
	public static final int WLFT = 8;

	int cells[][];
	Point current_cell;
	Stack hold;
	int total, count;
	int gridw, gridh, cellsize;
	Image offscreen;
	Graphics offgr;
	Thread t;

	public void init()
	{
		int x, y;
		String param;

		/* Get applet params */
		param = getParameter("gridw");
		gridw = Integer.parseInt(param);
		param = getParameter("gridh");
		gridh = Integer.parseInt(param);
		param = getParameter("cellsize");
		cellsize = Integer.parseInt(param);

		cells = new int[gridw][gridh];
		/* Or together the wall bits to show that all
		 * the walls are up.
		 */
		int full = WTOP | WBOT | WLFT | WRGT;
		for (x = 0; x < gridw; x++)
			for (y = 0; y < gridh; y++)
				cells[x][y] = full;
		/* Then, mark the borders
		 */
		int left = WLFT << 4;
		int right = WRGT << 4;
		for (y = 0; y < gridh; y++)
		{
			cells[0][y] |= left;
			cells[gridw-1][y] |= right;
		}
		int top = WTOP << 4;
		int bottom = WBOT << 4;
		for (x = 0; x < gridw; x++)
		{
			cells[x][0] |= top;
			cells[x][gridh-1] |= bottom;
		}
		total = gridw*gridh;
		offscreen = createImage((gridw+2)*cellsize, (gridh+2)*cellsize);
		offgr = offscreen.getGraphics();
	}

	public void start()
	{
		t = new Thread(this);
		t.start();
	}

	public void stop()
	{
		t.stop();
		t = null;
	}

	public void run()
	{
		int dir;

		/*
		 * Implement depth-first search to build maze
		 */
		current_cell = new Point(rnd(gridw)-1,rnd(gridh)-1);
		count = 1;
		hold = new Stack();
		while (count < total)
		{
			dir = findNewNbr(current_cell);
			if (dir == 0)
				current_cell = (Point)(hold.pop());
			else
			{
				removeWall(current_cell, dir);
				count++;
				hold.push(current_cell);
				current_cell = getNbr(current_cell, dir);
			}
			/*
			 * Break for the animation effect
			 */
			repaint();
			try
			{
				Thread.sleep(50);
			} catch (Exception e) {};
		}
		/*
		 * All done
		 */
		repaint();
	}

	public void update(Graphics g)
	{
		paint(offgr);
		g.drawImage(offscreen,0,0,this);
	}

	public void paint(Graphics g)
	{
		int val, x ,y;

		int basex = 10;
		int basey = 10;
		g.setColor(Color.white);
		g.fillRect(basex, basey, gridw*cellsize, gridh*cellsize);
		g.setColor(Color.black);
		for (x = 0; x < gridw; x++)
			for (y = 0; y < gridh; y++)
			{
				val = cells[x][y];
				if ((val & WTOP) != 0)
					g.drawLine(basex+x*cellsize, basey+y*cellsize,
						basex+(x+1)*cellsize, basey+y*cellsize);
				if ((val & WRGT) != 0)
					g.drawLine(basex+(x+1)*cellsize-1, basey+y*cellsize,
						basex+(x+1)*cellsize-1, basey+(y+1)*cellsize);
				if ((val & WBOT) != 0)
					g.drawLine(basex+x*cellsize, basey+(y+1)*cellsize-1,
						basex+(x+1)*cellsize, basey+(y+1)*cellsize-1);
				if ((val & WLFT) != 0)
					g.drawLine(basex+x*cellsize, basey+y*cellsize,
						basex+x*cellsize, basey+(y+1)*cellsize);
			}
		/*
		 * Draw the current_cell as well
		 */
		g.setColor(Color.red);
		if ((count < total) && (current_cell != null))
			g.fillOval(basex+current_cell.x*cellsize, basey+current_cell.y*cellsize,
				cellsize, cellsize);
	}

	/*
	 * The following routines provide access to the underlying
	 * maze data structure.
	 */
	int findNewNbr(Point p)
	{
		/* Return a direction in which the point p has
		 * a neighbor which hasn't been visited yet (we test
		 * this by checking that all its walls are intact).
		 */
		int full = WTOP | WBOT | WLFT | WRGT;
		int d = rnd(4)-1;
		int k = 0;
		while (k < 4)
		{
			switch(d)
			{
				case 0:	/* Top nbr? */
					if ((cells[p.x][p.y] & (WTOP<<4)) != 0) break;
					/*
					 * Mask with 0xF to get bottom 4 bits
					 */
					if ((cells[p.x][p.y-1] & 0xF) == full) return WTOP;
					break;
				case 1: /* Right nbr? */
					if ((cells[p.x][p.y] & (WRGT<<4)) != 0) break;
					if ((cells[p.x+1][p.y] & 0xF) == full) return WRGT;
					break;
				case 2: /* Bottom nbr? */
					if ((cells[p.x][p.y] & (WBOT<<4)) != 0) break;
					if ((cells[p.x][p.y+1] & 0xF) == full) return WBOT;
					break;
				case 3: /* Left nbr? */
					if ((cells[p.x][p.y] & (WLFT<<4)) != 0) break;
					if ((cells[p.x-1][p.y] & 0xF) == full) return WLFT;
					break;
			}
			d = (d+1) % 4;
			k++;
		}
		return 0;
	}

	void removeWall(Point p, int d)
	{
		/* Exclusive or bit with cell to drop wall
		 */
		cells[p.x][p.y] ^= d;
		/*
		 * And drop neighboring wall as well
		 */
		switch(d)
		{
			case WTOP: cells[p.x][p.y-1] ^= WBOT;
				break;
			case WRGT: cells[p.x+1][p.y] ^= WLFT;
				break;
			case WBOT: cells[p.x][p.y+1] ^= WTOP;
				break;
			case WLFT: cells[p.x-1][p.y] ^= WRGT;
				break;
		}
	}

	Point getNbr(Point p, int d)
	{
		switch(d)
		{
			case WTOP: return new Point(p.x, p.y-1);
			case WRGT: return new Point(p.x+1, p.y);
			case WBOT: return new Point(p.x, p.y+1);
			case WLFT: return new Point(p.x-1, p.y);
		}
		return null;
	}

	int rnd(int n)
	{
		return (int)(Math.random()*n+1);
	}
}