Sources

• Rust Auckland - Azriel: ECS: A Programming Paradigm .

  • Really good video for explaining the general theory behind ECS, but then falls short when it comes to implementation and Rust things.

  • I didn't like the video after {31:00}, as it went for an implementation with Rust and I though it was very confusing.

Bitsquid Engine - Building a Data-Oriented Entity System

• pt1

• pt2

• pt3

• pt4 .

const unsigned ENTITY_INDEX_BITS = 22;
const unsigned ENTITY_INDEX_MASK = (1<<ENTITY_INDEX_BITS)-1;

const unsigned ENTITY_GENERATION_BITS = 8;
const unsigned ENTITY_GENERATION_MASK = (1<<ENTITY_GENERATION_BITS)-1;

struct Entity
{
    unsigned id;

    unsigned index() const {return id & ENTITY_INDEX_MASK;}
    unsigned generation() const {return (id >> ENTITY_INDEX_BITS) & ENTITY_GENERATION_MASK;}
};

class EntityManager
{
    Array<unsigned char> _generation;
    Deque<unsigned> _free_indices;

    public:
    Entity create() {
        unsigned idx;
        if (_free_indices.size() > MINIMUM_FREE_INDICES) {
            idx = _free_indices.front();
            _free_indices.pop_front();
        } else {
            _generation.push_back(0);
            idx = _generation.size() - 1;
            XENSURE(idx < (1 << ENTITY_INDEX_BITS));
        }
        return make_entity(idx, _generation[idx]);
    }

    bool alive(Entity e) const {
        return _generation[e.index()] == e.generation();
    }

    void destroy(Entity e) {
        const unsigned idx = e.index();
        ++_generation[idx];
        _free_indices.push_back(idx);
    }
};

• The idea here is that the index part directly gives us the index of the entity in a lookup array.

  • The generation part is used to distinguish entities created at the same index slot. As we create and destroy entities we will at some point have to reuse an index in the array. By changing the generation value when that happens we ensure that we still get a unique ID.

• In our system we are restricted to using 30 bits for the entity ID. We steal two bits from this pointer in order to distinguish it from other types of light userdata that we use in the engine.

  • We've split up our 30 bits into 22 bits for the index and 8 bits for the generation. This means that we support a maximum of 4 million simultaneous entities. It also means that we can only distinguish between 256 different entities created at the same index slot. If more than 256 entities are created at the same index slot, the generation value will wrap around and our new entity will get the same ID as an old entity.

• A nice thing about only having 8 bits in generation is that we just need 8 bits per entity in our lookup array. This saves memory, but also gives us better performance, since we will fit more in the cache.

• Component:

• Components in our system are not individual objects, instead all components of a particular type are handled by a component manager for that type. The component manager has full control over how the component data is stored internally and how updates are applied.

• It is perhaps not self-evident why we want to store the entity that owns the component, but it will come in handy later.

• Component Manager:

• The task of a ComponentManager is to associate entities with components. It is up to the component manager to decide if it makes sense for an entity to have multiple components of its type.

• There is no place where we keep a list of all the components that an entity has. This is only defined by what has been registered with the different component managers in the game.

• When considering how we should layout the data in the component manager we have two goals:

  • Given an entity we want to be able to quickly look up the component data for that entity.

  • We want the component data to be packed tightly in memory for good cache performance.

class PointMassComponentManager {
    struct InstanceData {
        Array<Entity> entity;
        Array<float> mass;
        Array<Vector3> position;
        Array<Vector3> velocity;
        Array<Vector3> acceleration;
    };
    InstanceData _data;
};

• That works well enough, but it does mean that the data gets stored in five separately allocated memory buffers.

• I use a different approach. I allocate the entire memory buffer as a single allocation and then just let entity, mass, etc, point to different parts of that buffer:

class PointMassComponentManager {
    struct InstanceData {
        unsigned n;          ///< Number of used instances.
        unsigned allocated;  ///< Number of allocated instances.
        void *buffer;        ///< Buffer with instance data.

        Entity *entity;
        float *mass;
        Vector3 *position;
        Vector3 *velocity;
        Vector3 *acceleration;
    };
    InstanceData _data;

