public class Maze {
  private ArrayList <ArrayList <MazeCell>> m_maze;
  private Point m_exit;

  /**
   * Crea un laberinto a partir de un algoritmo de generación de laberintos
   * ya inicializado.
   *
   * @param alg
   *          Algoritmo de creación de laberintos ya inicializado
   */
  public Maze (MazeCreationAlgorithm alg) {
    if (alg != null) {
      m_maze = alg.createMaze();
      m_exit = alg.getExit();
    }
    else
      throw new IllegalArgumentException(
          MainWindow.getTranslations().exception().invalidMazeCreationAlgorithm());
  }

  /**
   * Crea un laberinto a partir de su versión serializada en un fichero.
   *
   * @param fileName
   *          Nombre del fichero del que cargar el laberinto.
   * @throws IOException
   *           Cuando no se encuentra el fichero, no se puede abrir para su
   *           lectura o no contiene un laberinto válido.
   */
  public Maze (String fileName) throws IOException {
    loadFile(fileName);
  }

  /**
   * Obtiene la celda situada en una posición concreta del laberinto.
   *
   * @param row
   *          Fila.
   * @param column
   *          Columna.
   * @return Celda en la posición indicada.
   */
  public MazeCell get (int row, int column) {
    return m_maze.get(row).get(column);
  }

  /**
   * Establece el contenido de una celda en el laberinto.
   *
   * @param row
   *          Fila.
   * @param column
   *          Columna.
   * @param cell
   *          Celda que se quiere introducir.
   */
  public void set (int row, int column, MazeCell cell) {
    m_maze.get(row).set(column, cell);
  }

  /**
   * Obtiene el número de columnas (anchura) del laberinto.
   *
   * @return Anchura (en celdas) del laberinto.
   */
  public int getWidth () {
    return m_maze.get(0).size();
  }

  /**
   * Obtiene el número de filas (altura) del laberinto.
   *
   * @return Altura (en celdas) del laberinto.
   */
  public int getHeight () {
    return m_maze.size();
  }

  /**
   * Cambia la salida del laberinto a otro lugar, añadiendo y eliminando las
   * paredes necesarias.
   *
   * @param pos
   *          Índice de la celda en la que se quiere colocar la salida.
   *          Dependiendo de la dirección este valor se referirá a una columna
   *          (si la dirección es arriba o abajo) o a una fila (si la dirección
   *          es izquierda o derecha).
   * @param dir
   *          Borde del laberinto donde colocar la salida.
   */
  public void setExit (int pos, Direction dir) {
    // Comprobamos que los parámetros son válidos
    if (pos < 0 || dir == Direction.NONE)
      return;
    if (dir.isVertical() && pos >= getWidth())
      return;
    if (dir.isHorizontal() && pos >= getHeight())
      return;

    // Tapamos la salida anterior antes de modificar su posición
    if (m_exit.x < 0)
      m_maze.get(m_exit.y).get(0).setWall(Direction.LEFT);
    else if (m_exit.x >= getWidth())
      m_maze.get(m_exit.y).get(getWidth() - 1).setWall(Direction.RIGHT);
    else if (m_exit.y < 0)
      m_maze.get(0).get(m_exit.x).setWall(Direction.UP);
    else if (m_exit.y >= getHeight())
      m_maze.get(getHeight() - 1).get(m_exit.x).setWall(Direction.DOWN);

    // Modificamos la salida del laberinto y abrimos la pared
    switch (dir) {
      case UP:
        m_exit.move(pos, 0);
        break;
      case DOWN:
        m_exit.move(pos, getHeight() - 1);
        break;
      case LEFT:
        m_exit.move(0, pos);
        break;
      case RIGHT:
        m_exit.move(getWidth() - 1, pos);
        break;
      default:
        break;
    }

    m_maze.get(m_exit.y).get(m_exit.x).unsetWall(dir);
    m_exit.setLocation(dir.movePoint(m_exit));
  }

  /**
   * Obtiene una copia del lugar donde está la salida del laberinto.
   *
   * @return La posición donde se encuentra la salida al laberinto.
   */
  public Point getExit () {
    return new Point(m_exit);
  }

  /**
   * Determina si el punto se encuentra dentro del laberinto o no.
   *
   * @param p
   *          Punto a testear.
   * @return Si el punto está dentro del laberinto o no.
   */
  public boolean containsPoint (Point p) {
    return p.x >= 0 && p.y >= 0 && p.x < getWidth() && p.y < getHeight();
  }

  /**
   * Carga una instancia de laberinto de un fichero que contiene una instancia
   * de esta clase serializada.
   *
   * @param fileName
   *          Nombre del fichero del que cargar el laberinto.
   * @throws IOException
   *           Cuando no se encuentra el fichero, no se puede abrir para su
   *           lectura o no contiene un laberinto válido.
   */
  @SuppressWarnings ("unchecked")
  public void loadFile (String fileName) throws IOException {
    try {
      FileInputStream fileIn = new FileInputStream(fileName);
      ObjectInputStream in = new ObjectInputStream(fileIn);
      m_maze = (ArrayList <ArrayList <MazeCell>>) in.readObject();
      m_exit = (Point) in.readObject();
      in.close();
      fileIn.close();
    }
    catch (ClassNotFoundException c) {
      throw new IOException(c);
    }
  }

  /**
   * Guarda la actual instancia de la clase {@link Maze} en un fichero mediante
   * su serialización.
   *
   * @param fileName
   *          Nombre del fichero donde guardar el laberinto.
   * @throws IOException
   *           Cuando el fichero no se puede abrir o no se tienen permisos de
   *           escritura en el mismo.
   */
  public void saveFile (String fileName) throws IOException {
    FileOutputStream fileOut = new FileOutputStream(fileName);
    ObjectOutputStream out = new ObjectOutputStream(fileOut);
    out.writeObject(m_maze);
    out.writeObject(m_exit);
    out.close();
    fileOut.close();
  }

