Проект генерирует лабиринты и осуществляет поиск пути в них. Приложение способно генерировать лабиринты различной сложности и размеров, а также предоставлять несколько методов поиска пути от заданной точки А (начала) к точке Б (конца). Лабиринт рисуется в виде псевдографики - на основе эмодзи.
!Разработка и тестирование проводилась в IDE Goland, приведенные скриншоты сделаны там же. В других консолях может произойти "съезд" псевдографики ввиду нестандартизированной ширины эмодзи.
- Реализация генерации лабиринта с помощью модифицированного алгоритма бинарного дерева.
- Реализация генерации лабиринта с помощью модифицированного алгоритма Прима.
- Реализация алгоритма Дейкстры для поиска кратчайшего пути из точки А в Б.
- Реализация алгоритма A* для поиска кратчайшего пути из точки А в Б.
- Отображение найденного пути через лабиринт при его наличии.
- Генерации "болот" в лабиринте - специальных клеток с большей "стоимостью" посещения. Стоимость выше в 5 раз чем у обычных клеток, поэтому нужно стараться избегать их при поиске кратчайшего пути.
Лабиринт представляет собой прямоугольник. Он состоит из стен, свободных проходов и болот. Все эти типы поверхностей являются эмодзи: ⬛, ⬜ и 🟩 соответственно. Через стены нельзя пройти во время решения лабиринта, через свободные проходы и болота пройти можно. Характеристика прохода через болото (время\расстояние) в 5 раз больше чем у свободного прохода. Это учитывается при поиске пути через две точки.
Так как разные типы поверхностей представляют собой различные веса, используется алгоритмы, которые эти веса учитывают - алгоритм Дейкстры и A*. При нахождении пути на изображение лабиринта добавляется путь, состоящий из символов 🟥.
Для генерации лабиринтов используются два алгоритма - алгоритм Прима и алгоритм двоичного дерева.
Модификация алгоритма Прима
В оригинальном алгоритме новая клетка соединяется только с одной посещенной. В этой реализации после каждого соединения есть вероятность, что продолжится проверка остальных соседей. В итоге новая клетка может быть соединена с несколькими открытыми клетками, что создает циклы, дает возможность генерации нескольких путей между двумя точками.
Модификация алгоритма бинарного дерева
В оригинальном алгоритме любая клетка соединяется только с соседом. В этой реализации очищается до четырех последовательных клеток. Из-за этого возникают дополнительные соединения, циклы, поэтому между двумя точками может генерироваться несколько путей.
Таким образом, программа находит кратчайший путь, если их несколько.
- Параметры лабиринта (ширина, высота).
- Настройки алгоритма генерации лабиринта.
- Начальная и конечная точки для поиска маршрута.
- Визуализация сгенерированного лабиринта в консоли.
- Путь от начальной до конечной точки, если таковой был найден, в виде визуализации.
- Выполнить:
go run .\cmd\run\main.go
В начале программа запрашивает высоту и ширину лабиринта. Из-за немного разного вывода лабиринтов с четной\нечетной размерностью высота и ширина включают в себя внешние стены.
После указание корректных размеров следует выбрать тип генерации лабиринта: a - модификация алгоритма бинарного дерева ; b - модификация алгоритма Прима.
Затем будет нарисован сгенерированный лабиринт, нужно будет указать координаты X, Y начальной и конечной точек. Следует считать, что отчет начинается с 0 (для Y - нижняя, для X - левая внешняя стены рисунка).
После этого исходный лабиринт будет нарисован с путем между выбранными точками. Для каждого из двух рисунков также будет указано, какой алгоритм искал путь.
