Nesta semana, comecei a trabalhar no meu mecanismo do Vagabond e comecei a implementar o modelo de entidade-componente-sistema .

Neste artigo, quero falar sobre minha implementação, disponível gratuitamente no GitHub . Mas, em vez de simplesmente comentar o código, quero explicar como sua estrutura foi projetada. Portanto, começarei com a primeira implementação que escrevi, analisarei seus pontos fortes e fracos e mostrarei como a aprimorei. No final, listarei uma lista de aspectos que também podem ser aprimorados.

1. Introdução

Motivação

Não falarei sobre os benefícios do ECS sobre a abordagem orientada a objetos, porque muitas pessoas antes de mim fizeram isso bem. Scott Bilas foi um dos primeiros a falar sobre ECS no GDC 2002 . Outras introduções notáveis ​​ao tópico incluem Evolve Your Hierarchy, de Mike West, e o capítulo Components, do impressionante livro Game Programming Patterns de Robert Nistrom.

Em resumo, direi que a tarefa do ECS é criar uma abordagem orientada a dados para entidades de jogos e uma separação conveniente de dados e lógica. As entidades são compostas de componentes que contêm dados. E sistemas contendo lógica processam esses componentes.

Se você entrar em detalhes, em vez de herança , a composição é usada no ECS. Além disso, essa abordagem orientada a dados faz melhor uso do cache, o que significa que ele atinge excelente desempenho.

Exemplos

Antes de nos aprofundarmos no código, eu gostaria de mostrar o que vamos criar.

A atribuição de componentes é muito simples:

struct Position : public Component<Position> { float x; float y; }; struct Velocity : public Component<Velocity> { float x; float y; }; 

Como você pode ver, usaremos o modelo CRTP .

Então, por razões técnicas, que explicarei mais adiante, precisamos corrigir o número de componentes e o número de sistemas:

 constexpr auto ComponentCount = 32; constexpr auto SystemCount = 8; 

Em seguida, você pode especificar um sistema que pegue todas as entidades que possuem os dois componentes e atualize suas posições:

 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; }; 

O sistema simplesmente usa o método setRequirements para setRequirements seus componentes de setRequirements . Em seguida, no método de update , ele pode chamar getManagedEntities para percorrer iterativamente todas as entidades que atendem aos requisitos.

Por fim, vamos criar um gerenciador de entidades, registrar os componentes, criar um sistema e várias entidades e atualizar suas posições usando o 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); 

Benchmarks

Não pretendo criar a melhor biblioteca ECS. Eu só queria escrever isso sozinho. Além disso, trabalhei nisso por apenas uma semana.

No entanto, esse não é um motivo para criar algo completamente ineficaz. Então, vamos instalar os benchmarks:

• O primeiro criará entidades;
• O segundo usará o sistema para atravessar iterativamente entidades;
• Este último criará e destruirá entidades;

Os parâmetros de todos esses benchmarks são o número de entidades, o número de componentes para cada entidade, o número máximo de componentes e o número máximo de sistemas. Dessa maneira, podemos ver quão bem nossa implementação é escalada. Em particular, mostrarei os resultados para três perfis diferentes:

• Perfil A: 32 componentes e 16 sistemas;
• Perfil AA: 128 componentes e 32 sistemas;
• Perfil AAA: 512 componentes e 64 sistemas.

Apesar de esses benchmarks nos darem uma idéia da qualidade da implementação, eles são bastante simples. Por exemplo, nesses benchmarks, usamos apenas entidades homogêneas e seus componentes são pequenos.

Implementação

Essence

Na minha implementação, uma entidade é apenas um ID:

 using Entity = uint32_t; 

Além disso, em Entity.h , também definiremos um Index alias, que será útil mais tarde:

 using Index = uint32_t; static constexpr auto InvalidIndex = std::numeric_limits<Index>::max(); 

Decidi usar o uint32_t vez do tipo de 64 bits ou std::size_t para economizar espaço e melhorar a otimização do cache. Não perderemos tanto: é improvável que alguém tenha bilhões de entidades.

Componente

Agora vamos definir a classe base para os componentes:

 template<typename T, auto Type> class Component { public: static constexpr auto type = static_cast<std::size_t>(Type); }; 

A classe do modelo é muito simples, apenas armazena o ID do tipo, que usaremos posteriormente para indexar estruturas de dados pelo tipo de componentes.

O primeiro parâmetro do modelo é o tipo de componente. O segundo é o valor convertido em std::size_t , que servirá como o ID do tipo de componente.

Por exemplo, podemos definir o componente Position seguinte maneira:

 struct Positon : Component<Position, 0> { float x; float y; }; 

No entanto, uma enumeração pode ser mais conveniente:

 enum class ComponentType { Position }; struct Positon : Component<Position, ComponentType::Position> { float x; float y; }; 

No exemplo introdutório, existe apenas um parâmetro de modelo: não precisamos especificar o ID do tipo manualmente. Mais tarde, veremos como melhorar a estrutura e gerar identificadores de tipo automaticamente.

EntityContainer

A classe EntityContainer será responsável por gerenciar entidades e std::bitset para cada uma delas. Este conjunto de bits indicará os componentes que a entidade possui.

Como usaremos entidades para indexar contêineres, e em particular std::vector , precisamos que o ID seja o menor possível e ocupe menos memória. Portanto, reutilizaremos o ID das entidades destruídas. Para isso, o ID gratuito será armazenado em um contêiner chamado mFreeEntities .

Aqui está a 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; }; 

Vamos ver como os métodos são implementados.

getEntityToBitset e getBitset são os pequenos getters comuns:

 std::vector<std::bitset<ComponentCount>>& getEntityToBitset() { return mEntityToBitset; } const std::bitset<ComponentCount>& getBitset(Entity entity) const { return mEntityToBitset[entity]; } 

O método create é mais interessante:

 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; } 

Se houver uma entidade livre, ele a reutiliza. Caso contrário, o método cria uma nova entidade.

O método remove simplesmente adiciona a entidade a ser removida no mFreeEntities :

 void remove(Entity entity) { mFreeEntities.push_back(entity); } 

O último método é reserve . Sua tarefa é reservar memória para vários contêineres. Como sabemos, alocar memória é uma operação cara, portanto, se conhecermos aproximadamente o número de entidades futuras no jogo, a memória de reserva acelerará o trabalho:

 void reserve(std::size_t size) { mFreeEntities.resize(size); std::iota(std::begin(mFreeEntities), std::end(mFreeEntities), 0); mEntityToBitset.resize(size); } 

Além de um simples backup de memória, ele também preenche o mFreeEntities .

ComponentContainer

A classe ComponentContainer será responsável por armazenar todos os componentes do tipo especificado.

Na minha arquitetura, todos os componentes de um determinado tipo são armazenados juntos. Ou seja, existe uma matriz grande para cada tipo de componente, chamada mComponents .

Além disso, para poder adicionar, receber ou remover um componente de uma entidade em tempo constante, precisamos de uma maneira de passar de uma entidade para um componente e de componente para entidade. Para fazer isso, precisamos de mais duas estruturas de dados chamadas mComponentToEntity e mEntityToComponent .

Aqui está a declaração 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; }; 

Você pode ver que ele herda do BaseComponentContainer , que é definido assim:

 class BaseComponentContainer { public: virtual ~BaseComponentContainer() = default; virtual void reserve(std::size_t size) = 0; virtual bool tryRemove(Entity entity) = 0; }; 

O único objetivo dessa classe base é poder armazenar todas as instâncias do ComponentContainer em um contêiner.

Vamos agora olhar para a definição de métodos.

Primeiro, considere o construtor: ele obtém uma referência a um contêiner contendo conjuntos de bits de entidade. Esta classe a utilizará para verificar a presença de um componente em uma entidade e atualizar o conjunto de bits de uma entidade ao adicionar ou remover um componente:

 ComponentContainer(std::vector<std::bitset<ComponentCount>>& entityToBitset) : mEntityToBitset(entityToBitset) { } 

O método get é simples, basta usar mEntityToComponent para encontrar o índice de um componente de entidade em mComponents :

 T& get(Entity entity) { return mComponents[mEntityToComponent[entity]]; } 

O método add usa seus argumentos para inserir um novo componente no final de mComponents e, em seguida, prepara os links para ir de entidade para componente e de componente para entidade. No final, ele define o bit do conjunto de bits da entity que corresponde ao componente como 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; } 

