Лабиринт

Проект разработан в качестве второго домашнего задания в Т-Академии по теме «Принципы и шаблоны проектирования».

Лабиринт — консольное Java-приложение для генерации, визуализации и решения прямоугольных лабиринтов. Программа поддерживает несколько алгоритмов построения лабиринта и поиска кратчайшего пути, учитывает стоимость разных типов поверхности, выводит результат в ASCII- или Unicode-представлении и умеет сохранять его в файл.

Возможности

• генерация лабиринтов алгоритмами DFS, Прима и Краскала;
• поиск оптимального маршрута алгоритмами A* и Дейкстры;
• учёт стоимости обычных клеток, дорог, песка и болот при поиске пути;
• настройка ширины и высоты генерируемого лабиринта;
• чтение лабиринта из текстового файла;
• вывод лабиринта и найденного пути в консоль или файл;
• отрисовка стен ASCII-символами или Unicode-псевдографикой;
• модульные и black-box тесты;
• автоматические проверки качества кода в GitHub Actions.

Алгоритмы

Генерация

Значение --algorithm	Алгоритм	Краткое описание
dfs	Поиск в глубину	Последовательно углубляется в случайно выбранные непосещённые клетки и возвращается назад при достижении тупика.
prim	Рандомизированный алгоритм Прима	Расширяет лабиринт случайными клетками из границы уже построенной области.
kruskal	Рандомизированный алгоритм Краскала	Объединяет изолированные области, случайно удаляя разделяющие их стены.

Все генераторы создают связный лабиринт. Параметры width и height задают количество логических клеток. Итоговое текстовое представление имеет размер (2 × width + 1) × (2 × height + 1), поскольку включает внешние и внутренние стены.

Поиск пути

Значение --algorithm	Алгоритм	Краткое описание
astar	A*	Использует манхэттенское расстояние как эвристическую оценку и находит маршрут с минимальной стоимостью.
dijkstra	Алгоритм Дейкстры	Находит маршрут с минимальной стоимостью без эвристической оценки.

Движение выполняется по четырём направлениям: вверх, вправо, вниз и влево. Непроходимые стены не включаются в маршрут.

Требования

• JDK 24 или новее;
• Maven 3.9.11 или новее либо Maven Wrapper из репозитория;
• Docker для запуска black-box тестов.

Сборка

В корне проекта выполните:

./mvnw clean package

В Windows:

.\mvnw.cmd clean package

Команда создаёт исполняемый JAR-файл target/project-1.0.jar со всеми необходимыми зависимостями.

Проверить доступные команды приложения:

java -jar target/project-1.0.jar --help

Использование

Приложение предоставляет две подкоманды:

maze-app generate [параметры]
maze-app solve [параметры]

Генерация лабиринта

Обязательные параметры:

Параметр	Описание
`--algorithm=<dfs	prim
--width=<число>	Ширина лабиринта в логических клетках, больше нуля.
--height=<число>	Высота лабиринта в логических клетках, больше нуля.

Дополнительные параметры:

Параметр	Описание
--output=<путь>	Сохраняет результат в указанный файл вместо вывода в консоль.
--unicode	Использует Unicode-псевдографику для стен.
--terrain-road=<доля>	Задаёт вероятность появления дороги +.
--terrain-sand=<доля>	Задаёт вероятность появления песка :.
--terrain-swamp=<доля>	Задаёт вероятность появления болота ~.

Вероятности поверхностей задаются числами от 0 до 1. Для предсказуемого распределения сумма значений не должна превышать 1.

Примеры:

# Сгенерировать ASCII-лабиринт 10 × 10 и сохранить его в файл
java -jar target/project-1.0.jar generate \
  --algorithm=dfs \
  --width=10 \
  --height=10 \
  --output=maze.txt

# Вывести Unicode-лабиринт с разными типами поверхности в консоль
java -jar target/project-1.0.jar generate \
  --algorithm=prim \
  --width=20 \
  --height=10 \
  --terrain-road=0.10 \
  --terrain-sand=0.05 \
  --terrain-swamp=0.02 \
  --unicode

Решение лабиринта

Обязательные параметры:

Параметр	Описание
`--algorithm=<astar	dijkstra>`
--file=<путь>	Путь к текстовому файлу с лабиринтом.
--start=<x,y>	Начальная точка в формате x,y.
--end=<x,y>	Конечная точка в формате x,y.

Дополнительные параметры:

Параметр	Описание
--output=<путь>	Сохраняет решённый лабиринт в указанный файл вместо вывода в консоль.
--unicode	Использует Unicode-псевдографику для стен.

Координаты задаются целыми неотрицательными числами. Начальная и конечная точки должны находиться внутри лабиринта и быть проходимыми.

Примеры:

# Найти путь алгоритмом A* и вывести результат в консоль
java -jar target/project-1.0.jar solve \
  --algorithm=astar \
  --file=maze.txt \
  --start=1,1 \
  --end=9,9

# Найти путь алгоритмом Дейкстры и сохранить результат
java -jar target/project-1.0.jar solve \
  --algorithm=dijkstra \
  --file=maze.txt \
  --start=1,1 \
  --end=9,9 \
  --output=solution.txt

Формат лабиринта

Входной файл должен содержать непустой прямоугольный лабиринт в кодировке UTF-8. Все строки должны иметь одинаковую длину.

Символ	Назначение	Стоимость входа
#	Стена, проход запрещён	Непроходимая клетка
пробел	Обычная проходимая клетка	1
+	Дорога	1
:	Песок	3
~	Болото	5
O	Начальная точка в выводе	1
X	Конечная точка в выводе	1
.	Найденный маршрут в выводе	1

Пример решённого лабиринта:

###########
#O..#     #
###.##### #
#  .....# #
# #####.# #
#      X# #
###########

При чтении файла символы O, X и . считаются обычными проходимыми клетками. Фактические точки начала и конца маршрута задаются параметрами --start и --end.

Тестирование и качество кода

Полная локальная проверка проекта:

./mvnw clean verify

Запуск только модульных тестов:

./mvnw test

Проверка форматирования и статический анализ:

./mvnw clean compile -am \
  spotless:check \
  modernizer:modernizer \
  spotbugs:check \
  pmd:check \
  pmd:cpd-check

Автоматическое форматирование:

./mvnw spotless:apply

Для black-box тестов сначала соберите JAR и Docker-образ, затем запустите тестовый раннер:

./mvnw clean package -DskipTests=true -Djacoco.skip=true
docker build -t app .
bash ./tests/run.sh tests/cases

Black-box набор проверяет вывод справки, валидацию координат, генерацию лабиринта и сохранение найденного решения.

Структура проекта

.
├── .github/workflows/ci.yml     # GitHub Actions workflow
├── src/main/java/academy        # исходный код приложения
├── src/test/java/academy        # модульные тесты
├── tests                        # black-box тесты и тестовый раннер
├── Dockerfile                   # образ для запуска приложения
├── pom.xml                      # конфигурация Maven
├── pmd.xml                      # правила PMD
└── spotbugs-excludes.xml        # исключения SpotBugs

Основные компоненты:

• academy.Application — точка входа и регистрация CLI-команд;
• academy.commands — обработка команд generate и solve;
• academy.maze.generators — реализации алгоритмов генерации;
• academy.maze.solvers — реализации алгоритмов поиска пути;
• academy.maze.util — разбор и отображение лабиринтов;
• academy.maze.dto — модель лабиринта, точек, пути и типов клеток.

Непрерывная интеграция

Workflow GitHub Actions запускается для push и pull request и последовательно выполняет:

1. проверку форматирования и статический анализ;
2. модульные тесты и Maven Verify;
3. сборку исполняемого JAR-файла;
4. сборку Docker-образа и black-box тесты.

Собранный project-1.0.jar сохраняется как артефакт workflow.