Генерация и решение лабиринта с помощью метода поиска в глубину по графу
В этой статье речь пойдет о самом простом в реализации алгоритме генерации «идеального» лабиринта и его применении для поиска пути.
Мы рассмотрим алгоритм, основанный на бэктрекинге, позволяющий создавать лабиринты без циклов, имеющие единственный путь между двумя точками. Алгоритм не самый быстрый, довольно требователен к ресурсам, по сравнению с алгоритмом Эйлера или Крускала, но очень прост в реализации и позволяет создавать ветвистые лабиринты с очень длинными тупиковыми ответвлениями.
Заинтересовавшихся — прошу под кат. В русскоязычном интернете очень мало информации по алгоритмам генерации лабиринтов, что и стало причиной для написания этой статьи. Примеры кода на языке Си, а также полный исходный код проекта на GitHub доступны под лицензией GNU GPLv3. Ссылки на англоязычные ресурсы и проект вы найдете в конце статьи.
Описание алгоритмаЗамечание: предполагается, что изначально у каждой клетки есть стенки со всех четырех сторон, которые отделяют ее от соседних клеток.
1. Сделайте начальную клетку текущей и отметьте ее как посещенную. 2. Пока есть непосещенные клетки 1. Если текущая клетка имеет непосещенных «соседей» 1. Протолкните текущую клетку в стек 2. Выберите случайную клетку из соседних 3. Уберите стенку между текущей клеткой и выбранной 4. Сделайте выбранную клетку текущей и отметьте ее как посещенную. 2. Иначе если стек не пуст 1. Выдерните клетку из стека 2. Сделайте ее текущей 3. Иначе 1. Выберите случайную непосещенную клетку, сделайте ее текущей и отметьте как посещенную.
Вы, вероятно, заметили что при выполнении условия 3, готовый лабиринт вероятнее всего будет иметь изолированную область. Это условие включено в алгоритм в порядке исключения, на практике при нормальной работе алгоритма и правильных исходных данных, оно не выполняется никогда.
РеализацияКак уже сказано выше, предполагается, что при начале работы алгоритма все клетки отделены стенками.
Иллюстрация работы алгоритма0. < — Начальная матрица.
1. < — Выбираем начальную точку стартовой.
2.1. < — Перемещаемся к случайному непосещенному соседу, пока таковые есть.
2.2. < — Непосещенных соседей нет. Возвращаемся назад по стеку, пока нет непосещенных соседей.
2.1. < — Непосещенные соседи есть. Перемещаемся к случайному непосещенному соседу.
2. < — Нет непосещенных клеток. Лабиринт сгенерирован.
Программный кодПриступаем к самому интересному.
Начнем действовать по порядку и сначала сгенерируем начальную матрицу, с которой будет работать алгоритм. Для удобства условимся, что все типы клеток заданы в перечислении.
Теперь, когда все приготовления сделаны, можно приступать к генерации.
Структуры значительно упростят жизнь при обмене информацией между функциями.
Отрывок кода, отвечающий за генерацию:
Как видно, реализация алгоритма проста и абстрактна от теории, как говорится, «справится даже ребенок». Чтобы не перегружать статью, код функций, используемых в вышеприведенном отрывке, под спойлером.
Функция getNeighbours возвращает массив непосещенных соседей клетки
Функция removeWall убирает стенку между двумя клетками:
Сначала вычисляется значение разности координат второй и первой точек. Очевидно, значение может быть либо отрицательное, либо положительное, либо 0.
Надо найти такие координаты xy, чтобы при сложении их с координатами первой точки получались координаты стенки.
Так как мы точно знаем, что вектор разности между координатами стенки и первой точке равен либо (|1|, 0) либо (0, |1|), мы можем этим воспользоваться.
Таким образом, аддитив для x координаты при xDiff != 0 будет равен xDiff / |xDiff|, при xDiff = 0, нулю. Для y соответственно. Получив аддитивы для x и y, мы легко вычисляем координаты стенки между первой и второй клетками и назначаем клетку по этим координатам посещенной.
Итак, теперь у нас есть генератор лабиринтов, который может строить запутанные лабиринты, размер которых ограничен только размером оперативной памяти.
В итоге, мы можем получить что-то такое:
Генерация работает, теперь дело за малым: найти в таком лабиринте выход.
Алгоритмов поиска пути несколько больше, чем алгоритмов генерации, и некоторые из них, если будет интерес читателей, я освещу в следующих статьях, но пока что будем довольствоваться тем, что есть, и «пройдем» лабиринт тем же алгоритмом.
И все еще сильнее упрощается, так как нам больше не надо убирать стенки.
Алгоритм поиска пути бэктрекингом: 1. Сделайте начальную клетку текущей и отметьте ее как посещенную. 2. Пока не найден выход 1. Если текущая клетка имеет непосещенных «соседей» 1. Протолкните текущую клетку в стек 2. Выберите случайную клетку из соседних 3. Сделайте выбранную клетку текущей и отметьте ее как посещенную. 2. Иначе если стек не пуст 1. Выдерните клетку из стека 2. Сделайте ее текущей 3. Иначе выхода нет
Выходной точкой, как и стартовой, может выступать любая точка лабиринта, не являющаяся стенкой. Традиционно, выход должен быть «прижат» к одной из стенок, но по сути может находиться где угодно. Все таки, в данном случае, «вход» и «выход» — всего лишь две точки, между которыми надо найти путь.
Критерий нахождения «выхода» очень прост: достаточно сравнить координаты текущей точки и координаты «выхода»: если они равны, путь между стартовой и выходной точками найден.
Посмотрим что вышло:
Красным обозначен путь, голубым — посещенные клетки. 100x100
Вот и все, что нужно для самой простой реализации генератора случайных лабиринтов.
Для тех, кто заинтересовался, полный исходный код проекта на GitHub: Maze Generator and Solver (offscreen rendering)