O método remove define o componente de bit correspondente como false e, em seguida, move o último componente mComponents no índice daquele que queremos remover. Ele atualiza os links para o componente que acabamos de mover e remove um dos componentes que queremos destruir:

 void remove(Entity entity) { mEntityToBitset[entity][T::type] = false; auto index = mEntityToComponent[entity]; // Update mComponents mComponents[index] = std::move(mComponents.back()); mComponents.pop_back(); // Update mEntityToComponent mEntityToComponent[mComponentToEntity.back()] = index; mEntityToComponent.erase(entity); // Update mComponentToEntity mComponentToEntity[index] = mComponentToEntity.back(); mComponentToEntity.pop_back(); } 

Podemos realizar movimentos em tempo constante movendo o último componente no índice que queremos destruir. De fato, basta remover o último componente, o que pode ser feito em std::vector em tempo constante.

O método tryRemove verifica se uma entidade possui um componente antes de tentar removê-lo:

 virtual bool tryRemove(Entity entity) override { if (mEntityToBitset[entity][T::type]) { remove(entity); return true; } return false; } 

O método getOwner retorna a entidade que possui o componente, para isso usa aritmética de ponteiro e mComponentToEntity :

 Entity getOwner(const T& component) const { auto begin = mComponents.data(); auto index = static_cast<std::size_t>(&component - begin); return mComponentToEntity[index]; } 

O último método é reserve , ele tem o mesmo objetivo que o método semelhante no EntityContainer :

 virtual void reserve(std::size_t size) override { mComponents.reserve(size); mComponentToEntity.reserve(size); mEntityToComponent.reserve(size); } 

O sistema

Agora vamos olhar para a classe System .

Cada sistema possui um conjunto de bits mRequirements que descreve os componentes necessários. Além disso, ele armazena um conjunto de entidades mManagedEntities que atendem a esses requisitos. Repito, para poder implementar todas as operações em tempo constante, precisamos de uma maneira de passar de uma entidade para seu índice em mManagedEntities . Para fazer isso, usaremos std::unordered_map chamado mEntityToManagedEntity .

Aqui está a aparência da declaração do 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 uma expressão de convolução para definir os valores de bits:

 template<typename ...Ts> void setRequirements() { (mRequirements.set(Ts::type), ...); } 

getManagedEntities é um getter que será usado pelas classes geradas para acessar as entidades que estão sendo processadas:

 const std::vector<Entity>& getManagedEntities() const { return mManagedEntities; } 

Ele retorna uma referência constante para que as classes geradas não tentem modificar mManagedEntities .

onManagedEntityAdded e onManagedEntityRemoved estão vazios. Eles serão redefinidos mais tarde. Esses métodos serão chamados ao adicionar uma entidade a mManagedEntities ou excluí-la.

Os métodos a seguir serão particulares e acessíveis apenas no EntityManager , declarado como uma classe amigável.

setUp será chamado pelo gerente da entidade para atribuir um ID ao sistema. Em seguida, ele pode ser usado para indexar matrizes:

 void setUp(std::size_t type) { mType = type; } 

onEntityUpdated é chamado quando uma entidade muda, ou seja, ao adicionar ou remover um componente. O sistema verifica se os requisitos foram atendidos e se a entidade já foi processada. Se ele atender aos requisitos e ainda não tiver sido processado, o sistema o adicionará. No entanto, se a entidade não atender aos requisitos e já tiver sido processada, o sistema a excluirá. Em todos os outros casos, o sistema não faz 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 é chamado pelo gerente da entidade quando uma entidade é excluída. Se a entidade foi processada pelo sistema, ela a exclui:

 void onEntityRemoved(Entity entity) { if (mEntityToManagedEntity.find(entity) != std::end(mEntityToManagedEntity)) removeEntity(entity); } 

removeEntity e removeEntity são apenas métodos auxiliares.

addEntity define o link para ir da entidade adicionada pelo seu índice em mManagedEntities , adiciona a entidade e chama onManagedEntityAdded :

 void addEntity(Entity entity) { mEntityToManagedEntity[entity] = static_cast<Index>(mManagedEntities.size()); mManagedEntities.emplace_back(entity); onManagedEntityAdded(entity); } 

removeEntity chama primeiro onManagedEntityRemoved . Em seguida, move a última entidade processada no índice da que está sendo excluída. Atualiza a referência para a entidade movida. No final, ele exclui a entidade a ser excluída de mManagedEntities e 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á em outras classes. Um gerente de entidade simplesmente une tudo.

Vamos dar uma olhada no anúncio dele:

 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; }; 

