Привет, Хабр. Меня зовут Кирилл. Я увлекаюсь геймдевом в свободное от работы время. В этой статье я поделюсь опытом разработки процедурного генератора миров для своей инди-игры Unsigned Character. Игра представляет собой платформер с бесконечным процедурным миром, который достраивается по мере продвижения игрока. Я попытался реализовать процедурную генерацию, которая выдаёт интересный и разнообразный результат. И во многом это удалось.

Задача

В общих чертах задачу генератора можно описать таким списком требований:

1. Мир игры должен быть проходим прыгающим персонажем. Никаких полётов, телепортов, крюков и прочего.

2. Генератор должен работать достаточно быстро, чтобы достраивать мир игры на лету.

3. Генератор должен быть легко расширяемым для внедрения новых элементов.

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

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

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

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

Внутри комнаты создаются платформы и другие элементы, необходимые для движения персонажа. Кроме того, комната заполняется противниками, бонусами и прочим игровым контентом.

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

Теперь можно более менее точно сформулировать задачу: Есть прямоугольный регион (комната). На гранях этого региона задана точка входа (из предыдущей комнаты) и выходное окно. Выходное окно - отрезок на одной из граней региона, в котором должен располагаться выход из комнаты. Это окно берётся из пересечения граней текущей и следующей комнаты (см. рисунок). Генератор должен сформировать геометрию комнаты исходя из требований, перечисленных в начале раздела. На выходе алгоритма должен быть набор игровых объектов (платформы и т.д.) а также координаты точки выхода. Она будет использована как точка входа для следующей комнаты.

Идея

Требование 3 гласит, что функционал генератора должен легко расширяться. То есть должна быть возможность научить генератор новым трюкам не переписывая основную массу кода. Отсюда органично вытекает идея, что конкретные способы построения геометрии должны быть скрыты за некой абстракцией. Тут напрашивается паттерн проектирования "Стратегия".

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

Алгоритм этот основан на методе BSP (Binary Space Partitioning), то есть рекурсивном разбиении исходного региона на два подрегиона. Вкратце алгоритм можно описать так:

1. Разбиваем регион на два подрегиона (вертикально или горизонтально).

2. Строим геометрию в первом подрегионе с выходом во второй.

3. Строим геометрию во втором подрегионе со входом из первого и выходом в исходное окно.

4. В конце рекурсии применяем одну из стратегий.

5. Добавляем стены-разделители между подрегионами.

Основной алгоритм

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

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

Благодаря запасной стратегии не нужно отменять ранее принятые решения. Алгоритм пытается разбить регион на два подрегиона. Если видит, что сделать это не получается, просто применяет запасную стратегию. Каждое решение алгоритма при этом окончательное. Не нужно перебирать дерево вариантов с экспоненциальной сложностью. Таким образом выполняется требование 2.

Рекурсивную часть алгоритма можно описать такими этапами:

• Готовим варианты разбиения исходного региона (пары подрегионов).

• Для каждого варианта разбиения пытаемся подобрать совместимые пары стратегий.

• В итоге получаем множество вариантов разбиения с заведомо применимыми стратегиями.

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

• Иначе применяется запасная стратегия.

Нерекурсивная часть алгоритма выглядит так:

• Находим подходящую стратегию для исходного региона

• Строим геометрию в регионе, используя найденную стратегию как запасную

• Строим внешние стены комнаты

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

Разбиение региона

При разбиении региона на два подрегиона нужно учесть несколько требований:

• Подрегионы не должны быть слишком маленькими. Это решается ограничением на минимальный размер стороны подрегиона.

• Точка входа в родительский регион вместе с минимальным необходимым запасом должна быть в одном из подрегионов.

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

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

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

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

Интерфейс стратегии

Прежде чем описать выбор стратегий для подрегионов, необходимо определиться с интерфейсом стратегий. Стратегия - это генератор в миниатюре. Она также получает на вход прямоугольный регион, точку входа и выходное окно. Возвращает она также набор объектов игрового мира и точку выхода. Так работает основной метод интерфейса стратегии. Назовём его fill(). Однако если генератор в целом должен работать почти везде, конкретная стратегия может быть неприменима к конкретной задаче. Поэтому есть ещё один метод tryFill(), который отвечает за применимость стратегии. Этот метод принимает регион и выходное окно а возвращает набор входных окон. То есть окон, в которых может располагаться входная точка для данного региона, чтобы стратегия могла выполнить поставленную задачу.

Выбор стратегий

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

Делается это так:

• Отображаем выходное окно родительского региона на второй (выходной) подрегион.

• Перебираем стратегии для второго подрегиона. У них вызываем метод tryFill(), который возвращает возможные входные окна.

• Для каждого входного окна перебираем стратегии первого подрегиона. Входное окно второго подрегиона используем как выходное окно для первого.

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

• если всё сошлось вариант разбиения с парой стратегий добавляется к общему множеству 

Обрезка регионов

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

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

Параметры генератора

И так, у нас есть два параметра: SPLIT_DEVIATION_RATE и CUT_RATE. Также к ним добавляется третий: MIN_REGION_SQUARE - минимальная площадь подрегиона при разбиении. Изменяя эти параметры можно значительно влиять на результат работы алгоритма даже в одинаковых комнатах. Таким образом выполняется требование 4. В игре эти параметры постоянно меняются от комнаты к комнате.

Стратегии

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

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

PyramidStrategy

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

А так выглядит комната, собранная с помощью одной только PyramidStrategy:

GridStrategy

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

Принцип работы таков:

• Создаём диагональную сетку из платформ так, чтобы персонаж мог запрыгивать с нижних платформ на верхние (см. схему ниже).

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

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

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

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

Так выглядит комната, собранная с помощью GridStrategy:

JumpPadStrategy

Джамп пад (jump pud) - устройство которое подбрасывает персонажа на заданную высоту. Что-то вроде лестницы, но гораздо динамичнее.

JumpPadStrategy просто создаёт джамп пад под выходным окном. А также создаёт нижнюю и заднюю платформу подобно PyramidStrategy.

Так выглядит комната из джамп падов:

Спавн-регионы

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

Заключение

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

https://github.com/cyberslav-games/SplitAndFillGenerator.git

Там же лежит демонстрационное приложение на libGDX. В нём можно задавать параметры генератору и наблюдать за результатом.