Недавно я реализовал очень необычную задумку — демонстрацию Minecraft-подобного движка с игровой логикой, выполняющейся полностью на GPU.
Как и зачем я это сделал, и как дошёл до жизни такой, я поведаю в этой статье.
Внимание, в статье есть много скриншотов!
Предыдущая работа
Уже давно, ещё в студенческие годы, я вместе с одним университетским товарищем разрабатывал игру в стиле Minecraft — с миром из блоков. Я в этой игре был занят 3d-визуализацией мира и в процессе собрал достаточно знаний, чтобы понять, как подобного рода игры работают и рисуются.
Разработка этой игры дальше как-то не задалась. Несколько позже при этом мне в голову пришла достаточно оригинальная идея — использовать вместо кубов блоки в форме шестиугольной призмы. Подобные блоки также заполняют трёхмерное пространство, как и кубы, но при этом выглядят интереснее в сравнении с ними. Данные идеи я воплотил (уже в одиночку) в своём проекте, который без фантазии назвал Hex.
Над этим проектом я периодически работал в течении нескольких лет, добавляя туда различные фичи — сохранение мира, освещение, текущую воду, неполные блоки, смену времени суток, огонь, шестиугольную фильтрацию текстур и т. д. При этом сделать что-то законченное я не особо хотел и данный проект так и остался лишь демонстрацией подхода и полем для экспериментов.
Результат в итоге вышел весьма интересным, но страдал от некоторых недостатков. Код генерации мешей геометрии мира был сложноват и всё взаимодействие с GPU казалось не очень оптимальным. На больших размерах мира игровая логика и генерация мешей несколько тормозили.
Переосмысление
Иногда я возвращался в мыслях к проекту Hex и думал, как бы я мог его улучшить. Особо новых и стоящих идей при этом не возникало. Но относительно недавно я начал думать, как бы можно было устранить существующие проблемы производительности.
Одной из идей был перенос кода построения мешей геометрии мира на GPU. Это казалось логичным — ведь результат этого кода используется на GPU для рисования. Но просто перенести этот код на GPU казалось половинчатой идеей, ведь это всё равно потребовало бы затратного перемещения данных блоков мира в память GPU. Тогда я развил свою мысль дальше и пришёл к выводу, что сами данные мира стоит хранить на GPU. Ну а раз данные там хранятся, то и логика мира (его обновление) должны там выполняться. В конечном итоге я довёл мою первоначальную идею до логического конца, решив, что на GPU должно выполняться вообще всё, что только можно.
Подход к реализации новых идей
Я решил, что стоит попробовать воплотить мои идеи в реальность. При этом я не хотел реализовывать их на основе кодовой базы старого проекта Hex. Она была достаточно стара и многие места по-неопытности были написаны не очень хорошо, сейчас бы я сделал это сильно лучше. К тому же в этом проекте использовался графический API OpenGL, который я считаю сейчас устаревшим и несколько неудобным в работе.
На основании этих размышлений я решил писать проект с чистого листа. Язык программирования я выбрал прежний — C++, а в качестве графического API выбрал более современный Vulkan. Он даёт больше низкоуровневого контроля и не страдает проблемами OpenGL со сменами состояний. В качестве шейдерного языка я выбрал GLSL с оффлайн-компиляцией в SPIR-V при помощи GLSLangvalidator.
Над названием новой версии проекта я особо долго не раздумывал. Его я назвал HexGPU — чтобы выразить преемственность со старой версией и подчеркнуть основное отличие.
Основы мира и его рисования
Мир в проекте состоит из шестиугольных призм. В памяти они хранятся как большой трёхмерный массив, во многом так же, как и любые другие трёхмерные массивы, но с отличаем, что для шестиугольной сетки адресация чуть менее тривиальна. Поначалу каждый блок хранился как один байт для обозначения его типа — воздух, камень, земля, древесина и т. д.
Этот мир надо как-то нарисовать. Для этого его надо превратить в набор треугольников, которые GPU умеют весьма хорошо растеризировать. Другие варианты отрисовки (вроде трассировки лучей) были рассмотрены, но я пришёл к выводу, что они были бы слишком медленными и непрактичными.
Самый простой вариант — это рисовать для каждого блока отличного от воздуха меш шестиугольной призмы с соответствующей типу блока текстурой. Этот подход вполне рабочий, но жутко непроизводительный, ведь большинство блоков на самом деле не видны, т. к. они загорожены другими непрозрачными блоками. Поэтому я выбрал другой подход, который (насколько мне известно) используется во всех Minecraft-подобных движках. Подход этот заключается в том, что для мира генерируется меш, включающий только те полигоны, что действительно могут быть видны. Эти полигоны лежат на сторонах непрозрачных блоков, обращённых к прозрачным или частично-прозрачным блокам.
Вышеописанный алгоритм был воплощён ещё в Hex. Но так, как у нас GPU, просто взять его было бы непрактично, ведь он был однопоточным — обходил блоки в мире и добавлял полигоны в выходной массив один за одним. На GPU это было бы слишком медленно, поэтому я реализовал его многопоточную версию. Каждый поток на GPU обрабатывает один блок и записывает его полигоны в выходной массив (для начала просто очень большого размера). Для подсчёта количества полигонов используется атомарная переменная.
Реализован этот алгоритм через вычислительный шейдер на GLSL, который запускается посредством вызова vkCmdDispatch. Почти все описанные далее алгоритмы работают аналогичным образом.
Первый сгенерированный меш
Поначалу, кстати, данных блоков даже не было, а была просто функция из двух помноженных синусоид, которая создавала простейший рельеф. В дальнейшем массив блоков мира был таки создан и функция генерации меша стала читать данные из этого массива.
Меш мира, генерируемый вычислительным шейдером — это четырёхугольники в трёхмерном пространстве, заданные их вершинами. Боковые стороны блоков имеют по одному четырёхугольнику, нижние и верхние стороны — по два. Можно было бы делать верхние и нижние стороны шестиугольниками, но это бы усложнило работу — пришлось бы генерировать дополнительно индексный буфер. В подходе, где вся геометрия представлена четырёхугольниками, можно сделать проще и использовать заранее подготовленный индексный буфер для меша, содержащего только четырёхугольники.
Вышеописанный массив с четырёхугольниками далее используется как вершинный буфер в команде отрисовки. Отрисовка осуществляется при помощи вызова vkCmdDrawIndexedIndirect, для которого отдельным вычислительным шейдером подготавливается структура VkDrawIndexedIndirectCommand, в которой кроме прочего количество индексов рассчитывается на основе актуального количества четырёхугольников. Тем самым количество рисуемых четырёхугольников определяется полностью на GPU, CPU же даже не знает, сколько их рисуется.
Чанки
Хранить весь мир в одном большом массиве не очень удобно. Гораздо лучше разбить его на фрагменты фиксированного размера — чанки. Так делают все Minecraft-подобные игры. HexGPU тут не исключение — я тоже сделал разбивку на чанки. Один проход алгоритма генерации мешей строит четырёхугольники для одного чанка. При этом важно всё же учитывать блоки из соседних чанков, чтобы не было швов на границах. В HexGPU чанки имеют размер 16x16x128 блоков. Мир сам по себе имеет ограничение по высоте в 128 блоков, что делает сетку чанков двухмерной.
Разбиение на чанки даёт много преимуществ. Например, можно отсекать геометрию вне поля зрения по чанкам. Данные мира сохраняются по чанкам (об этом позже). Также разбиение по чанкам даёт возможность равномерно во времени разделить расчёты — как построение мешей, так и другие.
Сетка чанков. Для наглядности краевые блоки не рисуются.
Вскоре после внедрения разбиения на чанки я сделал построение их мешей разреженным. Каждый кадр перестраиваются меши только для небольшого числа чанков. Таким образом в течении нескольких кадров каждый чанк рано или поздно перестроится. При этом количество перестраиваемых за кадр мешей чанков фиксировано и не зависит от того, действительно ли это нужно (данные блоков обновились), т. к. отслеживать необходимость этого обновления было бы слишком затратно.
Память под меши
Поначалу я просто выделял достаточно большое количество памяти под меши чанков. Но потребление памяти в таком подходе было слишком большим. Поэтому я решил распределять память более хитрым образом, написав своего рода аллокатор.
Аллокация памяти — задача весьма сложная. Все существующие алгоритмы для этого весьма нетривиальны и содержат много кода. Ещё сложнее реализовать их на GPU. Поэтому я создал свой собственный, относительно простой, но вполне рабочий алгоритм.
Для начала для каждого чанка, обновляемого в данном кадре, подсчитывается количество четырёхугольников в нём, без их непосредственной генерации. Когда для всех чанков это количество подсчитано, запускается однопоточный вычислительный шейдер, который выделяет память под данные из одного очень большого массива. После выделения памяти запускается проход непосредственной генерации мешей.
Алгоритм аллокации следующий — необходимое количество четырёхугольников округляется вверх до числа, кратного 512 и делится на 512. Это юнит аллокации. Вся память выделяется из одного очень большого массива, для которого хранится простая таблица, в который каждый бит — это индикация занят ли/свободен ли юнит. При выделении памяти под чанк в этом массиве линейно ищется свободный участок нужного размера. Для ускорения поиска биты сгруппированы в 32-битные целые числа и с ними проводятся битовые манипуляции. Когда блок свободных юнитов найден — соответствующие биты выставляются в 1. При освобождении они выставляются в 0.
Данный алгоритм не идеален — он имеет линейную сложность и вообще однопоточен, но практика показала, что он достаточно быстр. Неоспоримым преимуществом является его простота, что позволяет реализовать его безошибочно, не прибегая отладке и юнит-тестированию, что для вычислительных шейдеров практически невозможно.
Также стоит отметить, что под меши всё ещё выделяется очень много памяти — сравнимо с памятью под блоки. Это делается, чтобы минимизировать потенциальную возможность исчерпание памяти. Но вышеописанный алгоритм аллокации позволяет это размер сократить, в сравнении с подходом, когда под меш каждого чанка выделяется максимально-необходимое ему количество памяти.
Генерация мира
Изначальные данные мира (где какие блоки находятся), генерируются процедурно. Делается это, конечно же, на GPU. В основе генерации лежит некая вариация шума Перлина, адаптированная под шестиугольную сетку. Каждый поток на GPU работает для колонки блоков — вычисляет высоту ландшафта и в зависимости от неё заполняет мир блоками воздуха, травы, земли, песка, воды, камня и т. д.
Ландшафт на основе шума
В дальнейшем алгоритм был доработан — было добавлено размещение деревьев. Деревья размещаются по заранее-просчитанной карте распределения, которая строится на CPU и загружается на GPU. В основе — нечто вроде распределение Пуассона. Деревья при этом — заранее заданные модели из блоков.
Отладочное изображение с распределением деревьев
Так деревья выглядят на ландшафте
Генерация мира работает по чанкам. Она запускается на старте для чанков, для которых нету сохранённых данных. Также генерация запускается (если надо) при движении по миру — для впервые посещённых чанков.
Движение по миру
Весь мир потенциально очень большой. При этом он и близко не бесконечный — из различных ограничений его размер составляет всего около пары десятков тысяч блоков с севера на юг и с запада на восток. Одномоментно при этом находится в памяти и обрабатывается только область мира вокруг камеры (активная область), состоящая из MxN чанков (настраиваемо).
При движении игрока по миру происходит сдвиг активной области. Происходит генерация чанков, которые видимы впервые или загрузка, если они были посещены ранее. Выгружаемые чанки сохраняются на диск.
Вне активной области мир не просчитывается (остаётся статичным), что может иметь последствия для игровой логики — не работает смена сезонов, не течёт вода, не работают построенные игроком механизмы и т. д. Это неприятно, но не сильно страшно и может считаться игровой условностью.
Освещение
Мир просто из блоков выглядит достаточно плоско. Ему нужно какое-нибудь освещение, которое я и реализовал.
HexGPU использует модель освещения, характерную для Minecraft и подражателей. Суть её следующая: каждый блок имеет определённую освещённость в некотором небольшом диапазоне, скажем [0; 15]. Блоки, представляющие собою источники света, имеют уровень освещённости характерный для этого источника. Остальные блоки имеют освещённость, на 1 меньше максимальной освещённости их соседей. Непрозрачные блоки имеют нулевую освещённость. Данная модель и близко не реалистична, но тем не менее годится как игровая условность. Её преимуществом является вычислительная простота и возможность использовать освещённость для целей игровой логики.
Возникает вопрос — как посчитать свет по этой модели, да к тому же на GPU и достаточно быстро? Я пришёл в своих раздумьях к следующему подходу: освещённость хранится в большом массиве, аналогично блокам, с одним байтом на блок. Каждый шаг запускается вычислительный шейдер, который считает свет для каждого блока в мире (по потоку на блок). Каждый поток вычисляет освещённость и записывает её в другой (выходной) массив, который и будет содержать результат расчёта. На следующем шаге массивы меняются местами. Данный подход весьма быстр и устраняет какие-либо проблемы многопоточности. Если каждый поток пишет только в предназначенную ему область памяти (свет своего блока), то не нужны никакие синхронизации. Главное, чтобы для всего мира свет считался за один проход перед сменой массивов.
В статичном окружении (блоки не меняются) результат данного подхода стабилизируется на конечном решении за количество шагов, равное максимальному количеству уровней освещённости. При изменении блоков (добавлен/удалён источник света, добавлена/удалена преграда) можно наблюдать волны распространения света. Их можно устранить, всегда проводя несколько шагов распространения света, а можно и оставить всё как есть и счесть это таким эффектом.
Освещение от одного блока-источника
Дополнительно к свету от блоков я добавил свет от неба. Он считается аналогичным образом, за исключением некоторых нюансов. Источниками света неба служат только блоки в самом верху мира. Свет неба с максимальным уровнем распространяется вниз без потерь. Считается свет неба тем же вычислительным шейдером, что и свет от блоков-источников. Хранятся оба вида освещения вместе — свет блоков в младших четырёх битах, свет неба — в старших.
Отдельное хранение света неба и блоков позволяет, например, реализовать плавную смену времени суток — в сумерках и ночью интенсивность света неба просто уменьшается, в то время как свет от блоков остаётся постоянным. Ещё один плюс подхода с отдельным хранением света неба — возможность в игровой логике отличать пространство на поверхности земли и в пещерах/помещениях через уровень небесного освещения.
Вода
В Hex была вода, которая могла течь. Это никоим образом не физически-корректная симуляция, а скорее нечто условное — вода течёт в стороны и вниз, вверх (под давлением) течь она не может. В этой модели у каждого блока воды есть число — количество воды в нём, вода течёт вниз, если может, и в стороны, если уровень воды там меньше.
Передо мною встал вопрос — как же реализовать такую физику воды на GPU? Очевидным тут видится подход схожий с освещением — когда каждый поток обновляет состояние одного блока. Чтобы не было гонок чтения/записи, также используется двойная буферизация (с разделением входного и выходного массивов блоков).
Подход получился довольно хитрым. На чётных итерациях обновления мира вода течёт только вниз. Блок воздуха, который имеет блок воды вверху, преобразуется в блок воды и наоборот — блок воды, у которого внизу есть блок воздуха, становится блоком воздуха. Уровень воды при этом (естественно) сохраняется. На нечётных итерациях обновления мира вода течёт в стороны. Если блок воды не может течь вниз (внизу твёрдый блок или полный блок воды), вода из него течёт в стороны — другие блоки воды или в блоки воздуха. Соответственно блоки воздуха могут преобразовываться в блоки воды и соседние блоки воды могут принимать входящую воду из блоков, где количество воды больше.
Главное в этом подходе — это соблюдать симметрию расчётов. Если для блока A был посчитан исходящий поток в блок B, то для блока B должен быть подсчитан точно такой же входящий поток от блока A. Тогда в процессе расчётов сохраняется общий объём воды. В дальнейшем, правда, было добавлено высыхание воды в блоках с низким уровнем, что иногда приводит к общему её уменьшению, но это не страшно.
Для хранения уровня воды используется отдельный массив — по байту на каждый блок. В дальнейшем этот массив также был использован для хранения дополнительных данных других типов блоков.
Мир с достаточно глубокими водоёмами
Огонь
Огонь — это блок, который может размножаться и уничтожать горючие блоки рядом. Логика его несколько легче в реализации чем у воды, т. к. не нужно сохранять каких-либо инвариантов. Блоки воздуха рядом с блоком огня могут псевдослучайно сами стать блоками огня, если рядом с ними есть горючие блоки. Горючие блоки, рядом с которыми есть блоки огня, могут быть уничтожены. Огонь тухнет, если рядом с ним нет более горючих блоков или если рядом/наверху есть блок воды.
Рисуется огонь особым образом — с помощью полигонов на границах блока огня и окружающих его горючих блоков. Для них используется специальный шейдер с анимацией поднимающегося пламени.
Как горит огонь
Другие нетривиальные блоки
Также я реализовал ряд других типов блоков, которые имеют некую логику функционирования.
Блоки песка падают вниз, если могут. Правда пока что есть баг, из-за которого песок не может падать в воду.
Блоки листвы исчезают, если находятся далеко от блоков древесины. Удалённость для них считается алгоритмом, схожим с тем, что используется для освещения.
Зелёная трава может размножаться. Для этого ей нужен блок земли рядом, а также достаточное количество света и влаги. Блоки воды создают вокруг себя влагу. Также влага наличествует, если уровень солнечного освещения в блоке над блоком травы выше некоторого порога и в данный момент не выставлен флаг засухи. Это аппроксимирует наличие атмосферных осадков — даёт возможность траве расти на поверхности, но не в пещерах без доступа к воде.
Также зелёная трава может превратиться в жёлтую, если рядом нету влаги. Жёлтая трава размножаться не может, зато может гореть. Также она может превратиться обратно в зелёную, если влага снова появилась.
На блоках с максимальным уровнем небесного света (что означает, что они находятся прямо под небом), может образовываться снег, если этот блок находится выше Z-уровня снеговой линии. Снеговая линия может быть различной, например выставлена в 0 для наступления зимы, или быть повыше для создания снега только в горах. Когда же блок снега лежит ниже уровня снеговой линии, или же когда уровень света блоков (вроде огня) выше определённого порога, он исчезает.
Стоить отметить, что вся вышеописанная логика для этих блоков вычисляется в том же самом вычислительном шейдере, в котором вычисляется распространение воды и огня. По сути этот вычислительный шейдер вычисляет некий весьма сложный клеточный автомат. Внутри этот шейдер содержит ветвление по типу блока, для которого он запущен и производит вычисление логики, специфичной для каждого типа.
Сохранение мира
Хоть все расчёты и производятся на GPU, отказаться от передачи данных между GPU и основной памятью не получится. Ведь надо сохранять состояние мира между запусками и при движении и должным образом его загружать.
При движении по миру или при выходе из игры данные чанков (массивы типов блоков и дополнительных данных блоков) копируются в память, видимую CPU. Далее эти массивы сжимаются алгоритмом snappy, объединяются в группы по 14x12 чанков (экспериментально-подобранный размер) и сохраняются на диск — отдельный файл для региона 14x12. Когда же надо загрузить данные, всё происходит наоборот — данные грузятся с диска, разжимаются и копируются в память GPU.
Использование сторонней библиотеки snappy — очевидное отступление от принципа выполнения каких-либо расчётов только на GPU. Но это вынужденное отступление. Типичные алгоритмы сжатия линейные, что для GPU не подходит. Возможно в будущем кто-нибудь изобретёт алгоритм сжатия, быстро работающий на GPU, но пока такового нету или он мне не известен. Библиотека snappy при этом очень быстра и даже при использовании всего одного потока CPU весь загруженный мир сжимается/разжимается за доли секунды.
Логика игрока
Даже логику игрока я реализовал на GPU. CPU передаёт в специальный вычислительный шейдер только ввод (какие кнопки нажаты и как мышь была сдвинута). Далее этот шейдер рассчитывает движение игрока, повороты камеры и команды на строительство и разрушение. Стоит отметить, что этот шейдер работает в один поток, т. к. вычисления логики игрока сложно, да и не нужно распараллеливать.
Взаимодействие игрока с миром при этом происходит не напрямую, а несколько опосредованно. Это необходимо, т. к. циклы обновления мира и игрока не идентичны. Игрок обновляется каждый кадр, а мир — с некой фиксированной частотой. Поэтому для взаимодействия введена пара вспомогательных структур данных — окно мира и очередь изменений мира. Окно мира — это грубо говоря небольшой массив с блоками вокруг игрока, который используется для подсчёта позиции строительства/разрушения и столкновений. Очередь изменений содержит команды на строительство и разрушение. В конце цикла обновления мира эти структуры обновляются — события из очереди изменений применяются к миру и очередь очищается, строится новое окно мира.
Стоит также отметить, что состояние игрока периодически копируется в видимую CPU память. Это необходимо, чтобы прочитать позицию игрока и если надо запустить передвижение мира, загрузку/сохранение чанков и прочее.
Текстуры
Minecraft для стилизации использует текстуры низкого разрешения с nearest-фильтрацией. У себя я хотел нечто подобное, но с шестиугольной сеткой текселей.
Ещё в Hex я реализовал шейдер, который делает шестиугольные тексели. И это в принципе работало — алгоритм создания шестиугольного узора относительно прост и быстр. Но была кое-какая проблема: пропорции текстур при этом искажались — квадратная текстура или становилась прямоугольной, или искажались сами шестиугольники. В Hex это проблему тогда я так и не решил.
Вышеназванная проблема сделала весьма проблематичным использование готовых текстур, т.к. они все созданы с учётом квадратности текселя. Насколько мне известно, никто не рисует текстур с расчётом на неквадратные тексели. Инструменты генерации текстур такое тоже не умеют.
Посему я решил проблему кардинальным образом — я отказался от готовых текстур. Вместо этого я решил создать себе текстуры в нужном соотношении сторон самостоятельно. Не вручную, естественно, это было бы как-то не по-программистски. Я решил все текстуры генерировать.
Сейчас все текстуры (коих пока немного) генерируются при запуске — каждая при помощи своего вычислительного шейдера. Неквадратность текслелей при этом учитывается должным образом. Пока что при этом алгоритмы генерации достаточно простые — по большей части они основаны на шуме, аналогичном тому, который используется для генерации мира, а также на простейших геометрических узорах (вроде кирпичной кладки).
Текстуры с шестиугольной фильтрацией вблизи
То же самое, но с прямоугольными текселями
Отображение мира
Графика в HexGPU достаточно проста — затекстурированные полигоны с простым освещением и туманом вдалеке. Что-то более сложное я нахожу излишним. Для воды используется честное смешивание (артефакты неправильного порядка полигонов могут быть, но они редки). Для блоков вроде стекла, листвы, травы, огня используется ordered dithering с фильтром-постобработкой, который сглаживает характерный ему узор шашечек.
Благодаря относительной вычислительной простоте рисования удалось реализовать сглаживание методом supersampling — когда всё рисуется в буфер кадра, в 2 раза больший по осям (площадь больше в 4 раза), после чего блоки пикселей 2x2 усредняются. Такой алгоритм сглаживания имеет то преимущество относительно общепринятого MSAA, что может сглаживать даже внутренности полигонов, а не только их края. Это полезно для сглаживания альфа-теста и описанной ранее шистиугольной фильтрации текстур.
Также реализовано рисование неба со сменой времени суток, звёздами и облаками. Эффекты эти, во многом, чисто косметические.
Как выглядит мир с туманом
Возможные доработки
Пока на этом всё. Законченной игры у меня нету, есть лишь демонстрация с различными возможностями. Но из этого можно было бы сделать полноценную игру, особых препятствий я не вижу.
Мало чего стоит добавить множество новых видов блоков. Большинство из них были бы тривиальны (без особой логики), самое сложное было бы — сгенерировать для них текстуры.
Можно реализовать автоматическую смену времени суток и погодных условий. Сейчас это есть, но управляется вручную из отладочного меню. Вместо этого можно было бы весьма тривиально реализовать цикл день-ночь, изменение погоды, сезоны.
Сейчас физика взаимодействия игрока с миром элементарна — есть рудиментарные коллизии и нету даже гравитации. Можно было бы её доработать, чтобы игрок мог нормально ходить, бегать, прыгать, плавать.
Строительство/разрушение с накоплением/затратой блоков тоже не выглядят чем-то сложным. Аналогично можно было бы реализовать такие механики как сон и голод.
Не столь тривиально было бы реализовать мобов, монстров и взаимодействие с ними. Мне видится вполне рабочим всё тот же подход с двойной буферизацией и обновлением состояния каждого монстра отдельным потоком GPU. Можно было бы для монстров реализовать поиск пути для атаки игрока, а если быть точнее — поиск пути от игрока к ним, что вычислительно эквивалентно задаче вычисления освещения.
Почему же я это всё не реализовал? В текущих условиях я как-то не вижу, как это может привести к законченной интересной игре. В лучшем случае выйдет ещё один клон Minecraft, коих и так уже тьма. Действительно стоило бы развивать проект дальше, только если бы я мог придумать интересный игровой процесс, опирающийся на подход переноса игровой логики на GPU.
Производительность
Я подозревал, что производительность нового подхода будет сильно выше старого. Но поначалу (после реализации алгоритмов построения мешей и расчёта света) я заметил, что производительность оставляет желать лучшего. На размерах мира, сравнимых с теми, что без проблем работали в Hex, достигаемая частота обновления мира была весьма низкой — единицы в секунду. Я начал разбираться, почему так может быть. После некоторых поисков я обнаружил, в чём была проблема. По умолчанию вычислительные шейдеры имеют размер рабочей группы равный 1, что означает, что каждый поток запускается на своём собственном вычислительном юните GPU. Изменив размер рабочей группы на больший, чем 1, я получил таки желаемое кратное увеличение производительности. Сейчас для основных алгоритмов этот размер — 4x4x8=128.
Итак, в HexGPU симуляция мира запускается с частотой 8 раз в секунду. Это включает один шаг обновления всех блоков (включая воду, огонь и прочие) и один шаг обновления освещения. Также каждый кадр (типично 60 раз в секунду) перестраиваются меши 1/64 всех чанков и 1/4 всех чанков в квадрате 3x3 вокруг игрока. Кроме этого мир рисуется обычным образом — растеризацией треугольников, коих обычно в кадре около миллиона.
На ноутбучной видеокарте NVIDIA GeForce MX150 удаётся удерживать целевую частоту обновления мира и стабильные 60 кадров в секунду вплоть до размеров активной области в 34x40 чанков (544x640x128 блоков). На более мощной десктопной AMD RX 570 это возможно вплоть до умопомрачительных размеров 84x72 чанков (1344x1152x128 блоков). В последнем случае под все данные требуется около 3.5 Гб памяти.
Для сравнения — Hex имел ограничение размера мира в 64x64 чанков. При этом работать при таких размерах он мог только в случаях, когда никаких симуляций в больших масштабах не было — когда мир был по большей части статичен. Производительность скатывалась до единиц обновлений мира в секунду даже на мире 32x32, когда, например, в мире был слой воды в несколько блоков толщиной, или когда был масштабный лесной пожар.
Подход с вычислениями на GPU обладает тем преимуществом, что в нём нету проблемы масштабируемости. С примерно одинаковой скоростью работает как обновление мира, состоящего только из воздуха и камня, так и случаи с океаном в десятки блоков глубиной, и с лесными пожарами размером во всю карту, и с повсеместным засыханием травы, и с единовременным выпадением снега везде. Вышеназванные размеры мира, который удаётся симулировать, в значительной мере излишни, но этот пример показывает, что запас производительности очень высок. Вместо симуляции столь большой области можно увеличить частоту обновления при меньших её размерах, или же реализовать блоки с ещё более сложной логикой.
Что касается потребления ресурсов CPU, то оно крайне мало — в районе 1-2 процентов. Это и не удивительно, т. к. почти вся работа сводится к вызовам Vulkan, коих немного, в сравнении с типичными играми. Ну и периодически выполняется сжатие-разжатие чанков для сохранения/загрузки, которое относительно быстро.
О когерентности вычислений
Ранее я описал многопоточные алгоритмы, которые работают на GPU. Но важно отметить, что потоки на GPU в значительной мере отличаются от таковых на CPU, что имеет значительное влияние на эти алгоритмы. На CPU каждый поток выполняется на своём ядре, которое обладает отдельным потоком команд и отдельными вычислительными блоками. Благодаря этому каждый поток может исполнять независимый от других код. На GPU всё обстоит несколько сложнее. Потоки там объединены в группы, скажем, по 32 штуки. Эти группы вычисляются отдельными вычислительными юнитами. В таком юните типично есть единственный поток команд, но много потоков данных.
Наличие одного потока команд на множество потоков данных делает ветвление (условия, циклы) на GPU весьма нетривиальной вещью. Первые поколения GPU вообще не умели ветвления. Позже ветвления стали возможны, но за счёт выполнения обеих ветвей, с отбрасыванием вычислений для тех потоков, в которых данная ветвь не была взята. В дальнейшем эта схема усложнилась и добавилась возможность пропускать ветви кода, которые не берутся ни одним потоком в группе. Примерно таким образом работают все более-менее современные GPU.
Наличие ветвлений в одной вычислительной группе может потенциально приводить к увеличению времени исполнения кода — т. к. исполняются обе ветви. Этого стараются обычно избегать или хотя бы минимизировать. Как же я в HexGPU решил эту проблему? Решения тут различны. Во-первых, часть вычислений не так сложны, чтобы замедление от ветвлений было особо проблемным. Во-вторых, помогает когерентность данных. Например, вычислительный шейдер обновления блоков будет относительно быстро работать в областях, где внутри рабочей группы (4x4x8 блоков) все типы блоков идентичны. Будет некоторое замедление там, где это не так и типов блоков больше — два-три. Больше всего падение производительности будет в случаях, когда в одной области содержится очень большое количество блоков с различной логикой. Это может ронять производительность, но практически встречается редко и этим можно пренебречь.
Выводы подхода с расчётом всего на GPU
После реализации всего вышеописанного разнообразия я могу подвести некоторые итоги.
Наиболее очевидный из них — реализация игровой логики на GPU вполне работает. Я не вижу серьёзных препятствий, которые бы этому мешали. Я даже надеюсь, что в будущем появится больше примеров такого подхода.
Производительность подхода кратно выше того, что можно достичь на CPU. Это открывает простор возможностей для игр, которые имеют очень вычислительно-затратную логику и делает некоторые игры вообще возможными.
Существенный недостаток подхода — сложность отладки. Она практически невозможна. Если фрагментные шейдеры ещё можно как-то отлаживать, выводя на экран какие-либо результаты промежуточных расчётов, то с вычислительными шейдерами это невозможно. Остаётся лишь весьма вдумчиво писать код, или в крайнем случае пытаться через какой-нибудь RenderDoc смотреть, что там шейдеры записали в память.
Изоляция процессов? Нет, не слышали. Можно довести видеокарту до зависания, ошибившись в коде вычислительного шейдера, например, создав бесконечный цикл. В лучшем случае это ведёт к перезагрузке видеодрайвера, а в худшем — утягивает за собою всю систему, принуждая к жёсткой перезагрузке. В написании логики на CPU всё гораздо проще — если что-то неправильно, просто падает один процесс.
Заметный недостаток в контексте Minecraft-подобной игры — невозможность многопользовательского режима через подход с авторитарным сервером. Данные лежат на GPU и очень сложно отслеживать, что там изменилось, чтобы передавать их клиентам по сети. Также не понятно как синхронизировать игроков, которые находятся в разных участках мира. Единственное возможное решение для хоть какой-либо многопользовательской игры — выполнять симуляцию на всех компьютерах игроков и молиться, чтобы она не разошлась.
Запуск расчётов на GPU весьма многословен. Надо создать вычислительный шейдер, compute pipeline, запускать его когда надо и синхронизировать по доступу к данным с другими расчётами. Это всё весьма усложняет жизнь, в сравнении с расчётами на CPU, где можно просто написать функцию и вызвать её.
Слабость GPU в однопоточных расчётах толкает к использованию многопоточных расчётов, что выливается в необходимость придумывания особых алгоритмов игровой логики, которые принципиально распараллеливаемы. Это требует некоторой смены парадигмы мышления разработчика.
Множество стандартных компонентов, использующихся для написания игровой логики, не могут быть использованы на GPU — физические движки, ECS, системы сериализации/десериализации, очереди сообщений и т. д. Всё это при необходимости нужно писать своё.
Заключение
Я надеюсь, мой опыт будет кому-либо полезен. Мне было бы весьма отрадно, если кто-то ещё реализует нечто подобное.
Код проекта открыт, кто интересуется — может его собрать у себя и доработать, ну или использовать для вдохновения своего проекта.
Ссылки
Github проекта. Там же есть свежая сборка. Репозиторий оригинального Hex.
Youtube канал автора, где есть в том числе видео демонстрации вышеописанного проекта.