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

/**
 * <p>Program allowing player to navigate a four dimensional labyrinth.  This
 * program draws a board sized to what is specified in its parameters or in the
 * default values if parameters are not given; it may therefore be larger or
 * smaller than the applet window that it is put in.</p>
 *
 * <p>This program is a Java re-implementation of a maze originally written by
 * Jonathan Hayward in eighth grade, in Apple ][ BASIC, and re-implemented in C
 * during undergraduate studies.  It retains a classic style of graphics and
 * the original algorithms and basic data structures, but adds a recursive
 * solvability verifier, configurability in invocation that was impossible
 * under previous implementations, and a point-and-click interface.  The
 * applet may be seen at
 * <a href="http://JonathansCorner.com/etc/maze/"> http://JonathansCorner.com/etc/maze/</a>;
 * it was slashdotted within a week of going online.</p>
 *
 * <p>This is presented as a code sample for:<p>
 *
 * <p style="margin-left: 1.5cm">Jonathan Hayward<br>
 * <a href="mailto:jonathan.hayward@pobox.com"> jonathan.hayward@pobox.com</a></p>
 *
 * <p>Dimensions are as follows:</p>
 * <pre>
 * Within squares:
 *
 *  ^
 * Y|
 *  +-&gt;
 *   X
 *
 * Between squares:
 *
 *  ^
 * Z|
 *  +-&gt;
 *   W
 * </pre>
 *
 * <p>This is disanalogous, but gives the most obvious place to the fourth
 * (spatial) dimension after the first three dimensions have been assigned
 * their usual letters.  Therefore, I am keeping it that way.</p>
 *
 * <p>Thanks to my father, John Hayward, for help with an AWT bug, James
 * Holt for a bugfix and additional code to address bug which manifested in
 * larger mazes, and Darren Edmonds for pointers on how to update the
 * MouseEvent handling.</p>
 *
 * @author Jonathan Hayward
 */

public class HarderMaze4D extends Applet implements MouseListener, Runnable
    {
    public static final long serialVersionUID = 0;
    private static final boolean PASSABLE = true,
      IMPASSABLE = false;
    private boolean noDrawMaze = false;
    private boolean[][][][] maze = null;
    private static final int X = 0,
      Y = 1,
      Z = 2,
      W = 3,
      DEFAULT_SIZE = 4,
      DIMENSION = 4,
      FAILED_MOVE_OFF_MAZE = 5,
      FAILED_MOVE_IMPASSABLE = 6; // Next code 7
    private static int[][] d = {{1,0,0,0},{-1,0,0,0},{0,1,0,0},{0,-1,0,0},{0,0,1,0},{0,0,-1,0},{0,0,0,1},{0,0,0,-1}};
    private int borderWidth = 40,
      borderHeight = 40,
      slotWidth = 20,
      slotHeight = 20;
    private int[] size = new int[4],
      playerPosition = new int[4],
      endLocationPosition = new int[4];
    private double probabilityPassable = 0.5;
    private Color backgroundColor = Color.black,
      impassableColor = Color.red,
      passableColor = Color.white,
      playerColor = Color.blue,
      endLocationColor = Color.green;
    private Graphics givenGraphics = null,
      offScreenGraphics = null;
    private Image offScreenImage = null;

    /**
     * <p>Attempt to move the player by a given vector relative to his present
     * position.  Will succeed if the move is to a legal board space and the
     * space is passable.</p>
     */

    private void attemptToMove(int xDiff, int yDiff, int zDiff, int wDiff)
        {
        if ((0 <= playerPosition[X] + xDiff) &&
          (playerPosition[X] + xDiff < size[X]) &&
          (0 <= playerPosition[Y] + yDiff) &&
          (playerPosition[Y] + yDiff < size[Y]) &&
          (0 <= playerPosition[Z] + zDiff) &&
          (playerPosition[Z] + zDiff < size[Z]) &&
          (0 <= playerPosition[W] + wDiff) &&
          (playerPosition[W] + wDiff < size[W]))
            {
            if (maze[playerPosition[X] + xDiff]
              [playerPosition[Y] + yDiff]
              [playerPosition[Z] + zDiff]
              [playerPosition[W] + wDiff] == PASSABLE)
                {
                playerPosition[X] += xDiff;
                playerPosition[Y] += yDiff;
                playerPosition[Z] += zDiff;
                playerPosition[W] += wDiff;
                drawBoard();
                }
            else
                {
                failedMove(FAILED_MOVE_IMPASSABLE);
                }
            }
        else
            {
            failedMove(FAILED_MOVE_OFF_MAZE);
            }
        }

    /**
     * <p>Calculate the height of the board, in pixels.</p>
     */

    private int boardHeight()
        {
        return 2 * borderHeight + (size[Y] + 1) * size[Z] * slotHeight;
        }

    /**
     * <p>Calculate the width of the board, in pixels.</p>
     */

    private int boardWidth()
        {
        return 2 * borderWidth + ((size[X] + 1) * size[W]) * slotWidth;
        }

    /**
     * <p>Calculate the screen x coordinate of the lower lefthand corner of a
     * square * representing a slot in the maze.  CornerX and cornerY both take
     * more information than they need, in an information hiding fashion to
     * indicate "This is how I get the graphical x coordinate for a
     * hyperspace point", and not "Which two arguments go into the
     * formula?"</p>
     */

    private int cornerX(int x, int y, int z, int w)
        {
        return borderWidth + (x + w * (size[X] + 1)) * slotWidth;
        }

    /**
     * <p>Calculate the y coordinate of the lower lefthand corner of a square
     * representing a slot in the maze.  CornerX and cornerY both take more
     * information than they need, in an information hiding fashion to indicate
     * "This is how I get the graphical y coordinate for a hyperspace point",
     * and not "Which two arguments go into the formula?"</p>
     */

    private int cornerY(int x, int y, int z, int w)
        {
        return boardHeight() - (borderHeight + (y + z * (size[Y] + 1) + 2) *
          slotHeight);
        }

    /**
     * <p>Draw the board on the screen.</p>
     */

    public void drawBoard()
        {
        if (!noDrawMaze)
            {
            offScreenGraphics.setColor(backgroundColor);
            offScreenGraphics.fillRect(0, 0, boardWidth() + 1, boardHeight() +
              1);
            for(int i = 0; i < size[X]; ++i)
                for(int j = 0; j < size[Y]; ++j)
                    for(int k = 0; k < size[Z]; ++k)
                        for(int l = 0; l < size[W]; ++l)
                            {
                            if (maze[i][j][k][l] == PASSABLE)
                                offScreenGraphics.setColor(passableColor);
                            else
                                offScreenGraphics.setColor(impassableColor);
                            offScreenGraphics.fillRect(cornerX(i, j, k, l),
                              cornerY(i, j, k, l), slotWidth, slotHeight);
                            }
            offScreenGraphics.setColor(playerColor);
            int playerX = cornerX(playerPosition[X], playerPosition[Y],
              playerPosition[Z], playerPosition[W]);
            int playerY = cornerY(playerPosition[X], playerPosition[Y],
              playerPosition[Z], playerPosition[W]);
            offScreenGraphics.fillRect(playerX, playerY, slotWidth,
              slotHeight);
            offScreenGraphics.setColor(endLocationColor);
            int endLocationX = cornerX(endLocationPosition[X], endLocationPosition[Y],
              endLocationPosition[Z], endLocationPosition[W]);
            int endLocationY = cornerY(endLocationPosition[X], endLocationPosition[Y],
              endLocationPosition[Z], endLocationPosition[W]);
            offScreenGraphics.fillRect(endLocationX, endLocationY, slotWidth,
              slotHeight);
            givenGraphics = this.getGraphics();
            if (givenGraphics != null)
                givenGraphics.drawImage(offScreenImage, 0, 0, this);
            validate();
            }
        }

    /**
     * <p>Method invoked when the player attempts an illegal move.  This hook
     * is presently unimplemented.</p>
     */

    private void failedMove(int failureCode)
        {
        // At present, do nothing.  If desired, an error message can be
        // displayed to the user.
        }

    /**
     * <p>Generate a solveable maze.  The original eighth-grade program did
     * not check to see if the generated maze was solveable.</p>
     */

    private void generateMaze()
        {
        maze = new boolean[size[X]][size[Y]][size[Z]][size[W]];
        for(int i = 0; i < size[X]; ++i)
            for(int j = 0; j < size[Y]; ++j)
                    for(int k = 0; k < size[Z]; ++k)
                    for(int l = 0; l < size[W]; ++l)
                        if (Math.random() < probabilityPassable)
                            maze[i][j][k][l] = PASSABLE;
                        else
                            maze[i][j][k][l] = IMPASSABLE;
        maze[0][0][0][0] = PASSABLE;
        maze[size[X] - 1][size[Y] - 1][size[Z] - 1][size[W] - 1] = PASSABLE;
        if (!mazeIsSolveable())
            generateMaze();
        }

    /**
     * <p>Generate a maze by repeated restricted depth-first searches.</p>
     */

    private void generateTighterMaze()
    {
        maze = new boolean[size[X]][size[Y]][size[Z]][size[W]];
        maze[0][0][0][0] = PASSABLE;
        ArrayList leaves = new ArrayList();
        int[] position = {0,0,0,0};
        leaves.add(position);
        while(!leaves.isEmpty()) {
            int index = (int)(Math.random()*leaves.size());
            position = (int[])(leaves.get(index));
            leaves.remove(index);
            depthFirst(maze,position,leaves);
        }
        endLocationPosition = findLeastAccessiblePoint(maze);
    }

    /**
     * <p>Find a location as far from the original as possible.</p>
     */

    private int[] findLeastAccessiblePoint(boolean[][][][] maze)
    {
        int[][][][] dist = new int[size[X]][size[Y]][size[Z]][size[W]];
        for (int i = 0; i < size[X]; i++)
            for (int j = 0; j < size[Y]; j++)
                for (int k = 0; k < size[Z]; k++)
                    for (int m = 0; m < size[W]; m++)
                        dist[i][j][k][m] = 9999999;
        dist[0][0][0][0] = 0;
        LinkedList locations = new LinkedList();
        int[] current = {0,0,0,0};
        locations.add(current);
        while(!locations.isEmpty()) {
            current = (int[])(locations.removeFirst());
            int thisDistance = dist[current[0]][current[1]][current[2]][current[3]];
            for (int i = 0; i < 8; i++) {
                if (!inMaze(current,d[i])) continue;
                if (maze[current[0]+d[i][0]][current[1]+d[i][1]][current[2]+d[i][2]][current[3]+d[i][3]]==IMPASSABLE) continue;
                int thatDistance = dist[current[0]+d[i][0]][current[1]+d[i][1]][current[2]+d[i][2]][current[3]+d[i][3]];
                if (thatDistance>thisDistance+1) {
                    dist[current[0]+d[i][0]][current[1]+d[i][1]][current[2]+d[i][2]][current[3]+d[i][3]]=thisDistance+1;
                    int[] next = {current[0]+d[i][0],current[1]+d[i][1],current[2]+d[i][2],current[3]+d[i][3]};
                    locations.add(next);
                }
            }
        }
        return current;
    }

    /**
     * <p>From a given position, find a new path to be added to the maze,
     * no parts of which are adjacent to previous paths.</p>
     */

    private void depthFirst(boolean[][][][] maze, int[] position, ArrayList leaves)
    {
        ArrayList possibleMoves = findPossibleMoves(maze,position);
        if (possibleMoves.size()==0) return;
        if (possibleMoves.size()>1) {
            leaves.add(position);
        }
        int index = (int)(Math.random()*possibleMoves.size());
        int[] toMove = (int[])(possibleMoves.get(index));
        maze[toMove[0]][toMove[1]][toMove[2]][toMove[3]] = PASSABLE;
        depthFirst(maze,toMove,leaves);
    }

    /**
     * <p>Determine whether position+d is in the maze.</p>
     */

    private boolean inMaze(int[] position, int[] d) {
        boolean inMaze = true;
        for (int j = 0; j < 4; j++) {
            if (position[j]+d[j]<0 || position[j]+d[j]>=size[j]) inMaze = false;
        }
        return inMaze;
    }

    /**
     * <p>Determine whether position+d+dd is in the maze.</p>
     */

    private boolean inMaze(int[] position, int[] d, int[] dd) {
        boolean inMaze = true;
        for (int j = 0; j < 4; j++) {
            if (position[j]+d[j]+dd[j]<0 || position[j]+d[j]+dd[j]>=size[j]) inMaze = false;
        }
        return inMaze;
    }

    /**
     * <p>Determine which directions are feasible: in the maze, not blocked, and
     * not 'too adjacent'.
     */

    private ArrayList findPossibleMoves(boolean[][][][] maze, int[] position) {
        ArrayList moves = new ArrayList();
        for (int i = 0; i < 8; i++) {
            if (!inMaze(position,d[i])) continue;
            if (maze[position[0]+d[i][0]][position[1]+d[i][1]][position[2]+d[i][2]][position[3]+d[i][3]]==PASSABLE) continue;
            int surroundingPassable = 0;
            for (int k = 0; k < 8; k++) {
                if (!inMaze(position,d[i],d[k])) continue;
                if (maze[position[0]+d[i][0]+d[k][0]][position[1]+d[i][1]+d[k][1]][position[2]+d[i][2]+d[k][2]][position[3]+d[i][3]+d[k][3]]==PASSABLE) surroundingPassable++;
            }
            if (surroundingPassable<2) {
                int[] move = { position[0]+d[i][0], position[1]+d[i][1], position[2]+d[i][2], position[3]+d[i][3] };
                moves.add(move);
            }
        }
        return moves;
    }

    /**
     * <p>Initializations performed when the applet is created.</p>
     */

    public void init()
        {
        size[X] = readInt("X", DEFAULT_SIZE);
        size[Y] = readInt("Y", DEFAULT_SIZE);
        size[Z] = readInt("Z", DEFAULT_SIZE);
        size[W] = readInt("W", DEFAULT_SIZE);
        playerPosition[X] = playerPosition[Y] = playerPosition[Z] =
          playerPosition[W] = 0;
        endLocationPosition[X] = size[X]-1;
        endLocationPosition[Y] = size[Y]-1;
        endLocationPosition[Z] = size[Z]-1;
        endLocationPosition[W] = size[W]-1;
        probabilityPassable = readDouble("Probability", probabilityPassable);
        generateTighterMaze();
        borderHeight = readInt("BorderHeight", borderHeight);
        borderWidth = readInt("BorderWidth", borderWidth);
        slotHeight = readInt("SlotHeight", slotHeight);
        slotWidth = readInt("SlotWidth", slotWidth);
        offScreenImage = createImage(boardWidth(), boardHeight());
        offScreenGraphics = offScreenImage.getGraphics();
        // enableEvents(AWTEvent.MOUSE_EVENT_MASK);
        addMouseListener(this);
        }

    /**
     * <p>Recursive helper function to mark all slots reachable from a given
     * slot. Used in seeing if the maze is navigable.</p>
     */
    private void markReached(boolean[][][][] reached, int x, int y, int z,
      int w)
        {
        reached[x][y][z][w] = true;
        if (x - 1 >= 0)
            if (maze[x - 1][y][z][w] == PASSABLE && !reached[x - 1][y][z][w])
                markReached(reached, x - 1, y, z, w);
        if (x + 1 < size[X])
            if (maze[x + 1][y][z][w] == PASSABLE && !reached[x + 1][y][z][w])
                markReached(reached, x + 1, y, z, w);
        if (y - 1 >= 0)
            if (maze[x][y - 1][z][w] == PASSABLE && !reached[x][y - 1][z][w])
                markReached(reached, x, y - 1, z, w);
        if (y + 1 < size[Y])
            if (maze[x][y + 1][z][w] == PASSABLE && !reached[x][y + 1][z][w])
                markReached(reached, x, y + 1, z, w);
        if (z - 1 >= 0)
            if (maze[x][y][z - 1][w] == PASSABLE && !reached[x][y][z - 1][w])
                markReached(reached, x, y, z - 1, w);
        if (z + 1 < size[Z])
            if (maze[x][y][z + 1][w] == PASSABLE && !reached[x][y][z + 1][w])
                markReached(reached, x, y, z + 1, w);
        if (w - 1 >= 0)
            if (maze[x][y][z][w - 1] == PASSABLE && !reached[x][y][z][w - 1])
                markReached(reached, x, y, z, w - 1);
        if (w + 1 < size[W])
            if (maze[x][y][z][w + 1] == PASSABLE && !reached[x][y][z][w + 1])
                markReached(reached, x, y, z, w + 1);
        }

    /**
     * <p>Method to determine if a given maze is solveable.</p>
     */

    private boolean mazeIsSolveable()
        {
        boolean[][][][] reached = new
          boolean[size[X]][size[Y]][size[Z]][size[W]];
        for(int i = 0; i < size[X]; ++i)
            for(int j = 0; j < size[Y]; ++j)
                for(int k = 0; k < size[Z]; ++k)
                    for(int l = 0; l < size[W]; ++l)
                        reached[i][j][k][l] = false;
        markReached(reached, 0, 0, 0, 0);
        return reached[size[X] - 1][size[Y] - 1][size[Z] - 1][size[W] - 1];
        }

    /**
     * <p>Process a mouse click to see if it is corresponds to a legal move,
     * and, if so, make that move.  A legal move is one that takes to a space
     * adjacent to his present space in hyperspace (not necessarily on the
     * board).</p>
     */

    public void mouseClicked(MouseEvent theEvent)
        {

        if (theEvent.getY() < borderHeight ||
          theEvent.getY() > boardHeight() - borderHeight ||
          theEvent.getX() < borderWidth ||
          theEvent.getX() > boardWidth() - borderWidth)
            {
            return;
            }

        int x = ( ( theEvent.getX() - borderWidth ) / slotWidth ) % (size[X] +
            1),
          w = ( ( theEvent.getX() - borderWidth ) / slotWidth ) / (size[X] +
            1),
          y = ( ( ( boardHeight() - borderHeight - theEvent.getY() ) /
            slotHeight ) % (size[Y] + 1) ) - 1,
          z = ( ( boardHeight() - borderHeight - theEvent.getY() ) / slotHeight
            ) / (size[Y] + 1);

        if ((0 <= x && x < size[X]) &&
          (0 <= y && y < size[Y]) &&
          (0 <= z && z < size[Z]) &&
          (0 <= w && w < size[W]))
            {
            int xDiff = x - playerPosition[X],
              yDiff = y - playerPosition[Y],
              zDiff = z - playerPosition[Z],
              wDiff = w - playerPosition[W];
            // Only move to adjacent spaces.
            if (Math.abs(xDiff) + Math.abs(yDiff) + Math.abs(zDiff) +
              Math.abs(wDiff) < 2)
                {
                attemptToMove(xDiff, yDiff, zDiff, wDiff);
                }
            }
        testWin();
        }

    /**
     * <p>Respond appropriately to the mouse cursor entering the component. At
     * present, this does nothing.</p>
     */

    public void mouseEntered(MouseEvent theEvent)
        {
        }

    /**
     * <p>Respond appropriately to the mouse cursor exiting the component. At
     * present, this does nothing.</p>
     */

    public void mouseExited(MouseEvent theEvent)
        {
        }

    /**
     * <p>Respond appropriately to the mouse button being pressed. At
     * present, this does nothing.</p>
     */

    public void mousePressed(MouseEvent theEvent)
        {
        }

    /**
     * <p>Respond appropriately to the mouse button being released. At
     * present, this does nothing.</p>
     */

    public void mouseReleased(MouseEvent theEvent)
        {
        }

    /**
     * <p>This method is called when the display is to be painted.</p>
     */

    public void paint(Graphics g)
        {
        drawBoard();
        }

    /**
     * <p>Read a string for a given double value, returning specified default
     * if there is a parse error.</p>
     */

    private double readDouble(String toReadFrom, double defaultValue)
        {
        try
            {
            return new Double(getParameter(toReadFrom)).doubleValue();
            }
        catch(Exception e)
            {
            return defaultValue;
            }
        }

    /**
     * <p>Read a string for a given integer value, returning specified default
     * if there is a parse error.</p>
     */

    private int readInt(String toReadFrom, int defaultValue)
        {
        try
            {
            return new Integer(getParameter(toReadFrom)).intValue();
            }
        catch(Exception e)
            {
            return defaultValue;
            }
        }

    /**
     * <p>Display a success message for two seconds before generating a new
     * maze.  This is done in a separate thread because if it is done in the
     * mouse event handler, the screen is not updated until the end of the two
     * seconds, where it flashes, subliminal message style.</p>
     */

     public void run()
        {
        noDrawMaze = true;
        offScreenGraphics.setColor(Color.white);
        offScreenGraphics.fillRect(borderWidth, borderHeight, boardWidth()
          - 2 * borderWidth - slotWidth, boardHeight() - 2 * borderHeight -
          slotHeight);
        offScreenGraphics.setColor(Color.black);
        offScreenGraphics.drawString(
          "Congratulations, you've solved the maze!", borderWidth * 2,
          borderHeight * 2);
        givenGraphics = this.getGraphics();
        givenGraphics.drawImage(offScreenImage, 0, 0, this);
            validate();
        try
            {
            Thread.sleep(2000);
            }
        catch(InterruptedException e)
            {
            }
        noDrawMaze = false;
        drawBoard();
        }

    /**
     * <p>Test to see if the player has won, and, if so, congratulate the
     * player and create a new maze.</p>
     */

    private void testWin()
        {
        if (playerPosition[X] == endLocationPosition[X] &&
          playerPosition[Y] == endLocationPosition[Y] &&
          playerPosition[Z] == endLocationPosition[Z] &&
          playerPosition[W] == endLocationPosition[W])
            {
            playerPosition[X] = playerPosition[Y] = playerPosition[Z] =
            playerPosition[W] = 0;
            /*
            generateMaze();
            */
            generateTighterMaze();
            Thread displayWinMessage = new Thread(this);
            displayWinMessage.start();
            }
        }

    /**
     * <p>This applet method is called to update the contents of the
     * screen.</p>
     */

    public void update(Graphics g)
        {
        drawBoard();
        }

    }