[C++] ECS Vector

Marcus Aseth

Utente Attivo
383
127
Hardware Utente
Sistema Operativo
Windows 10
Salve gente, ho ripreso da qualche giorno a programmare saltuariamente (per merito vostro che mi avete pingato nell'altro topic e fatto ricordare che avevo quest'hobby xD) ed ho pensato di postare quello che ho fin'ora, o per ricevere suggerimenti o magari in modo che qualcun altro possa prendere spunto o imparare.
Sto provando a creare un vector con il quale sia comodo lavorare in un Entity Component System, ed i requisiti sono semplici:
1)deve poter contenere vector di qualsiasi tipo (ogni tipo di Component và nel corrispettivo vector)
2)i Components presenti in ciascun vector devono mantere un index fisso, percui rimuovere elementi non deve alterare la posizione degli altri elementi presenti

e questa la classe che ho fin'ora:
C++:
#include <iostream>
#include <map>
#include <memory>
#include <vector>
#include <algorithm>
#include <type_traits>
using uInt = std::size_t;

struct Entity {
    struct Params { using ownerType = Entity; };
};

struct RectComponent {

    struct Params
    {
        int width{};
        int height{};
        using ownerType = RectComponent;
    };

    RectComponent(Params&& p) :width(p.width), height{ p.height }{}

private:
    int width{};
    int height{};
};

struct ConstraintComponent {
    struct Params
    {
        int val{};
        using ownerType = ConstraintComponent;
    };
    ConstraintComponent(Params&& p) :val(p.val) {}
    int val;
};

struct TextComponent {
    struct Params { using ownerType = TextComponent; };
};

template <typename... Args>
class ECSVector
{
public:

    //vector wrapper
    template<typename T>
    class vector_wrapper
    {
    public:

        using const_iterator = typename std::vector<T>::const_iterator;

        size_t size()const { return _vec.size(); }
        size_t capacity()const { return _vec.capacity(); }
        bool empty()const { return _vec.empty(); }
        const std::vector<uInt>& freeSlots()const { return _freeSlots; }
        const_iterator begin() const { return _vec.cbegin(); };
        const_iterator end() const { return _vec.cend(); };

        uInt add(typename T::Params&& params) {
            uInt elementID{};
            // if there is a free slot to store the component, use that.
            if (!_freeSlots.empty()) {
                elementID = _freeSlots.back();
                _freeSlots.pop_back();
                _vec[elementID] = T(std::forward<typename T::Params>(params));
            }
            else
            {//no free slot found, emplace it back.
                elementID = _vec.size();
                _vec.emplace_back(std::forward<typename T::Params>(params));
            }
            return elementID;
        }

        void remove(uInt id) {
            _freeSlots.emplace_back(id);
            std::sort(_freeSlots.begin(), _freeSlots.end(), std::greater<uInt>());
            //remove duplicates with unique-erase idiom
            _freeSlots.erase(std::unique(_freeSlots.begin(), _freeSlots.end()), _freeSlots.end());
        }

    private:
        std::vector<T> _vec;
        std::vector<uInt> _freeSlots;
    };

    //ECS VECTOR CLASS

    ECSVector() {
        //allocate 1 vector for each type.
        (..., internal_AddVector<Args>());
    }

    template<typename T> vector_wrapper<T>& getVector() {
        static_assert ((... | std::is_same<T, Args>::value), "ECSVector::getVector<T> called with an invalid type");
        void* ptr = data[getTypeID<T>()].get();
        auto* vec = static_cast<vector_wrapper<T>*>(ptr);
        return *vec;
    }

    template<typename T> uInt add(typename T::Params&& params) {
        return getVector<T>().add(std::forward<typename T::Params>(params));
    }

    template<typename T> void remove(uInt id)
    {
        getVector<T>().remove(id);
    }

    void print_data_layout()
    {
        (..., print_vector<Args>());
    }


private:
    std::map<uInt, std::shared_ptr<void>> data;

    template<typename T> uInt getTypeID() const {
        static uInt id = internal_GenerateTypeID();
        return id;
    }

    uInt internal_GenerateTypeID() const {
        static uInt typeIDCounter{};
        return typeIDCounter++;
    }

    template<typename T> void internal_AddVector() {
        data[getTypeID<T>()] = static_cast<std::shared_ptr<void>>(std::make_shared<vector_wrapper<T>>());
    }

    template<typename T> void print_vector()
    {
        auto& vec = getVector<T>();
        std::cout << "typeId " << getTypeID<T>() << ":" << std::endl;
        std::cout << "[";
        for (size_t i = 0; i < vec.size(); i++)
        {
            bool isFree = false;
            for (auto val : vec.freeSlots()) {
                if (val == i) { isFree = true; }
            }

            std::cout << (isFree ? "_" : "O");

            if (i + 1 != vec.size())
                std::cout << "|";
        }
        std::cout << "]" << std::endl;
    }

};
I component sopra sono dei placeholder giusto per provare che tutto funzioni, e quel codice permette di scrivere questo:

C++:
ECSVector<
    Entity,
    RectComponent,
    ConstraintComponent,
    TextComponent
> ECdata;

template<typename... Args>
void CreateEntity(Args&&... args)
{
    (..., ECdata.add<typename Args::ownerType>(std::forward<Args>(args)));
}

int main()
{
    CreateEntity(RectComponent::Params{ .width{300}, .height{400} },
                 RectComponent::Params{ .width{300}, .height{400} },
                 RectComponent::Params{ .width{300}, .height{400} },
                 RectComponent::Params{ .width{300}, .height{400} },
                 RectComponent::Params{ .width{300}, .height{400} },
                 ConstraintComponent::Params{ .val{41} }
    );
    ECdata.remove<RectComponent>(1);
    ECdata.remove<RectComponent>(3);
    ECdata.print_data_layout();

    return 0;
}
che darà questo output nella console:
typeId 0:
[]
typeId 1:
[O|_|O|_|O]
typeId 2:
[O]
typeId 3:
[]
dove "[]" significa vector vuoto per quel tipo, "O" significa che lo slot è attualmente occupato da un elemento e "_" che lo slot è libero (un elemento è stato in precedenza rimosso)

Una "constraint" del modo in cui lo sto facendo è che ogni classe/struct che và dentro questo ECSVector deve contenere una classe/struct chiamata "Params" che a sua volta deve contenere "ownerType"
In questo modo è possibile utilizzare "designated initializers" (c++ 20, VS li supporta) come nell'esempio sopra { .width{300}, .height{400} } così da poter creare gli oggetti in manierà più espressiva e chiara (putroppo VS non fornisce l'autocomplete in questo caso, ma magari in futuro)
Il vantaggio dell'avere il tutto organizzato in questo modo qui (per chi non lo sapesse gia) è che i "Systems" nell ECS possono occuparsi dei vectors di Components uno alla volta (esempio un PhysicSystem puo calcolare tutti i ConstraintComponent in un solo pass, il RenderingSystem può disegnare tutti i RectComponent in un solo pass) il che è molto più veloce quando tutti gli elementi sono in memoria contigua per via del pre-fetching, al contrario del più lento classico OOP dove magari per ogni Entity viene chiamato Update() e Draw() che fà le stesse operazioni menzionate in precedenza ma saltando da una parte all'altra della memoria (ConstraintComponent1, RectComponent1, ConstraintComponent2, RectComponent2 etc...) e non traendo alcun beneficio dal pre-fetching.
Di sicuro ho imparato uno o due cosa da questo esercizio, spero ci sia qualcosa di interessante anche per voi :)
Post automaticamente unito:

dopo aver riflettuto un pò di più sull'organizzazione dei dati, ovvero questa pattern qui: [O|_|O|_|O] mi son reso conto che avere elementi ad index fissi non è una buona soluzione, perchè
1)maggior consumo di memoria
2)se ci sono molti "buchi" lasciati dagli elementi rimossi, un System potrebbe ritrovarsi ad iterare un vector enorme e lavorare solo su pochi elementi
3)l'accesso ad ogni elemento và controllato, qualcosa del tipo una bool "isAlive", perchè quegli spazi rappresentano elementi distrutti

Decisamente la direzione sbagliata, percui ho deciso di rimuovere la limitazione degli index fissi, la ragione per cui l'avevo messa in principio è che un'entity non è altro che un contenitore di index ai components che possiede (non pointers visto che un vector può decidere di riallocare ed invalidarli tutti), percui se i components cambiano posizione a causa di un elemento rimosso, le entity si ritrovano con un index ad un component sbagliato o "out of range".
Percui quello che mi serve è una sorta di map, ma a differenza di std::map deve garantire che tutti i component "vivi" siano in un memoria adiacente.
Questa la mia soluzione attuale:


C++:
template <typename... Args>

class ECSVector

{

public:


    //vector wrapper

    template<typename T>

    class vector_wrapper

    {

    public:


        using const_iterator = typename std::vector<T>::const_iterator;


        size_t size()const { return _vec.size(); }

        size_t capacity()const { return _vec.capacity(); }

        bool empty()const { return _vec.empty(); }

        const_iterator cbegin() const { return _vec.cbegin(); };

        const_iterator cend() const { return _vec.cend(); };

        uInt idToSlot(uInt id)const { return _idToSlot[id]; }

        uInt slotToID(uInt slot)const { return _slotToID[slot]; }

        uInt totalIDsAmmount()const { return _idToSlot.size(); }


        uInt add(typename T::Params&& params) {


            // if there is a free ID, use that, otherwise generate a new one.

            uInt elementID{};

            if (_vec.size() < _slotToID.size()) {

                elementID = _slotToID[_vec.size()];

            }

            else {

                elementID = _vec.size();

                _slotToID.push_back(elementID);

                _idToSlot.push_back(elementID);

            }

            _vec.emplace_back(std::forward<typename T::Params>(params));

            return elementID;

        }


        void remove(uInt ID) {


            //check if ID is present.


            uInt leftElementID = ID;

            uInt rightElementID = _slotToID[_vec.size() - 1];


            uInt leftSlot = _idToSlot[leftElementID];

            uInt rightSlot = _idToSlot[rightElementID];


            //swap element with the back() element of the vector.

            std::swap(_vec[leftSlot], _vec[rightSlot]);


            //update mapping.

            std::swap(_idToSlot[leftElementID], _idToSlot[rightElementID]);

            std::swap(_slotToID[leftSlot], _slotToID[rightSlot]);


            _vec.pop_back();

        }


    private:

        std::vector<T> _vec;

        std::vector<uInt> _slotToID;

        std::vector<uInt> _idToSlot;

    };


    //ECS VECTOR CLASS


   //...etc
};


percui adesso eliminare un elemento non è altro che uno swap con l'ultimo elemento del vector mentre i due vector "_idToSlot" e "_slotToID" si occupano di mappare i corretti slot con i corretti index per la (suppongo) rara eventualità di dover accedere i components attraverso gli ID tenuti da un'Entity, e tutti i System ora possono iterare i rispettivi vector senza dover fare nessun controllo per vedere se il component esiste o è stato distrutto.

Per testarlo, scrivendo questo codice qui:
C++:
CreateEntity(RectComponent::Params{ .width{300}, .height{400} },
                 RectComponent::Params{ .width{300}, .height{400} },
                 RectComponent::Params{ .width{300}, .height{400} },
                 RectComponent::Params{ .width{300}, .height{400} },
                 RectComponent::Params{ .width{300}, .height{400} }
    );
    ECdata.print_data_layout();
    ECdata.remove<RectComponent>(1);
    std::cout << "Element ID 1 removed!" << std::endl;
    ECdata.print_data_layout();
    ECdata.remove<RectComponent>(4);
    std::cout << "Element ID 4 removed!" << std::endl;
    ECdata.print_data_layout();
    ECdata.add(RectComponent::Params{ .width{300}, .height{400} });
    std::cout << "Added component!" << std::endl;
    ECdata.print_data_layout();
    ECdata.add(RectComponent::Params{ .width{300}, .height{400} });
    std::cout << "Added component!" << std::endl;
    ECdata.print_data_layout();
    ECdata.add(RectComponent::Params{ .width{300}, .height{400} });
    std::cout << "Added component!" << std::endl;
    ECdata.print_data_layout();
genera questo risultato qui
353978


