Всем привет, я делаю свой пет-проект - игровой движок, и какой пет-проект без собственноручно сваренного велосипеда, так я и пришел к идее реализации своей ECS.

В этой статье я хочу рассказать простыми словами - что такое ECS, и как он эволюционно появился у меня.

Что такое ECS - Entity Component System (Сущность Компонент Система) - архитектура хранения данных, где логика - системы, явно отделена от данных - компонентов, которые объединены одним общим id - сущностью.

В двух словах, идея ECS заключается в том, чтобы навести порядок в игровом коде, и игровом мире - выделить все данные игровых объектов(сущностей), и желательно сделать это data-oriented (почему желательно я расскажу ниже).

Предположим, у вас в игре есть объект КУБ - квадратный, все стороны равны, все углы равны, классический такой КУБ. У него есть положение в мире (Transform) у него есть его кубический меш (Mesh), он умеет быть отрендеренным (IsRenderable), и, ко всему прочему, он еще и обладает какой-то своей кубической физикой (Physic).

Классический способ заставить это существовать в игровом мире - создать сцену, на которой создать объект КУБ, который наследник класса RenderObject, который наследник класса Object, в RenderObject вероятно будет лежать Mesh, в Object будет Transform, со своими методами: updateTransform, isDirty, markDirty etc. Еще какой-нибудь ObjectId, в Mesh - будет AssetId ...
В общем получится что-то вроде:

struct Transform {
  vec3 pos;
  vec3 rotation;
  mat4 transformMat;
  bool isDirty = true;
  
  void UpdateTransform();
  void IsDirty();
  void MarkDirty();
  ...
};

struct Asset {
  std::string assetId;
};

struct Mesh : public Asset {
  std::vector<Vertex> vertices;
  std::vector<uint32_t> indices;
  // какие-нибудь меш методы
};

class Object {
  virtual ~Object() = default;
  Transform transform;
  std::string objectId;
};

class RenderObject : public Object {
  
};

class RenderObjectWithPhys : public RenderObject {...}; // или виртуальное наследование? 

В общем, как видно из примера выше, даже на таком базовом минимуме (С) начинаются вопросы : как это всё правильно разложить? когда и как обновлять трансформ? где? как обновлять mesh? нужно ли создать отдельный легковесный mesh?
Расширяемость низкая, сделать это всё кэш-френдли сложно, плюс слой виртуализации...

Но нам на помощь приходит data oriented design - сначала думаем о том как правильно разложить данные по памяти, а потом уже думаем к��к эти данные использовать.

Смотрим на пример: Данные - это transform, mesh, physics, isRenderable, mesh. Нужно их вынести во что-то отдельное (в голове маячат странные аббревиатуры SoA, AoS. Но мы пока не понимаем что это такое, и откуда этот странный шум).

Рассуждаем логически - должны ли данные сами себя менять? Это удобно в ООП, машина сама себя "едет". Но данные из transform нужны не только самому transform для апдейта логики, но и, например, физике и, естественно, рендеру. Transform может прийти к физике, и она его будет как-то использовать, и рендер тоже, как минимум попросит матрицу, но изменять сам transform уже не будет. Естественным образом появляется логика:

struct Transform {
  vec3 pos;
  vec3 rotation;
  mat4 transformMat;
  bool isDirty = true;
  
  void UpdateTransform();
  void IsDirty();
  void MarkDirty();
  ...
};

Physic::Update(Transform& objT) {
//меняем трансформы под влиянием физики
  objT.pos.x += 1.f; // у нас очень простая физика - полёт вперед и только вперёд
  objT.MarkDirty();
}

Render::Draw(Transform& objT){
//рисуем объект там где он должен быть нарисован
  if (objT.IsDirty()){
    objT.UpdateTransform();
  }
  Draw(objt.transformMat);
}

Но почему трансформ обновляет себя в draw? Во первых, намного эффективнее было бы делать это в другом потоке. Во вторых, ответственность Render не должна распространяться на нерисование.

Выносим эту логику из рендера:

struct Transform

Physic::Update(Transform& objT) {
   //меняем трансформы под влиянием физики
   objT.pos.x += 1.f; // у нас очень простая физика - полёт вперед и только вперёд
   objT.MarkDirty();
}

TransformUpdater::Update(Transform& objT){
  if (objT.IsDirty()){
    objT.UpdateTransform();
  }
}

Render::Draw(Transform& objT){
   //рисуем объект там где он должен быть нарисован
   Draw(objt.transformMat);
}

И вот мы стоим на пороге великого открытия (C), если трансформ обновляется в отдельном объекте, у которого есть свой апдейт, его меняют другие объекты (Physic), и используют третьи(Render).

Зачем хранить логику апдейта внутри самого Transform? Это же банально не удобно и не логично, 2 из 3 просто меняют его, третий тоже так должен делать.
Рождается component system архитектура, когда данные уже лежат отдельно от логики, но пока что не отдельно от Object. Данные мы начинаем звать компонентами, так как они части одного целого Object.

Мы обновляем эти Object через системы, и подход может выглядеть так:

struct Transform {//only data};
struct PhysicsComp {};
struct IsRenderable {bool is = true; };
struct Mesh{};
  
struct Object {
  Transform t;
  PhysicsComp p;
  IsRenderable r;
  Mesh m;
};

Core::Update(float dt){
  std::vector<Object>& world = GetWorld();
  for (auto& obj : world) {
    // Updater объектов это система - 
    PhysicsSys::Update(obj);
    TransformSys::Update(obj);
  }

  // сделаем вид что это другой поток
  for (auto& obj : world) {
    RenderSys::Draw(obj);
  }
}

У нас массив Object, у каждого Object набор компонентов. Расширяемость уже сильно проще, структура тоже, можно добавлять новые компоненты, но это раздувает Object.

Давайте вспомним те странные аббревиатуры SoA и AoS - Structure Of Arrays и Array Of Structures. У нас получилось буквально - AoS (vector<object>). В чем минусы: физике не нужно знать о том renderable ли объект, а если мы добавим SoundComponent, то он тем более не нужен физике, равно как и не нужен PhysicsComponent системе звуков.

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

Нам нужно разбить Object на набор массивов компонентов, по массиву на компонент. Но как тогда PhysicsSys получит transform? Ей нужен не какой-то там transform, а принадлежащий тому же объекту, которому принадлежит physics. Всё очень просто: по уникальному id - EntityID.
Круг замкнулся: entity component system - entity - это просто связь между компонентами, компоненты - данные, system - функция, которая эти данные меняет.

Добавили в игру новый компонент - просто создали еще один массив. Удалили компонент - yдалили массив.

Классическая SoA.

struct Transform {//only data};
struct PhysicsComp {};
struct IsRenderable {bool is = true; };
struct Mesh{};
  
uint32_t entityId;
std::vector<entityId> entities;

std::map<Transform> t;
std::map<PhysicsComp> p;
std::map<IsRenderable> r;
std::map<Mesh> m;

Core::Update(float dt){
  std::vector<entityId>& world = GetWorld();
  for (auto& entity : world) {
    // Updater объектов это система - 
    PhysicsSys::Update(t[entity]);
    TransformSys::Update(p[entity]);
  }

  // сделаем вид что это другой поток
  for (auto& entity : world) {
    RenderSys::Draw(r[entity], m[entity]);
  }
}

Выше описан минимальный пример ECS (некоторые ECS примерно так и выглядят).

Надеюсь к этому моменту у читателя появилось понимание, что такое ECS и как его готовить.

В целом можно у себя в движке сделать прямо так, как показано сверху - оно будет работать (возможно даже не слишком медленно). Но помимо удобства хранения данных и расширяемости хочется скорость! Мы говорили что-то про SoA, но map это не совсем A в данном уравнении.

Я писал выше, что желательно чтобы ECS был DoD (по моему мнению это обязательно, маст хэв, и прям очень нужно и просится!). Технически оно уже data oriented, но само хранение data сделано очень неэффективно: данные лежат в дереве, разбросаны по памяти, и итерация по ним будет невероятно медленной (а итерация - это основной use case данных в ECS). Поэтому данные должны быть плотно упакованы. Итерация должна быть не сильно дороже обычной итерации по Array, поиск по id сущности должен быть быстрым, но никаких деревьев! Только массивы, только хардкор и кэш-френдли структуры (а сущностей могут быть миллионы).

Плюс я предполагал, что SoA - это классно, но иногда нужно несколько компонентов объединить в один блок памяти (ради кэш-френдли), но не терять гибкости и возможности итерироваться по таким компонентам так, как будто они отдельные объекты.

Я хотел гибкость и скорость. И максимум контроля.

И у меня появилась идея - сделать layout в памяти, в котором будут храниться компоненты, я назвал его Sector.

А свою ECS - ECS with Sectors - ECSS.

Sector - фактически просто разметка памяти. У него есть информация о том, какие компоненты в нем живы, и id. Разметка сектора происходит снаружи, и компоненты кладутся в него через слой рефлексии (самописный маленький класс, максимально быстрый).

Таким образом Sector ничего не знает о том, что в нем лежит. ECS знает смещения до компонента внутри сектора, и при попытке достать из сектора компонент - проверяет бит "живости", если он равен 1 - берет память компонента и кастует его к нужному типу.

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

Sector настраивается на старте приложения, информация о его разметке в большей мере - compile time, таким образом он практически не даёт оверхеда при итерации. Но если правильные компоненты упаковать в Sector (например Transform и DrawData), если структуры этих данных тривиальные (хотя бы trivially-copyable), и эти данные в горячем месте должны быть вместе, то это даёт отличный профит по скорости, из-за увеличения cache friendliness (данные хранятся вместе).

Ниже можно посмотреть бенчмарки, которые доказывают эффективность моего подхода
https://wagnerks.github.io/ecss_benchmarks/

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

Код бенчмарков - https://github.com/wagnerks/ecss_benchmarks
Исходники открытые, кода немного, буду рад фидбеку) - https://github.com/wagnerks/ecss