Контент-ориентированная генерация уровня в Unity в конкурсе «Храм Хаоса»

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

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

Пролог

Сначала был массив…

Нет, сначала конечно же был вопрос самому себе — зачем мне это?  С этим вопросом я обратился к интернету. И бездушная машина выдала мне ответ: процедурная генерация уровней — вопрос достаточно старый и обсосанный, чтобы давать конкретные ответы.

Конечно же, миллион статей я все же нашел. И, по правде сказать, они были довольно интересные. Множество техник, философские рассуждения на тему «процедурщина, какая бы ни была, не заменит дизайнера», споры и срачи в комментариях. Все это было живо и весело, пока дело не дошло до математики. Времени на курсы матана и линейки у меня не было, знания 15-летней давности давно иссякли, поэтому я пошел по пути простого поиска готовых решений на любом псевдоязыке, дабы потом перевести это все на С#. И тут начинается настоящее приключение.

Классика жанра

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

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

И есть одно общее, можно сказать, один мегаэлемент, объединяющий абсолютно все алгоритмы и методы генерации. Это МАССИВ. Чаще двумерный, в отдельных упоротых случаях — многомерный. Массив, задача которого хранить нагенеренные позиции зон. В классическом данжен-генераторе значения элементов в массиве это 0 и 1, стена или пол, а индексы — координаты зоны в пространстве. В лабиринтах зачастую чуток сложнее, но за рамки квадратного массива это не выходит.

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

Это обстоятельство поначалу никак не заботило меня. Моя задача была — запустить хоть какую-то генерацию. Я планировал сделать ряд вложенных генераторов, дабы усложнить уровень, но…

Первая попытка. Печальная

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

Я взял за основу один из многочисленных алгоритмов данжен-генератора. Смысла его описывать здесь не вижу, их много, и я взял тот, который уже был написан на С#, и мне оставалось лишь незначительно переписать его под Unity — варимый вариант.

Я планировал так.  Первый проход алгоритма — глобальный генератор — создает макро-уровень, где каждый элемент массива — зона 100х100 юнитов (префаб). 1 — зона, заполненная «зданием», 0 — пустая зона улицы. Далее, каждая зона «здания» внутри себя запускает свой генератор, который расставляет зоны поменьше (допустим 20х20), но с другими префабами, которые представляли собой либо комнаты (1), либо проходы без стен (0). Помимо всего прочего, каждый префаб комнат и проходов тоже мог содержать в себе генератор пропсов, но уже без особых алгоритмов.

Как выяснилось позже, на живых тестах демки — все было плохо. Генерировалось все хорошо, но фрактализация была жуткая, occlusion culling всего этого работал плохо, отчего тормозило безоговорочно сильно. В конце концов, я добавил поворот на рандомный угол каждой мегазоны, что поначалу показалось мне интересным, но превратило игру еще в большую кашу…

Я отчаялся. Отчаялся и начал думать…

Пытки разума

Думал я мучительно. Смотрел десятки видео, читал статейки. Но везде у меня приходило в голову одно и то же — «это все не то!». Я вспомнил главного рандом-монстра игровой истории — Diablo. Вспомнил как круто все там было, как здорово, мегарандомно, но и мега-слажено одновременно. И вдруг я стал понимать. В Дьябле все было круто, потому что игра была — изометрия про данжены!

Но у меня — экшен! Да еще и из головы (FPS)! И в памяти начал всплывать угарный угар, в который я долго рубался давным давно — многими противоречиво любимо-ненавидимый Hellgate. Точной информации о методах генерации уровней в Хеллгейте всемирный разум мне не дал (возможно, я плохо искал), но вспоминая уровни, я начал, похоже, догадываться, что мне нужно делать для экшена. Так начали проявляться первые наброски идеи под названием CBLG (Content-Based Level Generator).

Чё за кантент, ё?

Казалось бы, при чем тут контент? Ответ на этот вопрос будет немного ниже.

А начну я с другого. Что мы знаем об экшенах? Особенно о современных экшенах, старых консольных экшенах? В основном то, что мы бежим по коридорам и комнатам, стреляем врагов, ищем ключи… Мы знаем, что в экшенах нет сетчатых уровней, лабиринтов в классике, где коридоры имеют шаг, углы 90 градусов, а комнаты статичны и пропорциональны. В экшенах окружающий нас контент — многообразен. Однообразие Вольфенштейна закончилось вместе с ним. А значит, генерация блоками здесь уже неуместна.  Нужно, чтобы коридоры были кривыми, разной длины, комнаты были любой геометрии. Были спуски, подъемы, ямы, непонятные формы пола и потолка.

Становится ясно, что реализация всего этого классическими массивами становится затруднительной, где-то даже сомнительной затеей. Что же тогда? Как генерировать? Ведь тогда генерация каждого последующего элемента геометрии уровня должна зависеть от предыдущего? То есть генерация контента должна быть в прямой и абсолютной зависимости от самого контента!

Вот оно! Решение!

Основа

Любой коридор имеет вход и выход. Любая комната имеет вход и выход, даже несколько. Всё, во что мы можем войти, имеет место, откуда мы входим — начало. И если это не тупик — имеет выход — конец. Если мы выходим «откуда-то», то мы входим в новое «куда-то». То есть 

конец одного места совмещен с началом другого места

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

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

Симуляция на пальцах

Префабы в Юнити — пожалуй, самая полезная из доступных штук. Они лучше всего подходят к нашей задаче. Максимально. Если бы их не было — их пришлось бы придумать 🙂 

Итак, пусть у нас есть 2 префаба геометрии уровня: коридор и комната. У каждого префаба есть «вход» — для удобства работы вход — это точка (0, 0, 0) внутри префаба, относительно которой строится вся геометрия. Обычно это уровень пола, центр дверного проема, а дальше вся геометрия строится вдоль оси Z в положительную сторону, при этом в высоту и ширину (Y и X) в любые стороны. Но Z — строго от нуля и вперед!

Это первый важный элемент нашей системы. Вход в зону — всегда (0, 0, 0)!

Набросок расположений входов и выходов

Далее, мы создаем объект (префаб) под названием zoneExit, ставим в него пару примитивов, симулируя визуально стрелочку вдоль оси Z. Задача — конец стрелочки внутри префаба zoneExit должен находиться в точке (0, 0, 0), сама стрелочка тянется вдоль оси Z от минуса к нулю. По X и по Y — строго по нулям! Это нужно нам для визуальной ориентации выхода из зоны и последующего использования этой ориентации в генераторе.

Префаб zoneExit

Также, для собственного удобства и контроля, сделаем префаб zoneEntry. Он не участвует в генераторе и его можно потом удалить вообще. Но он помогает контролировать точку входа при создании нового префаба зоны, чтобы не потерять из виду (0, 0, 0) в пылу дизайнерской страсти. Этот префаб — точная противоположность zoneExit-а. Он начинается строго в (0, 0, 0), и тянется вдоль Z вперед, представляя собой какую-нибудь узнаваемую фигуру:

Префаб zoneEntry

Его мы размещаем в наших префабах зон строго в 0.0.0 и направлении forward (Z), строим дальше всю зону исключительно в положительной плоскости по Z (по X и Y при этом ограничений нет)

Размещаем  zoneExit-ы  в наших префабах зон так, чтобы начало предполагаемой последующей зоны встало именно так, как нам нужно. Мы знаем одно — кончик «стрелочки» zoneExit, её originPoint, по замыслу совпадет с (0, 0, 0) новой зоны, а направление нашей стрелочки — укажет ориентацию следующей зоны относительно выхода этой. Я для простоты вращал exitPoint-ы только по Y, это и логично — смысла следующий коридор наклонять относительно горизонта нет. Мы же бегать хотим 🙂

Если мы правильно все поставили, то в результате генерации зоны скрепятся довольно точно:

И в зависимости от того, на какой угол по Y была повернута zoneExit — наш генератор возьмет этот угол за основу и повернет следующую зону на него же:

Таким образом, в зависимости от положения zoneExit-ов в каждом префабе зоны — у нас будет строится несетчатая и довольно разнообразная геометрия уровня. Все будет зависеть ТОЛЬКО ОТ количества разнообразных префабов зон!