A classe EntityManager possui três variáveis ​​de membro: mComponentContainers , que armazena std::unique_ptr para BaseComponentContainer , mEntities , que é apenas uma instância do EntityContainer e mSystems , que armazena ponteiros unique_ptr no System .

Uma classe tem muitos métodos, mas na verdade são todos muito simples.

Vamos primeiro dar uma olhada no getComponentContainer , que retorna um ponteiro para um contêiner de componente que processa componentes do tipo T :

 template<typename T> auto getComponentContainer() { return static_cast<ComponentContainer<T, ComponentCount, SystemCount>*>(mComponentContainers[T::type].get()); } 

Outra função auxiliar é checkComponentType , que simplesmente verifica se o ID do tipo de componente está abaixo do número máximo de componentes:

 template<typename T> void checkComponentType() const { static_assert(T::type < ComponentCount); } 

checkComponentTypes usa uma expressão de convolução para executar vários tipos de verificações:

 template<typename ...Ts> void checkComponentTypes() const { (checkComponentType<Ts>(), ...); } 

registerComponent cria um novo contêiner de componentes do tipo especificado:

 template<typename T> void registerComponent() { checkComponentType<T>(); mComponentContainers[T::type] = std::make_unique<ComponentContainer<T, ComponentCount, SystemCount>>( mEntities.getEntityToBitset()); } 

createSystem cria um novo sistema do tipo especificado e define seu 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()); } 

O método de reserve chama os métodos de reserve dos EntityContainer ComponentContainer e 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); } 

O método createEntity retorna o resultado do método create do gerenciador do EntityManager :

 Entity createEntity() { return mEntities.create(); } 

hasComponent usa um conjunto de bits de entidade para verificar rapidamente se essa entidade possui um componente do tipo especificado:

 template<typename T> bool hasComponent(Entity entity) const { checkComponentType<T>(); return mEntities.getBitset(entity)[T::type]; } 

hasComponents usa uma expressão de convolução para criar um conjunto de bits que denota os componentes necessários e, em seguida, usa-o com um conjunto de bits da entidade para verificar se a entidade possui todos os componentes necessários:

 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 redireciona a solicitação para o contêiner de componente necessário:

 template<typename T> T& getComponent(Entity entity) { checkComponentType<T>(); return getComponentContainer<T>()->get(entity); } 

getComponents retorna uma tupla de links para os componentes solicitados. Para fazer isso, ele usa std::tie e uma expressão de convolução:

 template<typename ...Ts> std::tuple<Ts&...> getComponents(Entity entity) { checkComponentTypes<Ts...>(); return std::tie(getComponentContainer<Ts>()->get(entity)...); } 

addComponent e removeComponent redirecionam a solicitação para o contêiner de componente necessário e, em seguida, chame o onEntityUpdated sistema onEntityUpdated :

 template<typename T, typename... Args> void addComponent(Entity entity, Args&&... args) { checkComponentType<T>(); getComponentContainer<T>()->add(entity, std::forward<Args>(args)...); // Send message to systems const auto& bitset = mEntities.getBitset(entity); for (auto& system : mSystems) system->onEntityUpdated(entity, bitset); } template<typename T> void removeComponent(Entity entity) { checkComponentType<T>(); getComponentContainer<T>()->remove(entity); // Send message to systems const auto& bitset = mEntities.getBitset(entity); for (auto& system : mSystems) system->onEntityUpdated(entity, bitset); } 

Por fim, getOwner redireciona a solicitação para o componente de contêiner necessário:

 template<typename T> Entity getOwner(const T& component) const { checkComponentType<T>(); return getComponentContainer<T>()->getOwner(component); } 

Essa foi a minha primeira implementação. Consiste em apenas 357 linhas de código. Todo o código pode ser encontrado neste segmento .

Perfil e benchmarks

Benchmarks

Agora é a hora de comparar minha primeira implementação do ECS!

Aqui estão os resultados:




O modelo escala bem o suficiente! O número de processados ​​por segundo é aproximadamente o mesmo ao aumentar o número de entidades e alterar perfis (A, AA e AAA).

Além disso, ele se adapta bem a um aumento no número de componentes nas entidades. Quando iteramos através de entidades com três componentes, eles ocorrem três vezes mais devagar do que através de entidades com um componente. Isso é esperado porque precisamos obter três componentes.

Falhas no cache

Para verificar o número de falhas de cache, executei o exemplo de cachegrind retirado daqui .

Aqui está o 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% )

