Дьявольский генератор: принципы создания уровней в Diablo

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

Автор блога BorisTheBrave.Com опубликовал текст, в котором разобрал принципы генерации уровней в Diablo. Он подробно описал особенности алгоритмов каждой отдельной главы, а также рассказал, через какие этапы проходит уровень, прежде чем его увидит игрок. Мы выбрали из разбора самое главное.

Diablo — классический hack and slash экшен-RPG 1996 года. Это была одна из первых попыток реализации механик роуглайков не в нише ASCII-игр, а в формате тайтла, предназначенного для широкой аудитории. Diablo известна тёмной, угрюмой атмосферой, которая усиливается, когда пользователь спускается в подземелья под городом Тристрамом.

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

Общие особенности

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

Каждый уровень игры генерируется так, чтобы заполнить сетку 40×40 тайлов. Ось X соответствует юго-востоку на карте, а ось Y — юго-западу. Эти тайлы фактически используются только для генерации уровней. Как только уровень создан, каждый тайл делится на четыре части для рендеринга.

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

В отличие от других игр серии, карты подземелий не собраны из предварительно созданных фрагментов. Почти всё делается на основе отдельных тайлов с помощью алгоритмов.

Процесс генерации подземелья делится на два этапа. Генерация ранней версии подземелья вообще не связана с подбором тайлов. Алгоритм просто создаёт схему, чтобы определить, можно ли пройти эту карту. Также на ней определяется местонахождение дверей и некоторых других деталей. Затем, на втором этапе, ранняя версия подземелья преобразуется в массив тайлов, а затем производится дальнейшая генерация и внесение изменений с учётом имеющихся тайлов.

Это должно быть очень удобно для дизайнера — можно разобраться с планом локации и не зависеть от выбора тайлов и определённой стилистики. При создании каждого уровня сперва создаётся база, которая в дальнейшем обрастает деталями. На сгенерированную основу добавляются предварительно созданные фрагменты уровня. Они используются для большинства квестов в игре.

The Butcher's Den — один из первых сетов, встречающихся в игре

Минисеты — ещё один способ добавления заранее созданного контента в уровень. Это небольшие паттерны размером примерно 3×3, которые случайным образом вставляются в подземелье. Существует простая схема сопоставления с образцом, так что они помещаются только в «правильные» позиции. Часто у них есть дополнительные требования, например, минисеты не могут быть расположены близко друг к другу, не могут перекрывать определённые фрагменты и так далее.

Минисеты применяются в Diablo для самых разных целей — для размещения более крупных объектов на основе тайлов, таких как лестницы; для фиксации комбинаций тайлов, которые неправильно соединяются друг с другом; добавления случайных вариаций к тайлам и так далее.

Также для формирования уровня применяются тематические комнаты — небольшие помещения, в которых есть лишь стены и двери. Обычно в них есть несколько случайных предустановленных объектов. Например, в библиотеках всегда есть книжный шкаф с двумя свечами, несколько случайных книжных полок и монстров. У каждой тематической комнаты есть определённые требования, которые влияют на генерацию.

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

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

Примером такого механизма может выступать функция «lockout» — она проверяет можно ли пройти через уровень. Если она находит ошибку, то генерация запускается по-новой.

Большинство квестов формируются с использованием наборов фрагментов, но некоторые имеют собственную логику. Например, «Zhar the Mad» генерирует в тематических комнатах библиотеки, вход «Poisoned Water» создаётся с помощью минисета, а «Anvil of Fury» имеет специальный код генерации уровней.

Собор

Собор, несомненно, является самой знаковой главой Diablo — всё благодаря длинным рядам готических арок, квадратным комнатам и другим элементам. Создание ранней версии уровня начинается с формирования общего представления карты. Генератор случайным образом расставляет три комнаты размером 10×10 в определённых местах по центру оси X или Y.

Широкий коридор также проведён вдоль оси, чтобы соединить комнаты. Если на этом уровне используется какой-то сет, он всегда находится в центре одной из этих комнат. В дальнейшем в эти комнаты не будут добавляться дополнительные стены, так как эти помещения должны представлять собой большое открытое пространство.

Все остальные комнаты генерируются с помощью рекурсивного метода «budding» в функции под названием L5roomGen, которая запускается в каждой из вышеуказанных комнат.

Работа L5roomGen:

• для генерации выбирается прямоугольник исходной комнаты и конкретная ось;
• есть шанс 1:4, что произойдёт смена оси между X и Y;
• выбирается случайный размер для новой комнаты: два, четыре или шесть тайлов с каждой стороны;
• для каждой стороны изначально выбранной комнаты вдоль оси (юго-восток/северо-запад для X, юго-запад/северо-восток для Y): прямоугольник новой комнаты выравнивается по центру края начальной комнаты; проверка того, что там ещё ничего не нарисовано, и не достигнут край карты; для стен требуется один тайл на границе; если проверка прошла успешно, то рисуется комната;
• для каждой нарисованной комнаты рекурсивно вызывается L5roomGen, которая передаёт в новую комнату ось, противоположную только что использованной.

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

После этого генератор подсчитывает количество сгенерированных тайлов, по которым можно пройти. Если оно не соответствует минимальному порогу, который увеличивается с каждым уровнем, подземелье создаётся заново.

На этом этапе уровень состоит из базовых тайлов, которые составляют пол и стены. Следующий шаг — замена их на настоящие тайлы стен. Для этого Diablo использует «движущиеся квадраты».

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

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

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

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

Затем генератор случайным образом добавляет разделительные стены. Перегородки всегда проходят прямо вдоль оси от одной стены до другой. В 25% случаев стена представляет собой серию арок, в 25% случаев — серию арок с решётками, закрывающими вход, а в остальном — сплошная стена. Для решёток и сплошных стен случайным образом добавляется дверь или арка, чтобы гарантировать, что эту преграду точно можно будет преодолеть.

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

Сгенерированный уровень собора

Катакомбы

В то время как собор выглядит как спроектированное здание, катакомбы воспринимаются скорее как нечто более случайное и хаотичное. Для них характерны квадратные комнаты, соединённые друг с другом лабиринтами извилистых коридоров. В катакомбах широкие проходы заменяют двери во многих местах, увеличивая вероятность того, что на игрока нападёт сразу много врагов.

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

Генерация главной комнаты происходит с помощью рекурсивного алгоритма. Функция CreateRoom учитывает всю область подземелья 40×40 тайлов, но игнорирует один тайл границы.

Работа CreateRoom:

• CreateRoom создаёт прямоугольную область, в которой формируются комнаты;
• если область слишком узкая, то нужно повторить первый шаг;
• далее выбирается случайный размер для комнаты от четырёх до девяти тайлов с каждой стороны, учитывая максимальный размер области, в которой можно разместить комнату;
• выбирается случайная позиция для комнаты;
• рисуется комната на карте ASCII. Рисунок использует «.» для тайлов пола, «#» для окружающей стены и «A», «B», «C», «E» для обозначения четырёх углов;
• если есть исходная комната: выбирается случайный тайл на ближайших сторонах исходной и новой комнаты; далее эта информация записывается для последующего использования;
• оставшиеся части области разделяются на четыре прямоугольника, исключая эту комнату;
• для каждого прямоугольника размер уменьшается на два тайла, чтобы обеспечить пространство между комнатами, затем рекурсивно запускается CreateRoom с этим прямоугольником в качестве области и созданной комнатой в качестве исходной.

После вызова CreateRoom появится карта ascii, которая будет похожа на следующий пример.

// пример уровня A##B #..# A####B #..# #....# #..# #....# C##E #....# C####E A#####B #.....# #.....# A########B #.....# #........# #.....# #........# C#####E #........# A#B #........# #.# #........# #.# #........# #.# #........# #.# #........# #.# C########E #.# #.# A#B C#E #.# A####B #.# #....# #.# #....# #.# #....# #.# C####E #.# #.# A#####B C#E #.....# A###B #.....# #...# #.....# C###E #.....# C#####E

В этом случае самая нижняя комната была «корневой» — она была создана изначально.

На этом этапе используется информация о коридорах — между записанной парой точек проводится линия. Когда она пересекает стену, пишется «D», а когда она пересекает сплошной тайл, применяется «,». Коридоры имеют ширину в один, два или три тайла. Угловые тайлы используются для облегчения навигации.

После того, как все залы созданы, ASCII очищается. Угловые тайлы превращаются в стены, а все соседние также становятся стенами. Наконец, «,» заменяется на «.». Далее представлен пример уровня на этом этапе.

// пример уровня #### #..# ###### #..# #....# #..# #....# #D## #....# #.# #D#### ##D#### #..# #.....# #..# ###.....# ##D######## #.D.....# #........# #.#.....# #........# ### #.##D#### #........# #.### #.##...# #........###.D.# #.##...# #........##..#.# #.##...# #........##..#.# #.##...# #........##..#.# #.##...# #........##..#.# #.##...# ###D#######..#.# #.##...# #.......#..#.# #.###D## ###.....#..### #.# #.# #######D##.# #.# #.# #....#.# #.# #.# #....D.# #.# #.# #....###### #.# #.# ##D####....## #.# #.# #...........# #.# #.# ####....###D####.# ### ######.....##.# #####.D.....##.# #...D.#.....D..# #####.#.....#### #########

Эта процедура может оставить на карте довольно много пустого места. Следовательно, следующее, что делает генератор, это «заполняет пустоты» — ищет любой смежный участок стены, к которому он может приклеить дополнительные прямоугольники пола. Прямоугольники должны быть не менее 5×5 и не более 12×14.

Заполнение пустот продолжается до тех пор, пока будет не менее 700 тайлов или не будет превышен порог повторной попытки. Если их количество не достигает 700, подземелье генерируется с нуля.

В итоге получается финальный вариант ранней версии уровня.

