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:
I component sopra sono dei placeholder giusto per provare che tutto funzioni, e quel codice permette di scrivere questo:
che darà questo output nella console:
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 :)
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:
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:
genera questo risultato qui
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
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:
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 unito automaticamente:
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
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:
