import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Stack;

class Maze extends Game {
  private static final int MIN_DIMENSION = 5;
  private static final int MAX_DIMENSION = 101;

  public int cols;
  public int rows;
  public int moves;
  public int highscore;
  public char[][] map;
  public boolean[][] visited;
  public boolean generated;
  public int px; // Player x-coordinate
  public int py; // Player y-coordinate
  public int fx; // Finish x-coordinate
  public int fy; // Finish y-coordinate
  public int gx; // Generator x-coordinate
  public int gy; // Generator y-coordinate
  public final char[] icons = {' ', '|', '-', '+', '0', 'X', '#'};

  private final Random random = new Random();

  public Maze() {
    name = "Maze";
    description =
        "Find your way through a maze generated with randomized recursive backtracking.";
  }

  @Override
  public void init() {
    cols = readDimension("width");
    rows = readDimension("height");
    gameover = false;
    moves = 0;

    px = randomCellCoordinate(cols);
    py = randomCellCoordinate(rows);
    do {
      fx = randomCellCoordinate(cols);
      fy = randomCellCoordinate(rows);
    } while (fx == px && fy == py);

    gx = randomCellCoordinate(cols);
    gy = randomCellCoordinate(rows);
    map = new char[cols][rows];
    visited = new boolean[cols][rows];

    setUpGrid();
    generateMaze();

    map[px][py] = icons[4];
    map[fx][fy] = icons[5];
  }

  private int readDimension(String label) {
    while (true) {
      System.out.printf(
          "Enter the maze %s (an odd number from %d to %d): ",
          label,
          MIN_DIMENSION,
          MAX_DIMENSION);
      String response = INPUT.nextLine().trim();

      try {
        int dimension = Integer.parseInt(response);
        if (dimension >= MIN_DIMENSION
            && dimension <= MAX_DIMENSION
            && dimension % 2 == 1) {
          return dimension;
        }
      } catch (NumberFormatException exception) {
        // The message below covers non-numeric input as well as invalid numbers.
      }

      System.out.println("Please enter an odd whole number in the stated range.");
    }
  }

  private int randomCellCoordinate(int dimension) {
    int cellCount = (dimension - 1) / 2;
    return 1 + 2 * random.nextInt(cellCount);
  }

  private void setUpGrid() {
    for (int x = 1; x < cols - 1; x++) {
      for (int y = 1; y < rows - 1; y++) {
        map[x][y] = icons[0];
      }
    }

    for (int x = 0; x < cols; x += 2) {
      for (int y = 0; y < rows; y++) {
        map[x][y] = icons[1];
      }
    }

    for (int y = 0; y < rows; y += 2) {
      for (int x = 0; x < cols; x++) {
        map[x][y] = icons[2];
      }
    }

    for (int x = 0; x < cols; x += 2) {
      for (int y = 0; y < rows; y += 2) {
        map[x][y] = icons[3];
      }
    }
  }

  private void generateMaze() {
    Stack<Integer> xHistory = new Stack<>();
    Stack<Integer> yHistory = new Stack<>();
    xHistory.push(gx);
    yHistory.push(gy);
    visited[gx][gy] = true;
    generated = false;

    while (!xHistory.empty()) {
      gx = xHistory.peek();
      gy = yHistory.peek();
      char direction = getDirection(gx, gy);

      if (direction == 'X') {
        xHistory.pop();
        yHistory.pop();
        continue;
      }

      int nextX = gx;
      int nextY = gy;
      if (direction == 'N') {
        nextY -= 2;
      } else if (direction == 'E') {
        nextX += 2;
      } else if (direction == 'S') {
        nextY += 2;
      } else {
        nextX -= 2;
      }

      map[(gx + nextX) / 2][(gy + nextY) / 2] = icons[0];
      gx = nextX;
      gy = nextY;
      visited[gx][gy] = true;
      xHistory.push(gx);
      yHistory.push(gy);
    }

    generated = true;
  }

  public Character getDirection(int currentX, int currentY) {
    List<Character> directions = new ArrayList<>();

    if (currentY > 1 && !visited[currentX][currentY - 2]) {
      directions.add('N');
    }
    if (currentX < cols - 2 && !visited[currentX + 2][currentY]) {
      directions.add('E');
    }
    if (currentY < rows - 2 && !visited[currentX][currentY + 2]) {
      directions.add('S');
    }
    if (currentX > 1 && !visited[currentX - 2][currentY]) {
      directions.add('W');
    }

    if (directions.isEmpty()) {
      return 'X';
    }
    return directions.get(random.nextInt(directions.size()));
  }

  // Retain the original method name for code that used the first version.
  public Character GetDirection(int currentX, int currentY) {
    return getDirection(currentX, currentY);
  }

  @Override
  public void render() {
    System.out.println("\nUse W, A, S, and D to move 0 to X.");
    System.out.printf("Moves: %d", moves);
    if (highscore > 0) {
      System.out.printf(" | Best: %d", highscore);
    }
    System.out.println("\n");

    for (int y = 0; y < rows; y++) {
      for (int x = 0; x < cols; x++) {
        System.out.print(map[x][y]);
      }
      System.out.println();
    }
  }

  @Override
  public void input() {
    System.out.print("Move: ");
    String response = INPUT.nextLine().trim().toLowerCase();
    if (response.length() != 1 || "wasd".indexOf(response.charAt(0)) < 0) {
      System.out.println("Enter one movement key: W, A, S, or D.");
      return;
    }

    switch (response.charAt(0)) {
      case 'a':
        tryMove(-2, 0);
        break;
      case 'd':
        tryMove(2, 0);
        break;
      case 's':
        tryMove(0, 2);
        break;
      case 'w':
        tryMove(0, -2);
        break;
      default:
        break;
    }
  }

  private void tryMove(int deltaX, int deltaY) {
    int wallX = px + deltaX / 2;
    int wallY = py + deltaY / 2;
    if (map[wallX][wallY] != icons[0]) {
      System.out.println("A wall blocks that direction.");
      return;
    }

    map[px][py] = icons[0];
    px += deltaX;
    py += deltaY;
    map[px][py] = icons[4];
    moves++;
  }

  @Override
  public void update() {
    if (px == fx && py == fy) {
      gameover = true;
    }
  }

  @Override
  public void endgame() {
    boolean newHighscore = false;
    if (moves < highscore || highscore == 0) {
      highscore = moves;
      newHighscore = true;
    }

    render();
    if (newHighscore) {
      System.out.println("Well done! That's a new highscore of " + highscore + " moves!");
    } else {
      System.out.println("Congratulations, you completed the maze in " + moves + " moves!");
    }
  }
}