Aqui está o 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% )

Os resultados são muito bons. É um pouco estranho o porquê de tantas falhas de LLd em 100.000 entidades.

Criação de perfil

Para entender quais partes da implementação atual demoram mais, criei o perfil do exemplo com o gprof .

Aqui está o 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&)

Os resultados podem estar um pouco distorcidos porque compilei com o sinalizador -O1 que o gprof -O1 algo significativo. Parece que quando o nível de otimização aumenta, o compilador começa a incorporar tudo agressivamente e o gprof não diz quase nada.

De acordo com o gprof, o gargalo óbvio nessa implementação é std::unordered_map . Se queremos otimizá-lo, vale a pena tentar nos livrar deles.

Comparação com std::map

Fiquei curioso sobre a diferença de desempenho entre std::unordered_mape std::map, portanto, substituí tudo no código std::unordered_mappor std::map. Esta implementação está disponível aqui, e

aqui estão os resultados do benchmark:




Podemos ver que, desta vez, a implementação não é bem dimensionada com um aumento no número de entidades. E mesmo com 1000 entidades, é duas vezes mais lento nas iterações que a versão c std::unordered_map.

Conclusão

Criamos uma biblioteca simples, mas já prática, do modelo de entidade-componente-sistema. No futuro, vamos usá-lo como base para melhorias e otimizações.

Na próxima parte, mostraremos como aumentar a produtividade substituindo std::unordered_mappor std::vector. Além disso, mostraremos como atribuir automaticamente os tipos de identificação aos componentes.

Substituindo std :: unordered_map por std :: vector

Como vimos, eles std::unordered_maperam um gargalo em nossa implementação. Portanto, em vez de std::unordered_mapusarmos em mEntityToComponentfor ComponentContainere in mEntityToManagedEntitypara Systemvetores std::vector.

Alterações

As mudanças serão muito simples, você pode vê-las aqui .

As únicas mentiras sutileza no fato de que vectorem mEntityToComponente mEntityToManagedEntityter sido tempo suficiente para indexar qualquer entidade. Para fazer isso maneira simples, eu decidi armazenar estes vectorem EntityContainer, em que sabemos que a entidade máxima id. Depois passo os vetores para os vectorcontêineres do componente por referência ou ponteiro no gerenciador de entidades.

O código modificado pode ser encontrado neste segmento .

Resultados

Vamos verificar como esta versão funciona melhor que a anterior:




Como você pode ver, a criação e exclusão de um grande número de componentes e sistemas se tornou um pouco
mais lenta.

No entanto, a iteração se tornou muito mais rápida, quase dez vezes! E escala muito bem. Essa aceleração supera muito a desaceleração da criação e exclusão. E isso é lógico: as iterações da entidade ocorrerão muitas vezes, mas são criadas e excluídas apenas uma vez.

Agora vamos ver se isso reduziu o número de falhas de cache.

Aqui está a saída do cachegrind com 10.000 entidades: E aqui está a saída para 100.000 entidades: Vemos que esta versão cria cerca de três vezes menos links e quatro vezes menos perdas de cache.

==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

A última melhoria de que falarei é a geração automática de identificadores de tipo de componente.

Alterações

Todas as alterações para implementar a geração automática de tipos de ID podem ser encontradas aqui .

Pois, para poder atribuir um ID exclusivo a cada tipo de componente, você precisa usar o CRTP e uma função com um 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(); 

Você pode perceber que o ID do tipo agora é gerado em tempo de execução e era conhecido anteriormente em tempo de compilação.

O código após as alterações pode ser encontrado neste segmento .

Resultados

Para testar o desempenho desta versão, realizei benchmarks:




Para criação e exclusão, os resultados permaneceram aproximadamente os mesmos. No entanto, você pode ver que a iteração se tornou um pouco mais lenta, cerca de 10%.

Essa desaceleração pode ser explicada pelo fato de o compilador conhecer os identificadores de tipo no momento da compilação, o que significa que ele poderia otimizar melhor o código.

A atribuição manual de tipos de identificação é um pouco inconveniente e pode levar a erros. Portanto, mesmo que reduzamos um pouco o desempenho, ainda é uma melhoria na usabilidade da nossa biblioteca ECS.

Ideias para melhorias adicionais

Antes de concluir este artigo, gostaria de compartilhar com você idéias para outras melhorias. Até agora, eu não os implementei, mas talvez eu o faça no futuro.

