Процедурная генерация уровней

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

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

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

Вводная

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

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

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

• https://www.progamer.ru/dev/procedural-dungeon-generation.htm (*)
• https://habr.com/post/333692/
• http://www.gamasutra.com/blogs/GrahamDavis/20170130/290326/Procedural_Level_Generation_in_Unity_for_MERC_part_1_of_2.php
• http://ijdykeman.github.io/ml/2017/10/12/wang-tile-procedural-generation.html
• https://habr.com/post/332832/ (*)
• https://habr.com/post/184818/ (*)

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

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

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

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. Если соединение экстра длинное, генератор возвращается ко второму шагу.

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

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

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

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

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

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

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

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