Entity Component System written in C++

Question

Below is the core of an entity component system I am working on to learn more c++, the full project can be seen here: https://github.com/williamholm/IBECS. Any feedback is appreciated.

The goal of this ECS is to end up with component data being sorted in such a way that for expressions which require multiple component vectors from the same entity have the same index. This is only broken if sets are sorted by different things but I believe there is no solution to that. Also the components of the same Entity Type, which are analogous to structs/classes, must be stored in sequence.

Three questions in particular are:

• Is there a way to generate the tuple in ETData that does not require component types to be default constructable?
• How can the sparse set implementation be improved?
• Does it make more sense to move all of TypeSortedSS into EntityManager, and replace mSparses with a tuple of mCDS instead?

In order to keep this shorter sorting implementation and derivation of Comp and ET has been left out.

Comp.hpp

#include "ET.hpp"

template<Comp_ID id, typename ComponentType = typename CompInfo<id>::type>
struct Comp
{
    using type = ComponentType;
    static constexpr Comp_ID sortedBy = CompInfo<id>::sortedBy;
    static constexpr auto sparse = getCompSparse<id>();
    static constexpr int noOfETsWithComp = sparse[ET_ID::MAX_ET_ID];
    //array of ET_IDs which contain this component - mainly useful for testing
    static constexpr auto ETsWithComp = isInSparse<id, noOfETsWithComp>();
    static constexpr int sortGroup = positionalArray(sortArray(),
         uniqueElements<noOfUniqueElements(sortArray())>(sortArray()))[id];
};

ET.hpp

#include "ETInfo.hpp"
#include "cosntexprUtility.hpp"
template<ET_ID id>
struct ET
{
    //which ETs are an ET<id> (not just direct inheritors). 
    static constexpr int noOfInheritors = noOfUniqueElements(getInheritors<id>::value);
    static constexpr std::array<ET_ID, noOfInheritors> inheritors = 
        uniqueElements<noOfInheritors>(getInheritors<id>::value);
    //inclusive inheritors - same as inheritors but includes id, usefull for loops ect
    static constexpr std::array<ET_ID, noOfInheritors+1> incInheritors = concatinate(id,inheritors);
    //Components
    static constexpr int noOfComponents = noOfUniqueElements(
        concatinate(getComponents<id>::value, ETInfo<id>::newComponents));
    static constexpr std::array<Comp_ID, noOfComponents> components =
        uniqueElements<noOfComponents>(concatinate(getComponents<id>::value, ETInfo<id>::newComponents));
    //Sparse for getting order of components - used in ETData for ease of use
    static constexpr std::array<int, MAX_COMP_ID> sparse = CompSparse(components);
};

ETData.hpp

#include <assert.h>
#include "comp.hpp"
#include <tuple>
template<ET_ID id, int compIndex = 0, int lastComp = ET<id>::noOfComponents - 1> //-1 for easier specialization
struct ETDataTupleConstructor
{
    using CompType = Comp<ET<id>::components[compIndex]>::type;
    static constexpr auto data = std::tuple_cat(std::make_tuple(CompType()),
        ETDataTupleConstructor<id, compIndex + 1, lastComp>::data);
};

template<ET_ID id, int compIndex>
struct ETDataTupleConstructor<id, compIndex, compIndex>
{
    using CompType = Comp<ET<id>::components[compIndex]>::type;
    static constexpr std::tuple<CompType> data = {};
};

template<ET_ID id>
struct ETData
{
    using type = std::remove_const<decltype(ETDataTupleConstructor<id>::data)>::type;
    type data;
    //essentially should be std::get but with comp_id -> component position in ET mapping
    template<Comp_ID comp_id>
    constexpr Comp<comp_id>::type& get()
    {
        static_assert(ET<id>::sparse[comp_id] != Comp_ID::MAX_COMP_ID);
        return std::get<ET<id>::sparse[comp_id]>(data); 
    }
    template<Comp_ID comp_id>
    constexpr Comp<comp_id>::type&& move()//is move here ok or bad? not clear when using std::get on a member of class.
    {
        static_assert(ET<id>::sparse[comp_id] != Comp_ID::MAX_COMP_ID);
        return std::move(std::get<ET<id>::sparse[comp_id]>(data));
    }
};

Entity.hpp

static constexpr uint32_t maxEntityType = 0xFFF;
static constexpr uint32_t maxEntityNumber = 0xFFFFF;
static constexpr uint32_t entityValueBits = 20;

//with this set up: max 1m entities, 4095 entity types
class Entity32Bit
{
private:
    uint32_t mEntity;
public:
    constexpr uint32_t number() const  noexcept
    {
        return mEntity & maxEntityNumber;
    }
    constexpr uint32_t type() const noexcept
    {
        return (mEntity >> entityValueBits);
    }
    constexpr void addType(uint32_t type) noexcept
    {
        assert(type <= maxEntityType);
        mEntity |= (type << entityValueBits);
    }
    constexpr void addNumber(const uint32_t entityNum) noexcept
    {
        assert(entityNum <= maxEntityNumber);
        mEntity = entityNum + (this->type() << entityValueBits);
    }
    inline bool operator==(const Entity32Bit rhs) const noexcept
    {
        return this->number() == rhs.number() && this->type() == rhs.type();
    }

    Entity32Bit() noexcept :mEntity(0) {}
    constexpr Entity32Bit(const uint32_t entityNumber, const uint32_t type) noexcept : mEntity(entityNumber)
    {
        assert(entityNumber < maxEntityNumber);
        addType(type);
    }
};

These two classes together sort data so that in TypeSortedSS mpSS->mEDS[id] is a vector of all entities of the ET_ID, id and mCDS[id] which is a vector of the component data that runs parallel to mpSS->mEDS[id] .

TypeSortedSS.hpp

#include <vector>
#include <assert.h>
#include "Entity.hpp"
#include "Comp.hpp"

class SegSparseSet
{
private:
    std::array<std::vector<Entity32Bit>, MAX_ET_ID> mEDS; //Entity Dense Sets
    std::array<std::vector<uint32_t>, MAX_ET_ID> mSparses;
public:
    inline bool entityInSet(Entity32Bit entity) noexcept { return (mSparses[entity.type()][entity.number()] != _UI32_MAX); }

    inline std::vector<Entity32Bit>& getEntities(const uint32_t group) { return mEDS[group]; }
    inline Entity32Bit& getEntity(const ET_ID group, const uint32_t index) { return mEDS[group][index]; }
    inline uint32_t getIndex(const Entity32Bit entity) { return mSparses[entity.type()][entity.number()]; }
    inline void changeIndex(const Entity32Bit entity, const uint32_t value) { mSparses[entity.type()][entity.number()] = value; }

    void addEntity(const Entity32Bit entity)
    {
        assert(!entityInSet(entity));
        changeIndex(entity, mEDS[entity.type()].size());
        mEDS[entity.type()].push_back(entity);
    }
    void deleteEntity(const Entity32Bit entity)
    {
        assert(entityInSet(entity));
        //change last member in group to point to deleted component;
        changeIndex(*(mEDS[entity.type()].end() - 1), getIndex(entity));
        //swapComponent + delete EDS
        mEDS[entity.type()][getIndex(entity)] = *(mEDS[entity.type()].end() - 1);
        mEDS[entity.type()].pop_back();
        //clear entity in sparse
        changeIndex(entity, _UI32_MAX);
    } 
    uint32_t totalSize()
    {
        int size = mEDS[1].size(); //mEDS[0] is always empty
        for (int i = 2; i < MAX_ET_ID; ++i)
        {
            size += mEDS[i].size();
        }
        return size;
    }
    void resizeSparse(ET_ID id, uint32_t size)
    {
        mSparses[id].resize(size);
        for (int i = 0; i < size; ++i)
        {
            mSparses[id][i] = _UI32_MAX;
        }
    }  
    uint32_t size(ET_ID id)
    {
        return mEDS[id].size();
    }

