В этой статье я расскажу о том как генерировать рандомные лабиринты, используя рекурсивный алгоритм с возвратом. Этот алгоритм также может использоваться для решения других задач, которые связанны с неявными графами: судоку, комбинаторика и другие головоломки (например, задача о n ферзях).
Описание алгоритма в общих чертах:
Алгоритм Recursive backtracker - это метод систематического перебора всех возможных вариантов решения задачи, основанный на поиске в глубину (DFS).
Поэтапно, что делает алгоритм на примере графа:
Выбираем начальную вершину и делаем ее текущей.
Случайно выбираем следующую не посещенную вершину, в которую можно попасть из текущей.
Переходим на следующую вершину, обозначая ее как текущую. Предыдущую вершину обозначаем посещенной.
Повторяем предыдущие 2 шага до того момента, пока можно выбрать не посещенную вершину, в которую можно пойти из текущей.
Как только следующий ход из текущей вершины невозможен, возвращаемся в предыдущую и делаем ее текущей. Возвращаемся по проложенному пути до тех пор, пока из вершины нельзя будет пойти в еще не посещенную.
Алгоритм завершается, когда мы возвращаемся в начальную вершину и не можем из нее пойти ни в какую другую.
Примеры лабиринтов, которые получаются с помощью этого алгоритма:
Вы можете заметить, что на картинках выше некоторые лабиринты выглядят сильно по разному. Это происходит так как существуют несколько разных реализаций данного алгоритма и от выбора вариации принципиально зависит результат. В этой статье подробно описан способ, который позволит вам создать лабиринты, как на картинке 1 и 2. Но в конце статьи будет кратко описано, как реализовать данный алгоритм, чтобы получить результат как на 3ем фото.
Подробнее об установленной задаче:
До того как как писать код, думаю, стоит обговорить несколько деталей, чтобы в итоге не произошли недопонимания:
Итоговый лабиринт будет состоять из n * m клеток;
Мы создаем лабиринт без петель или замкнутых цепей, без недостижимых областей, также в нем из каждой точки существует ровно один путь к любой другой точке;
Представленное решение является рекурсивным и работает на явном графе; (Но если вам принципиально сэкономить время на построение, можно работать и с неявным графом, но тогда вероятность сделать ошибку в индексации сильно возрастает.)
Клетки поля - вершины, а переходы между ними – ребра;
Индексация начинается с 0.
как выглядит граф, построенный на основе заданного лабиринта Все структуры в этой реализации – двумерные. То есть вершина iая jая будет отвечать за клетку лабиринта в ряду i и колонне j. Пример на картинке. Клетка в лабиринте и вершина графа помечены одним зеленным цветом.
На схеме буквой «v» обозначены вершины, а также нарисованы ребра между вершинами.
Структура решения:
Весь код делится на несколько основных частей:
Создание графа;
Реализация алгоритма backtracker;
Функция проверки, которая вызывается в алгоритме;
Вывод лабиринта на экран/терминал (опционально).
Подробнее про каждый пункт:
Создание графа:
Предлагается хранить граф, как двумерный список смежности - g, так как это будет наиболее удобно в дальнейшем, при реализации алгоритма backtracker.
При построении, будем для каждой вершины проверять наличие соседей с 4 сторон и после, если соседи есть, будем обновлять список смежности. И это мы сделаем за O(n*m).
Построение лабиринта - алгоритм backtracker:
Этот этап посвящён конкретно построению лабиринта. Ранее в статье уже описана идея алгоритма, поэтому сейчас кратко о том, как он работает именно в ситуации с построением лабиринта.
Заведем двумерный массив used. В нем будем отмечать посещенные вершины. Изначально он будет заполен нулями, то есть все вершины еще не посещены. Забегая вперед, посещенные вершины станут пустотами, а не посещенные стенками нашего лабиринта.
Ближе к сути, рекурсивный обход будем делать так:
Отмечаем вершину в который мы находимся посещенной.
Перемащиваем список соседей нашей вершины. – g[i][j].
Проходимся по соседям, если можем пойти в вершину идем и за пускаемся уже из нее, если нет, не идем (о том, как это понять в следующем пункте).
Ниже приведен отрывок на языке Python, иллюстрирующий реализацию данной функции:
def backtracker(self, i: int, j: int): self.used[i][j] = 1 random.shuffle(self.g[i][j]) for u in self.g[i][j]: if self.check(u[0], u[1], i, j): self.backtracker(u[0], u[1])
Функция check - можем попасть в вершину или нет?
Данная часть кода достаточно объемная, при этом она очень интуитивно понятная. Чтобы осознать все условия нужно задать себе вопрос, какое состояние должно быть у клеток вокруг заданной, чтобы мы могли попасть из ячейки 1 в ячейку 2?
Что из важного:
1. Можно смотреть только на 8 клеток вокруг заданной.
2. Нам не важно закрашены или нет клетки номер 3 и 4.
3. Но нам важно, чтобы клетки, отмеченные зеленым, были НЕ закрашены (иначе появится цикл или другая недопустимая ситуация)
Поняв эти основные 3 факта, можно без проблем написать чекер. Мою реализацию можно посмотреть по ссылке в конце статьи. Не считаю, что ее стоит целиком прикреплять сюда, так как вариаций можно написать очень много, хотя в любом случае эта часть кода получается очень объемной. У меня это целых 30 строк кода...
Визуализация
Это, наверное, самый опциональный пункт. В моей реализации присутствует, как вывод в командную строку, так и возможность просмотра результата в формате картинки (используя PyGame). Думаю, единственное, что стоит напомнить - посещенные вершины станут пустотами, а не посещенные стенами лабиринта. А дальше все уже зависит от вашей фантазии!
Временная сложность решения:
Так как программа работает на явном графе, его нужно построить за O(n*m). Само построение лабиринта происходит в худшем случае за O(n*m) - т.е. мы посещаем все вершины. Остальными частями решения можно пренебречь и на выходе получается асимптотика O(n*m). При лабиринте из n*m клеток.
Варианты реализации:
Хотелось бы упомянуть, что помимо реализации через рекурсию, которая подробно описана в этой статье, есть способ реализации через стек (несмотря на то, что метод и называется рекурсивным). Вторая реализация работает немного быстрее, но специфично обрабатывает четные размеры. В ней часть клеток становиться "ребрами", часть "вершинами" и на выходе генерация лабиринта происходит с шагом в 2 клетки. Именно поэтому, как было сказано ранее, при разных реализациях получаются абсолютно разные лабиринты. Коды на языке Python с обеими реализациями вы можете найти на github:
рекурсивный способ здесь (подробно описанный в статье)
через стек здесь
Соавтор статьи: @NineTzy
