Alex Alex - 2 months ago 14
C++ Question

How to store pointers of vectors, containing different types

I am currently learning more about the ECS pattern and have been attempting to create my own implementation as practice. I decided I want to make it more cache friendly when looping through the components by packing all my different components into vectors, instead of having a vector of pointers.

A reference I've been reading suggests to put each different component type into a different array and to loop over it, like so:

AIComponent aiComponents[MAX_NUM];
PhysicsComponent physicsComponents[MAX_NUM];
RenderComponent renderComponents[MAX_NUM];

while (!gameOver)
{
// Process AI.
for (int i = 0; i < numEntities; i++)
{
aiComponents[i].update();
}

// Update physics.
for (int i = 0; i < numEntities; i++)
{
physicsComponents[i].update();
}

// Draw to screen.
for (int i = 0; i < numEntities; i++)
{
renderComponents[i].render();
}

// Other game loop machinery for timing...
}


I find this very limiting as it will require that everytime I create a new component that I will have to hand-create the array and the array loop.

I would much prefer a single field like so:

// A vector of pointers to other vectors of different types.
// For example, componentPool[0] could be RenderComponent and then
// componentPool[1] could be PhysicsComponent

vector< vector<AnyConcreteComponentType>* > componentPool;

for (int i = 0; i < componentPool.size(); i++)
{
for (auto& component : componentPool[i]) {
Update(component);
}
}


This would allow me to keep adding new systems dynamically in my init(), like so:

AddComponent(entityId, RenderComponent());


Which will automatically expand the componentPool to add a new RenderComponent slot, which will then point to the newly created vector and which I could then iterate over efficiently.

Problem is that I don't know how you would do this, or even do it optimally. I'd imagine there would have to be templates, casting and a way to know, before accessing the vector, what type I require but other than that I have no clue.

Answer

Assuming that:

  • your question is an XY problem and you only think storing pointers to vectors of different types might be a solution rather than the solution, and
  • you know the list of component types at compile-time (as opposed to allowing runtime-registration),

then this is relatively easily achieved by way of a tuple and some mechanism to iterate over it.

First, we want a metafunction to produce the correct tuple type given a list of component types:

namespace detail {
    template<std::size_t N, typename... Components>
    std::tuple<std::array<Components, N>...>
    makeComponentPool(std::tuple<Components...>) noexcept;
} // namespace detail

template<std::size_t N, typename ComponentTup>
using ComponentPool = decltype(detail::makeComponentPool<N>(std::declval<ComponentTup>()));

// example:
static_assert(std::is_same<
    ComponentPool<10, std::tuple<AIComponent, PhysicsComponent, RenderComponent>>,
    std::tuple<
        std::array<AIComponent, 10>,
        std::array<PhysicsComponent, 10>,
        std::array<RenderComponent, 10>
    >
>::value);

Then we need some way of iterating over the tuple; boost::fusion::for_each works well here, or we can roll our own:

namespace detail {
    template<typename TupT, typename FunT, std::size_t... Is>
    void for_each(TupT&& tup, FunT&& f, std::index_sequence<Is...>) {
        using expand = int[];
        (void)expand{0, (f(std::get<Is>(std::forward<TupT>(tup))), void(), 0)...};
    }
} // namespace detail

template<
    typename TupT, typename FunT,
    std::size_t TupSize = std::tuple_size<std::decay_t<TupT>>::value
>
void for_each(TupT&& tup, FunT&& f) {
    detail::for_each(
        std::forward<TupT>(tup), std::forward<FunT>(f),
        std::make_index_sequence<TupSize>{}
    );
}

Now we need to make a decision: should each component type have the same public access point? In the question there are both update() and render(); however if we can give these all the same name (e.g. process()) then things are quite straightforward:

struct AIComponent      { void process() { } };
struct PhysicsComponent { void process() { } };
struct RenderComponent  { void process() { } };

class Game {
    using ComponentTypes = std::tuple<AIComponent, PhysicsComponent, RenderComponent>;
    static constexpr std::size_t MAX_NUM = 3;

    ComponentPool<MAX_NUM, ComponentTypes> componentPool;
    std::atomic_bool gameOver{false};

public:
    void runGame() {
        while (!gameOver) {
            for_each(componentPool, [](auto& components) {
                for (auto& component : components) {
                    component.process();
                }
            });
        }
    }
    void endGame() { gameOver = true; }
};

Online Demo
(N.b. in the demo process() was given a parameter only for exposition, not due to any implementation requirement.)

Now you just need to manage MAX_NUM and ComponentTypes and everything else falls into place.

However, if you want to allow for different access points for different component types (e.g. update() for AIComponent and PhysicsComponent but render() for RenderComponent, as in the question) then we obviously have a bit of work left to do. One approach is to add a level of indirection for invoking the access point, and one way to accomplish that cleanly and with minimal overhead (both syntactic and runtime) is to use some utility to create local overload sets so that component processing can be trivially special-cased by type. Here is a basic implementation that works for all functors (inc. lambdas) but not for function pointers:

template<typename FunT, typename... FunTs>
struct overloaded : private FunT, private overloaded<FunTs...> {
    template<typename FunU, typename... FunUs>
    overloaded(FunU&& f, FunUs&&... fs)
      : FunT(std::forward<FunU>(f)),
        overloaded<FunTs...>(std::forward<FunUs>(fs)...)
    { }

    using FunT::operator();
    using overloaded<FunTs...>::operator();
};

template<typename FunT>
struct overloaded<FunT> : private FunT {
    template<typename FunU>
    overloaded(FunU&& f) : FunT(std::forward<FunU>(f)) { }

    using FunT::operator();
};

template<typename... FunTs>
overloaded<std::decay_t<FunTs>...> overload(FunTs&&... fs) {
    return {std::forward<FunTs>(fs)...};
}

If needed, more robust implementations of overload can be found online, but even with this simple implementation we can now do the following:

struct AIComponent      { void update() { } };
struct PhysicsComponent { void update() { } };
struct RenderComponent  { void render() { } };

class Game {
    using ComponentTypes = std::tuple<AIComponent, PhysicsComponent, RenderComponent>;
    static constexpr std::size_t MAX_NUM = 3;

    ComponentPool<MAX_NUM, ComponentTypes> componentPool;
    std::atomic_bool gameOver{false};

public:
    void runGame() {
        // `auto` overload is the least specialized so `update()` is the default
        static auto process = overload(
            [](           auto& comp) { comp.update(); },
            [](RenderComponent& comp) { comp.render(); }
        );

        while (!gameOver) {
            for_each(componentPool, [](auto& components) {
                std::for_each(begin(components), end(components), process);

                // alternatively, equivalently:
                //for (auto& component : components) {
                //    process(component);
                //}
            });
        }
    }
    void endGame() { gameOver = true; }
};

Online Demo

Now you need to manage MAX_NUM and ComponentTypes, and also potentially add a new overload to process (though you'll get a compiler error if you forget).

Comments