Чуете? Content-Based!

Дальше — Больше!

Вся суть генератора — в отсутствии единого генератора как такового. Главный участник генерации у нас — префаб генератора зоны. Он не содержит геометрии, только скрипт генератора одной (!) зоны. После появления, он создает из массива префабов в его свойствах случайный префаб зоны себе в дочерние объекты, обходит все его zoneExit-ы, с некоторой вероятностью создает в них свои копии, указывая им position и rotation соответствующих exitZone-ов, и замолкает. Первый префаб мы кладем просто на уровень в глобальную точку (0, 0, 0). У меня к ней придвинута статичная зона джунглей, где стартует игрок.

Ограничение на размер уровня хранится в глобальной переменной maxZonesCount, а также каждый префаб инкрементирует глобальный счетчик zonesCount в случае, если он не превысит максимальный предел. Если следующая зона должна быть последней ( текущее значение zonesCount == maxZonesCount-1), то префаб вместо следующей зоны генерит Финальную Зону (зону босса например, или как в моей игре — зону с дверью, от которой нужно найти ключи), инкрементирует zonesCount последний раз, и дальше остальные префабы уже не могут ничего строить. В силу невозможности определения последовательности отработки скриптов в инстансах — все происходит достаточно случайно и зона босса может появиться где угодно.

Генерация почти закончена. Однако, в силу описанного выше механизма «вероятности» создания на месте zoneExit-а нового префаба (типа RandomRange(0,5)>6), не все zoneExit-ы будут обработаны их генераторами для генерации в них следующих зон. Поэтому на сцене останется много свободных неудаленных zoneExit-ов — по сути, дырок в пустоту. Вот как раз префаб финальной зоны (босса) их всех соберет и создаст на них тупиковые зоны (это могут быть тупики, комнаты с лутом, секреты — все что угодно, что не имеет выхода. Даже комнаты с порталами). Согласно удобным инструментам Unity, все zoneExit-ы имеют тэг «zoneExit», по которому финальная зона их и находит, и, согласно такому же алгоритму позиционирования, как и основном генераторе, создает на их месте зоны тупиков.

Всё, генерация геометрии завершена. Но на этом процесс не заканчивается…

Наполняем геометрию

Каждый префаб зоны у нас определяет только геометрию — стены, пол, иногда потолок. Но нам же интересно, чтобы было еще и визуальное разнообразие! Поэтому для каждого префаба зоны мы делаем кучу префабов пропсов. Я их все строю в редакторе прямо внутри префаба, расставляю так, чтобы потом спавнить префаб пропсов прямо внутри префаба геометрии — и все стояло на своих местах. В игре у меня 5—6 префабов окружения для каждого типа зоны. Простейший скрипт propsSpawner в каждом префабе геометрии содержит паблик-массив префабов наборов пропсов, задача его — создать случайный из них себе в дочерний объект. То же самое с врагами.

И опять — чем больше разнообразных префабов — тем разнообразнее генерация!

Не все так радужно

Ну и о минусах. Без них ничего не бывает.

Во-первых, главный минус нужно много контента. Чем больше — тем лучше, разнообразие будет зависеть от этого сильно. На то оно и Content-Based.

Во-вторых, это все еще существующая проблема перекрытия зон. В принципе, она решаема. Я планировал добавить каждому префабу зоны объект-контроллер с колижин-боксом, покрывающим весь префаб и в случае, если при генерации два таких объекта пересеклись — перезапускать всю генерацию заново. Это увеличит время «загрузки» уровня, но все же позволит полностью избавиться от проблемы. У себя же я частично решил это введя длиииииинные спуски вниз, чтобы развести зоны по вертикали друг от друга.

В-третьих, это уже моя личная проблема — разобраться с навмешами внутри этих префабов, а так же с offmesh-links для того, чтобы враги умели гнаться за тобой между зонами. Но это уже личные мелочи. У меня враги дальше зоны префаба не выбегают…

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

Ну и конечно же, данный вопрос не закрыт и буду рад обсудить свои ошибки с вами.

Метки: , , , ,