Контент-ориентированная генерация уровня в Unity в конкурсе «Храм Хаоса»
Автор: Mike Pathetic
Я, как и обещал, делюсь своими идеями насчет процедурной генерации уровней. Все то, что я опишу далее, ни в коем разе не претендует на истину, новаторство и, тем более, на что-то амбициозно-гениальное. Все это родилось лишь из непонимания общепринятых принципов современной процедурщины и математики, а также жгучего желания облегчить себе жизнь.
Описаный мною подход к генерации помимо очевидных плюсов имеет и ряд жестких минусов. Так что идеальным его, конечно, не назовешь. Но, идеальных методов и не существует. Этот подход я использовал в своей недоделанной игре, которая была создана на конкурс «Храм Хаоса».
Пролог
Сначала был массив…
Нет, сначала конечно же был вопрос самому себе — зачем мне это? С этим вопросом я обратился к интернету. И бездушная машина выдала мне ответ: процедурная генерация уровней — вопрос достаточно старый и обсосанный, чтобы давать конкретные ответы.
Нет, миллион статей все же я нашел. И, по правде сказать, они были довольно интересные. Множество техник, философские рассуждения на тему «процедурщина, какая бы ни была, не заменит дизайнера», споры и срачи в комментариях. Все это было живо и весело, пока дело не дошло до математики. Времени на курсы матана и линейки у меня не было, поэтому я пошел по пути простого поиска готовых решений на любом псевдоязыке, дабы потом перевести это все на С#. И тут начинается настоящее приключение.
Классика жанра.
Так уж вышло, что почти все процедурные генераторы уровней сводятся к двум параллелям: процедурные лабиринты и процедурные данжены. Думаю, определение обоих понятий понятны и без особых иллюстраций. Лабиринты — фактически это куча коридоров, разделенных стенами. Дажены — это массивы блоков, либо заполненных (стена), либо пустых (пол). В принципе, все алгоритмы так или иначе эксплуатируют одну из этих двух параллелей (либо совмещают их). Классические подходы к генерации — это как раз совмещение обоих вариантов, когда в несколько проходов генерируется лабиринт, затем частично в стиле данжен-генераторов лабиринт заполняется либо большими помещениями (комнатами), либо непроходимыми темными зонами стен.
Сейчас в меня, возможно , начнут кидать тухлыми яйцами с ссылками на алгоритмы. Но подумайте глубже — ведь все они так и сделаны.
И есть одно общее, можно сказать, один мегаэлемент, объединяющий абсолютно все алгоритмы и методы генерации. Это МАССИВ. Чаще двумерный, в отдельных упоротых случаях — многомерный. Массив, задача которого хранить нагенерённые позиции зон. В классическом данжен-генераторе значения элементов в массиве это 0 и 1, стена или пол, а индексы — координаты зоны в пространстве. В лабиринтах зачастую чуток сложнее, но за рамки квадратного массива это не выходит.
У этих подходов, при всех их несомненных плюсах, есть одно НО. Массив всегда квадратный (если его искусственно не обрезают), а элемент массива представляет собой одну зону одинакового размера с остальными. То есть как бы мы сложно не задействовали алгоритмы генерации — базовый строительный элемент у нас всегда одного размера, да и чаще всего квадратный (ну или многоугольник с четным количеством граней).
Это обстоятельство поначалу никак не заботило меня. Моя задача была — запустить хоть какую-то генерацию. Я планировал сделать ряд вложенных генераторов, дабы усложнить уровень, но…
Первая попытка. Печальная.
Но, забегая вперед, скажу, что это привело лишь к убогой фрактализации всего. И это было отвратительно.
Я взял за основу один из многочисленных алгоритмов данжен-генератора. Смысла его описывать здесь не вижу, их много, и я взял тот, который уже был написан на С#, и мне оставалось лишь незначительно переписать его под Юнити-варимый вариант.
Я планировал так. Первый проход алгоритма — глобальный генератор — создает макро-уровень, где каждый элемент массива — зона 100х100 юнитов (префаб). 1 — зона, заполненная «зданием», 0 — пустая зона улицы. Далее, каждая зона «здания» внутри себя запускает свой генератор, который расставляет зоны поменьше (допустим 20х20), но с другими префабами, которые представляли собой либо комнаты (1), либо проходы без стен (0). Помимо всего прочего, каждый префаб комнат и проходов тоже мог содержать в себе генератор пропсов, но уже без особых алгоритмов.
Как мы помним из моей первой демки — все было плохо. Генерилось все хорошо, но фрактализация была жуткая, occlusion culling всего этого работал плохо, отчего тормозило дико. В конце концов, я добавил поворот на рандомный угол каждой мегазоны, что поначалу показалось мне интересным, но превратило игру еще в большую кашу…
Я отчаялся. Отчаялся и начал думать…
Пытки разума
Думал я мучительно. Смотрел кучу видосиков, читал статейки. Но везде у меня приходило в голову одно и то же — «это все не то!». Я вспомнил главного рандом-монстра игровой истории — Дьяблу. Вспомнил как круто все там было, как здорово, мегарандомно, но и мега-слажено одновременно. И вдруг я стал понимать. В Дьябле все было круто потому что игра была — изометрия про данжены!
Но у меня — экшен! Да еще и из головы! И в памяти начал всплывать угарный угар, в который я долго рубался давным давно — многими противоречиво любимо-ненавидимый Хеллгейт. Точной информации о методах генерации уровней в Хеллгейте всемирный разум мне не дал (возможно, я плохо искал), но вспоминая уровни, я начал, похоже, догадываться, что мне нужно делать для экшена. Так начали проявляться первые наброски идеи под названием CBLG (Content-Based Level Generator).
Чё за кантент, ё?
Казалось бы, при чем тут контент? Ответ на этот вопрос будет немного ниже.
А начну я с другого. Что мы знаем об экшенах? Особенно о современных экшенах, старых консольных экшенах? В основном то, что мы бежим по коридорам и комнатам, стреляем врагов, ищем ключи… Мы знаем, что в экшенах нет сетчатых уровней, лабиринтов в классике, где коридоры имеют шаг, углы 90 градусов, а комнаты статичны и пропорциональны. В экшенах окружающий нас контент — многообразен. Однообразие Вольфенштейна закончилось вместе с ним. А значит, генерация блоками здесь уже неуместна. Нужно, чтобы коридоры были кривыми, разной длины, комнаты были любой геометрии. Были спуски, подъемы, ямы, непонятные формы пола и потолка.
Становится ясно, что реализация всего этого массивами становится затруднительной, где-то даже сомнительной затеей. Что же тогда? Как гененировать? Ведь тогда генерация каждого последующего элемента геометрии уровня должна зависеть от предыдущего? То есть генерация контента должна быть в прямой и абсолютной зависимости от самого контента!
Вот оно! Решение!
Основа
Любой коридор имеет вход и выход. Любая комната имеет вход и выход, даже несколько. Всё, во что мы можем войти, имеет место, откуда мы входим — начало. И если это не тупик — имеет выход — конец. Если мы выходим «откуда-то», то мы входим в новое «куда-то». То есть конец одного места совмещен с началом другого места.
Неважно, коридор это, комната, улица — везде в шутерах есть входы и выходы. главное — их совместить. Только их. Конкретные точки в пространстве! Зная, где расположены эти точки, нам уже, по большому счету, неважно ни размер зоны, ни форма, ничего. Важно только где у зоны выход и где у следующей зоны вход.
Для упрощения задачи, примем за правило, что у зоны может быть один (и только один!) «вход» и сколь угодно выходов. Останется лишь правильно сорентировать следующую зону в пространстве относительно выхода предыдущей. И в этом деле Unity — очень большой молодец :)
Симуляция на пальцах
Префабы в Юнити — пожалуй, самая полезная из доступных штук. Они лучше всего подходят к нашей задаче. Максимально. Если бы их не было — их пришлось бы придумать :)
Итак, пусть у нас есть 2 префаба геометрии уровня: коридор и комната. У каждого префаба есть «вход» — для удобства работы вход — это точка
Это первый важный элемент нашей системы. Вход в зону — всегда
