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