[Из песочницы] Генерация уровня в аркаде на примере инди-игры
В этой статье я хотел бы рассказать про алгоритм генерации уровня в простейшей игре жанра «runner», разработанной мной несколько дней назад. Если вам интересна тема геймдева, а также алгоритмы случайной генерации игровых уровней, подземелий, ловушек или ландшафта, добро пожаловать под кат.
Об игреДля начала, чтобы было понятно, что к чему, немного расскажу про саму игру. Игра — хардкорный раннер, в которой маленький пиксельный человечек бежит слева направо, а вам нужно успевать нажимать одну кнопку (или тапать по экрану, если это мобильная версия), чтобы этот человечек подпрыгивал или планировал в воздухе и уворачивался от многочисленных ловушек из шипов. Основная механика игры заключается в своевременном подпрыгивании перед ловушкой и правильном расчёте времени планирования на маленьких ручках (да, по анимации человечек машет ручками, и падение за счёт этого замедляется).Первая версия генерации
Игра разрабатывалась в формате хакатона, поэтому для первой версии игры был создан простейший минимально-работающий алгоритм, который по мере движения игрока создавал один из трёх видов шипов на случайном расстоянии от предыдущего.Виды шипов: 
Шипы, которые я назвал «Сюрикен», создавались на случайной высоте между полом и потолком. «Шипы на полу» и «Шипы на потолке» соответствовали своему названию и располагались на полу и на потолке, так что высота в отличие от «Сюрикена» была стабильная.
Для первой версии генерация получилась очень даже неплохой и интересной, но, к сожалению, было два больших минуса:
Зачастую ловушки генерировались слишком высоко, из-за этого были моменты, когда можно было очень долго бежать, ничего не нажимая.
Периодически создавались комбинации шипов, которые невозможно пройти.
Исходя из проблем, приведённых выше, я принял решение создать хороший, проработанный алгоритм генерации, который бы не допускал создания «непроходимых» мест, держал бы игрока в постоянном напряжении и при всём этом был бы неоднообразен и уникален на каждом участке уровня.Окончательный алгоритм генерации
Основные понятия
Сложность — число от 0 до 100, в начале игры равняется 0, по ходу игры постепенно увеличивается со скоростью 1 ед. на 15 метров. Когда достигает 100, перестаёт расти. Отвечает за «сложность» генерируемых ловушек, как это ни банально.
Зона — участок уровня, в котором ловушки генерируются по определённому принципу, зависящему от типа зоны.
Ловушка — один шип или группа шипов, создаваемых одновременно. Есть несколько видов ловушек.
1 метр — ширина/высота человечка.
Зоны
Существует несколько типов зон, для простоты приведу кусок кода:
enum Zones // зоны
{
Random_spikes_on_floor, // случайные шипы только на полу
Random_spikes_on_floor_and_solid_ceiling, // случайные шипы на полу и сплошные шипы на потолке
Solid_spikes_on_floor, // сплошные шипы на полу
Shuriken_walls, // стены из сюрикенов (с дырками)
Random // случайная генерация
}
В начале игры зона выбирается случайно из 5 выше приведённых типов. Длина зоны ограничена, когда игрок её полностью пробегает, выбирается следующая зона так же как и в начале игры, случайным образом. При создании новой зоны задаётся новая случайная длина (в основном, от 40 до 100 метров). Также при смене зоны создаётся небольшой подстраховочный промежуток между зонами, чтобы они друг другу не «мешали».
У каждого типа зоны есть свой шанс на появление, например, новая зона окажется зоной со «стенами из сюрикенов» с вероятностью 30%.
Тип зоны отвечает за то, какие ловушки будут генерироваться на данном участке. Поэтому у каждой зоны свои особенности и способы преодоления препятствий, а, следовательно, и особые правила при генерации (чтобы не создать непроходимый участок).
Как уже указывалось выше, в игре присутствует параметр Сложность, который растёт со временем от 0 до 100, и этот параметр напрямую влияет на количество или расположение ловушек при генерации в каждой зоне. Но давайте перейдём от абстрактных вещей к конкретным примерам.
Зона со «случайными шипами на полу»
В данной зоне алгоритм основан на создании ловушек преймущественно из шипов на полу в более-менее случайной последовательности.Пример генерации при минимальной сложности (Сложность = 0)
Пример генерации при максимальной сложности (Сложность = 100)
Для начала немного объясню как работает генерация внутри любой зоны. При вхождении в зону создаётся одна из возможных (выбирается случайно) ловушек, и в зависимости от того, какая ловушка была выбрана, задаётся новая задержка (через сколько метров будет создана новая ловушка в данной зоне). Как только игрок проходит задержку, создаётся новая ловушка, опять же выбранная случайно. Естественно, для каждого типа ловушки в каждой зоне есть свой шанс на появление.
Основной принцип в нашей зоне: создавать или не создавать шипы на полу (в зависимости от рандома). Эта зона из всех самая простая по алгоритму и нахождению проблемных мест, потому что она состоит в основном из шипов на полу, которые всегда находятся на одной высоте. Соответственно, мы можем определить, сколько шипов подряд ставить можно, а сколько нельзя путём обычного тестирования.
На изображении выше видно, что при максимальной высоте прыжка и времени парения игрок может преодолеть не больше 5 шипов идущих вплотную друг к другу. Соответственно, в алгоритме нужно условие: если перед генерируемой ловушкой уже есть хотя бы 5 ловушек, обязательно оставлять пустое место (не генерировать ловушку). Для этого нужно обязательно запоминать, какие ловушки были перед текущей (мной для этого был использован обычный массив enum-ов размером 10, т.к. больше 10 запоминать не нужно).
В данной зоне каждая следующая ловушка (или отсутствие ловушки) генерируется с задержкой равной ширине ловушки. Таким образом, если ловушки будут создаваться непрерывно, то между ними не будет свободного пространства до тех пор, пока их не станет 5 подряд (дальше сработает наше условие «нельзя больше 5 шипов подряд»).
Но нельзя забывать про роль рандома в генерации. Каждая новая ловушка может быть либо создана, либо не создана. Вот тут-то, наконец, сыграет свою роль сложность. Чем выше сложность, тем выше шанс появления шипа на полу.
random = UnityEngine.Random.Range (0f, 100f); // случайное число от 0 до 100
if (random < 40f + (Difficulty.Difficulty_of_game() * 0.4f)) // Difficulty.Difficulty_of_game() возвращает сложность игры { // ...создать ловушку... } else { // ...не создавать... } Отлично, получился неплохой алгоритм генерации шипов на полу, но чего-то не хватает. Нужно добавить редкие шипы на потолке, чтобы добавить разнообразия, но при этом нельзя сломать основную логику преодоления ловушек. Например, если сделать шипы на потолке прямо над 5 шипами где-нибудь между ними, то игрок просто не сможет прыгнуть настолько высоко, насколько ему это потребуется для преодоления 5 шипов подряд. Поэтому шипы на потолке должны находиться где-нибудь по краям таких больших групп «напольных» ловушек.Добавляем в алгоритм создание «шипов на потолке» с вероятностью от 70% до 100% (в зависимости от сложности) при условии:
if ((Last_traps[1] == Traps.None) || (Last_traps[2] == Traps.None) || (Last_traps[3] == Traps.None)) { // …в этом месте шипы сверху создавать нельзя… } else { // …создаём шипы сверху… } То есть, если предпоследняя, или пред-предпоследняя, или пред-пред-предпоследняя ловушка отсутствует (нет шипов на земле), то можно создавать шипы на потолке, в противном случае — нельзя.Отлично, один алгоритм готов. Осталось разобрать остальные 4!
Зона со «случайными шипами на полу и сплошными шипами на потолке» Эта зона по сути усложнённая версия «зоны со случайными шипами на полу».Различия:
На протяжении всей зоны есть шипы на потолке.
Для разнообразия добавлены «сюрикены» в некоторых местах.
Максимальное количество шипов на полу подряд не 5, а 4 (за счёт шипов на потолке уменьшается максимальная высота прыжка).
Сложность = 0 (минимальная)
Сложность = 50 (средняя)
Сложность = 100 (максимальная)
В алгоритме никаких сильных отличий от предыдущей зоны нет, кроме того, что случайно генерируются не шипы на потолке, а «сюрикены», причём на разных сложностях разный шанс на появление «сюрикена». «Сюрикен» может появиться с вероятностью от 30% до 60% (в линейной зависимости от сложности) над местом без шипов на полу (потому что, если создавать их над шипами, очень велика вероятность того, что возникнет непроходимое место).
Кроме того, «сюрикены» могут появляться на разной высоте в зависимости от сложности. Если присмотреться к скриншотам, становится понятно, что чем ниже «сюрикен», тем сложнее не задеть его при прыжке. Исходя из этого, мной была создана зависимость высоты от сложности:
Сложность [0–50) — Создать «сюрикен» высоко.Сложность [50–80) — 50% Создать высоко; 50% Создать на средней высотеСложность [80–100] — Создать на средней высоте.
Зона со «сплошными шипами на полу»
Это зона сильно напоминает первую зону «со случайными шипами на полу», но имеет два отличия: Шипы идут всегда подряд группами от 3 до 5 шипов (зависит только от сложности, рандом не играет роли).
Между группами шипов всегда пропуск по ширине, сопоставимый с шириной шипов (2.25 метра).
Сложность = 0 (минимальная)
Сложность = 50 (средняя)
Сложность = 100 (максимальная)
Основной упор в этой зоне был расчитан на то, что игрок должен будет всегда прыгать на свой максимум, то есть через 5 шипов. Но, так как в игре присутствует изменяющаяся сложность, было введено 3 вариации зоны (скриншоты см. выше):
Сложность [0–25) — Лёгкая зона, 3 шипа подряд.Сложность [25–75) — Средняя зона, 4 шипа подряд.Сложность [75–100] — Сложная зона, 5 шипов подряд.
Эта зона является, наверное, самой простой, потому что нет неожиданных и очень сложных мест, на протяжении всей зоны повторяется одна и та же ситуация (N шипов подряд, пробел, N шипов подряд, пробел и т.д.). Хотя, со сложности 75 начинаются проблемы, потому что, если хотя бы чуть-чуть неправильно расчитаешь время и прыгнешь раньше, попадёшь на шипы.
Шипы на потолке здесь генерируется по тому же принципу, что и в первой зоне, но в отличие от первой зоны, здесь от них никакой пользы, кроме устрашения и разнообразия, т. к. напороться на них невозможно из-за слишком маленьких островков без шипов.
Зона со «стенами из сюрикенов»
Вот мы подошли к, наверное, самой сложной по прохождению зоне. Основной её принцип похож на трюк с «огненным кольцом» в цирке: нужно пролететь между шипами, не задев их при этом. Давайте посмотрим на скриншоты для разных сложностей: Сложность = 0 (минимальная)
Сложность = 50 (средняя)
Сложность = 100 (максимальная)
Также как и в предыдущей зоне, у нас есть 3 вариации по сложности:
Сложность [0–40) — Лёгкая зона, дырки шириной в основном по 2 «сюрикена».Сложность [40–90) — Средняя зона, намного сложнее «Лёгкой», так как в основном дырки шириной в 1 «сюрикен», есть разные варианты преодоления.Сложность [90–100] — Сложная зона, дырки всегда шириной в 1 «сюрикен», немного сложнее «Средней», так как вариант прохождения всегда один.
Основной принцип генерации таких стен: между каждой стеной всегда постоянное расстояние (не зависит от рандома), которое меняется в зависимости от текущей сложности. Расстояние между стенами всегда от 8.5 м до 7.5 м (чем выше сложность, тем меньше расстояние), причём при переходе из одного подтипа зоны в другой (например, из Лёгкой Зоны в Среднюю Зону) расстояние между стенами опять будет уменьшаться от 8.5 м до 7.5 м. Таким образом, при сложности 39.99 в зоне будут «лёгкие стены», но расстояние между ними 7.5 метра, а при сложности 40 — «средние стены», но расстояние 8.5 метра.
Расстояния тестировались на разных комбинациях стен, и было выявлено, что 7.5 метра это минимальное расстояние, при котором комфортно можно успевать приземлиться и прыгнуть снова, не задев при этом шипы. Постепенное уменьшение с 8.5 метров было сделано, чтобы шло хоть какое-то усложнение внутри подтипа зоны.
Теперь о том, как определяется, какая именно стена будет следующей в зоне. Всё очень просто, для каждой сложности есть определённый набор стен из «сюрикенов», и каждый раз выбирается случайная стена из этого набора:
Зона со «случайной генерацией»
Когда мной были созданы 4 предыдущие зоны, всё было отлично, но чего-то не хватало. Хоть моя первая версия генерации (полный рандом) и была с недостатками, но и прелесть в ней своя всё же была. Поэтому я решил создать ещё одну зону, которая была бы по сути копией моей первой версии генерации, но при этом без её прежних недостатков (непроходимых и скучных мест): 
Для создания улучшенной версии старой генерации я создал зону из уже существующих ловушек и задал им определённые правила и шансы:
35% «Сюрикен» на случайной высоте — расстояние до следующей ловушки от 7 до 4 метров (в зависимости от сложности). 30% Слабая стена из «сюрикенов» — создаётся на 4 метра дальше от предыдущей ловушки, расстояние до следующей ловушки от Random (9.5, 11.5) до Random (7.5, 8.5) метров (в зависимости от сложности), при условии, что Random (N, M) — случайное число от N до M. 20% Шипы на земле и потолке — расстояние до следующей ловушки от 6 до 3.75 метров (в зависимости от сложности). 10% Шипы на земле — расстояние до следующей ловушки от 6 до 3.75 метров (в зависимости от сложности). 5% Шипы на потолке — расстояние до следующей ловушки от 6 до 3.75 метров (в зависимости от сложности). Расстояния между ловушками были получены многочисленными тестами (в том числе, самых критических случаев), хотя после релиза был обнаружен один косяк в создании стены «сюрикенов», из-за которого очень редко создавалось непроходимое или очень сложное место, но этот косяк я оперативно исправил.Заключение В итоге мной был получен достаточно полный и нетривиальный алгоритм генерации ловушек в игре, который: Динамически генерирует сложные для прохождения уровни, что создаёт некий челлендж. Не создаёт тупиковых или почти тупиковых мест. Создаёт каждый раз уникальный уровень, не похожий на предыдущий. Зависит от постепенно увеличивающейся сложности. Спасибо, что дочитали! Если будут вопросы или найдете какие-то ошибки, обязательно напишите об этом в комментариях.