    void allocate(unsigned sz)
    {
        assert(sz > _data.n);

        InstanceData new_data;
        const unsigned bytes = sz * (sizeof(Entity) + sizeof(float) +
            3 * sizeof(Vector3));
        new_data.buffer = _allocator.allocate(bytes);
        new_data.n = _data.n;
        new_data.allocated = sz;

        new_data.entity = (Entity *)(new_data.buffer);
        new_data.mass = (float *)(new_data.entity + sz);
        new_data.position = (Vector3 *)(new_data.mass + sz);
        new_data.velocity = new_data.position + sz;
        new_data.acceleration = new_data.velocity + sz;

        memcpy(new_data.entity, _data.entity, _data.n * sizeof(Entity));
        memcpy(new_data.mass, _data.mass, _data.n * sizeof(float));
        memcpy(new_data.position, _data.position, _data.n * sizeof(Vector3));
        memcpy(new_data.velocity, _data.velocity, _data.n * sizeof(Vector3));
        memcpy(new_data.acceleration, _data.acceleration,
            _data.n * sizeof(Vector3));

        _allocator.deallocate(_data.buffer);
        _data = new_data;
    }
};

• This avoids any hidden overheads that might exist in the Array class and we only have a single allocation to keep track of. This is better both for the cache and the memory allocation system`.

Array<unsigned> _map;

• Here, the _map  allows us to look up a component index based on the entity index.
  This is a lot better, because now it is just the _map array that has holes, not the _data array, which means that the holes are fewer and smaller. Still, I would only use this if I was certain that the component was almost universal and that lookups where performance critical. In most cases, I think a hash index is a better approach:

HashMap<Entity, unsigned> _map;

• This uses less memory and lookups are still pretty fast.

• Update:

  • Since the component data is laid out sequentially in memory, writing a function that simulates physics for all entities is simple:

  void simulate(float dt)
  {
      for (unsigned i=0; i<_data.n; ++i) {
          _data.velocity[i] += _data.acceleration[i] * dt;
          _data.position[i] += _data.velocity[i] * dt;
      }
  }
  

  • This function traverses memory in-order which gives us good cache performance. It’s also easy to profile, vectorize and parallelize, should the need arise.

• Destroy:

  • When destroying components, we want to make sure that we keep the _data  array tightly packed. We can achieve that by moving the last element to the position of the component we want to remove. We must also update the _map  entry for the corresponding entity.

  void destroy(unsigned i)
  {
      unsigned last = _data.n - 1;
      Entity e = _data.entity[i];
      Entity last_e = _data.entity[last];
  
      _data.entity[i] = _data.entity[last];
      _data.mass[i] = _data.mass[last];
      _data.position[i] = _data.position[last];
      _data.velocity[i] = _data.velocity[last];
      _data.acceleration[i] = _data.acceleration[last];
  
      _map[last_e] =  i;
      _map.erase(e);
  
      --_n;
  }
  

  • Another question is how we handle destruction of components when an entity is destroyed. As you may recall, the entity does not have an explicit list of components that it owns. Also, it seems onerous to require of the user of the API to manually destroy the right components when the entity dies.

  • Components that need to be destroyed immediately (perhaps because they hold external resources) can register a destruction callback with the EntityManager and that callback will be called when the entity is destroyed.

  • However, for simpler components, like the point mass component, there is nothing that require components to be destroyed at exactly the same time as the entity. We can take advantage of that and use garbage collection to lazily destroy components instead of spending memory and effort on storing callback lists:

  void gc(const EntityManager &em)
  {
      unsigned alive_in_row = 0;
      while (_data.n > 0 && alive_in_row < 4) {
          unsigned i = random_in_range(0, _data.n - 1);
          if (em.alive(_data.entity[i])) {
              ++alive_in_row;
              continue;
          }
          alive_in_row = 0;
          destroy(i);
      }
  }
  

Mach Engine - Let's Build ECS in Zig

• pt1

• pt2 .

• Mentioned ECS in Bevy as a great source, but now "further simplified".

• There's a lot of 'method' usage, classes, etc. Not a pretty code.

• Seems to have used solely archetypes.

• Zig code is not great to look at; very OOP-ed.

pub const Entities = struct {
    ...
    // Returns a new entity.
    pub fn new(entities: *Entities) !EntityID {
        const new_id = entities.counter;
        entities.counter += 1;
        return new_id;
    }

    pub inline fn archetypeByID(entities: *Entities, entity: EntityID) *ArchetypeStorage {
        const ptr = entities.entities.get(entity).?;
        return &entities.archetypes.values()[ptr.archetype_index];
    }

    pub fn getComponent(entities: *Entities, entity: EntityID, name: []const u8, comptime Component: type) ?Component {
        var archetype = entities.archetypeByID(entity);

        var component_storage_erased = archetype.components.get(name) orelse return null;

        const ptr = entities.entities.get(entity).?;
        var component_storage = ErasedComponentStorage.cast(component_storage_erased.ptr, Component);
        return component_storage.get(ptr.row_index);
    }

    pub fn setComponent(entities: *Entities, entity: EntityID, name: []const u8, component: anytype) !void {
        var archetype = entities.archetypeByID(entity);

        const old_hash = archetype.hash;

        var have_already = archetype.components.contains(name);
        const new_hash = if (have_already) old_hash else old_hash ^ std.hash_map.hashString(name);

        var archetype_entry = try entities.archetypes.getOrPut(entities.allocator, new_hash);
        if (!archetype_entry.found_existing) {
            archetype_entry.value_ptr.* = ArchetypeStorage{
                .allocator = entities.allocator,
                .components = .{},
                .hash = 0,
            };
            var new_archetype = archetype_entry.value_ptr;
            var column_iter = archetype.components.iterator();
            while (column_iter.next()) |entry| {
                var erased: ErasedComponentStorage = undefined;
                entry.value_ptr.cloneType(entry.value_ptr.*, &new_archetype.entity_ids.items.len, entities.allocator, &erased) catch ...;
                new_archetype.components.put(entities.allocator, entry.key_ptr.*, erased) catch ...;
            }

            // Create storage/column for the new component.
            const erased = entities.initErasedStorage(&new_archetype.entity_ids.items.len, @TypeOf(component)) catch ...;
            new_archetype.components.put(entities.allocator, name, erased) catch ...;

            new_archetype.calculateHash();
        }

        var current_archetype_storage = archetype_entry.value_ptr;

        if (new_hash == old_hash) {
            const ptr = entities.entities.get(entity).?;
            try current_archetype_storage.set(ptr.row_index, name, component);
            return;
        }
        const new_row = try current_archetype_storage.new(entity);
        const old_ptr = entities.entities.get(entity).?;

        var column_iter = archetype.components.iterator();
        while (column_iter.next()) |entry| {
            var old_component_storage = entry.value_ptr;
            var new_component_storage = current_archetype_storage.components.get(entry.key_ptr.*).?;
            new_component_storage.copy(new_component_storage.ptr, entities.allocator, new_row, old_ptr.row_index, old_component_storage.ptr) catch |err| {
                current_archetype_storage.undoNew();
                return err;
            };
        }

        current_archetype_storage.entity_ids.items[new_row] = entity;
        current_archetype_storage.set(new_row, name, component) catch |err| {
            current_archetype_storage.undoNew();
            return err;
        };
    };
};

// Represents the storage for a single type of component within a single type of entity.
// Database equivalent: a column within a table.
pub fn ComponentStorage(comptime Component: type) type {
    return struct {
        // A reference to the total number of entities with the same type as is being stored here.
        total_rows: *usize,

        // The actual densely stored component data.
        data: std.ArrayListUnmanaged(Component) = .{},

        const Self = @This();

        pub fn deinit(storage: *Self, allocator: Allocator) void {
            storage.data.deinit(allocator);
        }
    };
}

const ptr: Pointer = entities.entities.get(entity_id).?;
var archetype = entities.archetypes.entries.get(ptr.archetype_index);

test "ecs" {
    ...

    const Location = struct {
        x: f32 = 0,
        y: f32 = 0,
        z: f32 = 0,
    };
    try world.setComponent(player, "Name", "jane"); // add Name component
    try world.setComponent(player, "Location", Location{}); // add Location component
    try world.setComponent(player, "Name", "joe"); // update Name component
}

Bevy Engine - ECS

• https://bevy.org/learn/quick-start/getting-started/ecs/

• ECS demo in Bevy .

• it's terrible trying to understand anything inside a rust code....