import java.awt.*;

public class WallMaze extends Maze
{
    public static final byte BLOCKED = (byte) (TOP | RIGHT | BOTTOM | LEFT);
    int lastX, lastY;
    PathStack pathStack;

    protected byte initSq ()
    {
	return (byte) (BLOCKED | DIRTY);
    }

    public WallMaze ()
    {
	setBackground (Color.white);
	lineWidth = lineHeight = 1;
    }

    public boolean isOpen (int x, int y)
    {
	return inBounds (x, y) && sqr (x, y) != BLOCKED;
    }

	/*
	 * Here is the algorithm used to generate the maze:
	 *  1.  Set all the squares in maze grid to the BLOCKED state.
	 *  2.  Randomly select a square on the left side of the maze as the current square,
	 *      clear the wall on the left side of the square, and set <lastSide> to LEFT.
	 *  3.  Randomly choose a sequence to rotate through the remaining sides (the sides
	 *      other than <lastSide>) of the current square.
	 *  4.  Set nextSide to the next selected side in the rotation.
	 *  5.  If there is a BLOCKED square adjacent to the <nextSide> of the current
	 *      square, then goto step 9.
	 *  6.  If there are more sides rotation sequence, then goto step 4.
	 *  7.  You get to this step when the current square is not adjacent to any
	 *      BLOCKED squares. Randomly select a non-BLOCKED square (a square already
	 *      added to the maze) as the current square. This creates a new branch
	 *      in the maze.
	 *  9.  You get to this step when you have found a square to add to the maze.
	 *      Remove the wall between the current square and the square adjacent to
	 *      its <nextSide>.
	 * 10.  Set the new current square to the adjacent square and set <lastSide> to
	 *      the side of this square that was removed in step 9. This sets <lastSide>
	 *      to the side opposite <nextSide>. For example, if <nextSide> is TOP, then
	 *      the new <lastSide> is BOTTOM.
	 * 11.  If there are any BLOCKED squares remaining in the maze grid then goto
	 *      step 3, otherwise you're done.
	 */
    public synchronized void generate (boolean displayConstruction)
    {
	int curX, curY, nextX=0, nextY=0, lastSide = LEFT;
	byte sq;
	boolean stuck = false;
	int blocked = mazeWidth * mazeHeight, nonBlocked = 0,
	    threshold = blocked/8;

	generating = true;
	path = null;
	pathStack = null;

	// 1. Set all the squares in maze grid to the BLOCKED state.
	clearMaze ();
	if (displayConstruction)
	    showMaze (true);

	//2. Randomly select a square on the left side of the maze
	//as the current square
	startX = curX = 0;
	startY = curY = (int) (Math.random() * mazeHeight);

	// clear the wall on the left side of the square,
	//and set <lastSide> to LEFT.
	maze [curX] [curY] = 
	    sq = (byte) ((BLOCKED | DIRTY) & ~LEFT);
	dirtySquare (curX, curY);
	lastSide = LEFT;
	blocked --;
	nonBlocked ++;
	if (displayConstruction)
	    showMaze (true);

	do {
	    // 3. Randomly choose a sequence to rotate through the remaining sides
	    int rot = (int) (Math.random () * 4);
	    //System.out.println ("Step 3, pos=("+curX+","+curY+"),rot = "+rot);

	    int count = 3;
	    boolean goodSquare = false;
	    int nextSide = 0;
	    byte oppSide = 0;
	    do {
		// 4.  Set nextSide to the next selected side in the rotation.
		nextSide = lastSide << rot;
		oppSide = (byte) nextSide;
		if (nextSide > BLOCKED)
		    nextSide >>= 4;
		switch (nextSide) {
		case LEFT:
		    oppSide = RIGHT;
		    nextX = curX-1; nextY = curY;
		    break;
		case RIGHT:
		    oppSide = LEFT;
		    nextX = curX+1; nextY = curY;
		    if (!inBounds (nextX, nextY) && finishX < 0) {
			finishX = curX; finishY = curY;
			maze [curX] [curY] &= ~RIGHT;
		    }
		    break;
		case TOP:
		    oppSide = BOTTOM;
		    nextX = curX; nextY = curY-1;
		    break;
		case BOTTOM:
		    oppSide = TOP;
		    nextX = curX; nextY = curY+1;
		    break;
		}
		goodSquare = inBounds (nextX, nextY)
		    && !isOpen (nextX, nextY);
		//System.out.println ("Step 6: "+nextX+" " + nextY+": "+goodSquare);
		count --;
		if (!goodSquare) {
		    rot ++;
		    if (rot > 3)
			rot = 1;
		}

		// 6. If there are more sides rotation sequence,
		//then goto step 4.
	    } while (!goodSquare && count > 0 && generating);

	    // 5.  If there is a BLOCKED square adjacent to the
	    //<nextSide> of the current square, then goto step 9.
	    if (goodSquare) {
		//9. Remove the wall between the current square and the square
		//adjacent to its <nextSide>.
		maze [curX] [curY] &= (byte) ~nextSide;
		maze [nextX] [nextY] &= (byte) ~oppSide;
		dirtySquare (curX, curY);
		dirtySquare (nextX, nextY);

		//10. Set the new current square to the adjacent square
		//and set <lastSide> to the side of this square that was
		//removed in step 9.
		curX = nextX;
		curY = nextY;
		lastSide = oppSide;
		blocked --;
		nonBlocked ++;
		if (displayConstruction)
		    showMaze (true);
	    } else {
		//7. Randomly select a non-BLOCKED square as the current
		//square.
		goodSquare = true;
		do {
		    int pickSquare = (int) (Math.random () * nonBlocked);
		    count = 0;
		    for (int x = 0; x < mazeWidth; x ++) {
			for (int y = 0; y < mazeHeight; y ++) {
			    if (isOpen (x, y)) {
				if (count++ == pickSquare) {
				    curX = x; curY = y;
				}
			    }
			}
		    }
		    //System.out.println ("Open square at ("+curX+","+curY+")");
		    if (blocked < threshold) {
			goodSquare = false;
			for (int i = 0; i < 4; i ++) {
			    int nx = curX, ny = curY;
			    switch (i) {
			    case 0:
				nx --; break;
			    case 1:
				nx ++; break;
			    case 2:
				ny --; break;
			    case 3:
				ny ++; break;
			    }
			    if (inBounds (nx, ny) && sqr (nx, ny) == BLOCKED)
				goodSquare = true;
			}
		    }
		} while (!goodSquare && generating);

		//8. pick a new lastSide
		sq = sqr (curX, curY);
		for (nextSide = 0; (sq & nextSide) != 0 && nextSide < BLOCKED;
		     nextSide <<= 1);
	    }

	    //* 11.  If there are any BLOCKED squares remaining in the maze grid then goto
	    //*      step 3, otherwise you're done.
	} while (blocked > 0 && generating);
	generating = false;
	showMaze (true);
    }

    public void stopGenerating ()
    {
	generating = false;
    }

    ////////////////////////////////////////
    //       PATH / TRAVERSAL METHODS
    ////////////////////////////////////////

    public boolean traverse (int fromX, int fromY, int toX,
			     int toY, boolean displaySearch)
    {
	return traverse (fromX, fromY, toX, toY, displaySearch, 1000);
    }

    //algorithm for traversal from square s1 to s2 over distance d
    //1. if s1 = s2, end in success
    //2. if d = 0, end in failure
    //3. push this location onto the stack / make s1 display
    //4. check each possible direction where maze can go and no path there
    //5. if one of the directions returns success, end
    //6. if none of the directions returns success:
    //7. remove last location from the stack / undisplay s1
    //8. remove previous location from stack / undisplay last

    public boolean traverse (int fromX, int fromY, int toX,
		      int toY, boolean displaySearch, int distance)
    {
	if (fromX == toX && fromY == toY) {
	    activatePath (toX, toY);
	    lastX = toX; lastY = toY;
	    return true;
	}
	if (distance == 0) {
	    return false;
	}
	
	int x = fromX, y = fromY;
	pathStack.push (new MazeSquare (fromX, fromY));
	activatePath (x, y);
	boolean left = inBounds (x-1, y) && (maze [x] [y] & LEFT) == 0
	    && path [x-1] [y] == 0,
	    right = inBounds (x+1, y) && (maze [x] [y] & RIGHT) == 0
	    && path [x+1] [y] == 0,
	    top = inBounds (x, y-1) && (maze [x] [y] & TOP) == 0
	    && path [x] [y-1] == 0,
	    bottom = inBounds (x, y+1) && (maze [x] [y] & BOTTOM) == 0
	    && path [x] [y+1] == 0;

	if ((left && traverse (x-1, y, toX, toY, displaySearch, distance-1))
	    || (right && traverse (x+1, y, toX, toY, displaySearch, distance-1))
	    || (top && traverse (x, y-1, toX, toY, displaySearch, distance-1))
	    || (bottom && traverse (x, y+1, toX, toY, displaySearch, distance-1))
	    ) {
	    return true;
	}
	MazeSquare m = pathStack.pop ();
	deactivatePath (fromX, fromY);
	//System.out.println ("I hereby deactivate "+fromX+", "+fromY);

	//try backing up one square
	MazeSquare m2 = pathStack.pop ();
	if (m2 != null) {
	    deactivatePath (m.x, m.y);
	    dirtySquare (m.x, m.y);
	    if (traverse (m2.x, m2.y, toX, toY, displaySearch,
			  distance-1)) {
		dirtySquare (m.x, m.y);
		//System.out.println ("TRUE");
		return true;
	    } else {
		pathStack.push (m2);
		//System.out.println ("FALSE");
		//System.out.println ("lastY is now "+lastY);
		activatePath (m2.x, m2.y);
	    }
	}

	return false;
    }

