ecs-pattern

# Entity Component System (ECS) — Deep Engineering Guide ECS is the dominant data-oriented architecture for modern game engines (Unity DOTS, Bevy, Unreal Mass, Frostbite, Overwatch's ECS, Minecraft, Soldank, EnTT). It replaces scattered OOP objects with contiguous arrays of plain data so tens of thousands of entities update at 60 FPS on cache-limited CPUs. ## 1. Why ECS Exists: The Performance Rationale ### 1.1 The OOP Cache Problem A classic OOP hierarchy: ```cpp class GameObject { public: virtual void Update() = 0; glm::vec3 m_Position; float m_Health; std::vector<GameObject*> m_Children; }; class Enemy : public GameObject { public: void Update() override; private: std::string m_Name; float m_Speed; }; ``` Each `Enemy` is heap-allocated individually. The pointer-chasing heap layout scatters `m_Position` across DRAM. Iterating 10,000 enemies forces the CPU to evict its L1/L2/L3 caches on **every single object**. The CPU does nothing but wait on memory. Measured impact: random-access iteration over a fragmented heap is **20–100x slower** than streaming over contiguous arrays. At 1.8 GHz × 8 cores, this is the difference between updating 1,000 and 100,000 entities per frame. ### 1.2 The Data-Oriented Answer ``` OOP layout (heap): [Enemy0][Enemy1][Enemy2] --- scattered pages --- Data layout (SoA): Position[].x = {2.1, 9.4, 5.0, ...} Position[].y = {0.0, 3.3, 8.2, ...} Health[] = {100, 42, 7, ...} ``` ### 1.3 The Three Pillars | Term | Definition | Example | |------|-----------|---------| | **Entity** | A lightweight opaque ID (integer). No data, no behavior. | `Entity(42)` is just `uint32_t 42` | | **Component** | A plain-data struct (POD, no virtuals, no methods beyond trivial accessors) | `struct Position { float x, y, z; }` | | **System** | Pure logic that reads/writes components for every matched entity | `MovementSystem` does `pos += vel * dt` | ### 1.4 Why This is Faster — Cache Lines A cache line is 64 bytes. A `Position + Velocity` pair in SoA form is 24 bytes. A cache-line fetch delivers **two entities' worth of hot data** instead of two pointers to cold data. This is called a **cache-miss-free stream**. ```mermaid %%{init: {"theme": "default", "flowchart": {"useMaxWidth": true}}}%% flowchart TD subgraph RAM ["DRAM: Component Arrays (SoA)"] A["Position[0..N] (contiguous)"] B["Velocity[0..N] (contiguous)"] C["Health[0..N] (contiguous)"] end subgraph CORE ["CPU L1/L2 Cache"] D["Cache Line: 64B"] E["prefetch next line"] end F["Movement System"] -->|"iterates pos[i]+=vel[i]"| A F --> B F -->|"next element already in cache"| D D --> E ``` ## 2. Storage Models ### 2.1 Naïve: Dictionary-of-Component-Arrays (AoS-friendly) The simplest ECS stores each component type in one flat array, where array index == entity ID: ```cpp struct PositionArray { std::vector<Vec3> data; }; // data[entity] = position struct HealthArray { std::vector<float> data; }; // data[entity] = health ``` - **Pros**: minimal implementation, easy to reason about. - **Cons**: index collisions when entities are destroyed (holes), stale IDs trigger undefined behavior, and unused components occupy memory slots. ### 2.2 Sparse Set The canonical solution to sparse entity IDs. Two parallel arrays: ```cpp template<typename T> class SparseSet { std::vector<int> dense; // component payload, packed by insertion order std::vector<int> sparse; // entity -> index into dense std::vector<Entity> entities; // dense -> entity public: void add(Entity e, T comp) { sparse[e.id] = dense.size(); dense.push_back(comp); entities.push_back(e); } void remove(Entity e) { int idx = sparse[e.id]; dense[idx] = dense.back(); dense.pop_back(); entities[idx] = entities.back(); entities.pop_back(); sparse[entities[idx].id] = idx; } T& get(Entity e) { return dense[sparse[e.id]]; } }; ``` `sparse` maps entity → index; `dense` packs only *live* components. Destruction swaps the last element into the hole (O(1)) — exactly how EnTT, Bevy, and flecs remove entities. ### 2.3 Archetype / Chunk-Based Storage (Unity DOTS, Bevy, Unreal Mass) Archetypes group entities with **identical component shape**: ``` Archetype A = {Position, Velocity} archetype_id = hash([Position, Velocity]) Archetype B = {Position, Velocity, Health} ``` Each archetype owns contiguous "chunk" blocks (typically 4KB–16KB) that are pure SoA: ``` Chunk (16 KB): Position[0..maxEntity Per Chunk] Velocity[0..maxEntities] Health [0..maxEntities] -- only if archetype has Health ``` Entity ID → archetype ID → chunk index → row. When an entity gains/removes a component, it is **moved** to a different archetype (data migration). This yields: - Truly cache-coherent iteration (only the components the system needs). - Cheap add/remove via chunks (no per-entity allocation). - Zero pointer chasing. ### 2.4 EnTT's Hybrid Approach EnTT (the most popular single-header ECS) uses a **grouped sparse set** storage: - Components stored in sorted, tightly packed arrays. - Grouped storage keeps all components for an archetype in predictable order, collapsing cache misses. - `view<>` iteration yields pointer-like iterators for direct SoA traversal. ## 3. Entity Hierarchy ## 3.1 Entity IDs in Practice | Engine | Entity representation | |--------|----------------------| | Unity DOTS | `uint32_t` index + `uint32_t` version (generation counter) | | Bevy | `Entity { index: u32, generation: u32 }` | | EnTT | `entt::entity` = `uint32_t` (32-bit) or `uint64_t` with version bits | | flecs | `ecs_entity_t` = `uint64_t` with flags | | Unreal Mass | `FMassEntityHandle { uint32 SerialNumber; uint32 Index; }` | Generation counters prevent a recycled ID from silently colliding with a stale reference: ```cpp uint32_t index = id & 0xFFFF; // low 16 bits = index uint32_t generation = (id >> 16); // high 16 bits = version Entity create(uint32_t& nextIndex, std::vector<uint32_t>& generation) { uint32_t idx = freeList; // reuse a freed slot uint32_t gen = generation[idx]; // bump the version generation[idx] = gen + 1; freeList = ...; // consume next freed slot return pack(idx, gen); } bool isValid(Entity e, const std::vector<uint32_t>& generation) { return generation[e.index()] == e.generation(); // stale ID detected } ``` ## 4. Systems & Scheduling ## 4.1 System Signature A system declares the components it reads (`Reads`) and writes (`Writes`). The scheduler uses this to: 1. **Detect data races**: two systems writing the same component simultaneously are illegal. 2. **Parallelize**: systems with disjoint read/write sets run in parallel threads. 3. **Order deterministically**: a write/read dependency imposes an order edge. ```rust // Bevy style fn movement_system(time: Res<Time>, mut query: Query<(&mut Transform, &Velocity)>) { for (mut transform, velocity) in query.iter_mut() { transform.translation += velocity.dir * time.delta_seconds(); } } ``` ## 4.2 The Scheduler The scheduler builds a task graph each frame. Edges encode dependencies: ```mermaid %%{init: {"theme": "default", "flowchart": {"useMaxWidth": true}}}%% flowchart LR A["Movement (W: Position)"] --> B["Physics (W: Collision, R: Position)"] A --> C["Render Raycast (R: Position)"] B --> D["Constraint Solve"] C --> E["Draw"] D --> E ``` - **Bevy**: uses a multithreaded executor that discovers parallelism from system signatures at runtime (startup systems vs. update systems). - **Unity DOTS**: the player loop owns a system group; `BurstCompilerOptions` + `Entities.ForEach` + `ISystem` schedule onto the main thread or job threads. - **flecs**: uses a flat graph + phases (OnUpdate / PostUpdate) and supports *pipelining* where systems from multiple frames overlap. ## 4.3 System Ordering Patterns ### Sequential (Simplest) ```yaml systems: [input, movement, collisions, render] ``` ### Parallel (Data-driven) ``` Frame N: input ──► movement ──► physics ──► render └─────────► ai ────────┘ (parallel branch) ``` ### Pipelined (Cross-frame, GPU/CPU overlap) Render of frame N overlaps simulation of frame N+1 via double buffering. ## 5. Writing High-Performance Systems ## 5.1 SoA vs AoS vs SoAoS | Layout | Memory pattern | Cache behavior | Use case | |--------|---------------|----------------|----------| | AoS `struct {x,y,vx,vy}` | interleaved per entity | poor for single-component systems | small systems, GPU vertex data | | SoA `float x[], y[], vx[], vy[]` | separate arrays | perfect streaming for one component at a time | simulation-heavy ECS | | SoAoS (structure of arrays of structs) | runs of entities grouped | balance between locality and API ergonomics | hybrid, tile-based games | ```cpp // SoA: ideal for a Position+Velocity move system float* x = posX.data(); float* y = posY.data(); float* vx = velX.data(); float* vy = velY.data(); for (size_t i = 0; i < n; ++i) { x[i] += vx[i] * dt; y[i] += vy[i] * dt; } ``` ## 5.2 The "One System → One Hot Path" Rule Design each system to touch the *minimum* set of components. `MovementSystem` should never touch `Inventory`. Pulling extra data into the cache line *is the bug*. - Keep read-only components (e.g., `Visual`) out of the hot update path entirely. - Split `Update()' into `UpdateSim()` (dirty flags) and `RenderPrepare()` (called only when visible). ## 5.3 Vectorization (SIMD) Contiguous SoA arrays vectorize trivially: ```cpp // With -O3 / -ftree-vectorize, the compiler emits AVX2 for this loop: for (size_t i = 0; i < n; i += 8) { __m256 xs = _mm256_loadu_ps(x + i); __m256 vs = _mm256_loadu_ps(vx + i); _mm256_storeu_ps(x + i, _mm256_add_ps(xs, _mm256_mul_ps(vs, _mm256_set1_ps(dt)))); } ``` Even better: `#pragma omp simd` or `[BurstCompile]` in Unity (which generates ARM NEON / AVX2 automatically). ## 6. Tying it Together: A Minimal Complete ECS ```cpp #include <vector> #include <unordered_map> #include <cstdint> using Entity = uint32_t; struct Position { float x, y; }; struct Velocity { float vx, vy; }; // Archetype-storage: one contiguous array per component type per archetype. struct Archetype { uint32_t id; std::vector<Position> pos; std::vector<Velocity> vel; std::vector<Entity> entities; }; class World { std::vector<Archetype> archetypes; std::unordered_map<uint32_t, uint32_t> entityToArchetype; public: Entity spawn(const Position& p, const Velocity& v) { Archetype& a = archetypes[0]; // archetype {Pos, Vel} a.pos.push_back(p); a.vel.push_back(v); Entity e = static_cast<Entity>(a.entities.size()); a.entities.push_back(e); entityToArchetype[e] = 0; return e; } template<typename Fn> void forEachSystem(Fn&& fn) { for (Archetype& a : archetypes) { for (size_t i = 0; i < a.pos.size(); ++i) fn(a.pos[i], a.vel[i]); // direct, cache-coherent access } } }; int main() { World w; for (int i = 0; i < 100000; ++i) w.spawn({(float)i, 0.f}, {0.01f, 0.02f}); float dt = 1.f / 60.f; w.forEachSystem([&](Position& p, Velocity& v) { // 100k updates p.x += v.vx * dt; // cache-friendly