dove due elementi vengono rimossi e poi 3 aggiunti, e tutto sembra funzionare :D
(in questo caso gli elementi marcati con "_" sono oltre la fine del vector, l'output mostra tutti gli ID attualmente disponibili e "_" indica ID pronti per essere ri-usati prima che nuovi ID vengano generati)

Codice completo: https://pastebin.com/zEfAKvS7
 
Ultima modifica:

Marcus Aseth

Utente Attivo
383
127
Hardware Utente
Sistema Operativo
Windows 10
Ok, migliorato ulteriormente, adesso è in grado di contenere sia Entity & Components che Systems nello stesso vector.
Il trucco sta nel fatto che è un vector di void* e i "template arguments" passati vengono smistati in maniera appropriata tramite inheritance, ovvero se "template argument" T è derivato da `elementMappingBase` allora viene creato un `vector<T>`, se è derivato da `systemMappingBase` viene conservato semplicemente come T (perchè T == RenderingSystem, non avrebbe senso averne più di uno, tutti i System sono unici).
In precedenza stavo usando classi tipo `getTypeID<RectComponent>()` che data una classe, esempio `RectComponent`, ritornava l'id associato, così da poter accedere il giusto index nel vector<void*> e fare il cast a `vector<RectComponent>*` ed accedere il tutto in maniera corretta.
Questo presenta un problema.
Un'entity in un ECS non è altro che uno struct contenente vari index (int) ai suoi vari components, percui se io so che vector<RectComponent>* si trova in `data[1]` e che quell'entity possiede 3 components, esempio id: [1,12,37] , allora entity può avere una `std::map<uInt, std::vector<uInt>>` con Key = 1 e Value = [1,12,37], così da poter iterare a runtime in un for-range loop e rimuovere tutti i component associati quando `removeEntity(id)` viene chiamato.
Il problema è che se ho una classe tipo `typename idToType<1>()::type` che con una chiamata simile ritorna il tipo "RectComponent", non posso usarla a run-time, ovvero non posso scrivere `typename idToType<run_time_variable>()::type`
Percui la mia soluzione attuale è generare tante classi con il mapping relativo al tipo ed il suffisso "_type" tramite macro ex:

C++:
#define GenerateElementTypeMappingClass(T)            \
class T/*forward declare*/;                            \
class T##_type : elementMappingBase, typeCounter {    \
public:                                                \
using type = T;                                        \
inline static const uInt value = _typeCounter++;    \
};
in questo modo posso chiamare questa macro in questa maniera qui
C++:
//Entity & Components
GenerateElementTypeMappingClass(Entity);
GenerateElementTypeMappingClass(RectComponent);
GenerateElementTypeMappingClass(ConstraintComponent);
GenerateElementTypeMappingClass(TextComponent);
che, genererà una classe tipo `class RectComponent_type{}` con dentro il corretto id ed i corretto alias per RectComponent.
In questo modo posso metterle tutte dentro una variant in questa maniera qui:

C++:
template <typename... Args>
class ECSData
{
private:
    using typeMapping_variant = std::variant<Args...>;

    std::vector<typeMapping_variant> dataMapping;
    //...
e quindi la creazione di questo container appare così:

C++:
ECSData<
        Entity_type,
        RectComponent_type,
        ConstraintComponent_type,
        TextComponent_type,
        RenderingSystem_type,
        ConstraintSystem_type
    > ecsData;
Il vantaggio è che adesso una chiamata a ecsData.removeEntity(EEHandle::TopMenu);` può fare questo

C++:
    //remove all components
        for (auto it = entity->components.begin(); it != entity->components.end(); it++) {
            for (auto compId : it->second) {
                _removeComponent(it->first, compId);
            }
        }
e _removeComponent() può usare std::visit per ottenere il giusto `_type` associato ad un int, che a sua volta contiene il giusto type alias per il cast, qualcosa del genere:
C++:
void _removeComponent(uInt vectorId, uInt componentId)
    {
        std::visit([this, componentId](auto&& mappedType)
                   {
                       using T = typename std::decay_t<decltype(mappedType)>::type;
                       auto& vec = this->_getVectorFromT<T>();
                       vec.remove(componentId);

                   }, dataMapping[vectorId]);
    }
Insomma, è l'unica soluzione che mi è venuta in mente per recuperare un tipo tramite run-time variable xD
Codice completo qui https://godbolt.org/z/njJajH
main() inizia nella linea 504 e l'output nella console mostra le operazioni eseguite, sperando non mi sia sfuggito nessun bug :D
 

Entra

oppure Accedi utilizzando