    SegSparseSet() noexcept :mSparses()
    {
        for (int i = 0; i < MAX_ET_ID; ++i)
        {
            resizeSparse((ET_ID)i, maxEntityAmount()[i]);
        }
    }
    template<Comp_ID component>
    SegSparseSet(const Comp<component>& comp) noexcept :mSparses()
    {
        for (int i = 0; i < MAX_ET_ID; ++i)
        {
            if (Comp<component>::compArray[i] == true)
            {
                resizeSparse((ET_ID)i, maxEntityAmount()[i]);
            }
        }
    }
};
  
template<Comp_ID mID, typename CompType = typename Comp<mID>::type>
class TypeSortedSS
{
private:
    using component = Comp<mID>;
    std::array<std::vector<CompType>, MAX_ET_ID> mCDS; //component dense set, parallel to mEDS in segSS.
    SegSparseSet* mpSS;
public:
  //checks to see if entity has this component
    inline bool validEntityGroup(Entity32Bit entity) noexcept { return (component::sparse[entity.type()] != 0); }
  
    void addComponent(Entity32Bit entity, const CompType& data)
    {
        assert(validEntityGroup(entity));
        mCDS[entity.type()].push_back(data);
    }
    void deleteComponent(Entity32Bit entity)
    {
        //need to do this check here (atleast in debug) as entity in SharedSS is deleted after components
        assert(mpSS->entityInSet(entity) && validEntityGroup(entity));
        mCDS[entity.type()][mpSS->getIndex(entity)] = *(mCDS[entity.type()].end() - 1);
        mCDS[entity.type()].pop_back();
    }
public:
    inline auto end(ET_ID id) { return mCDS[id].end(); }
    inline auto begin(ET_ID id) { return mCDS[id].begin(); }

    inline uint32_t getNoOfET(ET_ID id) { return mCDS[id].size(); }
    inline std::vector<CompType>& getETComps(ET_ID id) { return mCDS[id]; }
    inline CompType& getComponent(Entity32Bit entity) { return mCDS[entity.type()][mpSS->getIndex(entity)]; }
    inline CompType& getComponent(uint32_t eType, uint32_t index) { return mCDS[eType][index]; }
    inline void addSegmentedSS(SegSparseSet* SS) { mpSS = SS; }
    inline Entity32Bit getEntity(uint32_t eType, uint32_t index)  { return mpSS->getEntity(eType, index); }
  
    TypeSortedSS() : mpSS(nullptr) {}
};

EntityManager.hpp

#include "ETData.hpp"
#include "TypeSortedSS.hpp"
#include "Entity.hpp"

template<int... ints>
constexpr auto genTypesForTypeSortedTuple(std::integer_sequence<int, 0, ints...> seq)
{
    return std::tuple<int, TypeSortedSS<(Comp_ID)ints>...>();
}
typedef decltype(genTypesForTypeSortedTuple(std::make_integer_sequence<int, MAX_COMP_ID>())) TypeSortedSSTuple;

class EntityManager
{
private:
    //size of array == number of sorting groups
    std::array<SegSparseSet,noOfUniqueElements(sortArray())> mSharedSSs;
    TypeSortedSSTuple mSparses;
    std::array<uint32_t,MAX_ET_ID> mNextEntityNum;
    std::array<std::vector<uint32_t>, MAX_ET_ID> mDeletedEntityNum;
public:
    template<Comp_ID component>
    inline auto& sparse() { return std::get<component>(mSparses); } //for testing

    template<ET_ID id>
    Entity32Bit addEntity(ETData<id>& data)
    {
        Entity32Bit entity;
        if (mDeletedEntityNum[id].size() == 0)
        {
            assert(mNextEntityNum[id] < maxEntityNumber);
            entity.addNumber(mNextEntityNum[id]++);
            entity.addType(id);
        }
        else
        {
            entity.addNumber(*(mDeletedEntityNum[id].end() - 1));
            entity.addType(id);
            mDeletedEntityNum[id].pop_back();
        }
        //this makes assumption that at least one component of each entity is unsorted.
        mSharedSSs[0].addEntity(entity);
        addData(entity, data);
        return entity;
    }
    
