Алгоритмы генерации лабиринтов

Лабиринты — это не только самостоятельный класс игр, но и основа для создания локаций в играх других жанров: например, систем пещер, которые, в свою очередь, могут быть использованы в очень широком классе игр-бродилок и т.д. Однако если игроку придется постоянно «изучать» одни и те же локации, ему это может скоро надоесть, а потому перед разработчиками игр встает вопрос о процедурной генерации лабиринтов, т.е. чтобы каждое очередное прохождение игры проходило на заново сгенерированной территории.

Таких алгоритмов существует уже очень много, поэтому представленная нами подборка не претендует на полноту — в комментариях вы можете поделиться ссылками на известные вам способы генерации лабиринтов.

Лабиринты мы будем строить на прямоугольном клеточном поле (+ одна из статей о генерации в трехмерном пространстве), поэтому все их можно разделить на две группы: лабиринты с «тонкими» стенками и с «толстыми». Первые — это те, у которых стены расположены на границах клеток, вторые — это те, в которых некоторые клетки сами являются непроходимыми, т.е. стенами. Их отличает, например, способ хранения данных о карте.

Также существуют уже готовые решения для генерации лабиринтов: генератор Oblige, который используется в DOOM, DOOM II и Heretic, и др.

 Алгоритм Эллера

На тему генерации лабиринтов, где стенки расположены на границах клеток, на Хабре есть хороший перевод статьи «Eller’s Algorithm» (именно Эллера, а не Эйлера — «Eller’s», а не «Euler’s») о том, как создать идеальный (perfect) лабиринт — такой, что между любыми двумя его клетками существует путь, и притом единственный.

Общая идея алгоритма заключается в построчной генерации, где между каждыми двумя клетками строки при определенных условиях (чтобы не было циклов и недоступных клеток) случайным образом возникает стенка. При этом в конце все клетки окажутся «в одном множестве», что будет означать, что между каждыми двумя клетками существует путь.

Хранить карту лабиринта можно, например, в двух двумерных массивах: для вертикальных стенок и горизонтальных, соответственно.

Как хранить лабиринты с «толстыми» стенками?

Ответ на вопрос о хранении карт таких лабиринтов очевиден: в виде двумерного boolean массива, где, например, 1 — это непроходимая клетка (стена), 0 — свободная.

Подробнее о картах на клеточных полях написано в статье «Tilebased games». Теперь перейдем к самим лабиринтам генерации.

Наивный алгоритм

Естественно, возникают два вопроса: не будут ли комнаты пересекаться и как проложить между ними переходы? Ответ на первый вопрос зависит от ваших требований к лабиринту: если вы не хотите, чтобы комнаты пересекались, напишите функцию, которая проверяет пару комнат на пересечение и при появлении на карте очередной комнаты делайте проверку.

Подробнее об этом алгоритме (с примерами реализации) читайте в статье «Сreate a Procedurally Generated Dungeon Cave System».

Лабиринт на таблице

У описанного выше алгоритма есть один явный недостаток: проверять, пересекаются ли комнаты, приходится отдельной функцией. Возникает вопрос, можно ли не делать это лишнее действие. Оказывается, можно— и алгоритм описан ниже.

Идея заключается в том, что поле изначально разбивается на прямоугольные «большие» клетки (т.е. не элементарные клетки игрового поля, а прямоугольники, состоящие из нескольких клеток), образуя таким образом таблицу. Далее в каждой такой ячейке случайным образом появляется комната случайного размера, не превосходящая размеров ячейки — тем самым возможность появления пересекающихся помещений пропадает. Затем комнаты объединяются коридорами, например, тем же способом, что описано в предыдущем пункте.

Подробно этот алгоритм генерации описан в статье «Grid Based Dungeon Generator».

BSP деревья

BSP — это аббревиатура от Binary Space Partitioning — двоичное разделение пространства. Этот алгоритм также позволяет избежать пересечения комнат еще в процессе помещения их на карту, т.к. также предварительно делит игровое поле на части — «листья», внутри которых затем генерирует комнаты. Это деление площади идейно сложнее, т.к. разделяет все , чем предыдущий алгоритм, но и позволяет создать более интересные конфигурации расположения помещений.

Почитать подробнее о нем можно в статье «How to Use BSP Trees to Generate Game Maps».

Генерация лабиринтов с использованием клеточного автомата

Каждый программист хотя бы раз писал «Жизнь» — клеточный автомат, придуманный математиком Конвэем. Так почему бы не использовать схожую идею для генерации лабиринтов? Суть предложенного алгоритма состоит в реализации всего двух шагов: сначала все поле заполняется случайным образом стенами — т.е. для каждой клетки случайным образом определяется, будет ли она свободной или непроходимой — а затем несколько раз происходит обновление состояния карты в соответствии с условиями, похожими на условия рождения/смерти в «Жизни».

В источнике — на странице статьи «Generate Random Cave Levels Using Cellular Automata» — вы можете поэкспериментировать с интерактивной демкой, устанавливая различные значения для генерации: количество итераций обновления, граничные значения для жизни/смерти клетки и т.п. — и увидеть результат. Там же рассказывается о подводных камнях реализации.

Генерация в трехмерном пространстве

Каждый из модулей хранит информацию о своих входах и выходах, а также их ориентации: прежде чем соединить очередную пару элементарных частей, их нужно правильно ориентировать. В частности, автор предлагает хранить x-, y- и z- ориентацию модулей, чтобы затем соединять их по таким правилам: их y-оси должны совпадать, а x и z — иметь противоположное направление. Это, естественно, ставит вопрос о хранении информации о сгенерированной карте. Кроме того, не решена проблема с пересечением помещений — поэтому эта статья может являться лишь отправной точкой для исследования вопросов генерации трехмерных алгоритмов.

Что дальше?

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

Спасибо за внимание!