Using polymorphism in an Entity-Component System without sacrificing data-oriented design

Question

I've been planning out an Entity-Component System in C++. My idea of it is most in line with the one described on this page of the entity systems wiki. To summarize, components are just structs of data, all code is in systems, and entities are just IDs shared by components.

The issue I'm having is mostly to do with how components are stored and accessed. My intent was to have a vector for each component type (which inherit a base Component class). These vectors are then stored in an unordered map, with a ComponentType (an enum) as the key. An EntityManager handles interactions with the vector, with functions like removeComponent, which takes a ComponentType and ID as arguments (which would search the unordered map and then iterate over the matching vector until finding the correct component to remove).

I specifically liked this implementation because it meant I could add new component types without having to change the way the manager accesses the vectors.

I realized that this implementation only works when utilizing polymorphism (i.e., a bunch of vector<Component*>s), since this allows them to all be stored in a single container, and operated on the same way. Unfortunately, this design results in the actual object data being scattered all over memory (even though the pointers are contiguous).

An advantage of the original structure that I chose, in my mind, was the improved cache performance offered by accessing large contiguous structures of data. But storing components in vectors is a problem, because then each vector is of a different type (ex: vector<Position>vs vector<Velocity>). This means I can't store them in one container, or use the same interface for operations on all of them. I believe I'd have to add new code to handle each new type of vector every time one was added.

I've been wracking my mind for the last few hours trying to devise a compromise. I can't seem to think of a design that would both store each type of component contiguously in data as well as allow for generic operations on those collections (ex: functions like the aforementioned removeComponent that don't require edits with each new compent type). I'm also unsure if my desire to maintain contiguity is reasonable, or if the impact on performance would actually be quite minor.

Answer 1

The way I approached this was to use a constexpr string-hash which I apply to my components at compile-time to assign each of them a unique id. I essentially do this with the use of a macro where I provide a generated UUID string that gets hashed and a name to my macro.

Under the hood, this macro adds some static methods allowing me to fetch the the class name and its associated string-hash value of the UUID so that I have some basic RTTI data about this class.

struct PositionComponent 
{
  COMPONENT_RTTI( PositionComponent, "004cdde9-bf20-4da2-a013-c6150fe87492" )
}

The most important thing the above macro exposes is:

static ComponentType TYPE = StringHash::hash( uuid );

Next I design my component pools using a base class and a templated derived class where I actually manage the storage for each specific component-type:

struct ComponentPoolBase 
{
  virtual Component* CreateComponent(EntityId entityId) = 0;
  virtual Component* GetComponent(EntityId entityId) = 0;
  virtual void DestroyComponent(EntityId entityId) = 0;      
};

template<typename T>
class ComponentIterator
{
public:
  // ...
};

template<typename T>
class ComponentPool : public ComponentPoolBase, public ComponentIterator<T>
{
public:
  ComponentType GetType() const { return T::TYPE; }

  template<typename T> T* Create(EntityId entityId);
  template<typename T> T* Get(EntityId entityId);
  virtual void Destroy(EntityId entityId);

private:
  std::vector<T> components_;      
}

There are several benefits with this approach. The first is that how you store the components it abstracted away from the EntityManager. Should you decide to change the implementation, the EntityManager is none the wiser as it is based on whatever exposed API the pool provides, as it should be from a SRP perspective.

Secondly the component pool does store the components in contiguous memory; however you do need to take care here because of the vector implementation and the fact memory addresses could become invalidated after a new component is inserted.

Should you need some type of reliable pointer mechanism, you can add another layer of indirection to this solution where you have something like a uint32 or uint64 value that maintains several key pieces of information encoded into the value

1. Component handle valid or not (based on some version)
2. Index into a sparse array inside the component pool

The sparse array inside the component pool is meant to be a lookup-table that the pool maintains when components get shifted around so that you effectively can translate a Handle -> index in the vector.

But for a simple approach, something like this will always work:

Position *position = entityManager->AddComponent<Position>( playerId );
position->SetPosition( x, y, z );

Now inside the EntityManager, you can maintain an unordered_map of your component pools based on their component types quite simply.

template<typename T, typename... Args>
T* EntityManager::AddComponent(EntityId entityId, Args&&... args)
{
  ComponentPool<T> *pool = GetOrCreatePool<T>();
  return pool->Create( entityId, std::forward<Args>( args )... );
}

template<typename T>
ComponentIterator<T> EntityManager::GetComponents()
{
  return GetOrCreatePool<T>();
}

template<typename T>
ComponentPool<T>* EntityManager::GetOrCreatePool()
{
  ComponentPool<T> *pool = nullptr;

  auto itor = pools_.find( T::TYPE );
  if ( itor == pools_.end() )
  {
    pool = new ComponentPool<T>( this );
    pools_.insert( std::make_pair<>( T::TYPE, pool ) );        
  }
  else
    pool = itor->second;

  return pool;
}

As you can see I've exposed a ComponentIterator<T> class type allowing me to expose the ComponentPool<T> as a specialized iterator class where I can easily iterate all components in the underlying pool without concern of the storage itself.

Answer 2

I had almost the same problem you have right now, except i tried to use pointer for the to my Buffers createComponent-method and call those.

The solution they gave me was to have arrays (or vectors) of base classes like this: class ComponentBase { public: ComponentBase() {}; virtual void* createComponent(unsigned int ID) = 0; virtual void deleteComponent(unsigned int ID) = 0; virtual ComponentID getComponentID() = 0; virtual int getSize() = 0; };

Additionally i made a buffer class, saving components in an contiguous memory block until full, then opening another contiguous memory block and delete them when empty and so on.

These can be inherited by your ComponentBuffer:

template <typename TComponent = Component> class ComponentContainer : public Buffer<TComponent>, public ComponentBase

In your Entity manager, you can now have Array/Map/whatever[ComponentBase] oder [ComponentBase*], which hold your ComponentContainers.

Only 'Problem' with this is, that your EntityManager itself doesn't know, what Component type is inside each ComponentContainer. In my system that is not a problem, since every other manager registers the components it needs in the EntityManager and when needed asks the EntityManager for a ComponentBase and casts it to the ComponentContainer with the needed TComponent.