Número dinâmico de componentes e sistemas

É inconveniente indicar antecipadamente o número máximo de componentes e sistemas na forma de parâmetros do modelo. Eu acho que vai ser possível substituir std::arrayem EntityManageron std::vectorsem uma degradação do desempenho forte.

No entanto, é std::bitsetnecessário conhecer o número de bits em tempo de compilação. Embora eu ache que corrigir este problema, substituindo std::vector<bitset<ComponentCount>>em EntityContaineron std::vector<char>e liberar um número suficiente de bytes para representar os conjuntos de bits de todas as entidades. Em seguida, implementamos uma classe leve BitsetViewque recebe na entrada um par de ponteiros para o início e o final do conjunto de bits e, em seguida, executamos todas as operações necessárias com std::bitsetesse intervalo de memória.

Outra idéia: não use mais conjuntos de bits e verifique apenas mEntityToComponentse a entidade possui componentes.

Iteração de componente simplificada

No momento, se o sistema quiser percorrer iterativamente os componentes das entidades que processa, precisamos fazer o seguinte:

 for (const auto& entity : getManagedEntities()) { auto [position, velocity] = mEntityManager.getComponents<Position, Velocity>(entity); ... } 

Seria mais bonito e mais simples se pudéssemos fazer algo assim:

 for (auto& [position, velocity] : mEntityManager.getComponents<Position, Velocity>(mManagedEntities)) { ... } 

Será mais fácil implementá-lo com a ajuda da biblioteca de intervalosstd::view::transform no C ++ 20 . Infelizmente, ainda não está lá. Eu poderia usar a biblioteca de intervalos de Eric Nibler, mas não quero adicionar dependências. A solução poderia ser implementar uma classe que recebesse os tipos de componentes que precisam ser recebidos como parâmetros de modelo e uma referência de entidade como parâmetro de construtor . Então teríamos apenas para perceber , e o tipo de iterador para obter o comportamento desejado. Não é muito difícil, mas consome um pouco de tempo para escrever.




EntityRangeViewstd::vectorbeginend

Otimização de gerenciamento de eventos

Na implementação atual, ao adicionar ou remover um componente de uma entidade, chamamos onEntityUpdatedtodos os sistemas. Isso é um pouco ineficiente porque muitos sistemas não estão interessados ​​no tipo de componente que acabou de ser alterado.

Para minimizar danos, podemos armazenar ponteiros para sistemas interessados ​​no tipo especificado de componentes na estrutura de dados, por exemplo std::array<std::vector<System<ComponentCount, SystemCount>>, ComponentCount>. Então, ao adicionar ou remover um componente, chamaríamos simplesmente o método de onEntityUpdatedsistemas interessados ​​nesse componente.

Subconjuntos de entidades gerenciadas pelo gerente da entidade em vez de sistemas

Minha última idéia levaria a mudanças mais extensas na estrutura da biblioteca.

Em vez de sistemas que gerenciam seus conjuntos de entidades, um gerente de entidade faria isso. A vantagem desse esquema é que, se dois sistemas estiverem interessados ​​em um conjunto de componentes, não duplicamos um subconjunto de entidades que atendem a esses requisitos.

Os sistemas poderiam simplesmente declarar seus requisitos a um gerente de entidade. Em seguida, o gerente da entidade armazenaria todos os diferentes subconjuntos de entidades. Por fim, os sistemas consultariam entidades usando uma sintaxe semelhante:

 for (const auto& entity : mEntityManager.getEntitiesWith<Position, Velocity>()) { ... } 

Conclusão

Até agora, este é o fim de um artigo sobre minha implementação do sistema de componentes de entidade. Se eu fizer outras melhorias, talvez eu esteja escrevendo novos artigos no futuro.

A implementação descrita no artigo é bastante simples: consiste em menos de 500 linhas de código e também possui bom desempenho. Todas as transações são realizadas por tempo constante (amortizado). Além disso, na prática, ele otimiza o uso do cache e recebe e repete muito rapidamente as entidades.

Espero que este artigo seja interessante ou até útil para você.

Leitura adicional

Aqui estão alguns recursos úteis para um estudo mais aprofundado do padrão de entidade-componente-sistema:

• Michelle Kayney, autora de entt , escreve uma série muito interessante de artigos sobre o sistema de entidade-componente chamado ECS .
• O Wiki do Entity Systems contém informações e links muito úteis.