    template<ET_ID id>
    void deleteEntity(Entity32Bit entity)
    {
        removeData<id>(entity);
        mSharedSSs[0].deleteEntity(entity);
        mDeletedEntityNum[id].push_back(entity.number());
    }
private:
    template<ET_ID id, int index = ET<id>::noOfComponents - 1>
    void addData(Entity32Bit entity, ETData<id>& data)//go through each component in ET<id> and add data to the correct sparse
    {
        //if sorted by itself add entity to the correct sorted SharedSS
        if constexpr (Comp<ET<id>::components[index]>::sortedBy == ET<id>::components[index])
        {
            mSharedSSs[Comp<ET<id>::components[index]>::sortGroup].addEntity(entity);
        }
        std::get<ET<id>::components[index]>(mSparses).addComponent(entity, data.get<ET<id>::components[index]>());
        if constexpr (index != 0)
        {
            addData<id, index - 1>(entity, data);
        }
    }

    template<ET_ID id, int index = ET<id>::noOfComponents - 1>
    void removeData(Entity32Bit entity)//go through each component in ET<id> and remove component from the correct sparse
    {
        std::get<ET<id>::components[index]>(mSparses).deleteComponent(entity);
        //if sorted by itself delete entity from the correct sorted SharedSS
        if constexpr (Comp<ET<id>::components[index]>::sortedBy == ET<id>::components[index])
        {
            mSharedSSs[Comp<ET<id>::components[index]>::sortGroup].deleteEntity(entity);
        }
        if constexpr (index != 0)
        {
            removeData<id, index - 1>(entity);
        }
    }
public:
    //both size functions assume at least one component of each ET is unsorted.
    inline int size() { return mSharedSSs[0].totalSize(); }
    inline uint32_t noOfET(ET_ID id) { return mSharedSSs[0].size(id); }
    
    //returns an iterator for dense set of the component for ET<id>
    template<Comp_ID component>
    inline auto begin(ET_ID id) { return std::get<component>(mSparses).begin(id); }
    template<Comp_ID component> 
    inline auto end(ET_ID id) { return std::get<component>(mSparses).end(id); }

    //looks simular to calling by Entity32Bit, however it bypasses looking through the sparse to get index, so is faster if you know index.
    template<Comp_ID component, typename ReturnType = typename Comp<component>::type>
    inline ReturnType& getComp(ET_ID id, uint32_t index) { return std::get<component>(mSparses).getComponent(id, index); }
    template<Comp_ID component, typename ReturnType = typename Comp<component>::type>
    inline ReturnType& getComp(Entity32Bit entity) { return std::get<component>(mSparses).getComponent(entity); }
    template<Comp_ID component>
    inline Entity32Bit getEntity(ET_ID id, uint32_t index) { return mSharedSSs[Comp<component>::sortGroup].getEntity(id, index); }
private:
    template<int index = 1>
    void addSegmentedSS()
    {
        if constexpr (index < MAX_COMP_ID)
        {
            std::get<index>(mSparses).addSegmentedSS(&mSharedSSs[Comp<(Comp_ID)index>::sortGroup]);
            addSegmentedSS<index + 1>();
        }
        return;
    }
public:
    EntityManager() noexcept : mSharedSSs()
    {
        for (int i = 0; i < MAX_ET_ID; ++i)
        {
            mNextEntityNum[i] = 1;
        }
        addSegmentedSS();
    };
};

Example

#include "EntityManager.hpp"
int main()
{
    EntityManager EM;
    ET<PHYS_OBJ>::components; //provides array of components for reference
    //struct containing components of Entity Type OBJ
    ETData<PHYS_OBJ> physObjData;

    physObjData.get<STATE>() = 0;
    physObjData.get<POS3D>() = vec3(1, 2, 3);
    physObjData.get<SPEED>() = 10;
    physObjData.get<ORIENTATION>() = vec3(0,1,0);

    Entity32Bit phyObjEntity = EM.addEntity(physObjData);

    //add 1000 PHYS_OBJ
    for (int i = 0; i < 1000; ++i)
    {       
        EM.addEntity(physObjData); //note no need to store return if Entity is anonymous 
    }
    
    //exmaple to update position by velocity, with unsorted position
    auto posIter = EM.begin<POS3D>(PHYS_OBJ);
    auto oriIter = EM.begin<ORIENTATION>(PHYS_OBJ);
    auto speedIter = EM.begin<SPEED>(PHYS_OBJ);
    int size = EM.noOfET(PHYS_OBJ);

    for (int i = 0; i < size; ++i)
    {
        posIter[i] += oriIter[i].scalarMulti(speedIter[i]);
    }

    //same example but if you have sorted positions
    EM.sort<POS3D>(PHYS_OBJ);
    Entity32Bit currentEntity;

    for (int i = 0; i < size; ++i)
    {
        //this retrieves Entity that contiants speedIter[i],
        //this is a slower way to access data so systems should avoid if possible.
        currentEntity = EM.getEntity<SPEED>(PHYS_OBJ, i); 
        //as POS3D is now a sorted component you cannot rely on posVecIter[i] belonging to
        //same entity as ori/speedVecIter[i]
        EM.getComp<POS3D>(currentEntity) += oriIter[i].scalarMulti(speedIter[i]);
    }

    //you can utilize inheritance to update all PHY_OBJ and all things that inherit from it 
    for (const auto ET : ET<PHYS_OBJ>::incInheritors)
    {
        int size = EM.noOfET(ET);
        posIter = EM.begin<POS3D>(ET);
        oriIter = EM.begin<ORIENTATION>(ET);
        speedIter = EM.begin<SPEED>(ET);

        for (int i = 0; i < size; ++i)
        {
            currentEntity = EM.getEntity<SPEED>(ET, i);
            EM.getComp<POS3D>(currentEntity) += oriIter[i].scalarMulti(speedIter[i]);
        }
    }
}
```

Answer 1

General impression

I had a very hard time reading your code. The reasons for this were poor choices of naming things, very little useful documentation for someone who doesn't already know the code well, and lots of rather complex use of templates. I'll elaborate more on these issues below.

Answers to your questions

• Is there a way to generate the tuple in ETData that does not require component types to be default constructable?

Yes. The problem is that you have data members, because you want to use decltype, because you didn't know how to concatenate tuple types, but you did know about std::tuple_cat.

However, you can concatenate just using types; see this StackOverflow post. This avoids the need for the data member.

• How can the sparse set implementation be improved?

It doesn't look very sparse to begin with: you always resize mSparses[id] to maxEntityAmount()[id]. It even says so in the comment: the first member variable of SegSparseSet is an array of "Dense Sets".

Using a hash table you can also get \$O(1)\$ insertion and deletion, and \$O(N)\$ time to iterate over the \$N\$ entries it holds. Of course, it has a higher cost than your SegSparseSet.

You could also consider storing the set as a std::vector<bool>, where each bit indicates whether a given entity is in the set or not. If you keep track of the highest entity number in the set, then iterating over the set can be done quite efficiently; especially if it's not sparser than 1 in every 32 numbers being in the set, you will use the same or less memory bandwidth to scan through the items in the set.

• Does it make more sense to move all of TypeSortedSS into EntityManager, and replace mSparses with a tuple of mCDS instead?

If there is a signifcant reduction in the complexity of EntityManager by moving part of that complexity into TypeSortedSS, then I would keep it like it is. Otherwise, if EntityManager is the only user of TypeSortedSS, it might indeed be better to move it into EntityManager.

Naming things

You are using various ways to abbreviate names in your code, and not all of them are clear. So of them are:

• Comp. Sure, you are writing an Entity Component System, so it probably means Component. But there are multiple IT-related words starting with "Comp", and the documentation for the STL often used comp to refer to a comparison function object (see std::sort for example).
• ET. Not a friendly alien of course, but an Entity Type. But many things are types in C++. Entity32Bit is a type as well. Maybe it's better to name it EntityProperties?
• incInheritors. The abbreviation inc is very commonly used to mean "increment".
• sparse. Sparse what? A sparse set perhaps? Of what? There are also the similar named functions CompSparse() and getCompSparse(). Why does one "get" and the other doesn't?

Avoid unnecessary abbreviations. If you do use them, be very consistent. For example, using ID for "identifier" everywhere is great. Having both SS and SparseSet is not great.

Spelling is also important. You are making several spelling mistakes in the comments, but also in function names like concatinate(), which whould be concatenate(). Spelling is not everyones forte, and manually checking spelling is a lot of time. Luckily, there are spell checkers, some even dedicated to spell checking source code, like codespell. Use such a spell checker regularly. If you have a build system with a test target, make sure the spell checker is run as part of the test suite.

Documentation

Consider documenting every class, member function and member variable using the Doxygen format. This helps others navigate your code, but also will help you in the long run, since in only half a year you will have forgotten a lot of the details of the code you wrote. The Doxygen tools can generate output in HTML, PDF and other formats, and they can check whether you documented all the classes and members. Many IDEs also understand the Doxygen format, and can then show you a synopsis when hovering over or tab completing types, member variables and function.

Your use of templates

There is nothing wrong with using template; however the way you are using them seems unnecessarily complex. I think the problem stems from the fact that you are decoupling things too much, and also instead of having template parameters be types, a lot of your template parameters are numeric identifiers. If I read the declaration of ETData and want to know what ETData<PHYS_OBJ>::type is, I have to visit several layers of other templates before I could tell you what the type actually is.

It would be much nicer if things are visible in one go. For example:

struct PhysicsObject
{
    using components = std::tuple<State, Position, Speed, Orientation>;
    …
};

enum class State {
    …
};

…

Note the lack of IDs - it's purely types. PhysicsObjects lists the components it is made of using a std::tuple of component types. Now you might think: "but I need those IDs because I need to create arrays to hold the data for each type". This can also be solved using types. Instead of creating an enum listing all the possible components for example, you can write:

using AllComponents = std::tuple<State, Position, Speed, Orientation, …>;

So now you know that there are std::tuple_size<AllComponents> components in total (no need for a MAX_COMP_ID), and with some work you can get the index for a given type.

You can do something similar for entities, and create an AllEntities type.

Make range-based for loops possible

In your code you have to iterate over positions like so:

auto posIter = EM.begin<POS3D>(PHYS_OBJ);
auto size = EM.noOfET(PHYS_OBJ);

for (decltype(size) i = 0; i < size; ++i) {
    do_something_with(posIter[i]);
}

I'd rather be able to write something like:

for (auto& position: EM.get<POS3D>(PHYS_OBJ)) {
    do_something_with(position);
}

It's not just that you can use a range-based for loop this way, it also enables you to use the std::ranges algorithms on your components. The get() member function should return a range, which is basically just a struct with non-templated begin() and end() member functions.

Note that iterating over multiple components simultaneously is very common, so you could make get() take a template parameter pack, and return an object with begin() and end() members that return tuples of references to component data, such that one could write:

for (auto& [position, orientation, speed]: EM.get<POS3D, ORIENTATION, SPEED>(PHYS_OBJ)) {
    position += orientation * speed;
}

Use std::size for sizes, counts and indices

Your code uses both int and uint32_t for sizes. I would at least have expected better consistency. Also, write std::uint32_t instead of uint32_t; the latter is not guaranteed to exist in the global namespace. But even better would be to use std::size_t: it is guaranteed to exist (std::uint32_t is an optional type) and it is large enough to be able to count and index any size array that fits in memory.

If you do want to stick with std::uint32_t, consider creating a type alias for it, and use the alias instead. This way, you can easily change it without having to go through your code to replace std::uint32_t with something else, with the added danger that you might have used std::uint32_t for other purposes as well.