// пример уровня ########## #........# ########### #........# #.........# #........# #.........# #........# #.........# #### #........# #.........# #..# #######..###.........# #..# #..............# #..# #..............# #D## #..............# #.# #D####.........# ##D#### #..# ########### #.....# #..# ###.....# ##D######## #.D.....# #........# #.#.....# ########........# ### #.##D#### #...............# #.### #.##...# #...............###.D.# #.##...# #...............##..#.# #.##...# #...............##..#.# #.##...# #...............##..#.# #.##...# #...............##..#.# #.##...# #......###D#######..#.# #.##...# #......# #.......#..#.# #.###D## #......# ###.....#..### #.# #.# #......#########D##.# #.# #.# #.........# #....#.# #.# #.# #.........# #....D.# #.# #.# #.........# #....###### #.# #.# #.........# ##D####....## #.# #.# #.........# #...........# #.# #.# #.........# ####....###D####.# ### #.........# ######.....##.# #.........# #####.D.....##.# #.........# #...D.#.....D..# ########### #####.#.....#### #########

Опять же, катакомбы отходят от стандартной формулы уровня. Вместо того, чтобы использовать «движущиеся квадраты», существует специальная процедура сопоставления с образцом, которая сравнивает каждый прямоугольник 3×3 в ранней версии, чтобы определить соответствующий тайл в подземелье. Шаблоны указывают, должен ли каждый тайл ранней версии быть стеной, полом, дверью или какой-либо комбинацией вышеперечисленного.

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

Пещеры

В главе «Пещеры» игрок встречает широкие пространства и лавовые реки. Единственные прямолинейные элементы локации — деревянные доски. Эта глава производила очень хорошее впечатление, благодаря анимированной лаве и отличию от предшествующих уровней.

Локации в пещерах начинаются с одной случайной комнаты размером 2×2 где-то недалеко от центра карты. Затем вызывается процедура DRLG_L3CreateBlock на каждом краю этого блока.

Работа DRLG_L3CreateBlock:

• эта функция берёт ребро прямоугольника — начальную точку, направление и длину;
• размер нового блока между 3 и 4 на каждую сторону;
• новый блок выравнивается случайным образом по входной грани;
• если для создания блока нет места, то формируется выход;
• рисуется блок;
• в одном из четырёх случаев создаётся выход;
• рекурсивно запускается DRLG_L3CreateBlock с тремя рёбрами блока, отличными от того, через который персонаж вошёл.

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

После создания грубой формы подземелья, генератор запускает процедуры изменения:

• сначала он находит области тайлов 2×2, в которых два solid-тайла расположены по диагонали друг к другу. С этими формациями часто трудно разобраться при выполнении «движущихся квадратов», поэтому один из solid-тайлов случайным образом заменяется полом;
• любые одиночные solid-тайлы, окружённые восемью тайлами пола, заменяются на пол;
• если попадается слишком длинный участок сплошной стены, то 50% её тайлов заменяются на пол;
• затем во второй раз убираются диагонали.

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

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

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

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

Стена 3×3 превращается в лавовое озеро

Далее генератор делает несколько попыток нарисовать реку, которая начинается у озера лавы и заканчивается в стене. Требования состоят в том, что река должна иметь длину от 7 до 100 тайлов, и должно быть место, подходящее для размещения моста. Если это место найдено, то можно добавить от одной до четырёх рек.

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

Ад

Ад — это последняя глава Diablo, в которой акцент сделан на монстрах, а дизайн уровней отходит на второй план. В ней используется наименьший набор тайлов по сравнению с другими главами, и большая их часть используется для больших лестниц и пентаграмм. Уровни Ада, как правило, состоят из нескольких квадратных комнат, и в них применяется симметричная планировка.

Генерация Ада начинается со случайной комнаты размером от пяти до шести тайлов с каждой стороны (больше, если есть части квестового сета), затем применяется тот же рекурсивный алгоритм, что и в соборе. Генерация ограничена областью 20×20. Также есть вертикальный и горизонтальный коридор, простирающийся до края области.

Затем ранняя версия подземелья отражается по вертикали и горизонтали для увеличения пространства.

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

По итогам этого анализа можно сделать несколько выводов.

• Дьявол кроется в деталях — отдельные компоненты не являются безумно сложными, но они объединяются так, чтобы дать удивительный результат. Скорее всего разработчики продолжали улучшать качество генератора, пока уровни стали не просто хорошими, а удивительными. Количество тайлов и комбинаторная сложность сетов также очень велики — нельзя добиться хорошего результата без особого внимания к тому, как всё соединяется.
• Шаблоны поиска-замены очень эффективны, благодаря чему с ними можно создавать самые разные примечательные эффекты. 
• Разделение генерации подземелий на создание ранней версии подземелий и дальнейшую подстановку тайлов очень удобно как для проектирования, так и для проверки играбельности. 
• Если вы хотите придать нескольким областям разную специфику, написание отдельного алгоритма — отличный способ сделать это. Много кода можно использовать повторно, создавая совершенно другие впечатления. 

Источник