Как сделать воксельную модель
Как визуализировать и анимировать (геофизические) модели. Воксельные модели и сетчатые поверхности
Также смотрите другие статьи серии «Как визуализировать и анимировать (геофизические) модели»:
В результате численного моделирования мы обычно получаем воксельные модели, которые для дальнейшей обработки и анализа необходимо преобразовывать в сетчатые поверхности. На картинке ниже в полупрозрачной воксельной модели изображена геологическая структура, выделенная и преобразованная в сетчатую поверхность и дополненная поверхностью рельефа.
Постановка задачи
Численно-разностные методы и другие технологии моделирования мне знакомы еще с университета, и для научной работы было достаточно показать полученные результаты. В случае же геологического проекта это лишь часть работы — далее необходимо выделить определенные структуры, посчитать их объемы, плотность, концентрации различных полезных ископаемых и прочие характеристики. Самое простой путь — это использовать фильтрацию по диапазону значений (фильтр Threshold в ParaView) и показать полученную воксельную модель, пригодную для оценки объема. Объем полученной модели зачастую слишком большой и визуализация усложняется, но, в общем и целом, этого достаточно для вычисления объема и представления результатов. Что же касается отображения отдельных структур, моделирования потоков жидкости в них и так далее — нужны другие методы. Тем более, зачастую требуется возможность ручной корректировки выделенных структур — например, возможность раскрасить части структур или удалить незначимые детали. Здесь мне пришлось испробовать уйму различных методов и программного обеспечения, а в итоге указанная проблема разрешилась очень просто и даже элегантно. Решением является переход от воксельной модели к сетчатым моделям с помощью, как правило, выделения изоповерхностей (фильтр Contour в ParaView) по различным свойствам (атрибутам ячеек воксельной модели). Для хранения и передачи поверхностей удобно использовать формат STL (а также OBJ, PLY), в который можно их сохранить из ParaView и открыть во многих других программах.
Исходные данные
Все модели и изображения выложены на GitHub, смотрите ссылку в конце статьи.
Визуализация результатов
Рассмотрим пример визуализации воксельной модели, полученной решением обратной задачи гравики, то есть модель плотности геологической среды, построенную на основе значений гравитационного поля на поверхности:
Искомая структура в центре видна, но ее форма трудно различима. Сравним с визуализацией в виде сетчатой поверхности: 
Разница очевидна — в таком представлении все детали геологического строения видны безошибочно. Совместив оба представления, можно получить визуализацию для презентации результатов:
Пишем собственный воксельный движок
Примечание: полный исходный код этого проекта выложен здесь: [source].
Когда проект, над которым я работаю, начинает выдыхаться, я добавляю новые визуализации, дающие мне мотивацию двигаться дальше.
После выпуска первоначального концепта Task-Bot [перевод на Хабре] я почувствовал, что меня ограничивает двухмерное пространство, в котором я работал. Казалось, что оно сдерживает возможности емерджентного поведения ботов.
Предыдущие неудачные попытки изучения современного OpenGL поставили передо мной мысленный барьер, но в конце июля я каким-то образом наконец пробил его. Сегодня, в конце октября, у меня уже достаточно уверенное понимание концепций, поэтому я выпустил собственный простой воксельный движок, который будет средой для жизни и процветания моих Task-Bots.
Я решил создать собственный движок, потому что мне требовался полный контроль над графикой; к тому же я хотел себя испытать. В каком-то смысле я занимался изобретением велосипеда, но этот процесс мне очень понравился!
Конечной целью всего проекта была полная симуляция экосистемы, где боты в роли агентов манипулируют окружением и взаимодействуют с ним.
Так как движок уже довольно сильно продвинулся вперёд и я снова перехожу к программированию ботов, я решил написать пост о движке, его функциях и реализации, чтобы в будущем сосредоточиться на более высокоуровневых задачах.
Концепция движка
Движок полностью написан с нуля на C++ (за некоторыми исключениями, например, поиска пути). Для рендеринга контекста и обработки ввода я использую SDL2, для отрисовки 3D-сцены — OpenGL, а для управления симуляцией — DearImgui.
Я решил использовать воксели в основном потому, что хотел работать с сеткой, которая имеет множество преимуществ:
В статье я расскажу о текущем списке возможностей, а также подробнее рассмотрю более сложные подсистемы.
Класс World
Класс мира служит базовым классом для хранения всей информации мира. Он обрабатывает генерацию, загрузку и сохранение данных блоков.
Данные блоков хранятся во фрагментах (chunks) постоянного размера (16^3), а мир хранит вектор фрагментов, загруженный в виртуальную память. В больших мирах практически необходимо хранить в памяти только определённую часть мира, поэтому я и выбрал такой подход.
Фрагменты хранят данные блоков, а также некоторые другие метаданные, в плоском массиве. Изначально я реализовал для хранения фрагментов собственное разреженное октодерево, но оказалось, что время произвольного доступа слишком высоко для создания мешей. И хотя плоский массив неоптимален с точки зрения памяти, он обеспечивает возможность очень быстрого построения мешей и манипуляций с блоками, а также доступ к поиску пути.
Если я когда-нибудь реализую многопоточное сохранение и загрузку фрагментов, то преобразование плоского массива в разреженное октодерево и обратно может быть вполне возможным вариантом для экономии памяти. Здесь ещё есть пространство для оптимизации!
Моя реализация разреженного октодерева сохранилась в коде, поэтому можете спокойно ею воспользоваться.
Хранение фрагментов и работа с памятью
Фрагменты видимы только тогда, когда они находятся в пределах расстояния рендеринга текущей позиции камеры. Это значит, что при движении камеры нужно динамически загружать и составлять в меши фрагменты.
Фрагменты сериализованы при помощи библиотеки boost, а данные мира хранятся как простой текстовый файл, в котором каждый фрагмент — это строка файла. Они генерируются в определённом порядке, чтобы их можно было «упорядочить» в файле мира. Это важно для дальнейших оптимизаций.
В случае большого размера мира основным узким местом является считывание файла мира и загрузка/запись фрагментов. В идеале нам нужно выполнять только одну загрузку и передачу файла мира.
Для этого метод World::bufferChunks() удаляет фрагменты, которые находятся в виртуальной памяти, но невидимы, и интеллектуально загружает новые фрагменты из файла мира.
Под интеллектуальностью подразумевается, что он просто решает, какие новые фрагменты нужно загрузить, сортируя их по их позиции в файле сохранения, а затем выполняя один проход. Всё очень просто.
Пример загрузки фрагментов при малом расстоянии рендеринга. Артефакты искажения экрана вызваны ПО записи видео. Иногда возникают заметные пики загрузок, в основном вызванные созданием мешей
Кроме того, я задал флаг, сообщающий, что рендерер должен заново создать меш загруженного фрагмента.
Класс Blueprint и editBuffer
editBuffer — это сортируемый контейнер bufferObjects, содержащий информацию о редактировании в мировом пространстве и пространстве фрагментов.
Если при внесении изменений в мир записывать их в файл сразу же после внесения изменения, то нам придётся передавать весь текстовый файл целиком и записывать КАЖДОЕ изменение. Это ужасно с точки зрения производительности.
Поэтому сначала я записываю все изменения, которые нужно внести, в editBuffer при помощи метода addEditBuffer (который также вычисляет позиции изменений в пространстве фрагментов). Прежде чем записывать их в файл, я сортирую изменения по порядку фрагментов, которым они принадлежат по расположению их в файле.
Класс blueprint содержит editBuffer, а также несколько методов, позволяющих создавать editBuffers конкретных объектов (деревьев, кактусов, хижин, и т.д.). Затем blueprint можно преобразовать в позицию, в которую нужно поместить объект, а далее просто записать его в память мира.
Одна из самых больших сложностей при работе с фрагментами заключается в том, что изменения в нескольких блоках между границами фрагментов могут оказаться монотонным процессом со множеством арифметики по модулю и разделения изменений на несколько частей. Это основная проблема, с которой блестяще справляется класс blueprint.
Я активно использую его на этапе генерации мира, чтобы расширить «бутылочное горлышко» записи изменений в файл.
Класс world хранит собственный blueprint изменений, внесённых в мир, чтобы при вызове bufferChunks() все изменения записывались на жёсткий диск за один проход, а затем удалялись из виртуальной памяти.
Рендеринг
Рендерер по своей структуре не очень сложен, но для понимания требует знаний OpenGL. Не все его части интересны, в основном это обёртки функциональности OpenGL. Я довольно долго экспериментировал с визуализацией, чтобы получить то, что мне понравится.
Так как симуляция происходит не от первого лица, я выбрал ортографическую проекцию. Её можно было реализовать в формате псевдо-3D (т.е. предварительно спроецировать тайлы и наложить их в программном рендерере), но это показалось мне глупым. Я рад, что перешёл к использованию OpenGL.
Базовый класс для рендеринга называется View, он содержит большинство важных переменных, управляющих визуализацией симуляции:
Высокая глубина резкости (DOF). При больших расстояниях рендеринга может быть тормозной, но я всё это делал на своём ноутбуке. Возможно, на хорошем компьютере тормоза будут незаметны. Я понимаю, что это напрягает глаза и сделал так просто ради интереса.
На изображении выше показаны некоторые параметры, которые можно изменять в процессе манипуляций. Также я реализовал переключение в полноэкранный режим. На изображении виден пример спрайта бота, отрендеренного как текстурированный четырёхугольник, направленный в сторону камеры. Домики и кактусы на изображении построены при помощи blueprint.
Создание мешей фрагментов
Изначально я использовал наивную версию создания мешей: просто создавал куб и отбрасывал вершины, не касающиеся пустого пространства. Однако такое решение было медленным, и при загрузке новых фрагментов создание мешей оказывалось даже более узким «бутылочным горлышком», чем доступ к файлу.
Основной проблемой было эффективное создание из фрагментов рендерящихся VBO, но мне удалось реализовать на C++ собственную версию «жадного создания мешей» (greedy meshing), совместимую с OpenGL (не имеющую странных структур с циклами). Можете с чистой совестью пользоваться моим кодом.
В целом, переход к greedy meshing снизил количество отрисовываемых четырёхугольников в среднем на 60%. Затем, после дальнейших мелких оптимизаций (индексирования VBO) количество удалось снизить ещё на 1/3 (с 6 вершин на грань до 4 вершин).
При рендеринге сцены из 5x1x5 фрагментов в окне, не развёрнутом на весь экран, я получаю в среднем около 140 FPS (с отключенным VSYNC).
Хотя меня вполне устраивает такой результат, мне бы по-прежнему хотелось придумать систему для отрисовки некубических моделей из данных мира. Её не так просто интегрировать при greedy meshing, поэтому над этим стоит подумать.
Шейдеры и выделение вокселей
Реализация GLSL-шейдеров — одна из самых интересных, и в то же время самых раздражающих частей написания движка из-за сложности отладки на GPU. Я не специалист по GLSL, поэтому многому приходилось учиться на ходу.
Реализованные мной эффекты активно используют FBO и сэмплирование текстур (например, размытие, наложение теней и использование информации о глубинах).
Мне всё ещё не нравится текущая модель освещения, потому что она не очень хорошо обрабатывает «темноту». Надеюсь, это будет исправлено в дальнейшем, когда я буду работать над циклом смены дня и ночи.
Также я реализовал простую функцию выбора вокселей при помощи модифицированного алгоритма Брезенхэма (это ещё одно преимущество использования вокселей). Она полезна для получения пространственной информации в процессе работы симуляции. Моя реализация работает только для ортографических проекций, но можете ею воспользоваться.
Игровые классы
Создано несколько вспомогательных классов для обработки ввода, отладочных сообщений, а также отдельный класс Item с базовой функциональностью (который будет в дальнейшем расширен).
Мой обработчик событий (event handler) некрасив, зато функционален. С радостью приму рекомендации по его улучшению, особенно по использованию SDL Poll Event.
Последние примечания
Сам движок — это просто система, в которую я помещаю своих task-bots (подробно о них я расскажу в следующем посте). Но если вам показались интересными мои методы, и вы хотите узнать больше, то напишите мне.
Затем я портировал систему task-bot (настоящее сердце этого проекта) в 3D-мир и значительно расширил её возможности, но подробнее об этом позже (однако код уже выложен онлайн)!
Воксельная графика своими руками — первые шаги
Знакомство с воксельной графикой
В процессе поиска алгоритмов расчета коллизий на сайте GameDev, я наткнулся на маленькую статью про движок idTech 6 и заинтересовался воксельной графикой, которую противопоставляют полигональной графике, на которой сейчас основана почти вся компьютерная графика.
Вообще, воксел расшифровывается как «объемный пиксель», однако сейчас под вокселом в основном понимается некий примитив, чаще всего куб или прямоугольный параллелепипед, который имеет определенный размер и цвет. В idTech 6 и в движке Кена Сильвермана Voxlap они хранятся в разреженном октодереве (SVO — sparse voxel octree), что позволяет экономить память и делает возможным простую реализацию «уровня детализации».
Первые попытки
Штурмовать сразу трехмерное пространство я не решился — слишком пугающе выглядел весь тот список формул, которые бы пришлось освоить (о них речь пойдет чуть ниже), и решил просто переписать код, чтобы платформер использовал «боксы» — квадраты, и соответственно хранились не в разреженном октодереве, а в разреженном квадродереве.
Первый код был ужасен — все функции работы с деревом, такие как удаление, обход дерева, создание узлов, были итеративными отдельными от класса QuadTree функциями. В прочем, даже добавление их в пределы класса особо не сыграло роли, так как в последствии выяснилось, что рекурсивные функции сильно выигрывают в данном случае. Единственное, что принесли полезного эти первые попытки — это четкая формулировка, какие функции мне нужны, а также основы реализации деревьев на С++, что в дальнейшем очень помогало и, я надеюсь, еще будет помогать. И, конечно же, именно те первые попытки подтолкнули изучать OpenGL (правда до этого прельстился Direct2D, но очень быстро разочаровался в нем).
Переход в объем
OpenGL я начал изучать на NeHe gamedev и как то очень быстро втянулся в трехмерное пространство и начал планировать движок для Quake-подобной игры. Квадродерево было переписано в октодерево и начались первые сложности. Октодеревья потребляют памяти гораздо больше, и даже не смотря на то, что все основные функции стали рекурсивными, все равно они тратили слишком много времени и памяти. Для решения этой проблемы были реализованы следующие методы:
Оптимизация памяти
В октодереве очень часто приходится использовать операторы new/delete, которые выделяют для указателя место в динамической памяти (куче). Динамическая память медленнее, чем статическая (стек), а также сами функции new/delete выполнялись для меня слишком медленно. Из-за чего был написан собственный класс MemoryPool и шаблон mem_pool_tree.
mem_pool_tree был написан под впечатлением от BST-дерева, с которым я познакомился из книги Т. Кормана «Алгоритмы. Построение и анализ», и не работает напрямую с памятью, а только оперирует цифрами, которые в последствии используются для смещение указателя с начала массива в статической области памяти. Предугадать удаления не представлялось возможным, а вот выделять «правильные» куски памяти было реально, из-за чего я взял у BST дерева идею и повороты, и добавил «блочность» — mem_pool_tree хранит узлы, в котором две переменные хранят начало и конец блока, и еще две переменные — начало и конец занятого пространства. Если происходит попытка удалить кусок в середине занятого пространства, то узел делится, если вызывается функция выделения куска, то алгоритм ищет такой блок, где выделение пространства позволит ему объединится с соседним блоком. И периодически вызывается функция балансировки.
Многопоточность
Из-за строения дерева, в котором у родительского узла есть указатель на массив из восьми дочерних узлов, функции, где требуется полный обход дерева (такие, как удаление всего дерева, удаление лишних элементов, вычисление средних вокселов и т.д.), были написаны с возможностью включить многопоточность. Многопоточность была реализована с помощью OpenMP. К примеру, надо оптимизировать дерево (например, зачем хранить восемь дочерних узлов, если можно их цвет передать родительскому узлу, а их удалить). Реализуем:
Так как дочерние узлы между собой никак не связаны, такая операция не требует мьютексов, что очень хорошо в условиях, когда требуются минимальные затраты памяти.
Загрузка и сохранение вокселей
Долго пришлось искать оптимальный метод хранения вокселей в файле — ведь в условиях, когда оперативная память ценна, хранить лишние вокселы в оперативке является непозволительной роскошью. После долгих исканий, выбор остановился на SQLite3, в котором есть кэширование, а также возможность загрузить только те вокселы, которые требуются исходя из значений «уровня детализации». Самая быстрая работа с SQLite3 базами оказалось при встраивании в проект исходного кода sqlite3 и самостоятельной компиляции (точных цифр не помню, но что то вроде полмиллиона переменных за 200-250 ms, причем на нетбуке с Intel Atom). Естественно, в SQLite3 использовались для ускорения «Begin transaction;», «Commit transaction;», «PRAGMA journal_mode = MEMORY;», «PRAGMA synchronous = OFF;» и т.д.
Скриншоты
Собственно, здесь я покажу небольшие скриншоты, так как дальше идет описания кода, который на стадии реализации. Объекты на скриншотах, конечно, очень простенькие, но единственная причина этого в том, что у меня все не доходят руки нарисовать нормальную сложную модель, или переконвертировать существующие. Более того, это самые первые скриншоты, и для растеризации был написан малюсенький код с использованием GDI, а не OpenGL, и трассировку лучей выполнял самый обычный цикл, в котором расчеты матрицы поворота и прочие расчеты выполнялись на CPU.
Текущие задачи и заключение
Полиморфизм
Сейчас октодерево в очередной раз переписывается с применением полиморфизма. Основная задача — чтобы дерево было не чистым октодеревом, а скрещением с kd-tree (дерево, в котором идет не разбиение воксела на 8 маленьких вокселей, а разбиение на два воксела с определенной пропорцией и по определенной оси), и еще другими модификациями.
RayCasting
Октодерево позволяет Ray Casting, алгоритм «бросания лучей», с помощью которого сейчас пишу растеризатор. Также реализации алгоритма используется OpenGL (генерация текстуры из массива и отображение его на полигоне), «групповая трассировка» и C++ AMP. В целом, эта тема хорошо раскрыта на ray-tracing.ru.
Заключение
В целом, тема интересная, и можно много интересного найти по ней. Например: статья на хабре про движок Atomontage и презентация технологии SVO с SIGGRAPH 2012.
Написанный мною класс распределения памяти с использованием массива в статической памяти, после замеров, выдал следующие данные:
VoxEdit
Предназначение программы
Режимы работы
Программа предлагает три режима работы:
Переключение между режимами можно осуществлять по иконке домика вверху слева. Ниже представлены скриншоты Modeler и Animator:
Принципы работы
В Modeler можно создавать простые объекты, которые как правило умещаются в куб 32x32x32 воксела. Размер куба можно менять. А при создании объектов, из которых будет состоять большой объект, даже рекомендуется уменьшать объем сцены до максимально возможного. Каждый такой объект сохраняется в VXM файл. Из них можно сложить составной объект, назначить ему ноды и узлы в Animator. Каждую ноду можно анимировать на Timeline. Можно создать различные сценарии отдельных анимаций, которые будут вызываться через select-элемент. Например, для волка есть сценарии: бежать, атаковать, кушать, умирать. Примеры проектов волка, зайца и др. встроены в программу.
На нашем сайте есть обзор другого воксельного редактора MagicaVoxel, в котором в чем-то удобнее моделировать объекты. Так вот, VoxEdit может эти объекты импортировать для дальнейшей анимации. Для этого надо в режиме Animator в Library выбрать Import VOX. По этой теме смотрите видео по ссылке в конце обзора.
Более-менее подробный Help выложен на сайте разработчика: https://guidelines.voxedit.io/#/home
Обзорная статья на английском с опаисанием всех кнопок: https://medium.com/sandbox-game/voxedit-the-sandbox-voxel-editor
Последовательность создания анимации
Предположим, вы уже смоделировали отдельные объекты в VXM или VOX файлах (тело, голова, руки, ноги), которые призваны составить цельный объект.
Всё, первая анимация создана! Теперь от первого ключа до второго при проигрывании анимации объект будет вращаться. Таким же образом можно создать анимацию поступательного движения с помощью инструмента Move Node. Таким же образом можно создать анимации во времени к другим нодам.
Замечу, что программа позволяет записать разные сценарии в виде отделенных друг от друга анимаций. Если нажать на значок ▼ на Timeline под индикатором времени, а потом New Animation, то будет положено начала новому сценарию, которые вдальнейшем по этому же значку можно будет менять.
Скачать
Программа официально бесплатная, поэтому смело ее скачивайте с сайта производителя. Доступны версии для Windows и MacOS. По всей вдимости, на подходе версия для Linux.
Как мы сделали игру для Highload++ с воксельной графикой и VR
На самом деле, это легкий технический лонгрид, надеемся, после прочтения у вас появится дополнительный интерес сделать какую-нибудь игру, или хотя бы вы узнаете, как это работает.
О спикере: Александр Хаёров (@allexx) руководит отделом разработки в компании Ingram Micro Cloud. Ребята в команде Александра считают себя не просто отличными инженерами, а называют себя великой командой voxel джедаями, мастерами оптимизации, гуру 3D и повелителями больших данных! [примечание: по аналогии с названиями должностей в LinkedIn и Medium]
Эта классная команда, готовясь к выступлению на Highload++ 2017, решила развлечь аудиторию и сделать что-то новое и интересное для стенда. Поэтому они запилили игру, о создании которой и пойдет дальше речь.
Хозяйке на заметку: со стороны организаторов, мы очень приветствуем усилия по подготовке к участию в конференции. Они многократно окупаются, привлекая участников, и, как выясняется, идут на пользу команде.
Часто, разбирая почту, я просматриваю заголовки информационных лент, где мелькают самые разные новости. Однажды я увидел заголовок «Кто такие инди-разработчики». Почему-то он меня зацепил, и я решил почитать эту статью. Я открыл ее — там было очень много цифр, букв и статистики.
Справка: Инди-разработчики — это люди, которые творят игры без специального бюджета и без финансовой поддержки издателей компьютерных игр.
Как правило, инди-разработчики не обременены рамками сценария и шаблонами, поэтому у них получаются довольно интересные игры, фильмы и прочее.
В этой статье я узнал несколько забавных фактов:
Так получилось, что мы тоже начали делать игру.
Почему мы начали делать игру
Мне всегда нравились игры от сервиса Reddit. Думаю, и вы не один месяц своей жизни провели на этом ресурсе.
A social experiment by Reddit
Каждый год Reddit проводит социальный эксперимент, как они это называют. Хотя на самом деле это различные игры для сообщества. В 2017 году социальный эксперимент проходил, как всегда, в начале апреля (на день дурака).
Суть игры была многообещающей. Разработчики Reddit создали картину из 1 000 х 1 000 пикселей. Каждому зарегистрированному пользователю на Reddit, а их несколько миллионов, предлагалось закрасить 1 пиксель этой канвы одним цветом из достаточно широкой палитры.
Мероприятие продолжалось 72 часа, и каждый участник раз в 5 минут мог нарисовать лишь одну точку на экране. Люди создавали разные картинки, боролись между собой, перекрашивая пиксели. Некоторые страны и сообщества объединялись и делали совместную работу.
В конечном итоге получилось интересное панно, из которого кто-то потом сделал пазл, кто-то связал носки с таким орнаментом и т.д.
Мне очень понравилась сама идея, что можно вовлекать людей в массовые онлайн игры, пускай и с простым гейм-плеем. Это, наверное, было главным вдохновением для нас создать именно онлайн-игру. Вообще я считаю, что игры полны веселья и уверен, что вы иногда играете в разные игры и это приносит вам удовольствие.
Но для технаря самое интересное находилось внутри, поскольку игра привлекла огромное количество людей — в ней участвовало более миллиона зарегистрированных уникальных пользователей — до 90 тысяч человек одновременно закрашивало пиксели ежесекундно!
Профессионально я занимаюсь разработкой web-сервисов и различных M2M-сервисов, когда сервер общается с серверами. Это на самом деле очень важно и ответственно, но порой немножко скучно. Поэтому новый девелоперский опыт всегда интересен. Я им с вами сейчас как раз поделюсь.
Забегая вперед, скажу, что мы действительно узнали очень много нового и интересного про игры, не имея при этом никакого опыта изначально.
The Game
Features
Мы с ребятами собрались и набросали скелет идеи, о чем можно сделать игру. Сначала мы решили идти с козырей и написать классные Features.
Так у нас образовался Features set, но без определенного геймплея.
Concessions
Но, подумав примерно недельку, мы решили, что нужно как-то ограничить свои хотелки и пошли на небольшие компромиссы.
Справка: Воксель (Voxel) — это практически пиксель, но в 3-мерном мире. Например, в игре Minecraft мир представлен вокселями.
На этом мы разошлись на некоторое время и в дальнейшем решили разговаривать только по делу, в частности, обсудить геймплей и правила.
Gameplay и правила
Кажется, что геймплей — это очень простая вещь! Мы прекрасно знаем, как играть в StarCraft, Doom или Quack. Но когда вы создаете свою игру, у вас возникает огромное количество идей. Эти мысли разлетаются в разные стороны и очень сложно (особенно в команде) договориться о том, как игра будет выглядеть и что в ней будет происходить.
Этот процесс у нас не был линейным, мы не смогли сразу все определить. Финальная версия наших правил выглядит достаточно просто:
На этом мы определились со всеми менеджерскими функциями и решили заняться архитектурой.
Архитектура
Так как мы создаем enterprise-продукты, то решили начать с enterprise-архитектуры нашей игры. Мы подумали, что в ней обязательно должны быть:
Проблема репликаций в распределенных системах
Как «хранилка» должна общаться с браузером, где работает игра? Тут начинаются интересные моменты, и я бы хотел вас отвести в более знакомую область.
Вообще проблема репликаций в распределенных системах достаточно хорошо изучена. Репликации ежедневно используются в нашей отрасли. Но любая игра, особенно сетевая, представляет собой нетиповую ситуацию репликаций, когда нужно обеспечить репликацию только для того, чтобы игра случилась. Если у вас в распределенной системе нет репликации и связности, согласованности между игроками, то игру можно завершать, потому что в нее невозможно играть.
Выделяются два вида репликаций:
Плюсы и минусы активной репликации:
+ В активной репликации все просто и интуитивно понятно: берем данные, отправляем всем другим игрокам, получаем от всех других игроков информацию.
+ Второй важный момент — эта система достаточно эффективна. Действительно, не нужно никакое дополнительное устройство в виде сервера, которое будет принимать, обрабатывать и передавать другим игрокам данные.
— Но есть огромный минус — системы, построенные на активной репликации, очень хрупкие. Достаточно появления сетевых проблем, например, потерь, задержек или затруднений с клиентами, получается полностью несогласованная система. Синхронизация ломается, а наша задача — иметь одинаковый общий мир.
На самом деле выйти из ситуации со сломанной синхронизацией достаточно непросто. Для этого существуют различные протоколы, например, Paxos, но все они незаметно усложняют простую схему активной репликации, требуют времени и вычислительных ресурсов.
Для примера могу сказать, что классическая игра StarCraft построена на активной репликации. Это один из явных примеров использования простой, но достаточно хрупкой модели. Именно поэтому, когда появляются определенные проблемы в синхронизации, игру, как правило, приходится завершать и начинать заново.
Плюсы и минусы пассивной репликации:
+ В отличие от активной, пассивная репликация очень стойкая к десинхронизации. Если что-то пойдет не так, есть специальное устройство — сервер, который может привести систему в норму.
+ Вторым моментом, и зачастую очень недооцененным и важным, является безопасность игр. Недавно появилась игра VKpixel Battle — прямой аналог игры Place от Reddit, в которой тоже можно было разрисовывать доску. Эту игру взломали в течение нескольких часов ( источник ). В пассивной модели безопасность игры заметно легче обеспечить по той причине, что опять-таки есть сервер, где можно много всего контролировать.
— Но не бывает одних плюсов без минусов. С появлением сервера — устройства, которое принимает и отправляет данные, возникает классическая точка отказа. Если не применять специальные средства, например, шардирование, разделение на ноды, то можно потерять всю игру путем выхода из строя сервера.
Мы недолго думали, и, как и разработчики всех современных игр, выбрали пассивный способ репликации. На самом деле сейчас подавляющее большинство игр (порядка 99%) используют пассивную репликацию. Поэтому на нашей мощной enterprise-архитектуре появился еще один компонент — game-бэкенд, который берет на себя задачу синхронизации.
Data Structure
Поговорим немножко о системе хранения. Дело в том, что к выбору хранилища мы относились, скажем так, без должного внимания, как это принято в некоторых кругах.
Для того, чтобы понять, в чем хранить данные, нужно знать, как их представлять. Наверное, это наиболее важный вопрос, который определяет те или иные критерии. Рассмотрим структуру данных, которая возможна в нашей игре.
В ней очень много вокселей и ограниченный мир. Можно взять всю информацию о кубиках (вокселях) и хранить в обычном линейном большом массиве. Это очень простой и понятный способ. Его основным преимуществом является константная запись и чтение в ячейку. Мы можем спокойно получить информацию о вокселе, и это потребует какое-то константное время.
В действительности очень много современных игр, в том числе и Minecraft, стартовали именно с такой модели, и она себя показала достаточно успешной.
Минусом здесь является большое потребление памяти. Дело в том, что наш мир растет в трех измерениях, поэтому количество памяти, необходимое для хранения этих данных возрастает нелинейно.
Эту проблему можно решить, например, с помощью октодеревьев. Не будем вдаваться в то, что это такое, предлагаю для понимания просто посмотреть на картинку.
Если 3-мерный мир представить в виде большого куба, то его можно разделить на 8 частей — окты. Каждую из них можно также делить на 8 секций. Этот механизм позволяет сильно сэкономить на хранении структуры за счет областей, в которых отсутствуют данные.
Здесь есть явный плюс — это более выгодная с точки зрения хранения структура. Минус изначально не так очевиден, но быстро вылезает на практике. Дело в том, что нужно использовать различные кэши. Как правило, все, кто использует октодеревья, жалуются, что это заметно медленнее работает, чем обычные массивы.
Наконец, есть третий вариант, я бы его назвал компромиссным — можно взять обычный линейный массив и разделить его на некоторые равномерные области (чанки). Это дает определенные преимущества. Например, в отличие от обычного массива, можно подгружать отдельные блоки. Нам не нужно загружать целый мир одного пользователя. Мы можем загружать только ближайшие от него блоки.
Но есть определенный минус — это конечно же усложняет всю модель обычного массива, потому что нужно хранить ссылки на чанки, оперировать чанками, добавлять логику во фронтенд игры и т.п.
Мы решили, что для нашей игры последний вариант оптимален и выбрали его. После этого выбор хранилища для нас прошел незаметно: мы решили — пускай это будет MongoDB. Я бы сейчас не хотел разводить холивар на эту тему — уверен, что на многих других прекрасных базах данных это тоже можно реализовать. Однако мы имели небольшой опыт работы с этой базой и поэтому решили на ней остановиться для экспериментов.
Протокол взаимодействия между фронтендом и бэкендом
У нас есть некая структура, есть клиенты, наверное, появится какой-нибудь браузер, в котором это все будет отображаться. Но как передавать данные между хранилищем и игрой? Пора подумать о протоколе.
Как мы уже знаем, наш мир представлен в виде параллелепипеда с основанием 1000×1000 и высотой 200. Можно проигнорировать высоту и всегда использовать максимальную высоту в выгрузке. Это сильно упрощает создание игры.
В свою очередь каждый квадрат в соответствии с нашим стандартом мы разбили на чанки 32×32 вокселя внутри.
Как я уже сказал, мы решили использовать MongoDB. В ней воксели хранятся достаточно просто, для этого мы используем обычные документы. Внутри документ выглядит примерно, как нас слайде ниже:
Теперь у нас возникают, как минимум, две задачи. Например, мы направляем игрока. Он рождается в мире в некой точке.
В обратную сторону можно наблюдать запросы об обновлении прочих кубиков.
В данном случае речь идет о том, что, находясь в мире и получив некое его изначальное состояние, мы хотим наблюдать новые кубики, которые создают другие пользователи. Для этого мы подписываемся на события и получаем сообщения типа updated о всех кубиках, которые появляются в игре.
Наконец, мы хотели добавить немножко интерактивности в игру, и поэтому добавили специальное сообщение об активности пользователей — когда кто-нибудь зашел в игру, или вышел, или перехватил флаг, который позволяет получать очки.
Так у нас сформировался протокол взаимодействия.
У нас был небольшой выбор того, как мы можем общаться между бэкендом и фронтендом: HTTP, WebSocket, HTTP2. Мы решили остановиться на WebSocket по понятным причинам — для того, чтобы интуитивно уменьшить потенциальные задержки, которые были возможны.
Также мы подумали, что было бы неплохо получать результаты игры — например, смотреть, кто вошел в игру, какие у него очки. Для этого мы сделали отдельную «вьюшку», которую прикрутили к фронтенду и решили использовать для нее HTTP, чтобы не делать для нее авторизацию и не усложнять этот процесс.
Так у нас сформировался определенный стек в архитектуре. Ключевой точкой взаимодействия в нем стал WebSocket.
Game-backend
Бэкенд, как минимум, можно назвать сердцем нашей системы.
Game-frontend
Это изюминка нашей игры — то, как игра начинает жить и существовать.
В первую очередь у нас встал вопрос — каким образом мы можем написать игровой движок, как вообще делать игры и как это все работает. После недолгого изучения материала мы поняли, что существует библиотека WebGL, которая позволяет очень многое. Она работает с библиотекой OpenGL, которая уже в свою очередь работает с оборудованием, с драйверами, с видеокартой и т.п.
Поэтому первая мысль была — использовать обычный нативный JavaScript, посмотреть, какой API предоставляет WebGL и начать делать игру. Эту идею мы достаточно быстро отмели, потому что по опыту в web-разработке понимали, что разрабатывать самому web-сервер — очень странная и долгая затея. Тем более у нас не было так много времени.
После недолгих поисков мы нашли JS-библиотеку, которая называется Voxel.js. На самом деле она стала для нас Граалем, потому что представляет очень много инструментов.
Библиотека существует уже более 3 лет, и, как заявляет автор, фактически является tool-kit для создания современных браузерных игр, причем воксельных. В ней присутствует все, что необходимо.
Как выглядит весь стек
На самом деле сцену с использованием three.js, и в частности с Voxel.js, который это использует, произвести на свет не так уж и просто. Хотя кажется, здесь нет ничего сложного ровным счетом.
Посмотрим на код, но не будем заранее пугаться.
Чтобы создать классную 3D-картинку в браузере, нужны на самом деле всего 3-4 вещи:
4. Для того, чтобы создать объект, нам нужны:
Дальше вызывается простая функция animate. Как setInterval в браузере, она каждый раз отрисовывает новый фрейм и получается анимация. Фактически этот механизм используется в обычных 3D играх и доступен в браузере.
Виртуальная реальность
Я бы хотел поговорить немножко о VR. Как я уже говорил, нам хотелось использовать хайповую передутую технологию для того, чтобы привлечь внимание. Мы решили использовать VR. Это был случайный, спонтанный выбор, но изучив тему, мы поняли, что VR — это не очень новая и не очень хайповая технология. Эта картинка датирована началом XX века — это VR, но XX века!
Нужно всего лишь использовать этот шлем, чтобы рассматривать настоящие 3D-объекты — единственное, что в статике.
Oculus Rift
Мы решили использовать не статическую картинку, а все-таки создать графику с видео. Поэтому наш выбор пал на Oculus Rift.
Опять-таки выбор был достаточно интуитивный и спонтанный. В нем нет ничего особенного, Oculus Rift представлен, как минимум, 3 базовыми устройствами:
+ Это действительно VR-картинка — она вполне настоящая и позволяет обманывать наш мозг и представлять, что мы находимся в 3D-мире.
+ Неплохое разрешение экрана и очень приличная скорость обновления картинки. Я лично не наблюдал каких-то заметных ухудшений своего самочувствия во время просмотра картинки, в отличие от первых старых шлемов виртуальной реальности.
+ Это действительно очень удобное устройство, хорошо сделанное, которое прекрасно лежит в руке и отлично носится на голове. Можно сказать, что это действительно потребительское устройство.
— Я представлял себе VR так, что можно просто надеть шлем, девайсы и будет классно! На самом деле это огромное количество проводов. Фактически к каждому устройству необходим кабель, а то и два.
— Второй важный для меня момент и легкое разочарование — я ожидал, что я возьму свой обычный лэптоп и смогу программировать, сидя на диване. Оказалось, что есть серьезные ограничения: можно использовать только Windows, Oculus и SDK не доступен для macOS/Linux. Возможно, это стратегия компании или особенность операционной системы — мне сказать достаточно сложно.
— Я не смог запустить даже простое видео или игру в VR, не подключая достаточно приличную видеокарту. Я не являюсь ярым геймером современных 3D-игр и поэтому мне пришлось искать ее для того, чтобы начать разработку.
Думаю, что если вас не стесняют эти минусы, то смело можно пробовать современные шлемы виртуальной реальности.
Как делать игры для VR
Для нас эта тема была абсолютно закрыта и непонятна. Мы думали, что нужна специальная магия, возможно, устройства или ученая степень. На самом деле нет.
A-Frame
Сейчас не так много инструментов, которые позволяют делать VR-игры еще и в браузере.
Наверное, первое, что можно найти в интернете, это фреймворк A-Frame. Он является лидером и вообще доминирующим фреймворком для создания дополненной и виртуальной реальности.
Что здорово, он работает с огромным количеством устройств, включая Oculus Rift, и даже с обычными мониторами. Это позволяет работать в режиме совместимости, когда нет шлема, что очень удобно для разработки.
Но, наверное, самое здоровское то, что если вы являетесь web-разработчиком, он будет вам очень близок, потому что использует парадигму и концепцию HTML. Вам не придется компилировать код, не нужны специальные программы — достаточно использовать свой браузер и обычный блокнот для того, чтобы написать первую 3D VR-сцену в браузере.
Код на картинке выше выглядит, как обычная html-страница. Вспомните мой предыдущий рассказ о сцене и рендере, здесь можно увидеть примерно то же самое.
Есть сцена, на которой созданы разные объекты. Рендер и камера заданы по умолчанию, но их можно переопределить. Если вы скопируете этот блок кода, то в своем браузере увидите соответствующую картинку. На ней с помощью мышки или клавиатуры можно перемещаться и увидеть полностью 3D-объекты с тенями и т.п. Дальше можно здорово развиваться, расширяя эту идею.
Так мы начали делать версию для VR.
Вы спросите — а где здесь VR? VR здесь на самом деле находится в правом нижнем углу. На этой картинке этого нет. Там появляется очень маленький значок очков виртуальной реальности. При нажатии на эту кнопку, появляется VR-картинка. Это выглядит абсолютной магией, потому что вы не делаете ничего специально для того, чтобы появилась виртуальная реальность. Это делает за вас фреймворк.
Если посмотреть детальнее, то здесь нет ничего сложного. Для этого достаточно создать изображение для двух глаз и правильно его расположить. Это позволит генерировать правильную картинку.
Возвращаясь к нашей enterprise-архитектуре, мы пришли к тому, что у нас будет два клиента:
Оптимизация
Напоследок хотел бы рассказать немного об оптимизации.
Пока мы делали игру, приключалось очень много разных историй, три из которых мне бы хотелось отметить. Это довольно любопытные вещи, которые могут очень сильно упростить жизнь разработчика.
1. Pre-process voxel models
Как я уже говорил, для того чтобы создать мир, мы использовали воксели и программу для рисования вокселей наподобие PowerPoint. Конечно же, те объекты, которые мы создавали, состояли из огромного количества полных кубиков.
Когда этот мир загружался, наша картинка требовала много данных и достаточно медленно работала, поскольку содержала очень много вокселей. Первое, что нам пришло на ум: «Почему бы не сделать объекты полыми, то есть внутри не создавать эти самые кубики? Ведь пользователь их все равно не увидит!»
Мы написали очень простой алгоритм, который позволяет исключать из нашего мира, который мы создали в отдельном редакторе, воксели, которые находятся внутри. Это просто колоссально снизило количество передаваемых данных — примерно на 78% уменьшило количество вокселей в мире.
2. User Mesher
Вторым важным моментом является рекомендация использовать mesher. Дело в том, что, создавая игру с воксельной графикой, мы конечно же в голове у себя представляем отдельные кубики. Но в действительности мир, как и в Minecraft в том числе, устроен немножко по-другому.
Мы используем обычные полигональные модели, и поэтому имеет большой смысл все отдельные воксели соединять вместе в сеть (или Mesh). Для этого используется специальный инструмент mesher. Он колоссально увеличивает производительность, потому что уменьшает количество вершин, граней, ребер. Для того, чтобы просчитать, например, падение света или какую-то физику, нужно меньше вычислительных ресурсов, поскольку будет меньше полигонов.
Кстати, в некоторых фреймворках mesher включен по умолчанию. Так c Voxel.js мы получили достаточно приличный FPC изначально. В A-Frame такого нет, и мы использовали mesher уже дополнительно.
3. Enable compression for WebSocket (RFC 7692)
Наконец, оптимизация из мира web-разработки. WebSocket — отличная технология, но по умолчанию она не производит никаких манипуляций с теми сообщениями, которые передаются с ее помощью.
Мы передавали достаточно большое количество текста (в данном случае JSON) между клиентом и сервером. Эти данные были очень похожи друг на друга. Поэтому у нас возникла идея — почему бы нам их не сжать?
Единственной загвоздкой было наличие WebSocket, а не классического HTTP. Открытием для нас, возможно, это будет также приятным открытием для вас, стало существование специального RFC, который описывает, как можно делать компрессию внутри WebSocket.
Там есть несколько технологий, основанных на использовании специальных плагинов. Фактически включение такой технологии на сервере в нашем случае позволило заметно понизить трафик — буквально с 5 MB передаваемых данных до 1,8 MB.
Приятно, что современные браузеры — такие, как Chrome, Firefox, Safari — поддерживают компрессию со стороны клиента. Вам достаточно правильно включить компрессию на сервере и реализовать ее, и все будет прекрасно работать.
Единственно важным моментом является то, что во всех отладочных инструментах браузера информация по компрессии не отображается, а показывается информация уже раскрытых данных. Поэтому не стоит переживать — компрессия, скорее всего, у вас работает, а данные, которые показаны, уже активны после всех процедур.
В заключении хочу сказать — обязательно пробуйте что-то новое и получайте от этого удовольствие! Заходите к нам и посмотрите, как выглядит наша игра, в статье специально нет ни одного скриншота.
Для любопытных ребят, которым хочется посмотреть кодовую базу, мы сделали ее открытой. Вы можете понаблюдать, как мы разрабатывали игру, что она из себя представляет и даже запустить без проблем свой экземпляр игры, включая сервер и две версии — для VR и просто для браузера.
Кстати, к РИТ++ 2018 ребята готовят ремейк логической игры Pipes — называется CloudPipes.
Что еще раз подтверждает тезис, участие в конференциях, особенно наших, — это весело!
Расписание фестиваля с докладами, митапами, викториной и «Что? Где? Когда?» готово, а у вас еще есть шанс приобрести билет.
Также на забывайте про Highload++ Siberia, которая тоже всего через месяц.