Boundless City — город, бесконечный в трех измерениях

Boundless City — эксперимент в процедурной генерации бесконечного по вертикали (и в других измерениях) футуристического города и игра, которая этот алгоритм использует.

Был сделан для джема Game Off 2019, ссылка на «джемовскую версию» — Boundless City

Исходный код:

Пространство разбивается на кубические слоты. На каждый слот выделяется 36 вершин, т.е. 12 треугольников = 6 четырехугольников = 1 параллелепипед. После этого для каждого слота независимо определяется то, что в нем рисуется, исходя из вышеназванного бюджета вершин. Всё это делается в вершинном шейдере city‑v.glsl, что имеет некоторые достоинства, но также и существенные недостатки, но об этом позже.

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

Сначала я использовал для определения наличия блока градиентный шум, потом просто заменил его на случайное число. Следующим шагом было добавление вертикальных столбов в ячейки сетки 6*6 слотов. И, наконец, горизонтальных «проспектов» — почти пустых от блоков через каждые 50 слотов. В конечном итоге формула выглядит так:

Тут mod — деление по модулю, fract — дробная часть, обе встроенный функции GLSL. rand3 — псевдослучайное число от 0 до 1, а slot — целочисленный вектор, определяющий позицию слота в сетке.

Чтобы добавить разнообразия и «реалистичности», границы слотов сдвигаются на случайное значение в диапазоне +- четверть слота.

Для определения того, какие будут окна на здании, берутся три пары случайных чисел - отступы сетки окон от края блока, количество столбцов и рядов в сетки и размер окна относительно ячейки сетки. Собственно, это всё.

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

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

В какой-то момент при отладке шейдера стекла я «попросил» программу показать уровень «блестящести». Т.е. окна — белым (блестит), остальное — черным (не блестит). Результат неожиданно получился довольно стильным

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

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

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

Через город проходит множество транспортных потоков. По горизонталям перемещаются "флайеры" (в виде урезанных конусов), а по вертикалям движутся целые здания.

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

Если x и y четные, то ряд может двигаться вертикально (z является вертикальной осью).

Если y и z нечетные, то ряд может двигаться вдоль оси x.

Если x нечетно, а z четно, то ряд может двигаться вдоль оси y.

Это дает гарантию, что ряды не пересекаются.

После этого "кидается кубик", определяющий действительно ли ряд движется (вероятность порядка 1/10), с какой скоростью и в каком направлении.

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

Тут speed - вектор скорости, u_time - текущее время, shift - положение объекта относительно первоначального, u_blockSize - размер ячейки, а slot - та ячейка, из которой объект берется. Наличие блока считается по обычной формуле, но уже для "сдвинутого" блока. Если поток горизонтальный, то вместо пустых слотов рисуются флайеры, а вместо занятных - уменьшенные блоки. Для вертикальных потоков алгоритм аналогичен статичным слотам.

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

Рисуются они, как и окна, во фрагментном шейдере city-f.glsl

Вот все 4 анимации:

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

Игровой процесс укладывается в одно предложение. Красные кластеры дают монетки и ускорение, зеленые чекпойнты - продление лимита времени и увеличение множителя монеток, получаемых с кластеров.

Теперь подробности.

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

Кластеров много, генерируются они "броском кубика" для каждого пустого (совсем пустого, т.е. даже без "пристроек") слота независимо.

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

За собранные монеты можно купить апгрейды - полный список на скриншоте сверху.

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

Музыка для этой игры (и для Marshmallow Sky) была написана Ashley Thorpe (aka The Soundsmith, aka Ashley T.)

Что интересно, если бы не он, то ни эта игра, ни Marshmallow Sky, скорее всего, не были бы написаны. Я обсуждал идею "gliding sim" в дискорде Procjam, но в конце концов решил тогда сделать что-то более соответствующее теме. Уже после джема Ashley T. постучался в личку и предложил написать для такой игры музыку. Это вдохновило меня копать в этом направлении и написать эти две мини-игры, и, быть может, развивать эту тему дальше.

Кстати, для усиления эффекта музыки я слегка меняю освещённость окон в такт

Интерфейс функционален, но сбивает с толку поначалу (а местами, и не только поначалу).

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

И это (наверное) работает, но мне не стоило вываливать список апгрейдов на людей сразу, так как многие воспринимали это как монолитную стену текста и сильно пугались.

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

Генерация геометрии выполняется полностью в вершинном шейдере city-v.glsl. Т.е. CPU передаёт в GPU только самые общие параметры (например, положение камеры и количество вершин), а шейдер по порядковому номеру вершины определяет, к какому слоту она относится и всё остальное.

Достоинством этого метода является то, что практически вся работа выполняется внутри GPU, не загружая CPU, шину между GPU и CPU и т.д. Также, это несколько упрощает алгоритм.

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

При всём при этом, удалось получить довольно интересную и "реалистичную" картинку даже при очень простом алгоритме. И достичь 60 FPS (почти стабильно) на уже довольно стареньком GTX 760.

Но всё же, при более сложном алгоритме генерации (и/или для более стабильного FPS или более слабых GPU) от такого подхода придется отказаться.

Мне лично проект кажется имеющим потенциал дальнейшего развития и превращения в коммерчский продукт. Учитывая, например, что Superflight оценен довольно хорошо, несмотря на простоту геймплея и уровней, спрос на этот жанр наличествует. А судя по отзывам с джема, такой подход к реализации этого жанра людям нравится.

Возможные пути развития: