using namespace std;
Consider a traditional OOP approach to entity/object management:
struct Entity { bool alive{true}; }
struct Manager {
vector<unique_ptr<Entity>> entities; // Non cache-friendly
void update() {
// erase-remove_if idiom: remove all !alive entities
entities.erase(remove_if(begin(entities), end(entities),
[](const unique_ptr<Entity>& e){ return !e->alive; }));
}
};
struct UserObject {
// Even if Manager::entities contents are re-ordered
// this reference is still valid (if the entity was not deleted)
Entity& entity;
};
However, I would like to try a data-oriented approach: not dynamically allocating Entity
instances, but storing them in cache-friendly linear memory.
struct Manager {
vector<Entity> entities; // Cache-friendly
void update() { /* erase-remove_if !alive entities */ }
};
struct UserObject {
// This reference may unexpectedly become invalid
Entity& entity;
};
Seems nice. But... if std::vector
needs to reallocate its internal array, all references to the entities will become invalid.
The solution is using an handle class.
struct Entity { bool alive{true}; };
struct EntityHandle { int index; };
struct Manager {
vector<Entity> entities; // Cache-friendly
void update() { /* erase-remove_if !alive entities */ }
Entity& getEntity(EntityHandle h) { return entities[h.index]; }
};
struct UserObject { EntityHandle entity; };
If I'm only adding/removing entities at the back of the vector, it seems to work. I can use the getEntity
method to retrieve the entity I want.
But what if I remove an Entity
from the middle of the vector? All EntityHandle
instances will now hold the incorrect index, since everything was shifted. Example:
The handle points to index: 2
Entity A gets removed during update()
Now the handle points to the wrong entity.
How is this problem usually dealt with?
Are the handle indices updated?
Is the dead entity replaced with a placeholder?
To clarify:
This and this are examples of what I mean by cache-friendly design.
Also, component systems such as Artemis claim to be in a linear cache-friendly design, and they use solutions similar to handles. How do they deal with the problem I describe in this question?
There's a great powerpoint done by insomniac, their solution was something like this
template<typename T, size_t SIZE>
class ResourceManager
{
T data[SIZE];
int indices[SIZE];
size_t back;
ResourceManager() : back(0)
{
for(size_t i=0; i<SIZE; i++)
indices[i] = static_cast<int>(i);
}
int Reserve()
{ return indices[back++]; }
void Release(int handle)
{
for(size_t i=0; i<back; i++)
{
if(indices[i] == handle)
{
back--;
std::swap(indices[i], indices[back]);
return;
}
}
}
T GetData(size_t handle)
{ return data[handle]; }
};
I hope this example demonstrates the idea plainly.