1

I've been scouring information on Entity-Component-System designs for weeks to try to figure out how to implement it in C++, and there are lots of wonderful explanations for different aspects of it, but the one thing everybody seems to overlook in examples is how you actually access whatever the data members are in a specific derived Component class when all you have is a list of base class pointers in your Entity. I'm still new to programming in general, so if that's something that's "common knowledge," it's not common enough for all levels of skill.

The only way I can think of is to have a virtual function that returns an enum for the type of component and then cast it to that, but that seems like a hack job, and I can't help but feel like there must be a better way.

Edit: This is what I'm trying to accomplish:

//incomplete pseudocode

class DerivedComponent1 : public BaseComponent
{
  int a;
  int b;
}


class DerivedComponent2 : public BaseComponent
{
  string str;
  float c;
  float d;
};


class Entity
{
  vector<BaseComponent*> components;
};


class System
{
  void init()
  {
    entityInstance.components.push_back(derivedComponent1Instance);
    entityInstance.components.push_back(derivedComponent2Instance);
  }

  void doTask()
  {
    //access derived class members somehow
    entityInstance.components[0]->accessDerivedComponent1Members();
    entityInstance.components[1]->accessDerivedComponent2Members();
  }
};

This is in a system for a video game where an Entity can have zero or one of each type of component, like a health amount or a transform, and a System will only act on an entity that owns the specific components it needs to do its task, so behavior is customized by giving the Entity the correct Components for the desired behavior. The only way I can think of to access the component data is to add an enum with the component type and make doTask() something like this:

//incomplete pseudocode

enum ComponentType
{
  Derived1,
  Derived2
};


void System::doTask()
{
  DerivedComponent1* derived1;
  for(auto i : entityInstance.components)
  {
    if(i->getComponentType()==ComponentType::Derived1)
      derived1 = dynamic_cast<DerivedComponent1*>(i);
  }

  .
  .
  .

}

but my understanding is that if your code has to rely on casts, then it's probably bad code. My question is if there's a better way to do it.

  • if you have some example, of how you think you can do it, post them, it will help people to understand what you're trying to achieve. – Walfrat Oct 25 '18 at 11:32
  • Now that I think about it, I don't even know how I'd go about being able to store it in a pointer to the derived class without needing a giant switch statement covering each possible type. It's late, so I'll have to think about it more tomorrow. – Jarius Oct 25 '18 at 11:54
3

My Way

The way I do it, though this is not for the faint of heart as it involves variable-length structs, reinterpret casts, placement new and manual dtor invocations, and requires some knowledge of proper memory alignment if it is to be compacted as much as possible, is like this:

enter image description here

Each component type is stored in its own contiguous memory block as a VLS. There are no heap/free store allocations/deallocations on a per-component instance level (they are stored contiguously in an array that grows, similar to std::vector, and you can use that here, though it needs to behave like a free list with O(1) removals from the middle without invalidating any other indices).

And a pair of indices (type + index into the container for the type) adding up to 48-bits basically links the entities and components associated to that entity together, with -1 indicating the null terminator.

The real version actually stores the 48-bit link indices in parallel instead of directly into the same container as the component instances as a form of hot/cold field splitting (the links aren't traversed that often so much as traversing components of a particular type where it helps to reduce the stride), but I was too lazy to draw that into the diagram and that's a micro-optimization you can apply later.

And yes, there is casting going on (in my case a reinterpret cast which is even more ugly than a dynamic cast) to retrieve a component of a particular type from an entity when we write like:

MotionComponent* motion = entity.get<MotionComponent>();

But that is only one get method in the codebase that requires such a cast, and there's runtime checking going on to make sure the cast is legal to mitigate a lot of the usual problems associated with casting pointers.

In my use cases it's not uncommon for various systems to process half a million components per frame, so it's rather tuned for a specific use case. It might be a bit overkill for your needs but it's something that has served me for a long time now if you want to roll up your sleeves and get down and dirty with the bits and bytes.

Your Way

The way you have it now is, if you'll forgive me, about the most inefficient way I can imagine to do it for every kind of use case I can imagine. The problem there is that first you're dynamically-allocating every single component instance. That's often going to result in a loss of spatial locality between components. And then storing a separate container per entity which actually has its own size and capacity and pointer and dynamic allocations is also going to be quite a memory and performance overhead if you have a large, large number of entities. Lastly if you aren't storing components of a particular type contiguously in their own container, then that means when your system wants to fetch a list of components of a particular type (probably the most common query to an ECS), the ECS is going to have to iterate through every single entity in the entire scene that exists checking to see if it has that component (which involves potentially iterating through every single component in each entity).

If that's okay though, then one dynamic_cast in a central place is very understandable to implement ECS. Any time you want a syntax like this:

MotionComponent* motion = entity.get<MotionComponent>();

... that pretty much implies that there's some cast going on somewhere under the hood unless all that information is available statically at compile-time (in my case at least that's not feasible since plugin developers can introduce brand new component types into the software at runtime). The dynamic_cast is at least the safest kind of pointer cast there is and, if you centralize it to one get method as part of the entity interface, then it's not that big of a deal in practice.

As for your particular implementation, if you go with it, I'd seek to add something like this:

class Entity
{
public:
    template <class T>
    T* get() const
    {
        for (auto comp: components)
        {
            auto ptr = dynamic_cast<T*>(comp);
            if (ptr) 
                return ptr;
        }
        return nullptr;
    }

private:
    vector<BaseComponent*> components;
};

