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


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


Внимание! Под катом много текста и "жирных" гифок.


Вводная


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


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


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



Я решил начать с последних двух — они просто реализуются, и дают хорошие результаты.


Структура генератора


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


  1. Генерация изначальной геометрии (на выбор — или "BSP", или планировка помещений).
  2. Очистка от мусорных секций (таких секций, которые не могут существовать в игре).
  3. Построение соединений.
  4. Очистка от мусорных подграфов (таких групп секций, которые соединены между собой, но нет соединения с оставшимися секциями).
  5. Очистка от излишних соединений (построение остовного дерева, ссылка дана на минимальное остовное дерево, т.к. там есть картинка, но для генератора нет нужды именно в минимальном).
  6. Рандомизация соединений — восстановление обратно некоторых удалённых соединений (для более "человеческого" вида уровня), а также превращение некоторых других в проходы между секциями (что "сливает" несколько секций в одну, более сложной формы).
  7. Генерация секретных комнат.
  8. Генерация "сценария" (где будет начальная и конечная секция, и какой путь надо будет пройти, чтоб из начальной дойти в конечную).
  9. Оптимизация соединений.
  10. Создание дверей и окон.
  11. Выбор действия, которое надо будет выполнить в этой секции (нажать на переключатель, поднять ключ или найти секретную стену).

Есть ещё где-то 12 пунктов, но они пока не доделаны (когда доделаю, напишу про них отдельный пост).


Генерация изначальной геометрии: "BSP"



За основу был взят вот этот перевод. Я не уверен насколько то, что происходит в этом алгоритме близко к настоящему BSP, поэтому пишу "BSP" в кавычках.


Алгоритм достаточно прост. Изначально создаём прямоугольник, размером со всё игровое поле:



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



Рекурсивно проделываем тоже самое для новых прямоугольников:



И ещё раз и ещё раз, до некоторого предела:



Потом в каждом прямоугольнике выбираем "комнату" — прямоугольник такого же размера как исходный или меньшего (но не меньше, чем 3x3 — более детально об этом будет ниже).



Потом комнаты соединяются коридорами. Но не каждая с каждой, а несколько хитро, из-за того они хранятся в "BSP"-подобной структуре (для более подробных деталей смотрите оригинальный алгоритм).



Коридор, соединяющий фиолетовую и белую секции.


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


Кроме того, если комната (на рисунке — бирюзовая) пересекает коридор, то она должна делить его на две разные секции (поэтому один и тот же коридор может отрисовываться разными цветами):



И вот что получается в итоге:



Дальше начинается фаза пометки мусорных клеток:



Как я уже писал, никакой сектор не может быть меньше, чем 3x3 клетки. Это из-за того, что сектор обязательно должен быть окружен стенами (как минимум по 1 клетке с каждой стороны), и в нём как минимум должна быть одна клетка свободного пространства:



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


Вместо этого, для каждой помеченной клетки ищется тот сектор, к которому она может примкнуть (соблюдая правило 3x3):



Если клетку так и не удаётся отнести к какому-либо сектору, она удалятся (но не в этом случае — тут всё хорошо).


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



Генерация изначальной геометрии: планировка помещений



За основу была взята другая статья. Этот алгоритм несколько сложнее предыдущего, но тоже не rocket science.


Для начала игровое поле заполняется неким стоп-значением, а затем случайным образом на нём очищается прямоугольная область:



Этап очистки случайного прямоугольника проводится ещё некоторое (тоже случайное) количество раз, и в результате получаются внешние контуры уровня:



В свободном пространстве случайно раскидываются точки роста комнат (минимальный размер комнаты — 3x3):



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



Затем комнаты преобразовываются в полибоксы:



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


В результате получается полностью заполненное пространство:



Далее полибоксы отрисовываются в виде растра, и (как и в случае "BSP"-генератора) начинается этап пометки "мусорных" клеток:



И присоединения их к существующим секторам:



Тут не удалось присоединить все клетки — лишние были удалены.


Результат обратно превращается в полибоксы:



Очистка от мусорных секций


Иногда возникают такие секции, внутри которых не соблюдается правило 3x3:



Можно попытаться такие секции "восстановить", но я пошёл по более простому пути, и просто их удаляю:



Построение соединений



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


Очистка от мусорных подграфов


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



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


Очистка от излишних соединений


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



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


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


Рандомизация соединений



Здесь и далее иллюстрации пойдут из другой генерации, т.к. в предыдущей была ошибка в генераторе, из-за которой дальнейшие картинки были некорректными.


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


  1. Некоторые удалённые рёбра восстанавливаются.
  2. А некоторые превращаются в проходы.

Дальше те секции, между которыми образовались проходы, "сливаются" в одну:



Если вам показалось, что на этой иллюстрации вновь появились удалённые на предыдущем шаге соединения — вам показалось :). Когда я вычитывал текст, мне тоже так показалось, но внимательно присмотревшись к предыдущей иллюстрации становится понятно, что всё ок.


Генерация секретных комнат


На графе выбираются такие сектора, у которых есть только одно соединение:



Если таких секторов будет несколько, то они все собираются в массив, и сортируются по "площади". Затем этот массив обрезается случайным образом (но так, чтоб в нём остался хоть один элемент). Эти сектора и станут секретными комнатами:



Генерация "сценария"



Вначале выбираются сектора, с минимальным количеством свободных соединений (т.е. такие, которые ближе к "краю" графа):



На этой иллюстрации выбран один сектор, но, если бы их было больше — всё равно был бы выбран какой-то один (случайным образом).


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


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



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


NB. Во время вычитки статьи, мне показалось, что условие наличия только одного соединения — слишком строгое, достаточно было бы того же, что и на прошлом шаге — чтоб после удаления этого сектора, граф бы не распался.


Далее этому списку секторов назначается номер сценария (просто число, на этом этапе оно ничего конкретного не значит), а соединения на границах этого списка секторов помечаются как закрытые этим сценарием.



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


Дальше выбирается очередной сектор, составляется список, и этот список помечается новым сценарием:



Обратите внимание на маленькие синенькие точечки внутри красных квадратиков — так отрисовывается scenario opener — т.е. где-то внутри секции с красным сценарием будет находиться ключ или переключатель, который откроет проход к секторам с синим сценарием.


Так продолжается до тех пор, пока не останется свободных секторов:



Самому последнему сектору не присваивается сценарий, а только scenario opener. Этот сектор будет тем сектором, в котором игрок начнёт игру.


Для этого уровня:


  • Игрок начинает в стартовом секторе, где-то там находит "открывашку" к желтому сектору, идёт туда.
  • В желтом секторе открывает голубой сектор, идёт туда.
  • В голубом секторе открывает зелёный, идёт туда.
  • В зелёном секторе открывает фиолетовый, идёт туда.
  • В фиолетовом открывает красный.
  • В красном — синий.
  • Где и находит переключатель конца уровня.

Схематически это можно показать так:



"Открывашка" может быть как ключом или переключателем, так и чем-то иным, например, заданием уничтожить всех врагов в каком-либо секторе (но я не планирую, что в ближайшее время генератор или движок станет такое поддерживать).


Оптимизация соединений



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


Создание дверей и окон



Для каждого сектора просматриваются все его соединения (которые после предыдущего шага смотрят только в одну сторону), и на каждом просмотренном соединении размещаются двери и окна.


  • Вначале выбирается точка на соединении, желательно ближе к центру.
  • Затем в этой точке размещается либо дверь, либо окно (а если это соединение к секретной комнате, то секретная стена).
  • Если размещается дверь, то она может быть от 1-й до 3-х клеток размером (одна — обычная дверь, две или три — толстая гермодверь, которая открывается после нажатия на какой-нибудь переключатель).
  • Дальше соединение разбивается на две части — часть перед выбранной точкой, и часть после. И, если либо перед, либо после осталось место, то функция вызывается рекурсивно.

Чтоб уровень выглядел более интересно, на разных шагах разная вероятность размещения двери или окна:


  1. На первом шаге обязательно размещается дверь, т.к. что толку от соединения, если там одни окна.
  2. На втором шаге c большей вероятностью (75%) размещается окно, чем дверь.
  3. Если есть третий шаг (например, соединение длинное), то на нём обязательно размещается окно.
  4. В случае 4-го шага дверь либо окно размещаются равновероятно.
  5. Если соединение экстра длинное, генератор возвращается ко второму шагу.

Выбор действия


Хоть это и не имеет отношения к генерации, но на этом шаге меняется визуализация — теперь окантовка сектора красится в цвет сценария:



Стартовый сектор — светло-серый, конечный — синий. Так же заметьте, что вместо двери у секретной комнаты (тёмно-серая слева) нарисована стенка — всё правильно, это секретная стенка.


Далее выбираются те сектора, в которых можно разместить ключи:



Выбираются они достаточно просто:


  • Если это секретная комната, то в ней не может быть никакой "открывашки", и ключ размещать там нельзя.
  • Нельзя размещать ключ и в финальном секторе — ведь он же финальный.
  • Так же ключ не может открывать двойные и тройные двери — из-за особенностей движка они могут открываться только с помощью переключателя (на приведённой иллюстрации таких секторов нет).

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


В остальных секторах будут переключатели.