El Dia de Muertos: Генератор уровней.

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

Начну с классификации. Процедурные уровни (независимо от игры) могут создаваться двумя способами:

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

2. Некий алгоритм (генератор) расставляет элементарные куски уровня (в случае платформера — скажем, проходимые\непроходимые тайлы и объекты с которыми можно взаимодействовать). Плюсы: не надо самому составлять шаблоны, можно менять или добавлять фичи (поменять высоту прыжка, добавить пружинки) не переделывая под них шаблоны, уровень каждый раз действительно новый. Минусы: сложнее. Сложнее гарантировать проходимость уровня, сложнее сделать его интересным, сложнее сделать разнообразным.

Конечно, подходы можно комбинировать — например генератор может помимо простых комнат добавлять заранее нарисованные шаблоны. Или наоборот — все собирается из шаблонов, но некоторые шаблоны внутри содержат генерируемые структуры. Ну и так далее.

Практически все платформеры со случайными уровнями которые я видел используют первый вариант. Исключение — «платформеры» где можно копать и как следствие там не слишком парятся с генерацией — заполняем всё землей и добавляем объекты интереса, игрок наверняка сможет прокопать дорогу куда ему надо.

Другое исключение — «Тарас и платформы Хулиона», которая для меня, наверное, эталон годного платформера. Там случайная генерация становится возможной за счет того что нет собственно «платформенных» испытаний по допрыгиванию или перепрыгиванию куда-то. Прыжки нужны только чтобы стрелять\уклоняться от монстров, а по самой карте можно тривиально перемещаться из любой точки в любую точку  за счет лестниц.

Еще по варианту 2 я видел статью (https://www.gamedeveloper.com/design/how-to-make-insane-procedural-platformer-levels), которая сводится к «сначала создайте симулятор игрока который будет эти уровни проходить, лично я писал его много месяцев». Явно многовато работы для конкурса игр, так что я рассматривал для себя только вариант 1.

У варианта 1 можно выделить подварианты по тому насколько шаблоны влияют друг на друга. В каком-нибудь Enter the Gungeon то что уровни сделаны из шаблонов очевидно, т.к. прохождение уровня состоит из череды прохождения отдельных комнат. А в Spelunky, хотя там тоже уровень собирается из шаблонов, это не так очевидно т.к. ты можешь пойти левее, можешь пойти правее, можешь спуститься тут а можешь пройти дальше, спуститься и потом вернуться, камень который жахнет на алтарь может катиться за тобой далеко за пределы экрана и надо просчитать куда бежать, в общем шаблоны «взаимодействуют» друг с другом.

Я решил сделать еще более мягкий вариант генератора, где шаблоны могли бы комбинироваться образовывая ситуации на которые автор не рассчитывал, но при этом хотя бы один путь прохождения гарантировался тем что у шаблонов есть «вход» и «выход» и от входа можно гарантированно добраться до выхода.

Общая идея:

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

 — у каждого шаблона по краям есть одна или несколько клеток «вход», и одна или несколько клеток «выход». Из любой клетки «вход» гарантированно можно попасть в любую клетку «выход» пройдя испытание представляемое данным шаблоном (успешно пропрыгав по платформам, обойдя скелета и т. д.). Испытания может и не быть (например шаблон может быть просто развилкой с одни входом и двумя выходами).

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

 — и для целей соединения с «провальным выходом» есть «провальный вход» — клетки в которые может упасть герой из другого шаблона.

Провальных выходов и входов у шаблона может и не быть.

Как работает генерация уровня:

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

1. берем один шаблон в качестве стартового, размещаем в случайном месте, составляем список координат клеток типа «выход» и клеток типа («провальный выход»).

2. Берем из списка клеток «выход» очередные координаты (XY), сдвигаем на один тайл (чтобы оказаться за пределами шаблона которому она принадлежит), пытаемся подставить случайный шаблон так чтобы один из его «вход"ов совпал с (XY) и при этом сам шаблон не наложился ни на один из уже находящихся на поле.

3. Повторяем пункт 2 пока не сможем успешно наложить шаблон. Если за тыщу попыток ничего не вышло — значит клетка (XY) в каком-то тупике куда ничего не влезет, занесем эти координаты в отдельный список «закрытые выходы» (в дальнейшем мы поставим туда портал в начало, какой-нибудь бонус или даже конец уровня), а клетку из списка удаляем. Если вышло — (XY) тоже удаляем, а в списки «выходы» и «провальные выходы» добавляем выходы из нашего добавленного шаблона. Продолжаем:

4. Повторяем пока список «выходы» не опустеет. На этом этапе «нормальная» часть прохождения уровня кончилась, в самой далекой из точек «закрытые выходы» (жирный кружок слева на картинке) будет переход на следующий уровень, а остальные «закрытые выходы» заполним красными порталами или бонусами (два жирных кружка справа на картинке). Дальше нам осталось заполнить места куда игрок может провалиться, да и весь остальной уровень. Цифрами на картинке отмечается удаленность от стартовой комнаты а не просто номер, поэтому там две семерки.

5. Берем очередную клетку из списка «провальные выходы» и пытаемся состыковать с ней шаблон, как в пункте 2 но при этом можно брать не только «вход», но и «провальный вход». Если не вышло — что ж, тут тупик, игроку не следовало сюда падать. Если вышло — добавляем выходы и провальные выходы от нового шаблона в наш список.

6. Повторяем пункт 6 пока список выходов не опустеет (к каждому выходу и провальному выходу мы либо добавили шаблон, либо убедились что туда шаблон не влезет). Не очень жирные черные точки на картинке — места нормальных выходов шаблонов куда ничего не влезло. Изначально игрок попал сюда через «провальный выход», но т.к. после этого он прошел хоть один шаблон до «нормального выхода», то стоит наградить его поставив там красный портал или бонус.

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

Другая последовательность генерации:

8. (хотя в алгоритме это скорее нулевой шаг) Те места уровня которые остались белыми можно

 — заполнить стеной

 — заполнить пустым местом

 — заполнить рандомно пустыми либо заполненными клетками.

Первый вариант создает «подземельные уровни» где игрок вряд ли сможет пойти куда-то куда ему «не положено», мне это показалось скучновато:

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

Второй вариант я и выбрал, для фантасмагорического мира мертвых — то что надо, висящие в воздухи куски земли. Из минусов — по краям уровня образуются пустые места почти гарантирующие падение до самого дна уровня. Я решил это геймплейно, сделав в низу уровня лаву.

Вроде бы всё, спасибо за внимание. Код я бы открыл, но учитывая на каком он языке вряд ли он кому-то пригодится.