В этой статье я расскажу об алгоритме процедурной генерации лабиринтов методом поиска в глубину с возвратами (Randomized depth-first search with recursive backtracking). Предлагаю онлайн демо и свой код на github (javascript).
Работая над своим ремейком пакмана, я столкнулся с необходимостью создания множества уровней. Каждый раз делать их с нуля было утомительно и я задумался о процедурной генерации заготовок уровней. Я открыл Википедию, почитал об алгоритмах генерации лабиринтов, выбрал подходящий мне и реализовал его.
Алгоритм поиска в глубину (Depth-first search - DFS) является методом обхода графа, при котором применяется стратегия максимально возможного прохода в глубину графа, т.е. до тех пор, пока не будет достигнут тупик - вершина, не имеющая исходящих ребер, ведущих на ранее не рассматривавшиеся вершины. После достижения такой вершины алгоритм вновь применяется к следующей обрабатываемой вершине и так до тех пор, пока не будет перебран весь граф.
DFS имеет различные практические применения. Часто он используется для исследования топологических свойств графов, реже - как собственно поиск по древовидным структурам данных. Но в данной статье я опишу его применение для создания лабиринтов.
Рассмотрим задачу процедурной генерации случайного лабиринта в двухмерном пространстве. В этом случае лабиринт можно представить как двухмерный массив ячеек, каждая из которых взаимно связана с четырьмя смежными (выше, ниже, левее и правее). Две соседние ячейки могут иметь или не иметь стенку между ними. Совокупность этих стенок между ячейками и будет образовывать стены лабиринта, а сами ячейки, по сути, коридоры. Такой массив можно трактовать как граф: ячейки это вершины графа, связи между ними - ребра. А раз это граф, то ничто не мешает применить к нему рассматриваемый алгоритм.
Описание алгоритма
Лабиринт представлен двухмерным массивом клеток. В начале работы алгоритма каждая клетка имеет 4 стены - сверху, справа, снизу и слева. Выбираем любую клетку, выбираем случайное направление (из допустимых, конечно). Удаляем стенку и двигаемся через образовавшийся проем в соседнюю клетку. Повторяем процесс до тех пор, пока можем двигаться (т.е. пока среди соседей текущей клетки есть еще непосещенные). Зайдя в тупик (кругом только посещенные клетки или края поля), шагаем в обратном направлении (backtracking) до тех пор, пока не обнаружим клетку, у которой есть ранее непосещавшиеся соседи. Таким образом, удаляя стенки и посещая новые клетки, мы обойдем все поле и получим лабиринт. Используя разные начальные значения генератора случайных чисел (seed), мы каждый раз можем получать разные лабиринты. Продемонстрирую наглядно действие алгоритма:
Итак, пошаговый алгоритм:
Выбрать любую начальную клетку, отметить ее как посещенную, отправить в стек
Пока стек не пуст:
Достать из стека клетку и считать ее текущей
Если среди четырех клеток, смежных с текущей, имеются те, которые еще не были посещены:
Отправить текущую клетку в стек
Случайным образом выбрать одну из соседних непосещенных клеток
Удалить стенку между текущей и выбранной клеткой
Отметить выбранную клетку как посещенную и отправить ее в стек
Алгоритм очень простой и дает хорошие результаты.
Онлайн демо
UPD: выложил видео создания уровня для своего ремейка пакмана: https://youtu.be/mSg91TbagjE . В самом начале виден процесс генерации основы для уровня. Используется встроенный в редактор алгоритм из этой статьи.