    public boolean traverse (int destX, int destY)
    {
	if (path == null)
	    path = new byte [mazeWidth] [mazeHeight];
	int i = (destX-leftOffset) / squareWidth,
	    j = (destY-topOffset) / squareHeight;
	
	activatePath (i, j);
	repaint ();
	
	return true;
    }

    public synchronized boolean activatePath (int x, int y) {
	//System.out.println ("ADD: "+x+", "+y);
	boolean left = inBounds (x-1, y)
	    && (maze [x] [y] & LEFT) == 0,
	    right = inBounds (x+1, y)
	    && (maze [x] [y] & RIGHT) == 0,
	    top = inBounds (x, y-1)
	    && (maze [x] [y] & TOP) == 0,
	    bottom = inBounds (x, y+1)
	    && (maze [x] [y] & BOTTOM) == 0;

	if (left || right || top || bottom || x == startX && y == startY) {
	    path [x] [y] = PATHON;
	    dirtySquare (x, y);

	    if (left && path [x-1] [y] != 0) {
		path [x] [y] |= LEFT;
		path [x-1] [y] |= RIGHT;
		dirtySquare (x-1, y);
	    }
	    if (right && path [x+1] [y] != 0) {
		path [x] [y] |= RIGHT;
		path [x+1] [y] |= LEFT;
		dirtySquare (x+1, y);
	    }
	    if (top && path [x] [y-1] != 0) {
		path [x] [y] |= TOP;
		path [x] [y-1] |= BOTTOM;
		dirtySquare (x, y-1);
	    }
	    if (bottom && path [x] [y+1] != 0) {
		path [x] [y] |= BOTTOM;
		path [x] [y+1] |= TOP;
		dirtySquare (x, y+1);
	    }
	    return true;
	}
	return false;
    }

    public synchronized boolean deactivatePath (int x, int y) {
	path [x] [y] = 0;
	dirtySquare (x, y);
	if (inBounds (x-1, y)) {
	    path [x-1] [y] &= (byte) ~RIGHT;
	    dirtySquare (x-1, y);
	}
	if (inBounds (x+1, y)) {
	    path [x+1] [y] &= (byte) ~LEFT;
	    dirtySquare (x+1, y);
	}
	if (inBounds (x, y-1)) {
	    path [x] [y-1] &= (byte) ~BOTTOM;
	    dirtySquare (x, y-1);
	}
	if (inBounds (x, y+1)) {
	    path [x] [y+1] &= (byte) ~TOP;
	    dirtySquare (x, y+1);
	}
	return true;
    }

    public void pathToSquare (int destX, int destY)
    {
	if (path == null) {
	    path = new byte [mazeWidth] [mazeHeight];
	    lastX = startX; lastY = startY;
	    pathStack = new PathStack ();
	}
	int i = (destX-leftOffset) / squareWidth,
	    j = (destY-topOffset) / squareHeight;
	if (traverse (lastX, lastY, i, j, false, 3)) {
	    lastX = i;
	    lastY = j;
	    repaint ();
	}
    }

    public void flipSquare (int x, int y)
    {
	if (path [x] [y] == 0) {
	    activatePath (x, y);
	} else {
	    deactivatePath (x, y);
	}
	dirtySquare (x, y);
	repaint ();
    }

    public boolean won ()
    {
	return (path != null && path [finishX] [finishY] != 0);
    }

    ////////////////////////////////////////
    //    DRAWING METHODS
    ////////////////////////////////////////

    public void drawSquare (int x, int y)
    {
	byte sq = maze [x] [y];
	int xoff = x*squareWidth+leftOffset,
	    yoff = y*squareHeight+topOffset;

	if (sqr (x, y) == BLOCKED) {
	    offscr.setColor (Color.black);
	    offscr.fillRect (xoff, yoff, sqLineWidth, sqLineHeight);
	} else {
	    int halfWidth = lineWidth/2;
	    offscr.setColor (Color.white);
	    offscr.fillRect (xoff, yoff, sqLineWidth, sqLineHeight);
	    offscr.setColor (Color.black);
	    if ((sq & LEFT) != 0) {
		offscr.fillRect (xoff, yoff,
				 lineWidth, sqLineHeight);
	    }
	    if ((sq & RIGHT) != 0) {
		offscr.fillRect (xoff+squareWidth, yoff,
				 lineWidth, sqLineHeight);
	    }
	    if ((sq & TOP) != 0) {
		offscr.fillRect (xoff, yoff,
				 sqLineWidth, lineHeight);
	    }
	    if ((sq & BOTTOM) != 0) {
		offscr.fillRect (xoff, yoff+squareHeight,
				 sqLineWidth, lineHeight);
	    }
	    offscr.fillRect (xoff, yoff, lineWidth, lineHeight);
	    offscr.fillRect (xoff+squareWidth, yoff, lineWidth, lineHeight);
	    offscr.fillRect (xoff, yoff+squareHeight, lineWidth, lineHeight);
	    offscr.fillRect (xoff+squareWidth, yoff+squareHeight, lineWidth, lineHeight);
	}
    }

    public void drawFace (int x, int y)
    {
	int sq = maze [x] [y];
	int xoff = x*squareWidth+leftOffset,
	    yoff = y*squareHeight+topOffset;
	offscr.setColor (Color.yellow);
	offscr.fillArc (xoff+1, yoff+1, squareWidth-2, squareHeight-2, 0, 360);
	offscr.setColor (Color.black);
	offscr.drawArc (xoff+squareWidth/4, yoff+squareHeight/4,
			(squareWidth)/2, (squareHeight)/2, 180, 180);
	offscr.drawLine (xoff+squareWidth/3, yoff+squareHeight/3,
			 xoff+squareWidth/3, yoff+squareHeight/3);
	offscr.drawLine (xoff+squareWidth*2/3, yoff+squareHeight/3,
			 xoff+squareWidth*2/3, yoff+squareHeight/3);
    }

    protected void drawPathSquare (int px, int py, Color color)
    {
	int psq;
	if (path == null || (psq = path[px][py]) == 0)
	    return;
	int xoff = leftOffset + (px * squareWidth);
	int yoff = topOffset + (py * squareHeight);
	boolean top = false, bottom = false, left = false, right = false;
	offscr.setColor(color);
	if ((psq & TOP) != 0) {
	    top = true;
	    offscr.fillRect(xoff + pxoff, yoff, pathWidth, pyoff + pathHeight);
	}
	if ((psq & BOTTOM) != 0) {
	    offscr.fillRect(xoff + pxoff, yoff + pyoff, pathWidth, pyoff + pathHeight);
	    bottom = true;
	}
	if ((psq & LEFT) != 0) {
	    offscr.fillRect(xoff, yoff + pyoff, pxoff + pathWidth, pathHeight);
	    left = true;
	}
	if ((psq & RIGHT) != 0) {
	    offscr.fillRect(xoff + pxoff, yoff + pyoff, pxoff + pathWidth, pathHeight);
	    right = true;
	}
	if (!top && !left && !right && !bottom)
	    offscr.fillRect(xoff + pxoff, yoff + pyoff, pathWidth, pathHeight);
    }
}