Entity Component System, How? (Part2)

Cute implements a ECS using C++17 features, trying to solve as much as possible during compile time and allowing the compiler to inline as much as possible.

I will try to simplify as much as possible the implementation details with some pseudo code.

Each component is defined as a normal struct, for example:

  

struct Position
{
...
};

struct Speed
{
...
};

Then the user needs to define a list of possible entities type, each entity type is just defined with the list of the components that defines the type. The database is just defined with the list of components and the list of entity types:

using SquareType = ecs::EntityType<Position, Speed, Size, Square>;
using TriangleType = ecs::EntityType<Position, Speed, Size, Triangle>;
using CircleType = ecs::EntityType<Position,Speed,Size,Circle>;

using GameComponents = ecs::ComponentList<Position,Speed, Size, Square, Triangle, Circle>;
using GameEntityTypes = ecs::EntityTypeList<SquareType,TriangleType,CircleType>;

using GameDatabase = ecs::DatabaseDeclaration<GameComponents, GameEntityTypes>;

Cute ECS has the concept of zone as well, that means that all the instances in the database are grouped in zones, so when the system loops all the instances we can define the zones that we need to access. For example, we can group of our instances in 8x8 2D tiles (64 zones), then when we loop all the instances we can define which zones we want to include in the loop (for example if we look for instances in a radius distance, we can only loop the tiles, zones, that are touching the search radius). But zones can be used for more things, like filtering instances, for example you can differentiate entities by some important access pattern (like if they are touching the floor, can be hit by the player,...).

Component data storage

Each instance in the database is defined by a unique index, that will allow to identify an instance inclusive when is moving from one zone to another or when we move the component data for fragmentation reason. The database will keep for each index an instance descriptor, that includes the zone, the entity type and the index inside the components arrays.

The database is defined by an array of zone containers (size defined during init), each zone container will have an array of entity types containers and each entity type container will have an array of component containers. Each component container is a virtual buffer (explain in Uses of Virtual Memory), that will allow this memory to grow without doing copies.

Accessing the component data

So, if we want to access to a component from a instance, defined by an index.

struct EntityDescriptor
{
   int zone, entity_type, index;
};

EntityDescritor entity_descriptor = database.m_instance_table[instance_index];

Then, it can access to the component data with:

//Entity descriptor
EntityDescritor ed;

return database.m_zone_storage[ed.zone].m_entity_type_storage[ed.entity_type].m_components_storage[component_index][ed.index];

Of course, it seems quite a lot of access from a component, but this type of access is not the most common in a ECS, what we expect are is a lot of access with a kernel operation been executed for all the instances that contain specific components, using this storage pattern the kernel operation will access the component data in a cache friendly way, making the ECS approach to work. 

template<typename FUNCTION>
void LoopInstances(FUNCTION&& kernel, ComponentList components)
{
   for (auto& zones : database.m_zones)
   {
       for (auto& entity_types : zones.GetEntityTypesThatContain(components))   
       {
           //Get components storage
           auto components = entity_types.GetComponents(components);
           for (size_t i = 0; i < entity_types.NumInstances(); ++i)
           {
               //Components are accessed lineally in memory
               kernel(components[i]);
           }
       }
   }
}

Conclusions and more details

OO will allow really fast access from a pointer to all the data associated to it, but the line caches will not be aligned to the data type that you access, so inclusive having all the array access it could have good results, especially if you mix read and write operation and multi threading. ECS is a winner if you need to loop to all the instances.

Cute ECS has two functions for looping instances, one it will be run the the same thread and other will create all the jobs needed and sync them in a fence. Because we know the size of the cache line, we can create jobs that will not touch memory between them.

For this approach, all the memory needs to be compacted. Cute ECS has a tick database function, where all the deferred deletes and moves will happen. 

Having fixed number of entity types maybe seems a problem (it helps to extract details in compile time), but we always can create a more dynamic allocation for the entity_types, so we can create all possible combinations in realtime or adding/removing components to an entity.

Source code: https://github.com/JlSanchezB/Cute/blob/master/engine/ecs/entity_component_system.h

Part 1: https://middlelifegraphicsprogrammercrisis.blogspot.com/2019/05/entity-component-system-why-part1.html

Part 3: https://middlelifegraphicsprogrammercrisis.blogspot.com/2020/06/entity-component-system-testing-it-part3.html