В этой статье я расскажу об алгоритме процедурной генерации лабиринтов методом поиска в глубину с возвратами (Randomized depth-first search with recursive backtracking). Предлагаю онлайн демо и свой код на github (javascript).

Работая над своим ремейком пакмана, я столкнулся с необходимостью создания множества уровней. Каждый раз делать их с нуля было утомительно и я задумался о процедурной генерации заготовок уровней. Я открыл Википедию, почитал об алгоритмах генерации лабиринтов, выбрал подходящий мне и реализовал его.

Описание алгоритма

Лабиринт представлен двухмерным массивом клеток. В начале работы алгоритма каждая клетка имеет 4 стены - сверху, справа, снизу и слева. Выбираем любую клетку, выбираем случайное направление (из допустимых, конечно). Удаляем стенку и двигаемся через образовавшийся проем в соседнюю клетку. Повторяем процесс до тех пор, пока можем двигаться (т.е. пока среди соседей текущей клетки есть еще непосещенные). Зайдя в тупик (кругом только посещенные клетки или края поля), шагаем в обратном направлении (backtracking) до тех пор, пока не обнаружим клетку, у которой есть ранее непосещавшиеся соседи. Таким образом, удаляя стенки и посещая новые клетки, мы обойдем все поле и получим лабиринт. Используя разные начальные значения генератора случайных чисел (seed), мы каждый раз можем получать разные лабиринты. Продемонстрирую наглядно действие алгоритма:

Итак, пошаговый алгоритм:

1. Выбрать любую начальную клетку, отметить ее как посещенную, отправить в стек

2. Пока стек не пуст:
   

   1. Достать из стека клетку и считать ее текущей

   2. Если среди четырех клеток, смежных с текущей, имеются те, которые еще не были посещены:
      

      1. Отправить текущую клетку в стек

      2. Случайным образом выбрать одну из соседних непосещенных клеток

      3. Удалить стенку между текущей и выбранной клеткой

      4. Отметить выбранную клетку как посещенную и отправить ее в стек

Алгоритм очень простой и дает хорошие результаты.

Онлайн демо