src/model/Maze.java - master - victor_t/maze

src/model/Maze.java
422 строки13 KB
Victor
relocated project folder
03 июл 2026, 03:14
03 июл 2026, 03:14827638e
package model;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Random;
import java.util.Scanner;

/**
 * Модель лабиринта, представленная в виде сетки с правыми и нижними стенами.
 *
 * <p>Лабиринт генерируется с использованием алгоритма, основанного на
 * системе непересекающихся множеств (вариация алгоритма Эллера),
 * обеспечивая связность и отсутствие изолированных областей.</p>
 *
 * <p>Поддерживает загрузку/сохранение, генерацию и поиск пути
 * между двумя точками.</p>
 */
public class Maze {
  private int rows;
  private int cols;
  private boolean[][] rightWall;
  private boolean[][] bottomWall;
  private final List<int[]> path = new ArrayList<>();

  /**
   * Создает лабиринт размером 10x10 и автоматически генерирует его.
   */
  public Maze() {
    generate(10, 10);
  }

  /**
   * Загружает лабиринт из файла.
   *
   * <p>Формат файла:
   * первая строка — размеры,
   * далее матрица правых стен,
   * затем матрица нижних стен.</p>
   *
   * @param fileName путь к файлу
   * @throws Exception если файл отсутствует или формат некорректен,
   *                   либо лабиринт содержит изолированные области
   */
  public void loadFromFile(String fileName) throws Exception {
    try (Scanner sc = new Scanner(new File(fileName))) {
      if (!sc.hasNextInt()) {
        throw new Exception("File format is not correct");
      }
      rows = sc.nextInt();
      cols = sc.nextInt();
      if (rows < 1 || rows > 50 || cols < 1 || cols > 50) {
        generate(10, 10);
        throw new Exception("File format is not correct");
      }
      rightWall = new boolean[rows][cols];
      bottomWall = new boolean[rows][cols];
      for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
          if (!sc.hasNextInt()) {
            throw new Exception("File format is not correct");
          }
          int v = sc.nextInt();
          if (v == 1) {
            rightWall[i][j] = true;
          } else if (v != 0) {
            throw new Exception("File format is not correct");
          }
        }
      }
      for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
          if (!sc.hasNextInt()) {
            throw new Exception("File format is not correct");
          }
          int v = sc.nextInt();
          if (v == 1) {
            bottomWall[i][j] = true;
          } else if (v != 0) {
            throw new Exception("File format is not correct");
          }
        }
      }
    } catch (FileNotFoundException e) {
      throw new Exception("Unable to open file!");
    }
    if (hasIsolation()) {
      throw new Exception("This maze is not perfect");
    }
  }

  /**
   * Сохраняет лабиринт в файл.
   *
   * <p>Формат:
   * rows cols
   * матрица правых стен
   * пустая строка
   * матрица нижних стен</p>
   *
   * @param fileName путь к файлу
   * @throws Exception если запись невозможна
   */
  public void saveToFile(String fileName) throws Exception {
    try (PrintWriter pw = new PrintWriter(new FileWriter(fileName))) {
      pw.println(rows + " " + cols);
      for (int i = 0; i < rows; i++) {
        StringBuilder sb = new StringBuilder();
        for (int j = 0; j < cols; j++) {
          if (j > 0) {
            sb.append(' ');
          }
          sb.append(rightWall[i][j] ? 1 : 0);
        }
        pw.println(sb);
      }
      pw.println();
      for (int i = 0; i < rows; i++) {
        StringBuilder sb = new StringBuilder();
        for (int j = 0; j < cols; j++) {
          if (j > 0) {
            sb.append(' ');
          }
          sb.append(bottomWall[i][j] ? 1 : 0);
        }
        pw.println(sb);
      }
    } catch (IOException e) {
      throw new Exception("Unable to write in file");
    }
  }

  /**
   * Генерирует корректный лабиринт заданного размера.
   *
   * <p>Используется алгоритм, основанный на объединении множеств,
   * который гарантирует связность всех клеток.</p>
   *
   * @param row количество строк (1–50)
   * @param col количество столбцов (1–50)
   * @throws IllegalArgumentException если размеры некорректны
   */
  public void generate(int row, int col) {
    if (row < 1 || row > 50 || col < 1 || col > 50) {
      throw new IllegalArgumentException("Incorrect size of maze");
    }
    rows = row;
    cols = col;
    rightWall = new boolean[rows][cols];
    bottomWall = new boolean[rows][cols];

    int[] oneLine = new int[cols];
    int[] setCounter = {1};

    for (int i = 0; i < rows - 1; i++) {
      createLine(oneLine, setCounter, i);
    }
    createLastLine(oneLine, setCounter);
  }

  /**
   * Обрабатывает одну строку генерации лабиринта.
   */
  private void createLine(int[] oneLine, int[] setCounter, int row) {
    setAssign(oneLine, setCounter);
    createRightWall(oneLine, row);
    createBottomWall(oneLine, row);
  }

  /**
   * Присваивает уникальные множества клеткам строки.
   */
  private void setAssign(int[] oneLine, int[] setCounter) {
    for (int j = 0; j < cols; j++) {
      if (oneLine[j] == 0) {
        oneLine[j] = setCounter[0]++;
      }
    }
  }

  /**
   * Формирует правые стены между клетками.
   */
  private void createRightWall(int[] oneLine, int row) {
    for (int j = 0; j < cols - 1; j++) {
      if (randomBool() || oneLine[j] == oneLine[j + 1]) {
        rightWall[row][j] = true;
      } else {
        int deadSet = oneLine[j + 1];
        int newSet = oneLine[j];
        for (int k = 0; k < cols; k++) {
          if (oneLine[k] == deadSet) {
            oneLine[k] = newSet;
          }
        }
      }
    }
    rightWall[row][cols - 1] = true;
  }

  /**
   * Формирует нижние стены с сохранением связности множеств.
   */
  private void createBottomWall(int[] oneLine, int row) {
    for (int j = 0; j < cols; j++) {
      if (isBottomPossible(oneLine, row, oneLine[j]) && randomBool()) {
        bottomWall[row][j] = true;
        oneLine[j] = 0;
      }
    }
  }

  /**
   * Проверяет, можно ли поставить нижнюю стену,
   * не нарушая связность множества.
   */
  private boolean isBottomPossible(int[] oneLine, int row, int set) {
    int count = 0;
    for (int j = 0; j < cols; j++) {
      if (oneLine[j] == set && !bottomWall[row][j]) {
        count++;
      }
    }
    return count != 1;
  }

  /**
   * Обрабатывает последнюю строку лабиринта,
   * гарантируя полную связность.
   */
  private void createLastLine(int[] oneLine, int[] setCounter) {
    setAssign(oneLine, setCounter);
    createRightWall(oneLine, rows - 1);
    for (int j = 0; j < cols - 1; j++) {
      if (oneLine[j] != oneLine[j + 1]) {
        rightWall[rows - 1][j] = false;
        int deadSet = oneLine[j + 1];
        int newSet = oneLine[j];
        for (int k = 0; k < cols; k++) {
          if (oneLine[k] == deadSet) {
            oneLine[k] = newSet;
          }
        }
      }
      bottomWall[rows - 1][j] = true;
    }
    bottomWall[rows - 1][cols - 1] = true;
  }

  /**
   * Проверяет наличие изолированных областей в лабиринте.
   *
   * <p>Проверка выполняется через многократный запуск поиска пути
   * между различными точками.</p>
   *
   * @return true если есть изоляция
   */
  private boolean hasIsolation() {
    for (int i = 1; i < rows; i++) {
      for (int j = 1; j < cols; j++) {
        int[][] dist = new int[rows][cols];
        if (!leeMazeSolver(dist, 0, 0, i, j)) {
          return true;
        }
      }
    }
    return false;
  }

  /**
   * Поиск пути в лабиринте с помощью BFS (волновой алгоритм).
   *
   * @param dist   матрица расстояний
   * @param beginX начальная координата X
   * @param beginY начальная координата Y
   * @param endX   конечная координата X
   * @param endY   конечная координата Y
   * @return true если путь существует
   */
  private boolean leeMazeSolver(int[][] dist, int beginX, int beginY, int endX, int endY) {
    int[] moveX = {-1, 0, 1, 0};
    int[] moveY = {0, 1, 0, -1};
    Queue<int[]> queue = new LinkedList<>();
    queue.add(new int[] {beginX, beginY});
    dist[beginX][beginY] = 1;
    boolean found = false;
    while (!found && !queue.isEmpty()) {
      int[] curr = queue.poll();
      int x = curr[0];
      int y = curr[1];
      for (int i = 0; i < 4; i++) {
        int nx = x + moveX[i];
        int ny = y + moveY[i];
        if (isFreeToMove(x, y, nx, ny) && dist[nx][ny] == 0) {
          dist[nx][ny] = dist[x][y] + 1;
          queue.add(new int[] {nx, ny});
          if (nx == endX && ny == endY) {
            found = true;
          }
        }
      }
    }
    return found;
  }

  /**
   * Восстанавливает путь от конечной точки к начальной
   * по матрице расстояний BFS.
   */
  private void pathReconstruction(int[][] dist, int endX, int endY) {
    int[] moveX = {-1, 0, 1, 0};
    int[] moveY = {0, 1, 0, -1};
    path.clear();
    path.add(new int[] {endX, endY});
    int track = dist[endX][endY];
    while (track > 1) {
      track--;
      int[] last = path.get(path.size() - 1);
      int x = last[0];
      int y = last[1];
      for (int i = 0; i < 4; i++) {
        int nx = x + moveX[i];
        int ny = y + moveY[i];
        if (isFreeToMove(x, y, nx, ny) && dist[nx][ny] == track) {
          path.add(new int[] {nx, ny});
          break;
        }
      }
    }
  }

  /**
   * Проверяет возможность перехода между двумя соседними клетками
   * с учетом стен лабиринта.
   *
   * @return true если перемещение возможно
   */
  private boolean isFreeToMove(int x, int y, int nx, int ny) {
    if (nx >= rows || nx < 0 || ny >= cols || ny < 0) {
      return false;
    }
    if (y == ny && x < nx && bottomWall[x][y]) {
      return false;   // moving down
    }
    if (y == ny && x > nx && bottomWall[nx][ny]) {
      return false;  // moving up
    }
    if (x == nx && y < ny && rightWall[x][y]) {
      return false;    // moving right
    }
    return x != nx || y <= ny || !rightWall[nx][ny];   // moving left
  }

  /**
   * Находит путь между двумя точками лабиринта.
   *
   * <p>Использует BFS для поиска и восстановление пути.</p>
   *
   * @param beginX начальная координата X
   * @param beginY начальная координата Y
   * @param endX   конечная координата X
   * @param endY   конечная координата Y
   * @return список координат пути
   */
  public List<int[]> getPath(int beginX, int beginY, int endX, int endY) {
    int[][] dist = new int[rows][cols];
    boolean found = leeMazeSolver(dist, beginX, beginY, endX, endY);
    if (found) {
      pathReconstruction(dist, endX, endY);
    }
    return path;
  }

  /**
   * Генерирует случайное логическое значение.
   */
  private static boolean randomBool() {
    return new Random().nextBoolean();
  }

  /**
   * Возвращает количество строк.
   *
   * @return количество строк
   */
  public int getRows() {
    return rows;
  }

  /**
   * Возвращает количество столбцов.
   *
   * @return количество столбцов
   */
  public int getCols() {
    return cols;
  }

  /**
   * Возвращает правую стену.
   *
   * @return матрица правых стен
   */
  public boolean[][] getRightWall() {
    return rightWall;
  }

  /**
   * Возвращает нижнюю стену.
   *
   * @return матрица нижних стен
   */
  public boolean[][] getBottomWall() {
    return bottomWall;
  }
}