Esta semana, comencé a trabajar en mi motor de juego Vagabond y comencé a implementar la plantilla de
sistema de componente de entidad .
En este artículo quiero hablar sobre mi implementación, que está disponible gratuitamente en
GitHub . Pero en lugar de simplemente comentar sobre el código, quiero explicar cómo se diseñó su estructura. Por lo tanto, comenzaré con la primera implementación que escribí, analizaré sus fortalezas y debilidades, y luego mostraré cómo la mejoré. Al final enumeraré una lista de aspectos que también se pueden mejorar.
Introduccion
Motivación
No hablaré sobre los beneficios de ECS sobre el enfoque orientado a objetos, porque muchas personas antes que yo lo han hecho bien. Scott Bilas fue uno de los primeros en hablar sobre ECS en el
GDC 2002 . Otras introducciones famosas al tema incluyen
Evolve Your Hierarchy de Mike West y el capítulo
Componentes del impresionante libro de
Patrones de programación de juegos de Robert Nistrom.
En resumen, diré que la tarea de ECS es crear un enfoque orientado a los datos para las entidades del juego y la separación conveniente de datos y lógica. Las entidades están compuestas de componentes que contienen datos. Y los sistemas que contienen lógica procesan estos componentes.
Si entra en detalles, en lugar de
herencia , la
composición se usa en ECS. Además, este enfoque orientado a datos hace un mejor uso de la memoria caché, lo que significa que logra un rendimiento excelente.
Ejemplos
Antes de profundizar en el código, me gustaría mostrarle lo que vamos a diseñar.
Asignar componentes es muy simple:
struct Position : public Component<Position> { float x; float y; }; struct Velocity : public Component<Velocity> { float x; float y; };
Como puede ver, utilizaremos la plantilla
CRTP .
Luego, por razones técnicas, que explicaré más adelante, necesitamos fijar la cantidad de componentes y la cantidad de sistemas:
constexpr auto ComponentCount = 32; constexpr auto SystemCount = 8;
A continuación, puede especificar un sistema que tomará todas las entidades que tienen ambos componentes y actualizará sus posiciones:
class PhysicsSystem : public System<ComponentCount, SystemCount> { public: PhysicsSystem(EntityManager<ComponentCount, SystemCount>& entityManager) : mEntityManager(entityManager) { setRequirements<Position, Velocity>(); } void update(float dt) { for (const auto& entity : getManagedEntities()) { auto [position, velocity] = mEntityManager.getComponents<Position, Velocity>(entity); position.x += velocity.x * dt; position.y += velocity.y * dt; } } private: EntityManager<ComponentCount, SystemCount>& mEntityManager; };
El sistema simplemente usa el método
setRequirements para
setRequirements sus componentes de
setRequirements . Luego, en el método de
update , puede llamar a
getManagedEntities para atravesar iterativamente todas las entidades que satisfacen los requisitos.
Finalmente, creemos un administrador de entidades, registremos los componentes, creemos un sistema y varias entidades, y luego actualicemos sus posiciones usando el sistema:
auto manager = EntityManager<ComponentCount, SystemCount>(); manager.registerComponent<Position>(); manager.registerComponent<Velocity>(); auto system = manager.createSystem<PhysicsSystem>(manager); for (auto i = 0; i < 10; ++i) { auto entity = manager.createEntity(); manager.addComponent<Position>(entity); manager.addComponent<Velocity>(entity); } auto dt = 1.0f / 60.0f; while (true) system->update(dt);
Puntos de referencia
No pretendo crear la mejor biblioteca de ECS. Solo quería escribirlo yo mismo. Además, solo trabajé en ello durante una semana.
Sin embargo, esta no es una razón para crear algo completamente ineficaz. Así que instalemos los puntos de referencia:
- El primero creará entidades;
- El segundo usará el sistema para atravesar iterativamente entidades;
- Este último creará y destruirá entidades;
Los parámetros de todos estos puntos de referencia son el número de entidades, el número de componentes para cada entidad, el número máximo de componentes y el número máximo de sistemas. De esta manera, podemos ver qué tan bien escala nuestra implementación. En particular, mostraré los resultados para tres perfiles diferentes:
- Perfil A: 32 componentes y 16 sistemas;
- Perfil AA: 128 componentes y 32 sistemas;
- Perfil AAA: 512 componentes y 64 sistemas.
A pesar de que estos puntos de referencia nos darán una idea de la calidad de la implementación, son bastante simples. Por ejemplo, en estos puntos de referencia usamos solo entidades homogéneas, y sus componentes son pequeños.
Implementación
Esencia
En mi implementación, una entidad es solo una identificación:
using Entity = uint32_t;
Además, en
Entity.h también definiremos un
Index alias, que será útil más adelante:
using Index = uint32_t; static constexpr auto InvalidIndex = std::numeric_limits<Index>::max();
Decidí usar
uint32_t lugar del tipo de 64 bits o
std::size_t para ahorrar espacio y mejorar la optimización de caché. No perderemos tanto: es poco probable que alguien tenga miles de millones de entidades.
Componente
Ahora definamos la clase base para los componentes:
template<typename T, auto Type> class Component { public: static constexpr auto type = static_cast<std::size_t>(Type); };
La clase de plantilla es muy simple, solo almacena la identificación de tipo, que usaremos más adelante para indexar las estructuras de datos por tipo de componentes.
El primer parámetro de plantilla es el tipo de componente. El segundo es el valor convertido a
std::size_t , que servirá como id del tipo de componente.
Por ejemplo, podemos definir el componente
Position siguiente manera:
struct Positon : Component<Position, 0> { float x; float y; };
Sin embargo, una enumeración puede ser más conveniente:
enum class ComponentType { Position }; struct Positon : Component<Position, ComponentType::Position> { float x; float y; };
En el ejemplo introductorio, solo hay un parámetro de plantilla: no necesitamos especificar el tipo de identificación manualmente. Más adelante veremos cómo mejorar la estructura y generar identificadores de tipo automáticamente.
EntityContainer
La clase
EntityContainer será responsable de administrar las entidades y
std::bitset para cada una de ellas. Este conjunto de bits indicará los componentes que posee la entidad.
Dado que usaremos entidades para indexar contenedores, y en particular
std::vector , necesitamos que la identificación sea lo más pequeña posible y que ocupe menos memoria. Por lo tanto, reutilizaremos la identificación de las entidades destruidas. Para hacer esto, la identificación gratuita se almacenará en un contenedor llamado
mFreeEntities .
Aquí está la
EntityContainer :
template<std::size_t ComponentCount, std::size_t SystemCount> class EntityContainer { public: void reserve(std::size_t size); std::vector<std::bitset<ComponentCount>>& getEntityToBitset(); const std::bitset<ComponentCount>& getBitset(Entity entity) const; Entity create(); void remove(Entity entity); private: std::vector<std::bitset<ComponentCount>> mEntityToBitset; std::vector<Entity> mFreeEntities; };
Veamos cómo se implementan los métodos.
getEntityToBitset y
getBitset son los pequeños getters habituales:
std::vector<std::bitset<ComponentCount>>& getEntityToBitset() { return mEntityToBitset; } const std::bitset<ComponentCount>& getBitset(Entity entity) const { return mEntityToBitset[entity]; }
El método de
create es más interesante:
Entity create() { auto entity = Entity(); if (mFreeEntities.empty()) { entity = static_cast<Entity>(mEntityToBitset.size()); mEntityToBitset.emplace_back(); } else { entity = mFreeEntities.back(); mFreeEntities.pop_back(); mEntityToBitset[entity].reset(); } return entity; }
Si hay una entidad libre, la reutiliza. De lo contrario, el método crea una nueva entidad.
El método
remove simplemente agrega la entidad que se eliminará en
mFreeEntities :
void remove(Entity entity) { mFreeEntities.push_back(entity); }
El último método es la
reserve . Su tarea es reservar memoria para varios contenedores. Como podemos saber, asignar memoria es una operación costosa, por lo que si conocemos aproximadamente el número de entidades futuras en el juego, la memoria de reserva acelerará el trabajo:
void reserve(std::size_t size) { mFreeEntities.resize(size); std::iota(std::begin(mFreeEntities), std::end(mFreeEntities), 0); mEntityToBitset.resize(size); }
Además de una simple copia de seguridad de la memoria, también completa
mFreeEntities .
ComponentContainer
La clase
ComponentContainer será responsable de almacenar todos los componentes del tipo especificado.
En mi arquitectura, todos los componentes de un tipo dado se almacenan juntos. Es decir, hay una gran matriz para cada tipo de componente, llamada
mComponents .
Además, para poder agregar, recibir o eliminar un componente de una entidad en tiempo constante, necesitamos una forma de pasar de una entidad a un componente y de un componente a otra. Para hacer esto, necesitamos dos estructuras de datos más llamadas
mComponentToEntity y
mEntityToComponent .
Aquí está la declaración de
ComponentContainer :
template<typename T, std::size_t ComponentCount, std::size_t SystemCount> class ComponentContainer : public BaseComponentContainer { public: ComponentContainer(std::vector<std::bitset<ComponentCount>>& entityToBitset); virtual void reserve(std::size_t size) override; T& get(Entity entity); const T& get(Entity entity) const; template<typename... Args> void add(Entity entity, Args&&... args); void remove(Entity entity); virtual bool tryRemove(Entity entity) override; Entity getOwner(const T& component) const; private: std::vector<T> mComponents; std::vector<Entity> mComponentToEntity; std::unordered_map<Entity, Index> mEntityToComponent; std::vector<std::bitset<ComponentCount>>& mEntityToBitset; };
Puede ver que hereda de
BaseComponentContainer , que se establece así:
class BaseComponentContainer { public: virtual ~BaseComponentContainer() = default; virtual void reserve(std::size_t size) = 0; virtual bool tryRemove(Entity entity) = 0; };
El único propósito de esta clase base es poder almacenar todas las instancias del
ComponentContainer en un contenedor.
Veamos ahora la definición de métodos.
Primero, considere el constructor: obtiene una referencia a un contenedor que contiene conjuntos de bits de entidad. Esta clase lo usará para verificar la presencia de un componente en una entidad y para actualizar el conjunto de bits de una entidad al agregar o eliminar un componente:
ComponentContainer(std::vector<std::bitset<ComponentCount>>& entityToBitset) : mEntityToBitset(entityToBitset) { }
El método
get es simple, solo usamos
mEntityToComponent para encontrar el índice de un componente de entidad en
mComponents :
T& get(Entity entity) { return mComponents[mEntityToComponent[entity]]; }
El método
add usa sus argumentos para insertar un nuevo componente al final de
mComponents , y luego prepara enlaces para ir de entidad a componente y de componente a entidad. Al final, establece el bit del conjunto de bits de
entity que coincide con el componente en
true :
template<typename... Args> void add(Entity entity, Args&&... args) { auto index = static_cast<Index>(mComponents.size()); mComponents.emplace_back(std::forward<Args>(args)...); mComponentToEntity.emplace_back(entity); mEntityToComponent[entity] = index; mEntityToBitset[entity][T::type] = true; }
El método
remove establece el componente de bit correspondiente en
false , y luego mueve el último componente
mComponents en el índice del que queremos eliminar. Actualiza los enlaces al componente que acabamos de mover y elimina uno de los componentes que queremos destruir:
void remove(Entity entity) { mEntityToBitset[entity][T::type] = false; auto index = mEntityToComponent[entity];
Podemos realizar movimientos de tiempo constante moviendo el último componente en el índice que queremos destruir. Y de hecho, entonces solo necesitamos eliminar el último componente, que se puede hacer en
std::vector en tiempo constante.
El método
tryRemove verifica si una entidad tiene un componente antes de intentar eliminarlo:
virtual bool tryRemove(Entity entity) override { if (mEntityToBitset[entity][T::type]) { remove(entity); return true; } return false; }
El método
getOwner devuelve la entidad propietaria del componente, para esto utiliza aritmética de puntero y
mComponentToEntity :
Entity getOwner(const T& component) const { auto begin = mComponents.data(); auto index = static_cast<std::size_t>(&component - begin); return mComponentToEntity[index]; }
El último método es de
reserve , tiene el mismo propósito que un método similar en
EntityContainer :
virtual void reserve(std::size_t size) override { mComponents.reserve(size); mComponentToEntity.reserve(size); mEntityToComponent.reserve(size); }
El sistema
Ahora veamos la clase del
System .
Cada sistema tiene un conjunto de bits de
mRequirements que describe los componentes que necesita. Además, almacena un conjunto de entidades
mManagedEntities que satisfacen estos requisitos. Repito, para poder implementar todas las operaciones en tiempo constante, necesitamos una forma de pasar de una entidad a su índice en
mManagedEntities . Para hacer esto, usaremos
std::unordered_map mEntityToManagedEntity llamado
mEntityToManagedEntity .
Así es como se ve la declaración del
System :
template<std::size_t ComponentCount, std::size_t SystemCount> class System { public: virtual ~System() = default; protected: template<typename ...Ts> void setRequirements(); const std::vector<Entity>& getManagedEntities() const; virtual void onManagedEntityAdded([[maybe_unused]] Entity entity); virtual void onManagedEntityRemoved([[maybe_unused]] Entity entity); private: friend EntityManager<ComponentCount, SystemCount>; std::bitset<ComponentCount> mRequirements; std::size_t mType; std::vector<Entity> mManagedEntities; std::unordered_map<Entity, Index> mEntityToManagedEntity; void setUp(std::size_t type); void onEntityUpdated(Entity entity, const std::bitset<ComponentCount>& components); void onEntityRemoved(Entity entity); void addEntity(Entity entity); void removeEntity(Entity entity); };
setRequirements usa una
expresión de convolución para establecer los valores de bit:
template<typename ...Ts> void setRequirements() { (mRequirements.set(Ts::type), ...); }
getManagedEntities es un captador que será utilizado por las clases generadas para acceder a las entidades que se procesan:
const std::vector<Entity>& getManagedEntities() const { return mManagedEntities; }
Devuelve una referencia constante para que las clases generadas no intenten modificar
mManagedEntities .
onManagedEntityAdded y
onManagedEntityRemoved están vacíos. Serán redefinidos más tarde. Se llamará a estos métodos al agregar una entidad a
mManagedEntities o al eliminarla.
Los siguientes métodos serán privados y accesibles solo desde
EntityManager , que se declara como una clase amigable.
setUp de la entidad
setUp a la
setUp para asignar una identificación al sistema. Luego puede usarlo para indexar matrices:
void setUp(std::size_t type) { mType = type; }
onEntityUpdated se llama cuando una entidad cambia, es decir al agregar o eliminar un componente. El sistema verifica si se cumplen los requisitos y si la entidad ya ha sido procesada. Si cumple con los requisitos y aún no se ha procesado, el sistema lo agrega. Sin embargo, si la entidad no cumple con los requisitos y ya ha sido procesada, el sistema la elimina. En todos los demás casos, el sistema no hace nada:
void onEntityUpdated(Entity entity, const std::bitset<ComponentCount>& components) { auto satisfied = (mRequirements & components) == mRequirements; auto managed = mEntityToManagedEntity.find(entity) != std::end(mEntityToManagedEntity); if (satisfied && !managed) addEntity(entity); else if (!satisfied && managed) removeEntity(entity); }
onEntityRemoved de la entidad llama a
onEntityRemoved cuando se elimina una entidad. Si el sistema procesó la entidad, la elimina:
void onEntityRemoved(Entity entity) { if (mEntityToManagedEntity.find(entity) != std::end(mEntityToManagedEntity)) removeEntity(entity); }
addEntity y
removeEntity son solo métodos auxiliares.
addEntity establece el enlace para ir desde la entidad agregada por su índice en
mManagedEntities , agrega la entidad y llama a
onManagedEntityAdded :
void addEntity(Entity entity) { mEntityToManagedEntity[entity] = static_cast<Index>(mManagedEntities.size()); mManagedEntities.emplace_back(entity); onManagedEntityAdded(entity); }
removeEntity llama primero a
onManagedEntityRemoved . Luego mueve la última entidad procesada en el índice de la que se está eliminando. Actualiza la referencia a la entidad movida. Al final, elimina la entidad que se eliminará de
mManagedEntities y
mEntityToManagedEntity :
void removeEntity(Entity entity) { onManagedEntityRemoved(entity); auto index = mEntityToManagedEntity[entity]; mEntityToManagedEntity[mManagedEntities.back()] = index; mEntityToManagedEntity.erase(entity); mManagedEntities[index] = mManagedEntities.back(); mManagedEntities.pop_back(); }
EntityManager
Toda lógica importante está en otras clases. Un gerente de entidad simplemente une todo.
Echemos un vistazo a su anuncio:
template<std::size_t ComponentCount, std::size_t SystemCount> class EntityManager { public: template<typename T> void registerComponent(); template<typename T, typename ...Args> T* createSystem(Args&& ...args); void reserve(std::size_t size); Entity createEntity(); void removeEntity(Entity entity); template<typename T> bool hasComponent(Entity entity) const; template<typename ...Ts> bool hasComponents(Entity entity) const; template<typename T> T& getComponent(Entity entity); template<typename T> const T& getComponent(Entity entity) const; template<typename ...Ts> std::tuple<Ts&...> getComponents(Entity entity); template<typename ...Ts> std::tuple<const Ts&...> getComponents(Entity entity) const; template<typename T, typename... Args> void addComponent(Entity entity, Args&&... args); template<typename T> void removeComponent(Entity entity); template<typename T> Entity getOwner(const T& component) const; private: std::array<std::unique_ptr<BaseComponentContainer>, ComponentCount> mComponentContainers; EntityContainer<ComponentCount, SystemCount> mEntities; std::vector<std::unique_ptr<System<ComponentCount, SystemCount>>> mSystems; template<typename T> void checkComponentType() const; template<typename ...Ts> void checkComponentTypes() const; template<typename T> auto getComponentContainer(); template<typename T> auto getComponentContainer() const; };
La clase
EntityManager tiene tres variables miembro:
mComponentContainers , que almacena
std::unique_ptr a
BaseComponentContainer ,
mEntities , que es solo una instancia de
EntityContainer y
mSystems , que almacena punteros
unique_ptr a
System .
Una clase tiene muchos métodos, pero de hecho todos son muy simples.
Primero
getComponentContainer un vistazo a
getComponentContainer , que devuelve un puntero a un contenedor de componentes que procesa componentes de tipo
T :
template<typename T> auto getComponentContainer() { return static_cast<ComponentContainer<T, ComponentCount, SystemCount>*>(mComponentContainers[T::type].get()); }
Otra función auxiliar es
checkComponentType , que simplemente verifica que la identificación del tipo de componente esté por debajo del número máximo de componentes:
template<typename T> void checkComponentType() const { static_assert(T::type < ComponentCount); }
checkComponentTypes usa una expresión de convolución para realizar varios tipos de comprobaciones:
template<typename ...Ts> void checkComponentTypes() const { (checkComponentType<Ts>(), ...); }
registerComponent crea un nuevo contenedor de componentes del tipo especificado:
template<typename T> void registerComponent() { checkComponentType<T>(); mComponentContainers[T::type] = std::make_unique<ComponentContainer<T, ComponentCount, SystemCount>>( mEntities.getEntityToBitset()); }
createSystem crea un nuevo sistema del tipo especificado y establece su tipo:
template<typename T, typename ...Args> T* createSystem(Args&& ...args) { auto type = mSystems.size(); auto& system = mSystems.emplace_back(std::make_unique<T>(std::forward<Args>(args)...)); system->setUp(type); return static_cast<T*>(system.get()); }
El método de
reserve llama a los métodos de
reserve de los
EntityContainer ComponentContainer y
EntityContainer :
void reserve(std::size_t size) { for (auto i = std::size_t(0); i < ComponentCount; ++i) { if (mComponentContainers[i]) mComponentContainers[i]->reserve(size); } mEntities.reserve(size); }
El método
createEntity devuelve el resultado del método
EntityManager administrador de
EntityManager :
Entity createEntity() { return mEntities.create(); }
hasComponent usa un conjunto de bits de entidad para verificar rápidamente que esta entidad tiene un componente del tipo especificado:
template<typename T> bool hasComponent(Entity entity) const { checkComponentType<T>(); return mEntities.getBitset(entity)[T::type]; }
hasComponents usa una expresión de convolución para crear un conjunto de bits que denotan los componentes requeridos, y luego lo usa con un conjunto de bits de la entidad para verificar si la entidad tiene todos los componentes requeridos:
template<typename ...Ts> bool hasComponents(Entity entity) const { checkComponentTypes<Ts...>(); auto requirements = std::bitset<ComponentCount>(); (requirements.set(Ts::type), ...); return (requirements & mEntities.getBitset(entity)) == requirements; }
getComponent redirige la solicitud al contenedor de componentes requerido:
template<typename T> T& getComponent(Entity entity) { checkComponentType<T>(); return getComponentContainer<T>()->get(entity); }
getComponents devuelve una tupla de enlaces a los componentes solicitados. Para hacer esto, usa
std::tie y una expresión de convolución:
template<typename ...Ts> std::tuple<Ts&...> getComponents(Entity entity) { checkComponentTypes<Ts...>(); return std::tie(getComponentContainer<Ts>()->get(entity)...); }
addComponent y
removeComponent redirige la solicitud al contenedor de componentes requerido y luego llama al
onEntityUpdated sistema
onEntityUpdated :
template<typename T, typename... Args> void addComponent(Entity entity, Args&&... args) { checkComponentType<T>(); getComponentContainer<T>()->add(entity, std::forward<Args>(args)...);
Finalmente,
getOwner redirige la solicitud al componente contenedor requerido:
template<typename T> Entity getOwner(const T& component) const { checkComponentType<T>(); return getComponentContainer<T>()->getOwner(component); }
Esa fue mi primera implementación. Consta de solo 357 líneas de código. Todo el código se puede encontrar en este
hilo .
Perfiles y puntos de referencia
Puntos de referencia
¡Ahora es el momento de comparar mi primera implementación de ECS!
Aquí están los resultados:
¡La plantilla se escala lo suficientemente bien! El número de procesados por segundo es aproximadamente el mismo cuando se aumenta el número de entidades y se cambian los perfiles (A, AA y AAA).
Además, se escala bien con un aumento en el número de componentes en las entidades. Cuando iteramos a través de entidades con tres componentes, ocurren tres veces más lento que iterar a través de entidades con un componente. Esto se espera porque necesitamos obtener tres componentes.
La memoria caché falla
Para verificar la cantidad de errores de caché, ejecuté el ejemplo de
cachegrind tomado
de aquí .
Aquí está el resultado para 10,000 entidades:
==1652== D refs: 277,577,353 (254,775,159 rd + 22,802,194 wr)
==1652== D1 misses: 20,814,368 ( 20,759,914 rd + 54,454 wr)
==1652== LLd misses: 43,483 ( 7,847 rd + 35,636 wr)
==1652== D1 miss rate: 7.5% ( 8.1% + 0.2% )
==1652== LLd miss rate: 0.0% ( 0.0% + 0.2% )Aquí está el resultado para 100,000 entidades:
==1738== D refs: 2,762,879,670 (2,539,368,564 rd + 223,511,106 wr)
==1738== D1 misses: 207,415,181 ( 206,902,072 rd + 513,109 wr)
==1738== LLd misses: 207,274,328 ( 206,789,289 rd + 485,039 wr)
==1738== D1 miss rate: 7.5% ( 8.1% + 0.2% )
==1738== LLd miss rate: 7.5% ( 8.1% + 0.2% )Los resultados son bastante buenos. Es un poco extraño por qué hay tantas fallas de LLd en 100,000 entidades.
Perfilado
Para comprender qué partes de la implementación actual toman más tiempo, perfilé el ejemplo con
gprof .
Aquí está el resultado:
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ms/call ms/call name
57.45 1.16 1.16 200300000 0.00 0.00 std::__detail::_Map_base<unsigned int, std::pair<unsigned int const, unsigned int>, std::allocator<std::pair<unsigned int const, unsigned int> >, std::__detail::_Select1st, std::equal_to<unsigned int>, std::hash<unsigned int>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<false, false, true>, true>::operator[](unsigned int const&)
19.31 1.55 0.39 main
16.34 1.88 0.33 200500000 0.00 0.00 std::_Hashtable<unsigned int, std::pair<unsigned int const, unsigned int>, std::allocator<std::pair<unsigned int const, unsigned int> >, std::__detail::_Select1st, std::equal_to<unsigned int>, std::hash<unsigned int>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<false, false, true> >::_M_find_before_node(unsigned long, unsigned int const&, unsigned long) const
3.96 1.96 0.08 300000 0.00 0.00 std::_Hashtable<unsigned int, std::pair<unsigned int const, unsigned int>, std::allocator<std::pair<unsigned int const, unsigned int> >, std::__detail::_Select1st, std::equal_to<unsigned int>, std::hash<unsigned int>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<false, false, true> >::_M_insert_unique_node(unsigned long, unsigned long, std::__detail::_Hash_node<std::pair<unsigned int const, unsigned int>, false>*)
2.48 2.01 0.05 300000 0.00 0.00 unsigned int& std::vector<unsigned int, std::allocator<unsigned int> >::emplace_back<unsigned int&>(unsigned int&)
0.50 2.02 0.01 3 3.33 3.33 std::_Hashtable<unsigned int, std::pair<unsigned int const, unsigned int>, std::allocator<std::pair<unsigned int const, unsigned int> >, std::__detail::_Select1st, std::equal_to<unsigned int>, std::hash<unsigned int>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<false, false, true> >::~_Hashtable()
0.00 2.02 0.00 200000 0.00 0.00 std::_Hashtable<unsigned int, std::pair<unsigned int const, unsigned int>, std::allocator<std::pair<unsigned int const, unsigned int> >, std::__detail::_Select1st, std::equal_to<unsigned int>, std::hash<unsigned int>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<false, false, true> >::find(unsigned int const&)Los resultados pueden estar un poco distorsionados porque compilé con el indicador
-O1 que gprof
-O1 algo significativo. Parece que cuando se aumenta el nivel de optimización, el compilador comienza a incrustar todo agresivamente y gprof no dice casi nada.
Según gprof, el cuello de botella obvio en esta implementación es
std::unordered_map . Si queremos optimizarlo, entonces vale la pena intentar deshacerse de ellos.
Comparación con std::map
Sentí curiosidad por la diferencia en el rendimiento entre std::unordered_mapy std::map, así que reemplacé todo en el código std::unordered_mapcon std::map. Esta implementación está disponible aquí.Aquí están los resultados de referencia:Podemos ver que esta vez la implementación no escala bien con un aumento en el número de entidades. E incluso con 1000 entidades, es el doble de lento en iteraciones que la versión c std::unordered_map.Conclusión
Hemos creado una biblioteca simple pero ya práctica de la plantilla de entidad-componente-sistema. En el futuro, lo utilizaremos como base para mejoras y optimizaciones.En la siguiente parte, mostraremos cómo aumentar la productividad reemplazando std::unordered_mapcon std::vector. Además, mostraremos cómo asignar automáticamente tipos de identificación a los componentes.Reemplazar std :: unordered_map con std :: vector
Como vimos, std::unordered_mapfueron un cuello de botella en nuestra implementación. Por lo tanto, en lugar de std::unordered_mapusar en mEntityToComponentfor ComponentContainery in mEntityToManagedEntityfor Systemvectors std::vector.Cambios
Los cambios serán muy simples, puedes verlos aquí .Las únicas mentiras sutileza en el hecho de que vectoren mEntityToComponenty mEntityToManagedEntityhan sido durante mucho tiempo suficiente para indexar cualquier entidad. Para hacer esto de manera sencilla, decidí almacenarlos vectoren EntityContainer, en el que sabemos que la máxima entidad ID. Luego paso los vectores a los vectorcontenedores de componentes por referencia o puntero en el administrador de entidades.El código modificado se puede encontrar en este hilo .Resultados
Veamos cómo funciona esta versión mejor que la anterior:Como puede ver, crear y eliminar con una gran cantidad de componentes y sistemas se ha vuelto un pocomás lento.Sin embargo, la iteración se ha vuelto mucho más rápida, ¡casi diez veces! Y se escala muy bien. Esta aceleración supera en gran medida la desaceleración de la creación y eliminación. Y esto es lógico: las iteraciones de la entidad ocurrirán muchas veces, pero se crea y elimina solo una vez.Ahora veamos si esto redujo el número de errores de caché.Aquí está el resultado de cachegrind con 10,000 entidades: Y aquí está el resultado de 100,000 entidades: Vemos que esta versión crea aproximadamente tres veces menos enlaces y cuatro veces menos errores de caché.==1374== D refs: 94,563,949 (72,082,880 rd + 22,481,069 wr)
==1374== D1 misses: 4,813,780 ( 4,417,702 rd + 396,078 wr)
==1374== LLd misses: 378,905 ( 9,626 rd + 369,279 wr)
==1374== D1 miss rate: 5.1% ( 6.1% + 1.8% )
==1374== LLd miss rate: 0.4% ( 0.0% + 1.6% )==1307== D refs: 938,405,796 (715,424,940 rd + 222,980,856 wr)
==1307== D1 misses: 51,034,738 ( 44,045,090 rd + 6,989,648 wr)
==1307== LLd misses: 5,866,508 ( 1,997,948 rd + 3,868,560 wr)
==1307== D1 miss rate: 5.4% ( 6.2% + 3.1% )
==1307== LLd miss rate: 0.6% ( 0.3% + 1.7% )Tipos automáticos
La última mejora de la que hablaré es la generación automática de identificadores de tipo de componente.Cambios
Todos los cambios para implementar la generación automática de tipos de identificación se pueden encontrar aquí .Para poder asignar una identificación única a cada tipo de componente, debe usar CRTP y una función con un contador estático: template<typename T> class Component { public: static const std::size_t type; }; std::size_t generateComponentType() { static auto counter = std::size_t(0); return counter++; } template<typename T> const std::size_t Component<T>::type = generateComponentType();
Puede notar que la identificación de tipo ahora se genera en tiempo de ejecución y se conocía anteriormente en tiempo de compilación.El código después de los cambios se puede encontrar en este hilo .Resultados
Para probar el rendimiento de esta versión, realicé puntos de referencia:Para la creación y eliminación, los resultados se mantuvieron aproximadamente igual. Sin embargo, puede ver que la iteración se ha vuelto un poco más lenta, alrededor del 10%.Esta ralentización puede explicarse por el hecho de que el compilador solía conocer los identificadores de tipo en tiempo de compilación, lo que significa que podría optimizar mejor el código.La asignación manual de tipos de identificación es un poco incómoda y puede provocar errores. Por lo tanto, incluso si reducimos un poco el rendimiento, sigue siendo una mejora en la usabilidad de nuestra biblioteca ECS.Ideas para mejoras adicionales
Antes de concluir este artículo, me gustaría compartir con ustedes ideas para otras mejoras. Hasta ahora no los he implementado, pero tal vez lo haré en el futuro.Número dinámico de componentes y sistemas.
Es inconveniente indicar de antemano el número máximo de componentes y sistemas en forma de parámetros de plantilla. Creo que va a ser posible reemplazar std::arrayen EntityManagerel std::vectorsin una fuerte degradación del rendimiento.Sin embargo, std::bitsetrequiere conocer el número de bits en tiempo de compilación. Aunque creo que corregir este problema sustituyendo std::vector<bitset<ComponentCount>>en EntityContainerel std::vector<char>y liberar un número suficiente de bytes para representar los conjuntos de bits de todas las entidades. Luego implementamos una clase liviana BitsetViewque recibe en la entrada un par de punteros al principio y al final del conjunto de bits, y luego realizamos todas las operaciones necesarias con std::bitseteste rango de memoria.Otra idea: ya no use conjuntos de bits y solo verifique mEntityToComponentsi la entidad tiene componentes.Iteración de componentes simplificada
Por el momento, si el sistema quiere recorrer iterativamente los componentes de las entidades que procesa, debemos hacerlo así: for (const auto& entity : getManagedEntities()) { auto [position, velocity] = mEntityManager.getComponents<Position, Velocity>(entity); ... }
Sería más bonito y sencillo si pudiéramos hacer algo como esto: for (auto& [position, velocity] : mEntityManager.getComponents<Position, Velocity>(mManagedEntities)) { ... }
Será más fácil implementar esto con la ayuda de la biblioteca de rangosstd::view::transform en C ++ 20 . Lamentablemente, todavía no está allí. Podría usar la biblioteca de rango de Eric Nibler, pero no quiero agregar dependencias. La solución podría ser implementar una clase que recibiría los tipos de componentes que deben recibirse como parámetros de plantilla, y una referencia de entidad como parámetro constructor . Entonces habríamos tenido sólo para darse cuenta , y el tipo de iterador para lograr el comportamiento deseado. No es muy difícil, pero toma un poco de tiempo escribir.EntityRangeViewstd::vectorbeginendOptimización de gestión de eventos
En la implementación actual, al agregar o eliminar un componente de una entidad, llamamos a onEntityUpdatedtodos los sistemas. Esto es un poco ineficiente porque muchos sistemas no están interesados en el tipo de componente que se acaba de cambiar.Para minimizar el daño, podemos almacenar punteros a sistemas interesados en el tipo especificado de componentes en la estructura de datos, por ejemplo std::array<std::vector<System<ComponentCount, SystemCount>>, ComponentCount>. Luego, al agregar o eliminar un componente, simplemente llamaríamos al método de los onEntityUpdatedsistemas interesados en este componente.Subconjuntos de entidades gestionadas por el gestor de entidades en lugar de sistemas
Mi última idea conduciría a cambios más extensos en la estructura de la biblioteca.En lugar de sistemas que administran sus conjuntos de entidades, un administrador de entidades haría esto. La ventaja de tal esquema es que si dos sistemas están interesados en un conjunto de componentes, no duplicamos un subconjunto de entidades que satisfacen estos requisitos.Los sistemas simplemente podrían declarar sus requisitos a un gerente de entidad. Luego, el administrador de la entidad almacenaría todos los diferentes subconjuntos de entidades. Finalmente, los sistemas consultarían entidades usando una sintaxis similar: for (const auto& entity : mEntityManager.getEntitiesWith<Position, Velocity>()) { ... }
Conclusión
Hasta ahora, este es el final de un artículo sobre mi implementación de la entidad-componente-sistema. Si hago otras mejoras, podría estar escribiendo nuevos artículos en el futuro.La implementación descrita en el artículo es bastante simple: consta de menos de 500 líneas de código y también tiene un buen rendimiento. Todas las transacciones se realizan por tiempo constante (amortizado). Además, en la práctica, utiliza de manera óptima el caché y recibe e itera entidades muy rápidamente.Espero que este artículo haya sido interesante o incluso útil para ti.Lectura adicional
Aquí hay un par de recursos útiles para un estudio más profundo del patrón de entidad-componente-sistema: