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;

/**
 * <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 Maze4D extends Applet implements MouseListener, Runnable
    {
    private static final boolean PASSABLE = true,
      IMPASSABLE = false;
    private boolean noDrawMaze = false;
    private boolean[][][][] maze = null;
    public static final long serialVersionUID = 0;
    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 int borderWidth = 40,
      borderHeight = 40,
      slotWidth = 20,
      slotHeight = 20;
    private int[] size = new int[4],
      playerPosition = 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);
                            if ((i == size[X] - 1) &&
                              (j == size[Y] - 1) &&
                              (k == size[Z] - 1) &&
                              (l == size[W] - 1))
                                offScreenGraphics.setColor(endLocationColor);
                            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);
            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>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;
        probabilityPassable = readDouble("Probability", probabilityPassable);
        generateMaze();
        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] == size[X] - 1 &&
          playerPosition[Y] == size[Y] - 1 &&
          playerPosition[Z] == size[Z] - 1 &&
          playerPosition[W] == size[W] - 1)
            {
            playerPosition[X] = playerPosition[Y] = playerPosition[Z] =
            playerPosition[W] = 0;
            generateMaze();
            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();
        }

    }