  /**
   * Calcula el número máximo de aristas que se pueden añadir en un laberinto
   * del tamaño dado. Cada arista se refiere a un pasillo abierto entre 2
   * celdas. Se puede ver como el número de paredes que tiene en su interior un
   * laberinto perfecto, sin contar el contorno.
   *
   * @param rows
   *          Número de filas.
   * @param columns
   *          Número de columnas.
   * @return Número de paredes en el interior del laberinto.
   */
  public static int perfectMazeWalls (int rows, int columns) {
    return (rows * columns) - rows - columns + 1;
  }

  /**
   * Calcula el número de aristas que tiene un laberinto perfecto de las
   * dimensiones dadas. Las aristas representan pasillos entre 2 celdas.
   *
   * @param rows
   *          Númnero de filas.
   * @param columns
   *          Número de columnas.
   * @return Número de aristas del laberinto perfecto.
   */
  public static int perfectMazeEdges (int rows, int columns) {
    return (rows * columns) - 1;
  }
} public abstract class MazeCreationAlgorithm {
  /**
   * Número mínimo de filas que puede tener un laberinto (altura mímia).
   */
  public static final int MIN_ROWS = 5;

  /**
   * Número mínimo de columnas que puede tener un laberinto (anchura mínima).
   */
  public static final int MIN_COLUMNS = 5;

  /**
   * Número de filas del laberinto que se va a crear.
   */
  protected int m_rows;

  /**
   * Numero de columnas del laberinto que se va a crear.
   */
  protected int m_columns;

  /**
   * Matriz de celdas del laberinto que se va a crear o se esá creando.
   */
  protected ArrayList <ArrayList <MazeCell>> m_maze;

  /**
   * Punto de salida del laberinto.
   */
  protected Point m_maze_exit;

  private int m_cycles, m_walls;

  /**
   * Constructor. Crea una nueva instancia de la clase.
   *
   * @param rows
   *          Número de filas del laberinto.
   * @param columns
   *          Número de columnas del laberinto.
   */
  public MazeCreationAlgorithm (int rows, int columns) {
    if (rows < MIN_ROWS || columns < MIN_COLUMNS)
      throw new IllegalArgumentException(
          MainWindow.getTranslations().exception().tooSmallRowsCols());

    m_rows = rows;
    m_columns = columns;
    m_maze = initializeMaze();
  }

  /**
   * Devuelve la posición de la salida del laberinto.
   *
   * @return La posición de la salida del laberinto.
   */
  public Point getExit () {
    return new Point(m_maze_exit);
  }

  /**
   * Crea el laberinto, coloca la salida y añade los ciclos y paredes indicados.
   *
   * @return La matriz que contiene las celdas del laberinto.
   */
  public ArrayList <ArrayList <MazeCell>> createMaze () {
    runCreationAlgorithm();
    createExit();
    addRandomCycles(m_cycles);
    addRandomWalls(m_walls);

    return m_maze;
  }

  /**
   * Establece el número de ciclos que se quiere que genere el algoritmo.
   *
   * @param n_cycles
   *          Número de ciclos.
   */
  public void setCycles (int n_cycles) {
    m_cycles = n_cycles;
  }

  /**
   * Establece el número de componentes separadas que se quiere tener al generar
   * el laberinto. Si se especifica 1, no se modifica el laberinto perfecto.
   *
   * @param n_components
   *          Número de componentes.
   */
  public void setComponents (int n_components) {
    m_walls = n_components - 1;
  }

  /**
   * Ejecuta el algoritmo de creación del laberinto, dejando el resultado en la
   * variable miembro {@link MazeCreationAlgorithm#m_maze}.
   *
   * Cuando se llama a este método, la variable está inicializada con un mapa en
   * el que todas las celdas están rodeadas de paredes.
   */
  protected abstract void runCreationAlgorithm ();

  /**
   * Este método crea un laberinto vacío a partir del número de filas y columnas
   * especificado en el constructor. Hace más sencillo a las subclases
   * implementar el método {@link MazeCreationAlgorithm#createMaze}.
   *
   * @return Un laberinto vacío del tamaño especificado.
   */
  protected ArrayList <ArrayList <MazeCell>> initializeMaze () {
    ArrayList <ArrayList <MazeCell>> maze = new ArrayList <ArrayList <MazeCell>>(m_rows);
    for (int y = 0; y < m_rows; y++) {
      maze.add(new ArrayList <MazeCell>(m_columns));
      for (int x = 0; x < m_columns; x++)
        maze.get(y).add(new MazeCell());
    }

    return maze;
  }

  /**
   * Abre un pasillo entre la celda (x, y) y su adyacente en la dirección
   * indicada.
   *
   * @param y
   *          Posición en el eje Y (FILA).
   * @param x
   *          Posición en el eje X (COLUMNA).
   * @param dir
   *          Dirección hacia la que abrir el camino.
   */
  protected void openPassage (int y, int x, final Direction dir) {
    Pair <Integer, Integer> desp = dir.decompose();
    m_maze.get(y).get(x).unsetWall(dir);
    m_maze.get(y + desp.second).get(x + desp.first).unsetWall(dir.getOpposite());
  }

  /**
   * Abre una salida en una casilla aleatoria por los bordes del laberinto.
   */
  private void createExit () {
    // Decidimos en qué borde vamos a crear la salida
    Direction dir = Direction.random();

    // Posición en la que se abrirá el hueco: Puede ser tanto una coordenada en
    // X como en Y
    int pos;
    if (dir.isVertical())
      pos = (int) (Math.random() * m_columns);
    else
      pos = (int) (Math.random() * m_rows);

    // Cogemos la celda de salida y abrimos el hueco
    m_maze_exit = new Point();
    switch (dir) {
      case UP:
        m_maze_exit.move(pos, 0);
        break;
      case DOWN:
        m_maze_exit.move(pos, m_rows - 1);
        break;
      case LEFT:
        m_maze_exit.move(0, pos);
        break;
      case RIGHT:
        m_maze_exit.move(m_columns - 1, pos);
        break;
      default:
        break;
    }

    m_maze.get(m_maze_exit.y).get(m_maze_exit.x).unsetWall(dir);
    m_maze_exit.setLocation(dir.movePoint(m_maze_exit));
  }

  /**
   * Elimina paredes de un laberinto perfecto ya creado para crear ciclos y
   * hacer que deje de serlo.
   *
   * @param n
   *          Número de paredes a quitar.
   */
  private void addRandomCycles (int n) {
    if (n > Maze.perfectMazeWalls(m_rows, m_columns))
      throw new IllegalArgumentException(
          MainWindow.getTranslations().exception().tooManyWalls());

    int k = 0;
    Direction dir;
    while (k < n) {
      int x = (int) (Math.random() * m_columns);
      int y = (int) (Math.random() * m_rows);
      Point p = new Point(x, y);
      ArrayList <Direction> directions = new ArrayList <Direction>();

      for (int i = 1; i < Direction.MAX_DIRECTIONS; i++) {
        dir = Direction.fromIndex(i);
        Point p2 = dir.movePoint(p);
        if (p2.y >= 0 && p2.y < m_rows && p2.x >= 0 && p2.x < m_columns
            && m_maze.get(p.y).get(p.x).hasWall(dir))
          directions.add(dir);
      }

      if (!directions.isEmpty()) {
        dir = directions.get((int) (Math.random() * directions.size()));
        openPassage(p.y, p.x, dir);
        k++;
      }
    }
  }

  /**
   * Añade paredes al laberinto perfecto ya creado para que esté compuesto por
   * distintas componentes inaccesibles entre sí y deje de ser perfecto.
   *
   * @param n
   *          Número de paredes para añadir.
   */
  private void addRandomWalls (int n) {
    if (n > Maze.perfectMazeEdges(m_rows, m_columns))
      throw new IllegalArgumentException(
          MainWindow.getTranslations().exception().tooManyWalls());

    int k = 0;
    Direction dir;
    while (k < n) {
      int x = (int) (Math.random() * m_columns);
      int y = (int) (Math.random() * m_rows);
      Point p = new Point(x, y);
      ArrayList <Direction> directions = new ArrayList <Direction>();

      for (int i = 1; i < Direction.MAX_DIRECTIONS; i++) {
        dir = Direction.fromIndex(i);
        Point p2 = dir.movePoint(p);
        if (p2.y >= 0 && p2.y < m_rows && p2.x >= 0 && p2.x < m_columns
            && !m_maze.get(p.y).get(p.x).hasWall(dir))
          directions.add(dir);
      }

      if (!directions.isEmpty()) {
        dir = directions.get((int) (Math.random() * directions.size()));
        m_maze.get(p.y).get(p.x).setWall(dir);
        p = dir.movePoint(p);
        m_maze.get(p.y).get(p.x).setWall(dir.getOpposite());
        k++;
      }
    }
  }

} public class AldousBroder extends MazeCreationAlgorithm {
  private short cellVisitedCount = 0;
  private ArrayList <ArrayList <Boolean>> m_included_cells;

  /**
   * Constructor. Crea una nueva instancia de la clase.
   *
   * @param rows
   *          Número de filas del laberinto.
   * @param columns
   *          Número de columnas del laberinto.
   */
  public AldousBroder (int rows, int columns) {
    super(rows, columns);

    // Creamos una matriz de visitados para saber en cada momento cuáles son
    // las celdas que no se han visitado todavía.
    m_included_cells = new ArrayList <ArrayList <Boolean>>(rows);

    for (int y = 0; y < rows; y++) {
      m_included_cells.add(new ArrayList <Boolean>(columns));
      for (int x = 0; x < columns; x++)
        m_included_cells.get(y).add(false);
    }
  }

  /*
   * (non-Javadoc)
   *
   * @see maze.MazeCreationAlgorithm#runCreationAlgorithm()
   */
  @Override
  public void runCreationAlgorithm () {
    int x = (int) (Math.random() * m_columns);
    int y = (int) (Math.random() * m_rows);
    Point p = new Point(x, y);

    while (cellVisitedCount < (m_columns * m_rows)) {
      Direction dir = getRandomDirection(p.y, p.x);
      p = dir.movePoint(p);
      if (!m_included_cells.get(p.y).get(p.x)) {
        openPassage(p.y, p.x, dir.getOpposite());
        m_included_cells.get(p.y).set(p.x, true);
        cellVisitedCount++;
      }
    }
  }

  /**
   * Obtiene una dirección aleatoria a partir de la posición indicada que no
   * se sale del tamaño del laberinto.
   *
   * @param y
   *          Posición en el eje Y desde la que se quiere partir.
   * @param x
   *          Posición en el eje X desde la que se quiere partir.
   * @return Dirección aleatoria dentro del rango.
   */
  private Direction getRandomDirection (int y, int x) {
    Point p = new Point(x, y);
    Point next_pos;
    Direction dir;

    do {
      dir = Direction.random();
      next_pos = dir.movePoint(p);
    }
    while (next_pos.y < 0 || next_pos.y >= m_rows || next_pos.x < 0 || next_pos.x >= m_columns);

    return dir;
  }
} public class HuntAndKill extends MazeCreationAlgorithm {
  private ArrayList <ArrayList <Boolean>> m_included_cells;

  /**
   * Constructor. Crea una nueva instancia de la clase.
   *
   * @param rows
   *          Número de filas del laberinto.
   * @param columns
   *          Número de columnas del laberinto.
   */
  public HuntAndKill (int rows, int columns) {
    super(rows, columns);

    // Creamos una matriz de visitados para saber en cada momento cuáles son
    // las celdas que no se han visitado todavía.
    m_included_cells = new ArrayList <ArrayList <Boolean>>(rows);

    for (int y = 0; y < rows; y++) {
      m_included_cells.add(new ArrayList <Boolean>(columns));
      for (int x = 0; x < columns; x++)
        m_included_cells.get(y).add(false);
    }
  }

  /*
   * (non-Javadoc)
   *
   * @see maze.MazeCreationAlgorithm#runCreationAlgorithm()
   */
  @Override
  public void runCreationAlgorithm () {
    int x = (int) (Math.random() * m_rows);
    int y = (int) (Math.random() * m_columns);

    Point p = new Point(x, y);
    while (p != null) {
      walk(p);
      p = hunt();
    }
  }

  /**
   * Dada una posición de inicio va explorando dicho camino mientras no
   * llegue a un punto sin salida.
   *
   * @param p
   *          Punto con las coordenadas x e y de las cuales se quiere empezar a
   *          buscar un nuevo camino.
   */
  private void walk (Point p) {
    Direction dir = getRandomDirection(p.y, p.x);
    while (dir != Direction.NONE) {
      openPassage(p.y, p.x, dir);
      p = dir.movePoint(p);
      m_included_cells.get(p.y).set(p.x, true);
      dir = getRandomDirection(p.y, p.x);
    }
  }

  /**
   * Busca por todo el tablero una casilla explorada y que puede ser el origen
   * de una nueva exploración (el método {@link HuntAndKill#walk} puede empezar
   * por esa casilla). Dicha casilla con ese posible camino es explorado por el
   * método hunt (kill).
   *
   * @return Devuelve una posición por la cual el "cursor" puede seguir
   *         explorando.
   */
  private Point hunt () {
    for (int y = 0; y < m_rows; y++) {
      for (int x = 0; x < m_columns; x++) {
        Direction dir = getRandomDirection(y, x);
        if (dir != Direction.NONE) {
          openPassage(y, x, dir);
          Point p = dir.movePoint(new Point(x, y));
          m_included_cells.get(p.y).set(p.x, true);
          return p;
        }
      }
    }
    return null;
  }

  /**
   * Obtiene una dirección aleatoria desde la posición indicada que la conecte
   * con una posición no explorada dentro del laberinto que se está creando.
   *
   * @param y
   *          Posición en el eje Y desde la que se quiere partir.
   * @param x
   *          Posición en el eje X desde la que se quiere partir.
   * @return Una direccion aleatoria dentro de las posibles a las que ir
   *         en la casilla dada por las posiciones i y j.
   */
  private Direction getRandomDirection (int y, int x) {
    ArrayList <Direction> directions = new ArrayList <Direction>();
    Point actual = new Point(x, y);

    // Comprobamos qué posiciones de alrededor son válidas y no se han visitado
    // Suponemos que la posición proporcionada es válida para empezar
    for (int i = 1; i < Direction.MAX_DIRECTIONS; i++) {
      Direction dir = Direction.fromIndex(i);
      Point next = dir.movePoint(actual);

      if (next.y >= 0 && next.y < m_rows && next.x >= 0 && next.x < m_columns
          && !m_included_cells.get(next.y).get(next.x))
        directions.add(dir);
    }

    if (directions.isEmpty())
      return Direction.NONE;
    else
      return directions.get((int) (Math.random() * directions.size()));
  }

} public class Kruskal extends MazeCreationAlgorithm {
  private ArrayList <Integer> disjoint_set;
  private ArrayList <short []> walls;

  /**
   * Constructor. Crea una nueva instancia de la clase.
   *
   * @param rows
   *          Número de filas del laberinto.
   * @param columns
   *          Número de columnas del laberinto.
   */
  public Kruskal (int rows, int columns) {
    super(rows, columns);
    walls = new ArrayList <short []>();

    // Creamos una matriz de visitados para saber en cada momento cuáles son
    // las celdas que no se han visitado todavía.
    disjoint_set = new ArrayList <Integer>();

    for (int i = 0; i < m_rows * m_columns; i++)
      disjoint_set.add(i);

    addAll();
  }

  /*
   * (non-Javadoc)
   *
   * @see maze.MazeCreationAlgorithm#runCreationAlgorithm()
   */
  @Override
  public void runCreationAlgorithm () {
    int nextWall, y, x;
    while (!walls.isEmpty()) {
      // Seleccionamos una celda y una direccion de dentro de las posibles que
      // no hemos escogido aun.
      nextWall = (int) Math.round(0 + (Math.random() * (walls.size() - 1)));
      y = walls.get(nextWall)[0];
      x = walls.get(nextWall)[1];
      Direction dir = Direction.fromValue(walls.get(nextWall)[2]);
      Pair <Integer, Integer> desp = dir.decompose();

      // Si la celda vecina a la posicion i,j +dir pertenece a otro conjunto
      // entonces, la marcamos del mismo conjunto (y a cada elemento del mismo)
      // y abrimos el pasillo por ahi.
      if (value(y, x) != value(y + desp.second, x + desp.first)) {
        openPassage(y, x, dir);
        union(value(y, x), value(y + desp.second, x + desp.first));
      }
      walls.remove(nextWall);
    }
  }

  /**
   * Añade todos los muros a la lista de muros a elegir aleatoriamente.
   */
  private void addAll () {
    for (int y = 0; y < m_rows; y++)
      for (int x = 0; x < m_columns; x++)
        for (short k = 1; k < Direction.MAX_DIRECTIONS; k++) {
          Direction dir = Direction.fromIndex(k);
          Pair <Integer, Integer> desp = dir.decompose();
          if ((y + desp.second >= 0) && (x + desp.first >= 0) && (y + desp.second < m_rows)
              && (x + desp.first < m_columns)) {
            short [] aux = {(short) y, (short) x, dir.val};
            walls.add(aux);
          }
        }
  }

  /**
   * Obtiene el índice que representa la posición (x, y).
   *
   * @param y
   *          Posición en el eje Y.
   * @param x
   *          Posición en el eje X.
   *
   * @return La posición del vector dada por el punto (x, y).
   */
  private int pos (int y, int x) {
    // FIXME Esto está invertido. La fórmula real sería (y * m_columns) + x
    // No lo cambio porque no sé si hay código que depende de este
    // comportamiento erróneo.
    return (x * m_columns) + y;
  }

  /**
   * Une dos conjuntos disjuntos, de la forma siguiente: Todo conjunto que
   * tenga como valor representativo value_from, lo mueve al conjunto de valor
   * value_to.
   *
   * @param value_from
   *          Valor representativo del conjunto que se va a ser unido al otro
   *          conjunto.
   * @param value_to
   *          Valor representativo del conjunto al que se va a unir el otro
   *          conjunto.
   */
  private void union (int value_from, int value_to) {
    for (int k = 0; k < disjoint_set.size(); k++)
      if (disjoint_set.get(k) == value_from)
        disjoint_set.set(k, value_to);
  }

  /**
   * Obtiene el valor del conjunto del elemento (x, y).
   *
   * @param y
   *          Posición en el eje Y.
   * @param x
   *          Posición en el eje X.
   *
   * @return Valor del conjunto del elemento (x, y).
   */
  private int value (int y, int x) {
    return disjoint_set.get(pos(y, x));
  }

} public class Prim extends MazeCreationAlgorithm {
  private ArrayList <ArrayList <Boolean>> m_included_cells;
  private ArrayList <short []> walls;

  /**
   * Constructor. Crea una nueva instancia de la clase.
   *
   * @param rows
   *          Número de filas del laberinto.
   * @param columns
   *          Número de columnas del laberinto.
   */
  public Prim (int rows, int columns) {
    super(rows, columns);
    walls = new ArrayList <short []>();
    m_included_cells = new ArrayList <ArrayList <Boolean>>(rows);

    // Creamos una matriz de visitados para saber en cada momento cuáles son
    // las celdas que no se han visitado todavía.
    for (int y = 0; y < rows; y++) {
      m_included_cells.add(new ArrayList <Boolean>(columns));
      for (int x = 0; x < columns; x++)
        m_included_cells.get(y).add(false);
    }
  }

  /*
   * (non-Javadoc)
   *
   * @see maze.MazeCreationAlgorithm#runCreationAlgorithm()
   */
  @Override
  public void runCreationAlgorithm () {
    short y = 0;
    short x = 0;
    // Empezar el laberinto con todo lleno de paredes y selecionar una celda.
    m_included_cells.get(y).set(x, true);
    addCell(y, x);
    // Mientras haya celdas sin visitar, seguir visitando.
    int nextWall = 0;
    while (!walls.isEmpty()) {
      // Seleccionamos una celda y una direccion de dentro de las posibles que
      // no hemos escogido aun.
      nextWall = (int) Math.round(0 + (Math.random() * (walls.size() - 1)));
      y = walls.get(nextWall)[0];
      x = walls.get(nextWall)[1];
      Direction dir = Direction.fromValue(walls.get(nextWall)[2]);
      Pair <Integer, Integer> desp = dir.decompose();

      // Si la celda vecina a la posicion i,j +dir sigue estando disponible
      // la elegimos y agregamos las celdas vecinas a esta al conjunto, si no
      // eliminamos dicha posicion con dicha direccion para que no vuelva
      // a salir de forma aleatoria
      if (!m_included_cells.get(y + desp.second).get(x + desp.first)) {
        openPassage(y, x, dir);
        m_included_cells.get(y + desp.second).set(x + desp.first, true);
        addCell(y + desp.second, x + desp.first);
      }
      walls.remove(nextWall);
    }
  }

  /**
   * Añade las celdas adyacentes a la (x, y) a la lista de paredes.
   *
   * @param y
   *          Posición en el eje Y desde la que se quiere partir.
   * @param x
   *          Posición en el eje X desde la que se quiere partir.
   */
  private void addCell (final int y, final int x) {
    for (short k = 1; k < Direction.MAX_DIRECTIONS; k++) {
      Direction dir = Direction.fromIndex(k);
      Pair <Integer, Integer> desp = dir.decompose();
      if ((y + desp.second >= 0) && (x + desp.first >= 0) && (y + desp.second < m_rows)
          && (x + desp.first < m_columns)
          && !m_included_cells.get(y + desp.second).get(x + desp.first)) {
        short [] aux = {(short) y, (short) x, dir.val};
        walls.add(aux);
      }
    }
  }
} public class RecursiveBacktracking extends MazeCreationAlgorithm {
  private ArrayList <ArrayList <Boolean>> m_included_cells;

  /**
   * Constructor. Crea una nueva instancia de la clase.
   *
   * @param rows
   *          Número de filas del laberinto.
   * @param columns
   *          Número de columnas del laberinto.
   */
  public RecursiveBacktracking (int rows, int columns) {
    super(rows, columns);
    m_included_cells = new ArrayList <ArrayList <Boolean>>(rows);
    // Creamos una matriz de visitados para saber en cada momento cuáles son
    // las celdas que no se han visitado todavía.
    for (int y = 0; y < rows; y++) {
      m_included_cells.add(new ArrayList <Boolean>(columns));
      for (int x = 0; x < columns; x++)
        m_included_cells.get(y).add(false);
    }
  }

  /*
   * (non-Javadoc)
   *
   * @see maze.MazeCreationAlgorithm#runCreationAlgorithm()
   */
  @Override
  public void runCreationAlgorithm () {
    Stack <Point> stack = new Stack <Point>();

    stack.push(new Point(0, 0));
    m_included_cells.get(0).set(0, true);

    while (!stack.isEmpty()) {
      Point p = stack.peek();
      Direction dir = getRandomDirection(p.y, p.x);
      if (dir == Direction.NONE) {
        stack.pop();
      }
      else {
        openPassage(p.y, p.x, dir);
        p = dir.movePoint(p);
        m_included_cells.get(p.y).set(p.x, true);
        stack.push(p);
      }
    }
  }

  /**
   * Obtiene una dirección aleatoria desde la posición indicada que la conecte
   * con una posición no explorada dentro del laberinto que se está creando.
   *
   * @param y
   *          Posición en el eje Y desde la que se quiere partir.
   * @param x
   *          Posición en el eje X desde la que se quiere partir.
   * @return Una direccion aleatoria dentro de las posibles a las que ir
   *         en la casilla dada por las posiciones i y j.
   */
  private Direction getRandomDirection (int y, int x) {
    ArrayList <Direction> directions = new ArrayList <Direction>();
    Point actual = new Point(x, y);

    // Comprobamos qué posiciones de alrededor son válidas y no se han visitado
    // Suponemos que la posición proporcionada es válida para empezar
    for (int i = 1; i < Direction.MAX_DIRECTIONS; i++) {
      Direction dir = Direction.fromIndex(i);
      Point next = dir.movePoint(actual);

      if (next.y >= 0 && next.y < m_rows && next.x >= 0 && next.x < m_columns
          && !m_included_cells.get(next.y).get(next.x))
        directions.add(dir);
    }

    if (directions.isEmpty())
      return Direction.NONE;
    else
      return directions.get((int) (Math.random() * directions.size()));
  }

} public class RecursiveDivision extends MazeCreationAlgorithm {

  private final static int HORIZONTAL = 0;
  private final static int VERTICAL = 1;

  /**
   * Constructor. Crea una nueva instancia de la clase.
   *
   * @param rows
   *          Número de filas del laberinto.
   * @param columns
   *          Número de columnas del laberinto.
   */
  public RecursiveDivision (int rows, int columns) {
    super(rows, columns);
    for (int y = 0; y < m_rows; y++)
      for (int x = 0; x < m_columns; x++)
        for (int i = 1; i < Direction.MAX_DIRECTIONS; i++) {
          Direction dir = Direction.fromIndex(i);
          Point next = dir.movePoint(new Point(x, y));

          if (next.y >= 0 && next.y < m_rows && next.x >= 0 && next.x < m_columns)
            m_maze.get(y).get(x).toggleWall(dir);
        }
  }

  /*
   * (non-Javadoc)
   *
   * @see es.ull.mazesolver.maze.MazeCreationAlgorithm#runCreationAlgorithm()
   */
  @Override
  protected void runCreationAlgorithm () {
    divide(0, 0, m_columns, m_rows, chooseOrientation(m_columns, m_rows));
  }

  /**
   * Función principal recursiva que va generando sub-laberintos.
   *
   * @param x
   *          Posición en el eje X desde la que se quiere partir.
   * @param y
   *          Posición en el eje Y desde la que se quiere partir.
   * @param width
   *          Número de columnas del sub laberinto.
   * @param height
   *          Número de filas del sub Laberinto.
   * @param orientation
   *          Orientación a seguir para generar el sub laberinto
   */
  private void divide (int x, int y, int width, int height, int orientation) {
    if (height > 1 && width > 1) {

      // Inicio del muro del sub laberinto
      int wx = x, wy = y;
      wx += (orientation == HORIZONTAL)? 0 : (int) (Math.random() * (width - 1));
      wy += (orientation == HORIZONTAL)? (int) (Math.random() * (height - 1)) : 0;

      // Posicion de la puerta
      int px = wx, py = wy;
      px += (orientation == HORIZONTAL)? (int) (Math.random() * width) : 0;
      py += (orientation == HORIZONTAL)? 0 : (int) (Math.random() * height);

      // Direccion a la que moverse
      int dx = (orientation == HORIZONTAL)? 1 : 0;
      int dy = (orientation == HORIZONTAL)? 0 : 1;

      // Longitud del muro
      int length = (orientation == HORIZONTAL)? width : height;

      // Direccion donde dibujar el muro
      Direction dir = (orientation == HORIZONTAL)? Direction.DOWN : Direction.RIGHT;

      for (int i = 0; i < length; i++) {
        if (wx != px || wy != py) {
          Pair <Integer, Integer> desp = dir.decompose();
          m_maze.get(wy).get(wx).setWall(dir);
          m_maze.get(wy + desp.second).get(wx + desp.first).setWall(dir.getOpposite());
        }
        wx += dx;
        wy += dy;
      }

      int nx = x, ny = y;
      int w = (orientation == HORIZONTAL)? width : wx - x + 1;
      int h = (orientation == HORIZONTAL)? wy - y + 1 : height;
      divide(nx, ny, w, h, chooseOrientation(w, h));

      nx = (orientation == HORIZONTAL)? x : wx + 1;
      ny = (orientation == HORIZONTAL)? wy + 1 : y;
      w = (orientation == HORIZONTAL)? width : x + width - wx - 1;
      h = (orientation == HORIZONTAL)? y + height - wy - 1 : height;
      divide(nx, ny, w, h, chooseOrientation(w, h));
    }
  }

  /**
   * Función auxiliar para elegir la orientación por la que ir dividiendo el
   * laberinto
   *
   * @param width
   *          Número de columnas del Laberinto.
   * @param height
   *          Número de filas del laberinto.
   * @return Orientación a seguir para ir dividiendo el laberinto.
   */
  private int chooseOrientation (int width, int height) {
    if (width < height)
      return HORIZONTAL;
    else if (height < width)
      return VERTICAL;
    else
      return (int) (Math.random() * 2);
  }

} public class Wilson extends MazeCreationAlgorithm {
  private int m_remaining;
  private ArrayList <ArrayList <Boolean>> m_included_cells;

  /**
   * Constructor. Crea una nueva instancia de la clase.
   *
   * @param rows
   *          Número de filas del laberinto.
   * @param columns
   *          Número de columnas del laberinto.
   */
  public Wilson (int rows, int columns) {
    super(rows, columns);

    // Creamos una matriz de visitados para saber en cada momento cuáles son
    // las celdas que no se han visitado todavía.
    m_included_cells = new ArrayList <ArrayList <Boolean>>(rows);

    for (int y = 0; y < rows; y++) {
      m_included_cells.add(new ArrayList <Boolean>(columns));
      for (int x = 0; x < columns; x++)
        m_included_cells.get(y).add(false);
    }
    m_remaining = columns * rows - 1;
    int x = (int) (Math.random() * m_columns);
    int y = (int) (Math.random() * m_rows);
    m_included_cells.get(y).set(x, true);
  }

  /*
   * (non-Javadoc)
   *
   * @see es.ull.mazesolver.maze.MazeCreationAlgorithm#runCreationAlgorithm()
   */
  @Override
  protected void runCreationAlgorithm () {
    while (m_remaining > 0) {
      ArrayList <Short []> path = walk();
      for (int i = 0; i < path.size(); i++) {
        Short [] aux = path.get(i);
        Point p = new Point(aux[0], aux[1]);
        Direction dir = Direction.fromValue(aux[2]);
        m_included_cells.get(p.y).set(p.x, true);
        openPassage(p.y, p.x, dir);
        m_remaining -= 1;
      }
    }
  }

  /**
   * Método que calcula un camino a seguir.
   *
   * @return Lista de puntos con su respectiva dirección que hemos de seguir
   *         para llegar a una zona visitada.
   */
  private ArrayList <Short []> walk () {
    Point p_start = getRandomStarter();
    ArrayList <ArrayList <Direction>> directionsTaken;
    directionsTaken = new ArrayList <ArrayList <Direction>>(m_rows);

    for (int y = 0; y < m_rows; y++) {
      directionsTaken.add(new ArrayList <Direction>(m_columns));
      for (int x = 0; x < m_columns; x++)
        directionsTaken.get(y).add(Direction.NONE);
    }
    Point p = p_start;
    do {
      Direction dir = getRandomDirection(p.y, p.x);
      directionsTaken.get(p.y).set(p.x, dir);
      p = dir.movePoint(p);
    }
    while (!m_included_cells.get(p.y).get(p.x));

    p = p_start;
    ArrayList <Short []> path = new ArrayList <Short []>();
    do {
      Direction dir = directionsTaken.get(p.y).get(p.x);
      Short [] pos = {(short) p.x, (short) p.y, dir.val};
      path.add(pos);
      p = dir.movePoint(p);
    }
    while (!m_included_cells.get(p.y).get(p.x));

    return path;
  }

  /**
   * Obtiene una dirección aleatoria desde la posición indicada que la conecte
   * con una posición no explorada dentro del laberinto que se está creando.
   *
   * @param y
   *          Posición en el eje Y desde la que se quiere partir.
   * @param x
   *          Posición en el eje X desde la que se quiere partir.
   * @return Una direccion aleatoria dentro de las posibles a las que ir
   *         en la casilla dada por las posiciones i y j.
   */
  private Direction getRandomDirection (int y, int x) {
    ArrayList <Direction> directions = new ArrayList <Direction>();
    Point actual = new Point(x, y);

    // Comprobamos qué posiciones de alrededor son válidas y no se han visitado
    // Suponemos que la posición proporcionada es válida para empezar
    for (int i = 1; i < Direction.MAX_DIRECTIONS; i++) {
      Direction dir = Direction.fromIndex(i);
      Point next = dir.movePoint(actual);

      if (next.y >= 0 && next.y < m_rows && next.x >= 0 && next.x < m_columns)
        directions.add(dir);
    }

    if (directions.isEmpty())
      return Direction.NONE;
    else
      return directions.get((int) (Math.random() * directions.size()));
  }

  /**
   * Obtiene un punto inicial de manera aleatoria desde el cual se puede llamar
   * al método {@link Wilson#walk}.
   *
   * @return Punto inicial aleatorio para metodo walk
   */
  private Point getRandomStarter () {
    ArrayList <Point> freePoints = new ArrayList <Point>();
    for (int y = 0; y < m_rows; y++)
      for (int x = 0; x < m_columns; x++)
        if (!m_included_cells.get(y).get(x))
          freePoints.add(new Point(x, y));
    return freePoints.get((int) (Math.random() * freePoints.size()));
  }

} public interface Translations {
  MenuTranslations menu ();
  ButtonTranslations button ();
  MessageTranslations message ();
  ExceptionTranslations exception ();
  EnumTranslations enums ();

  ConsoleTranslations console ();
  EnvSelectorTranslations env ();
  MazeSelectorTranslations maze ();
  AgentSelectorTranslations agent ();

  SimulatorResultTranslations simulation ();
  Languages languages ();

  OtherTranslations other ();
}
import java.awt.BorderLayout;
import java.awt.FlowLayout;
import java.awt.GridLayout;
import java.awt.Window;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import javax.swing.BorderFactory;
import javax.swing.Box;
import javax.swing.ButtonGroup;
import javax.swing.JButton;
import javax.swing.JComboBox;
import javax.swing.JDialog;
import javax.swing.JLabel;
import javax.swing.JPanel;
import javax.swing.JRadioButton;
import javax.swing.JSpinner;
import javax.swing.SpinnerNumberModel;
import javax.swing.border.EtchedBorder;
import javax.swing.event.ChangeEvent;
import javax.swing.event.ChangeListener;
import es.ull.mazesolver.maze.Maze;
import es.ull.mazesolver.maze.MazeCreationAlgorithm;
import es.ull.mazesolver.maze.algorithm.AldousBroder;
import es.ull.mazesolver.maze.algorithm.HuntAndKill;
import es.ull.mazesolver.maze.algorithm.Kruskal;
import es.ull.mazesolver.maze.algorithm.Prim;
import es.ull.mazesolver.maze.algorithm.RecursiveBacktracking;
import es.ull.mazesolver.maze.algorithm.RecursiveDivision;
import es.ull.mazesolver.maze.algorithm.Wilson;
import es.ull.mazesolver.translations.Translations;
        new JSpinner(new SpinnerNumberModel(MIN_MAZE_SIZE, MIN_MAZE_SIZE, MAX_MAZE_SIZE, 1));

    basic_labels.add(new JLabel(tr.maze().algorithm() + ":"));
    basic_controls.add(m_algorithms);
    basic_labels.add(new JLabel(tr.maze().rows() + ":"));
    basic_controls.add(m_rows);
    basic_labels.add(new JLabel(tr.maze().columns() + ":"));
    basic_controls.add(m_columns);

    basic_global.add(basic_labels, BorderLayout.WEST);
    basic_global.add(basic_controls, BorderLayout.CENTER);
    basic_global.setBorder(BorderFactory.createCompoundBorder(BorderFactory.createEmptyBorder(2, 5,
        0, 5), BorderFactory.createTitledBorder(
        BorderFactory.createEtchedBorder(EtchedBorder.LOWERED), tr.maze().basicConfiguration())));

    JPanel adv_global = new JPanel(new BorderLayout());
    JPanel adv_labels = new JPanel(new GridLayout(3, 1));
    JPanel adv_controls = new JPanel(new GridLayout(3, 1));

    m_type = new ButtonGroup();
    m_perfect = new JRadioButton(tr.maze().perfectMaze(), true);
    m_perfect.setActionCommand("Perfect");
    m_add_cycles = new JRadioButton(tr.maze().addCycles() + ":");
    m_add_cycles.setActionCommand("Cycles");
    m_add_components = new JRadioButton(tr.maze().addWalls() + ":");
    m_add_components.setActionCommand("Walls");

    m_type.add(m_perfect);
    m_type.add(m_add_cycles);
    m_type.add(m_add_components);

    m_cycles =
        new JSpinner(new SpinnerNumberModel(0, 0, (int) Math.round(Maze.perfectMazeWalls(
            MIN_MAZE_SIZE, MIN_MAZE_SIZE) * 0.75), 1));
    m_components =
        new JSpinner(new SpinnerNumberModel(0, 0, (int) Math.round(Maze.perfectMazeEdges(
            MIN_MAZE_SIZE, MIN_MAZE_SIZE) * 0.75), 1));

    m_cycles.setEnabled(false);
    m_components.setEnabled(false);

    adv_labels.add(m_perfect);
    adv_controls.add(Box.createGlue());
    adv_labels.add(m_add_cycles);
    adv_controls.add(m_cycles);
    adv_labels.add(m_add_components);
    adv_controls.add(m_components);

    adv_global.add(adv_labels, BorderLayout.WEST);
    adv_global.add(adv_controls, BorderLayout.CENTER);
    adv_global.setBorder(BorderFactory.createCompoundBorder(BorderFactory.createEmptyBorder(2, 5,
        0, 5), BorderFactory.createTitledBorder(
        BorderFactory.createEtchedBorder(EtchedBorder.LOWERED), tr.maze().mazeType())));

    m_ok = new JButton(tr.button().ok());
    m_cancel = new JButton(tr.button().cancel());

    JPanel button_panel = new JPanel(new FlowLayout(FlowLayout.RIGHT));
    button_panel.add(m_ok);
    button_panel.add(m_cancel);

    JPanel global = new JPanel(new BorderLayout());
    global.add(basic_global, BorderLayout.CENTER);
    global.add(adv_global, BorderLayout.SOUTH);

    add(global, BorderLayout.CENTER);
    add(button_panel, BorderLayout.SOUTH);
    pack();
  }

  /**
   * Configura los controladores de la interfaz gráfica.
   */
  private void setupListeners () {
    ChangeListener dim_change_listener = new ChangeListener() {
      @Override
      public void stateChanged (ChangeEvent e) {
        int rows = (Integer) m_rows.getValue();
        int columns = (Integer) m_columns.getValue();

        int max_cycles = (int) Math.round(Maze.perfectMazeWalls(rows, columns) * 0.75);
        int max_components = (int) Math.round(Maze.perfectMazeEdges(rows, columns) * 0.75);

        SpinnerNumberModel cycles_model = (SpinnerNumberModel) m_cycles.getModel();
        SpinnerNumberModel components_model = (SpinnerNumberModel) m_components.getModel();

        cycles_model.setMaximum(max_cycles);
        components_model.setMaximum(max_components);

        cycles_model.setValue(Math.min((Integer) cycles_model.getValue(), max_cycles));
        components_model.setValue(Math.min((Integer) components_model.getValue(), max_components));
      }
    };

    m_rows.addChangeListener(dim_change_listener);
    m_columns.addChangeListener(dim_change_listener);

    ActionListener types_listener = new ActionListener() {
      @Override
      public void actionPerformed (ActionEvent e) {
        m_cycles.setEnabled(e.getSource() == m_add_cycles);
        m_components.setEnabled(e.getSource() == m_add_components);
      }
    };

    m_perfect.addActionListener(types_listener);
    m_add_cycles.addActionListener(types_listener);
    m_add_components.addActionListener(types_listener);

    m_ok.addActionListener(new ActionListener() {
      @Override
      public void actionPerformed (ActionEvent e) {
        String alg_name = (String) m_algorithms.getSelectedItem();
        int rows = (Integer) m_rows.getValue();
        int columns = (Integer) m_columns.getValue();

        MazeCreationAlgorithm alg = null;

        switch (alg_name) {
          case "Aldous Broder":
            alg = new AldousBroder(rows, columns);