http://habrahabr.ru/company/wargaming/blog/245321/

Пролог

Эта история началась более трех лет назад. Наша небольшая компания DAVA стала частью Wargaming, и мы начали обдумывать, какие проекты делать дальше. Чтобы напомнить, каким был мобайл три года назад, скажу, что тогда не было ни Clash Of Clans, ни Puzzle & Dragons, ни многих очень известных сегодня проектов. Mid-core тогда только-только начинался. Рынок был в разы меньше сегодняшнего.

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

Тогда в разработке у нас находилось несколько игр. Одна из них носила рабочее название «Sniper». Основной геймплей-идеей была стрельба в снайперском режиме из стоящего в обороне танка, по другим танкам, которыми управлял AI и которые могли атаковать в ответ.

В какой-то момент нам показалось, что стоящий танк — это очень скучно, и за неделю мы сделали прототип мультиплеера, где танки уже могли ездить и атаковать друг друга.

С этого все и началось!

Когда мы начинали разработку “Снайпера”, то рассматривали технологии, которые тогда были доступны для мобильных платформ. На тот момент Unity был еще на достаточно ранней стадии своего развития: по сути, необходимых нам технологий еще не было.

Основной вещью, которой нам не хватало, был рендеринг ландшафта c динамической детализацией, что является жизненно необходимым для создания игры с открытыми пространствами. Было несколько сторонних библиотек для Unity, однако их качество оставляло желать лучшего.

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

В итоге, мы решили дорабатывать свой движок!

Он на тот момент уже использовался в наших предыдущих казуальных проектах. Движок имел достаточно хорошо написанный низкий уровень работы с платформами и поддерживал iOS, PC, Mac, плюс были начаты работы по Android. Было написано много функциональности для создания 2D-игр. То есть, был неплохой UI и много всего для работы с 2D. В нем были первые шаги по 3D-части, так как одна из наших игр была полностью трехмерной.

Что у нас было в 3D-части движка:

• Простейший граф сцены.
• Возможность рисования статических мешей.
• Возможность рисования анимированных мешей со скелетной анимацией.
• Экспорт объектов и анимаций из Collada-формата.

В общем, если говорить о функциональности серьезного современного движка, в нем было очень мало.

Начало работ

Началось все с доказательства возможности отрисовать ландшафт на мобильных устройствах: тогда это были iPhone 4 и iPad 1.

После нескольких дней работы мы получили вполне функциональный динамический ландшафт, который работал довольно сносно, требовал где-то 8MB памяти и давал 60fps на этих устройствах. После этого мы начали полноценную разработку игры.

Прошло около полугода, и маленький мини-проект превратился в то, чем сейчас является Blitz. Появились совершенно новые требования: MMO, AAA-качество и другие требования, которые движок в его изначальном виде на тот момент уже не мог обеспечить. Но работа кипела полным ходом. Игра работала и работала неплохо. Однако производительность была средней, объектов на картах было мало, и, собственно, было множество других ограничений.

На этом этапе мы начали понимать, что фундамент, который мы заложили в движок, не выдержит пресса реального проекта.

Как все работало на тот момент

Вся отрисовка сцен была основана на простой концепции Scene Graph.

Основной концепции являлись два класса:

• Scene — контейнер сцены, внутри которого происходили все действия
• над сценой.
• SceneNode — базовый класс узла сцены, от которого наследовались все классы, которые находились в сцене:
• MeshInstanceNode — класс для отрисовки мешей.
• LodNode — класс для переключения лодов.
• SwitchNode — класс для переключения свитч объектов.
• еще около 15-ти классов наследников SceneNode.

Класс SceneNode позволял переопределить набор виртуальных методов, для реализации какой-то кастомной функциональности:
Основные функции, которые можно было переопределить, это:

• Update — функция которая вызывалась для каждого узла, для того чтобы сделать Update-сцены.
• Draw — функция, которая вызывалась для каждого узла, для того чтобы отрисовать этот узел.

Основные проблемы, с которыми мы столкнулись.

Во-первых, производительность:

• Когда количество нодов в уровне достигло 5000, оказалось что просто пройти по всем пустым функциям Update, занимает около 3ms.
• Аналогичное время уходило на пустые ноды, которым не требовалось Draw.
• Огромное количество кэш-миссов, так как работа всегда велась с разнотипными данными.
• Невозможность распараллелить работу на несколько ядер.

Во-вторых, непредсказуемость:

• Изменение кода в базовых классах влияло на всю систему целиком, то есть каждое изменение SceneNode::Update могло сломать что угодно и где угодно. Зависимости становились все сложнее и сложнее, и каждое изменение внутри движка почти гарантированно требовало тестирования всей связанной функциональности.
• Невозможно было сделать локальное изменение, например, в трансформациях, чтобы не задеть остальные части сцены. Очень часто малейшие изменения в LodNode (узел для переключения лодов), ломали что-то в игре.

Первые шаги по улучшению ситуации

Для начала мы решили полечить проблемы с производительностью и сделать это быстро.

Собственно, сделали мы это, введя дополнительный флаг NEED_UPDATE в каждой ноде. Он определял, нужно ли такой ноде вызывать Update. Это действительно повысило производительность, но создало целый ворох проблем. Фактически код функции Update выглядел вот так:

void SceneNode::Update(float timeElapsed)
{
     if (!(flags & NEED_UPDATE))return; 
     
     // the rest of the update function

     // process children
}

Это вернуло нам часть производительности, однако началось много логических проблем там, где их не ждали.

LodNode, и SwitchNode — ноды, отвечающие, соответственно, за переключение лодов (по расстоянию) и переключение объектов (например, разрушенных и неразрушенных) — начали регулярно ломаться.

Периодически тот, кто пытался исправить поломки, делал следующее: отключал NEED_UPDATE в базовом классе (ведь это было простое решение), и совершенно незаметно FPS опять падал.

Когда код, проверяющий флаг NEED_UPDATE, был закомментирован раза три, мы, решились на радикальные перемены. Мы понимали, что сделать все сразу у нас не получится, поэтому решили действовать поэтапно.

Самым первым шагом было заложить архитектуру, которая позволит в перспективе решить все возникающие у нас проблемы.

Цели

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

Основной целью на первом этапе была выбрана переделка архитектуры так, чтобы все эти цели можно было выполнить.

Комбинирование компонентного и data-driven-подхода

Решением этой проблемы стал компонентный подход, комбинированный c data-driven подходом. Дальше по тексту я буду употреблять data-driven-подход, так как не нашел удачного перевода.

Вообще понимание компонентного подхода у многих людей самое разное. То же — и с data-driven.

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

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

Что же такое data-driven. В моем понимании, это подход к проектированию программного обеспечения, когда за основу потока выполнения программы берутся данные, а не логика.

На нашем примере представим следующую иерархию классов:

class SceneNode
{
     // Данные отвечающие за иерархические трансформации
     Matrix4 localTransform;
     Matrix4 worldTransform; 
     
     virtual void Update();
     virtual void Draw();     

     Vector<SceneNode*> children;
}

class LodNode
{
     // Данные cпецифичные для вычисления лодов
     LodDistance lods[4];

     virtual void Update(); // переопределен метод Update, для того чтобы в момент переключения лодов, включать или выключать какие-то из его чайлдов
     virtual void Draw(); // рисуем только текущий активный лод
};

class MeshNode
{
     RenderMesh * mesh; 

     virtual void Draw(); // рисуем меш
};

Код обхода этой иерархии иерархически выглядит так:

Main Loop:
rootNode->Update();
rootNode->Draw(); 

В данной иерархии C++ наследования мы имеем три различных независимых потока данных:

• Трансформации
• Лоды
• Меши

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

Давайте представим, как это должно выглядеть в data-driven подходе. Напишу на псевдокоде, чтобы была понятна идея:

// Transform Data Loop:
for (each localTransform in localTransformArray)
{
     worldTransform = parent->worldTransform * localTransform;
}

// Lod Data Loop:
for (each lod in lodArray)
{
     // calculate lod distance and find nearest lod
     nearestRenderObject = GetNearestRenderObject(lod);
     renderObjectIndex = GetLodObjectRenderObjectIndex(lod);
     renderObjectArray[renderObjectIndex] = renderObject;
}

// Mesh Render Data Loop:
for (each renderObject in renderObjectArray)
{
     RenderMesh(renderObject);
}

По сути, мы развернули циклы работы программы, сделав это таким образом, чтобы все отталкивалось от данных.

Данные в data-driven подходе являются ключевым элементом программы. Логика — лишь механизмы обработки данных.

Новая архитектура

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

Читая информацию по этой теме, я наткнулся на блог T-Machine.

Он мне дал множество ответов, на мои вопросы, однако основным ответом было следующее:

• Entity не содержит никакой логики, это просто ID (или указатель).
• Entity знает только ID компоненты, которые ей принадлежат (или указатель).
• Компонент — это только данные, то есть. компонент не содержит никакой логики.
• Система — это код, который умеет обрабатывать определенный набор данных и выдавать на выходе другой набор данных.

Когда я понял это, в процессе дальнейшего изучения различной информации наткнулся на Artemis Framework и увидел хорошую реализацию этого подхода.
Исходники тут, если предыдущий линк не работает: Artemis Original Java Source Code

Если вы разрабатываете на Java, то очень рекомендую посмотреть на него. Очень простой и концептуально правильный Framework. На сегодняшний день он спортирован на кучу языков.

То, чем является Artemis, сегодня называют ECS (Entity, Component, System). Вариантов организации сцены на базе Entity, компонентов и data-driven достаточно много, однако мы по итогу пришли к архитектуре ECS. Сложно сказать, насколько это общепринятый термин, однако ECS значит, что есть следующие сущности: Entity, Component, System.

Самое главное отличие от других подходов это: Обязательное отсутствие логики поведения в компонентах, и отделение кода в системы.

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

Несмотря на гибкость, заканчивается обычно макаронами.



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

ECS — более чистый подход, и решает больше проблем.

Чтобы посмотреть на примере, как это работает в Artemis, можете глянуть вот тут.

Я на примере покажу, как это работает у нас.

Главным классом контейнером является Entity. Это класс, который содержит массив компонентов.

Вторым классом является Component. В нашем случае, это просто данные.

Вот список компонентов, используемых у нас в движке, на сегодняшний день:

    enum eType
    {
        TRANSFORM_COMPONENT = 0,
        RENDER_COMPONENT,
        LOD_COMPONENT,
        DEBUG_RENDER_COMPONENT,
        SWITCH_COMPONENT,
        CAMERA_COMPONENT,
        LIGHT_COMPONENT,
        PARTICLE_EFFECT_COMPONENT,
        BULLET_COMPONENT,
        UPDATABLE_COMPONENT,
        ANIMATION_COMPONENT,
        COLLISION_COMPONENT,    // multiple instances
        PHYSICS_COMPONENT,
        ACTION_COMPONENT,       // actions, something simplier than scripts that can influence logic, can be multiple
        SCRIPT_COMPONENT,       // multiple instances, not now, it will happen much later.
        USER_COMPONENT,
        SOUND_COMPONENT,
        CUSTOM_PROPERTIES_COMPONENT,
        STATIC_OCCLUSION_COMPONENT,
        STATIC_OCCLUSION_DATA_COMPONENT, 
        QUALITY_SETTINGS_COMPONENT,   // type as fastname for detecting type of model
        SPEEDTREE_COMPONENT,
        WIND_COMPONENT,
        WAVE_COMPONENT,
        SKELETON_COMPONENT,

        //debug components - note that everything below won't be serialized
        DEBUG_COMPONENTS,
        STATIC_OCCLUSION_DEBUG_DRAW_COMPONENT,
        COMPONENT_COUNT
    };

Третим классом является SceneSystem:

    /**
        \brief  This function is called when any entity registered to scene.
                It sorts out is entity has all necessary components and we need to call AddEntity.
        \param[in] entity entity we've just added
     */
    virtual void RegisterEntity(Entity * entity);
    /**
        \brief  This function is called when any entity unregistered from scene.
                It sorts out is entity has all necessary components and we need to call RemoveEntity.
        \param[in] entity entity we've just removed
     */
    virtual void UnregisterEntity(Entity * entity);

Функции RegisterEntity, UnregisterEntity вызываются для всех систем в сцене тогда, когда мы добавляем или удаляем Entity из сцены.

    /**
        \brief  This function is called when any component is registered to scene.
                It sorts out is entity has all necessary components and we need to call AddEntity.
        \param[in] entity entity we added component to.
        \param[in] component component we've just added to entity.
     */
    virtual void RegisterComponent(Entity * entity, Component * component);

    /**
        \brief  This function is called when any component is unregistered from scene.
                It sorts out is entity has all necessary components and we need to call RemoveEntity.
        \param[in] entity entity we removed component from.
        \param[in] component component we've just removed from entity.
     */
    virtual void UnregisterComponent(Entity * entity, Component * component);

