/*
 * Hex.java
 *
 * This file draws a picture of a hexagonal maze with
 * all walls up.  It is intended as a starting point
 * for generating a hexagonal maze.
 *
 * preliminary code by mike slattery - mar 2000
 * Code updated and partially rewritten by Matt Sharritt - apr 2000
 */
import java.awt.*;
import java.util.*;
import java.applet.*;

public class Hex extends Applet implements Runnable
{
	/*
	 * The grid consists of hexagons laid out in a
	 * parallelogram border.  This allows us to use
	 * an ordinary array to refer to the hexagons.
	 * They are indexed as shown:
	 *
	 *        / \   / \   /
	 *       /   \ /   \ /
	 *      | 0,0 | 1,0 | 2,0
     *      |     |     |
	 *       \   / \   / \
	 *        \ /   \ /   \ /
	 *         | 0,1 | 1,1 |
	 *         |     |     |
	 *          \   / \   / \
	 *
	 * We'll refer to the six sides as:
	 *
	 *           TOPL  / \  TOPR
	 *                /   \
	 *         LEFT  |     |  RIGHT
	 *               |     |
	 *       BOTTOML  \   /  BOTTOMR
	 *                 \ /
	 *
	 * As in the square grid, we'll use bits to represent each wall
	 * and bits to represent where the borders are.
	 */
	public static final int TOPL = 1;
	public static final int TOPR = 2;
	public static final int RIGHT = 4;
	public static final int BOTTOMR = 8;
	public static final int BOTTOML = 16;
	public static final int LEFT = 32;

	int cells[][];
	Point current_cell;
	Stack hold;
	int total, count;
	int gridw, gridh, cellw, cellh;
	boolean finished = false;

	Image offscreen;
	Graphics offgr;
	Thread t;

	public void init()
	{
		int x, y;

		/* Init params */
		gridw = 10;
		gridh = 8;
		cellw = 30;
		cellh = (int)(0.866*cellw); // approx. regular hexagon

		cells = new int[gridw][gridh];
		/* Or together the wall bits to show that all
		 * the walls are up.
		 */
		int full = TOPL | TOPR | RIGHT | BOTTOMR | BOTTOML | LEFT;
		for (x = 0; x < gridw; x++)
			for (y = 0; y < gridh; y++)
				cells[x][y] = full;
		/* Then, mark the borders.
		 * In each cell, we use the bottom 6 bits to
		 * record which walls are present and the next 6 bits
		 * to indicate if any of these walls are edges of
		 * the maze.  So, for instance, if the RIGHT bit
		 * is set (value 4), that means the right wall is present
		 * and if RIGHT<<6 (value 256) is set, it means the right
		 * wall should never be knocked down.
		 *
		 * (shift the wall constants over 6 bits
		 * to get the border bits)
		 */

		/*
		 * Along the top of the maze, we mark both top edges.
		 * Along the bottom, both bottom edges.
		 */
		int top = (TOPL | TOPR) << 6;
		int bottom = (BOTTOML | BOTTOMR) << 6;
		for (x = 0; x < gridw; x++)
		{
			cells[x][0] |= top;
			cells[x][gridh-1] |= bottom;
		}
		/*
		 * Similarly, we need to mark two edges along each side
		 */
		int left = (LEFT | BOTTOML) << 6;
		int right = (RIGHT | TOPR) << 6;
		for (y = 0; y < gridh; y++)
		{
			cells[0][y] |= left;
			cells[gridw-1][y] |= right;
		}

		total = gridw*gridh;
		offscreen = createImage(432, 237);
		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);
				/*
				 * findNewNBr() returns zero if there are no
				 * new neighbors (not in the maze) to connect
				 * to.  In that case, we go back to the
				 * previous square (by popping it from the
				 * stack).
				 */
				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
				 */

				if(total == count)
					finished = true;

				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(0, 0, gridw*cellw+(cellw+1)*gridh/2, (gridh+2)*cellh);
		g.setColor(Color.black);

		int x1=0, x2=0, x3=0, y1=0, y2=0, y3=0, y4=0;
		for (x = 0; x < gridw; x++)
			for (y = 0; y < gridh; y++)
			{
				val = cells[x][y];
				/*
				 * Compute the x and y values which appear in the
				 * coords of the vertices:
				 *
				 *           x1 x2 x3
				 *           !  !  !
				 *    y1....... !  !
				 *           ! / \ !
				 *    y2.....!/   \!
				 *           |     |
				 *    y3.....|     |
				 *            \   /
				 *    y4.......\ /
				 */
				x1 = basex + x*cellw + y*cellw/2;
				x2 = x1 + cellw/2;
				x3 = x1 + cellw;
				y1 = basey + y*cellh;
				y2 = y1 + cellh/3;
				y3 = y1 + cellh;
				y4 = y1 + 4*cellh/3;
				/*
				 * Then draw whatever edges are present
				 */
				if ((val & TOPL) != 0)
					g.drawLine(x1, y2, x2, y1);
				if ((val & TOPR) != 0)
					g.drawLine(x2, y1, x3, y2);
				if ((val & LEFT) != 0)
					g.drawLine(x1, y2, x1, y3);
				if ((val & RIGHT) != 0)
					g.drawLine(x3, y2, x3, y3);
				if ((val & BOTTOML) != 0)
					g.drawLine(x1, y3, x2, y4);
				if ((val & BOTTOMR) != 0)
					g.drawLine(x2, y4, x3, y3);
			}
			/*
			 * Draw the current_cell as well
			 */
			g.setColor(Color.red);
			if ((count < total) && (current_cell != null))
				g.fillOval(current_cell.y*(x3-x2)+basex+current_cell.x*cellw, basey+current_cell.y*cellh+4,
					cellw, cellh);

			g.setColor(Color.black);
			if(finished == true)
			g.drawString("COMPLETE", 430/2 -20, 230);
	}

	/*
	 * 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).
		 * Return zero if there's nowhere to go.
		 */
		int full = TOPL | TOPR | RIGHT | BOTTOMR | BOTTOML | LEFT;
		int d = rnd(6)-1;
		int k = 0;
		while (k < 6)
		{
			switch(d)
			{
				case 0:	/* Topl nbr? */
					if ((cells[p.x][p.y] & (TOPL<<6)) != 0) break;
					/*
					 * Mask with 0x3F to get bottom 6 bits
					 */
					if ((cells[p.x][p.y-1] & 0x3F) == full) return TOPL;
					break;
				case 1: /* Topr nbr? */
					if ((cells[p.x][p.y] & (TOPR<<6)) != 0) break;
					if ((cells[p.x+1][p.y-1] & 0x3F) == full) return TOPR;
					break;
				case 2: /* Right nbr? */
					if ((cells[p.x][p.y] & (RIGHT<<6)) != 0) break;
					if ((cells[p.x+1][p.y] & 0x3F) == full) return RIGHT;
					break;
				case 3: /* Bottomr nbr? */
					if ((cells[p.x][p.y] & (BOTTOMR<<6)) != 0) break;
					if ((cells[p.x][p.y+1] & 0x3F) == full) return BOTTOMR;
					break;
				case 4: /* Bottoml nbr? */
					if ((cells[p.x][p.y] & (BOTTOML<<6)) != 0) break;
					if ((cells[p.x-1][p.y+1] & 0x3F) == full) return BOTTOML;
					break;
				case 5: /* Left nbr? */
					if ((cells[p.x][p.y] & (LEFT<<6)) != 0) break;
					if ((cells[p.x-1][p.y] & 0x3F) == full) return LEFT;
					break;
			}
			d = (d+1) % 6;
			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 TOPL: cells[p.x][p.y-1] ^= BOTTOMR;
				break;
			case TOPR: cells[p.x+1][p.y-1] ^= BOTTOML;
				break;
			case RIGHT: cells[p.x+1][p.y] ^= LEFT;
				break;
			case BOTTOMR: cells[p.x][p.y+1] ^= TOPL;
				break;
			case BOTTOML: cells[p.x-1][p.y+1] ^= TOPR;
				break;
			case LEFT: cells[p.x-1][p.y] ^= RIGHT;
				break;
		}
	}

	Point getNbr(Point p, int d)
	{
		/*
		 * Return the coordinates (as a Point) of the neighbor
		 * in direction d from cell p.  We assume other code
		 * has checked that such a neighbor really exists.
		 *
		 * This routine isn't used in the current version
		 * Hex.java, but it's included to show how to work
		 * with the hexagonal geometry.  It's also one of the
		 * methods needed for the depth-first maze construction.
		 */
		switch(d)
		{
			case TOPL: return new Point(p.x, p.y-1);
			case TOPR: return new Point(p.x+1, p.y-1);
			case RIGHT: return new Point(p.x+1, p.y);
			case BOTTOMR: return new Point(p.x, p.y+1);
			case BOTTOML: return new Point(p.x-1, p.y+1);
			case LEFT: return new Point(p.x-1, p.y);
		}
		return null; // This shouldn't ever happen
	}

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