Jump to content
  • Advertisement
Sign in to follow this  
Juliean

Data structure for entity/component system

This topic is 2070 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello,

 

up until now I've head each of my entities in my component system store a vector of all its components. In the systems however, I am mostly just iterating over one component at a time, which means in my case constructing a vector with all entities that have this very component each frame, and probably bad cache coherency since components are scrambled all over the place. Now, I'd like to have it more like "classic" ECS implementations that have components of each type in their own container. Now my question is: What is the best possible container for this, mostly regarding cache utilization and iteration speed. I do require being able to cross access components from the same entity at some time (like a phyiscs system updating the physics component, then outputting transform to the transform component). In this regard, which one of the following would you prefer?

 

- std::vector<Component*>, component after component being inserted to the end, without any holes. This would require me to A) store the entity id in the component and B) store each components id in the entity, in order to access them. Removing an entity/component would require to change a lot of those ids.

 

- std::vector<Component*>, with each component being stored at the exact location of the entities id, regardless of the other components, all not-used components are being nullptr. This would mean that I could easily reference different components via the entity handle, and also removing and inserting would be pretty fast, however there might be a huge memory impact if I e.g. have a component that only few entities use, then I'd have an almost empty container with a lot of nullptr entries. Also I'd need some way for checking whether a component really exists when iterating over, and I don't want having to do an explicit nullptr-check for every component-loop I use.

 

- std::map<int, Component*>, whereas "int" is the entity handle id. Would get rid of most of the problems above, except that the syntax for iterating over would possibly less readable/self explanatory (since except of "pComponent" in the loop I'd now have "component.first" and "component.second"). Also, I'm not so sure how well map fares in terms of speed/cache.

 

- Any of the above variations, but instead of Component* use Component. More of a general question though, would this make any difference regarding iterating/cache efficiency? I belive it could be better, since stuff is layed out directly in the same memory area, but I'm not sure if the difference is really noticable, and if it is an (premature, I confess) optimization thats worth taking?

 

So, what would (did) you guys do with your own entity/component systems? Is there any theoretical background that justifies one of this methods (or some other I didn't think about)? I'm sure going to profile before/after and probably try different methods in the past, but I'd like to have some starting point before enganging in this rather huge change...

Edited by Juliean

Share this post


Link to post
Share on other sites
Advertisement

I would start with one vector per component type and storing components directly. If you use C++11 it may be a good idea to provide move constructor and operator= . I think using pointers and/or casting to the basetype will get awkward/slower.

There are many ways to store them and if you create a template class for handling this you can easily change and profile it later.

You can for example try sorting the components by entity id number to find a single one faster, but mosty you would just go through the whole vector from beginning to end.

Adding an index or switching to a map/hashmap/whatever is also possible later on.

Edited by wintertime

Share this post


Link to post
Share on other sites

I would start with one vector per component type and storing components directly. If you use C++11 it may be a good idea to provide move constructor and operator= . I think using pointers and/or casting to the basetype will get awkward/slower.

 

Makes sense, thanks for the pointer. Yes, I'm using c++11 already (quite massively to some extent), so I'll be using those anyway ;)

 

 

 


There are many ways to store them and if you create a template class for handling this you can easily change and profile it later.

 

Talking about it, how would I store such vectors anyway? I don't want my components to being hardcoded, I even support dynamically adding components via plugins. I didn't think about this before, but I think I've got some solution:

class BaseComponentContainer
{
public:

    // the templated constructor ensures that a correct component id is assigned
    template<typename Component>
    ComponentContainer(void)
    {
        m_componentId = Component::id();
    }

    // we call this method to access the underlying vector in its correct type
    template<typename Component>
    std::vector<Component>& GetComponents(void)
    {
        ACL_ASSERT(Component::id() == m_componentId); // each component struct has a CRTP-auto generated id, which is guaranted to be the same for the programs execution time
        return static_cast<std::vector<Component>&>(*GetComponentVector()); // therefore, the static cast is safe
    }

    virtual void* GetComponentVector(void) = 0;

private:

    unsigned int m_componentId;
};

// this class will be actually stored inside a std::vector in the component manager, using the correct component type
// as template
template<typename Component>
class ComponentContainer final :
    BaseComponentContainer
{

    ComponentContainer(void) : BaseComponentContainer<Component>()
    {
    }

    void* GetComponentVector(void) override
    {
        return (void*)&m_vComponents;
    }

private:

    std::vector<Component> m_vComponents;
};

// the component manager handles all components and their containers, most functionaly is handled by the entity
// handle
class ComponentManager
{
    template<typename Component>
    void RegisterComponentType(void)
    {
        m_vComponentContainers[Component::id] = new ComponentContainer<Component>();
    }

    template<typename Component, typename... Args>
    void AddComponent(Args&& args)
    {
        GetComponents<Component>().emplace_back(args...);
    }

    template<typename Component>
    std::vector<Component>& GetComponents(void)
    {
        return m_vComponentContainers[Component::id()].GetComponents<Component>;
    }

private:

    std::vector<BaseComponentContainer*> m_vComponentContainers;
};

Well, it utilizes a variation of the CRTP pattern, that I've already deployed for my components, in order to ensure a somewhat typesafe way for storing the different component containers in one place. Do you think this is acceptable, or do you know any better way to solve this? (this code does need a lot more work though, I know, its just some quick pseudo-code for how things could work out)... I hope its clear how this code works, if not, feel free to let me know and I'll try to explain more :D

Edited by Juliean

Share this post


Link to post
Share on other sites

When I programmed an ECS I only generated a unique entity id (either only an ever increasing number or from an entity manager storing an array with all used id numbers returning a free one) and then put this into all components on construction. That also makes for a consistent sorting in case you need to iterate through 2 of the component arrays in some system.

I dont feel the need of component id-s if the component storage is aware of possible gaps in the entity id numbers, as there would be only 0 or 1 component of each type per entity.

Share this post


Link to post
Share on other sites

I dont feel the need of component id-s if the component storage is aware of possible gaps in the entity id numbers, as there would be only 0 or 1 component of each type per entity.

 

Its not really a component-id, but a component type-id, its used so that I can do exactly that - reference my components e.g. in templates with absolute type safety. I was more concerned about how to store the components in the strongly typed vectors though, since the ID system is already being used throughout my code, and has prooven pretty robust so far (thanks for the input anyhow). As for the actual concern, my problem is as following:

 

I now want to store all components in a seperate container, vector in this case. I also need to store those vectors somewhere central for access. Without using pointers and type casting, I can't simply do:

 

std::vector<std::vector<BaseComponent*>> m_vComponentContainers; // vector of component-vectors

 

I basically need different vectors:

 

std::vector<Transform>

std::vector<Actor>

std::vector<Physics>

 

so that I can later say in some systems code:

const auto& components = m_pEntities->GetComponents<Transform>(); // basically returns a const vector reference, maybe an iterator if improved

for(auto& transform : components)
{
}

without requiring typecasting in the client code. And I was wondering how to achieve this without hardcoding them. The code I posted offers some solution, but I wonder if there is any better (= less complicated) way of doing so?

Edited by Juliean

Share this post


Link to post
Share on other sites

Using Component Pointers stored in the vector won't help the cache continuity, since they might be allocated in any part of the memory.  If you just use plain old Component, then when it's inserted into the vector, it will be in the vector's contiguous memory, thus, when looping through all the components of a type, it will smoothly be going through the cache.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!