Функции RegisterComponent, UnregisterComponent вызываются для всех систем в сцене, тогда, когда мы добавляем или удаляем Component в Entity в сцене.
Также для удобства есть еще две функции:

    /**
        \brief This function is called only when entity has all required components.
        \param[in] entity entity we want to add.
     */
    virtual void AddEntity(Entity * entity);
    
    /**
        \brief This function is called only when entity had all required components, and don't have them anymore.
        \param[in] entity entity we want to remove.
     */
    virtual void RemoveEntity(Entity * entity);

Эти функции вызываются, когда уже создан заказанный набор компонентов с помощью функции SetRequiredComponents.

Например, мы можем заказать получение только тех Entities, у которых есть ACTION_COMPONENT и SOUND_COMPONENT. Передаю это в SetRequiredComponents и — вуаля.

Чтобы понять, как это работает, распишу на примерах, какие у нас есть системы:

• TransformSystem — система которая отвечает за иерархию трансформаций.
• SwitchSystem — система которая отвечает за переключения переключаемых объектов.
• LodSystem — система которая отвечает за переключение лодов по расстоянию.
• ParticleEffectSystem — система которая обновляет эффекты частиц.
• RenderUpdateSystem — система которая обновляет рендер-объекты из графа сцены.
• LightUpdateSystem — система которая обновляет источники света из графа сцены.
• ActionUpdateSystem — система которая обновляет actions (действия).
• SoundUpdateSystem — система которая обновляет звуки, их позицию и ориентацию.
• UpdateSystem — система которая вызывает кастомные пользовательские апдейты.
• StaticOcclusionSystem — система применения статического окклюжена.
• StaticOcclusionBuildSystem — система построения статического окклюжена.
• SpeedTreeUpdateSystem — система апдейта деревьев Speed Tree.
• WindSystem — система расчета ветра.
• WaveSystem — система расчета колебаний от взырвов.
• FolliageSystem — система расчета растительности над ландшафтом.

Самый главный результат, которого мы добились, — высокая декомпозиция кода, отвечающего за разнородные вещи. Сейчас в функции TransformSystem::Process четко локализирован весь код, который касается трансформаций. Он очень прост. Его легко разложить на несколько ядер. И самое главное, сложно сломать что-то в другой системе, сделав логическое изменение в системе трансформаций.

В практически любой системе код выглядит следующим образом:

for (определенного набора объектов) 
{
  // получить необходимые компоненты 
  // выполнить действия над этими объектам
  // записать данные в компоненты
}

Системы можно классифицировать по тому как они обрабатывают объекты:

• Требуется обработка всех объектов, которые находятся в системе:
  • Физика
  • Коллизии
  
  
• Требуется обработка только помеченных объектов:
  • Система трансформаций
  • Система actions (действий)
  • Система обработки звуков
  • Система обработки частиц
  
  
• Работа со своей специально оптимизированной структурой данных:
  • Static Occlusion System

При таком подходе кроме того, что очень легко обрабатывать объекты в несколько ядер, очень легко можно делать то, что в обычной полиморфизм-парадигме делать достаточно сложно. Например, вы можете легко взять и обрабатывать не все lod-переключения за кадр. Если лод-объектов ОЧЕНЬ много в большом открытом мире, вы можете сделать так, чтобы каждый кадр обрабатывалась например треть объектов. При этом это не влияет на другие системы.

Итог

• Мы сильно повысили FPS, так как с компонентным подходом вещи стали более независимы и мы смогли их по отдельности развязать и оптимизировать.
• Архитектура стала более простой и понятной.
• Стало легко расширять движок, почти не ломая соседние системы.
• Стало меньше багов из серии «сделав что-то c лодами, сломали свитчи», и наоборот
• Появилась возможность это все распараллеливать на несколько ядер.
• На текущий момент, уже работаем над тем, чтобы все системы запускать на всех доступных ядрах.

Код нашего движка находится в Open Source. Движок в том виде, в котором он используется в World of Tanks Blitz, полностью доступен в сети на github.

Соответственно, если есть желание можете заходить и смотреть на нашу имплементацию в деталях.

Учитывайте тот факт, что все писалось в реальном проекте, и, конечно, это не академическая реализация.

Планы на будущее:

• Более эффективный менеджмент данных компонетов, то есть разложить данные компоненты линейно в памяти, для минимизации кэш-миссов
• Переход на многозадачность во всех системах.

Все полезные ссылки из текста напоследок:

• Почему entity systems это хорошо
• Красивый академический пример Entity-Component-System-подхода
• Наш движок