That centralizes the dynamic_cast to that one get<T> method in the codebase as opposed to having to litter casts and type checks all over your systems*.

Another Way

Another way I've seen people do, though it could easily be explosive in memory if implemented densely, is like this:

enter image description here

Basically you just think of it like an NxM matrix, where M is the number of entities, and N is the number of component types. You might store some marker or just a null pointer in the grid/matrix cells where no component of a particular type is attached to an entity. That's very straightforward but gets explosive in memory as you can probably quickly see.

A way to optimize the memory use then is to turn this into a sparse representation. For example, you might use a hash map for each column above (each hash table stores instances of a particular component type) which is associated to the row (entity) index as key, for example.

If you use this kind of rep and want this kind of syntax:

MotionComponent* motion = entity.get<MotionComponent>();

Then one straightforward way is to do something like this:

struct MotionComponent
{
    // Indicates which column (hash table, e.g.) to use in the 
    // above table where the motion components are stored.
    enum {type_index = ...};
    ...
};

... in which case you'd do something like:

template <class T>
T* Entity::get() const
{
    enum {idx = T::type_index};
    auto it = ecs.comp_maps[idx].find(this->entity_index);
    return (it != ecs.comp_maps[idx].end()) ? dynamic_cast<T*>(*it): nullptr;
}

To avoid the dynamic allocation per component, you can abstract at the hash map level like this as a very crude example:

class ComponentMap
{
public:
    virtual ~ComponentMap() {}
    virtual BaseComponent* find(int n) = 0;
};

template <class ComponentType>
struct ComponentMapT: public ComponentMap
{
    virtual BaseComponent* find(int n) override
    {
         auto it = comps.find(n);
         return (it != comps.end()) ? &*it: nullptr;
    }
    std::hash_map<ComponentType> comps;
};

Then you can store a polymorphic list of ComponentMap which actually stores each component subtype instance by value instead of storing BaseComponent* with dynamic allocations per component instance.

I suspect this solution can be quite performant if you do it this way. It does involve hash lookups to get from a particular entity to a component of a specific type, but typically your most critical execution paths in an ECS involve plowing through all available components in a scene of a particular type without even going through the entities first, like your physics system might want to plow through all the motion components in the system to transform, or your rendering system might want to plow through all the sprites (in 2D) or meshes/model (in 3D) in the system to render (or if a spatial index is involved, some system might want to plow through those components to update the spatial index only for your rendering system to then use the spatial index to render the appropriate components in the screen/frustum). This solution allows that to be done by just sequentially iterating through the hash map (which tends to store elements contiguously) storing all components of a given type without any kind of traversal from entity to an associated component.

  • 1
    You know, the first Entity::get()s implementation could be simplified to { for (auto& x : components) if (auto p = dynamic_cast<T*>(x)) return p; return nullptr; } with C++14 range-for. Also, I'm missing noexcept. – Deduplicator Dec 7 '18 at 23:34
  • @Deduplicator Cheers and thanks for pointing it out! I'm a bit behind and backwards a lot and often working in C++03 as a result of working in SDKs still focused on backwards source compatibility with ancient compilers. Will edit with range-based for and auto. – Dragon Energy Dec 8 '18 at 7:08
  • Since I asked the question I've changed my implementation to something much like your final example, and there are suggestions there that would definitely be useful. I'm still a newbie and the first solution was mostly beyond me (What's a variable length struct? Why make next and next_list point to the same object?), but I'll keep it bookmarked for when I'm less bad. – Jarius Dec 19 '18 at 9:42
  • @Jarius The essence of my solution is to link the component/entity arrays together, like Entity->ComptA->ComptC->nullptr. Except we're not like storing a linked list "container", we're actually storing these things in arrays. The way we're linking them together is through indices into each other's arrays. However, if you imagine we're trying to get from CompA to CompC in the above (skipping over CompB types), we need to know not only what index CompC is in the list but what type of component it is. The 16-bit integer identifies that type (and which list to use). – Dragon Energy Dec 19 '18 at 16:36
  • @Jarius And likewise instead of a nullptr, I use -1 to indicate a null (end of the list). That allows me to just use simple contiguous arrays to store everything without hash lookups or anything, and only traverse the relevant components associated to an entity if I'm doing entity->component traversal. As for variable-length structures, you don't need to do that but that's a C trick to allocate like a struct Foo with trailing memory at the end of it (we allocate more memory than the size of the structure). – Dragon Energy Dec 19 '18 at 16:37
2

The Entity doesn't need to have a vector<Component *>, as you've noticed, that's practically useless.

What you'll instead have is a bunch of vector<FooComponent *>s, for each type of Component.

In C++, you don't even need a class Component, instead your component-type agnostic code can be templates. You'll probably have a FooComponent -> Entity -> BarComponent lookup if any of your components interact with (optional) other components

  • Wouldn't that require each Entity to have a list for each possible Component? That seems like a waste when any particular Entity might have only a few of those out of potentially dozens. This is for a video game, so efficiency is a concern. – Jarius Oct 25 '18 at 18:36
  • Also, an Entity would only have one of each component at most, so that would just become a bunch of variables with some left empty. That seems like both a waste of space and a good way to create code bloat once you start adding more component types. – Jarius Oct 25 '18 at 19:33
  • No the entities don't have any of those – Caleth Oct 25 '18 at 19:41
  • I don't know what you're saying, then. – Jarius Oct 25 '18 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.