Cette semaine, j'ai commencé à travailler sur mon moteur Vagabond et commencé à implémenter le modèle de système entité-composant .

Dans cet article, je veux parler de mon implémentation, qui est disponible gratuitement sur GitHub . Mais au lieu de simplement commenter le code, je veux expliquer comment sa structure a été conçue. Par conséquent, je vais commencer par la première implémentation que j'ai écrite, analyser ses forces et ses faiblesses, puis montrer comment je l'ai améliorée. À la fin, je vais énumérer une liste d'aspects qui peuvent également être améliorés.

Présentation

La motivation

Je ne parlerai pas des avantages d'ECS par rapport à l'approche orientée objet, car beaucoup de gens avant moi l'ont bien fait. Scott Bilas a été l'un des premiers à parler d'ECS au GDC 2002 . Parmi les autres introductions célèbres au sujet, mentionnons Evolve Your Hierarchy de Mike West et le chapitre Composants du superbe livre de Robert Nistrom intitulé Game Programming Patterns .

En bref, je dirai que la tâche d'ECS est de créer une approche orientée données des entités de jeu et une séparation pratique des données et de la logique. Les entités sont composées de composants contenant des données. Et les systèmes contenant la logique traitent ces composants.

Si vous entrez dans les détails, au lieu de l' héritage , la composition est utilisée dans ECS. De plus, cette approche orientée données permet une meilleure utilisation du cache, ce qui signifie qu'il atteint d'excellentes performances.

Des exemples

Avant de plonger dans le code, je voudrais vous montrer ce que nous allons concevoir.

L'affectation de composants est très simple:

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

Comme vous pouvez le voir, nous utiliserons le modèle CRTP .

Ensuite, pour des raisons techniques, que j'expliquerai plus tard, nous devons fixer le nombre de composants et le nombre de systèmes:

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

Ensuite, vous pouvez spécifier un système qui prendra toutes les entités qui ont les deux composants et mettra à jour leurs positions:

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

Le système utilise simplement la méthode setRequirements pour setRequirements ses composants d' setRequirements . Ensuite, dans la méthode de update , il peut appeler getManagedEntities pour parcourir itérativement toutes les entités qui satisfont aux exigences.

Enfin, créons un gestionnaire d'entités, enregistrons les composants, créons un système et plusieurs entités, puis mettons à jour leurs positions à l'aide du système:

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

Repères

Je ne prétendrai pas créer la meilleure bibliothèque ECS. Je voulais juste l'écrire moi-même. De plus, je n'y ai travaillé que pendant une semaine.

Cependant, ce n'est pas une raison pour créer quelque chose de complètement inefficace. Installons donc les benchmarks:

• Le premier créera des entités;
• Le second utilisera le système pour parcourir itérativement des entités;
• Ce dernier créera et détruira des entités;

Les paramètres de tous ces benchmarks sont le nombre d'entités, le nombre de composants pour chaque entité, le nombre maximum de composants et le nombre maximum de systèmes. De cette façon, nous pouvons voir à quel point notre implémentation évolue. En particulier, je montrerai les résultats pour trois profils différents:

• Profil A: 32 composants et 16 systèmes;
• Profil AA: 128 composants et 32 ​​systèmes;
• Profil AAA: 512 composants et 64 systèmes.

Bien que ces repères nous donnent une idée de la qualité de la mise en œuvre, ils sont assez simples. Par exemple, dans ces repères, nous n'utilisons que des entités homogènes et leurs composants sont petits.

Implémentation

Essence

Dans mon implémentation, une entité n'est qu'un identifiant:

 using Entity = uint32_t; 

De plus, dans Entity.h, nous définirons également un Index alias, qui sera utile plus tard:

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

J'ai décidé d'utiliser uint32_t au lieu du type 64 bits ou std::size_t pour économiser de l'espace et améliorer l'optimisation du cache. Nous ne perdrons pas tant: il est peu probable que quelqu'un ait des milliards d'entités.

Composant

Définissons maintenant la classe de base pour les composants:

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

La classe de modèle est très simple, elle stocke juste l'identifiant de type, que nous utiliserons plus tard pour indexer les structures de données par type de composants.

Le premier paramètre de modèle est le type de composant. La seconde est la valeur convertie en std::size_t , qui servira d'ID de type de composant.

Par exemple, nous pouvons définir le composant Position comme suit:

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

Cependant, une énumération peut être plus pratique:

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

Dans l'exemple d'introduction, il n'y a qu'un seul paramètre de modèle: nous n'avons pas besoin de spécifier l'ID de type manuellement. Plus tard, nous verrons comment améliorer la structure et générer automatiquement des identificateurs de type.

EntityContainer

La classe EntityContainer sera responsable de la gestion des entités et std::bitset pour chacune d'elles. Cet ensemble de bits indiquera les composants que l'entité possède.

Puisque nous utiliserons des entités pour indexer les conteneurs, et en particulier std::vector , nous avons besoin que l'id soit le plus petit possible et occupe moins de mémoire. Par conséquent, nous réutiliserons l'identifiant des entités détruites. Pour ce faire, l'id gratuit sera stocké dans un conteneur appelé mFreeEntities .

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

Voyons comment les méthodes sont implémentées.

getEntityToBitset et getBitset sont les petits getters habituels:

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

La méthode create est plus intéressante:

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

S'il existe une entité libre, il la réutilise. Sinon, la méthode crée une nouvelle entité.

La méthode remove ajoute simplement l'entité à supprimer dans mFreeEntities :

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

La dernière méthode est la reserve . Sa tâche consiste à réserver de la mémoire pour différents conteneurs. Comme nous le savons peut-être, l'allocation de mémoire est une opération coûteuse, donc si nous connaissons approximativement le nombre d'entités futures dans le jeu, alors réserver de la mémoire accélérera le travail:

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

En plus d'une simple sauvegarde de mémoire, il remplit également mFreeEntities .

ComponentContainer

La classe ComponentContainer sera responsable du stockage de tous les composants du type spécifié.

Dans mon architecture, tous les composants d'un type donné sont stockés ensemble. Autrement dit, il existe un grand tableau pour chaque type de composant, appelé mComponents .

De plus, afin de pouvoir ajouter, recevoir ou supprimer un composant d'une entité en temps constant, nous avons besoin d'un moyen de passer d'une entité à un composant et d'un composant à une autre. Pour ce faire, nous avons besoin de deux autres structures de données appelées mComponentToEntity et mEntityToComponent .

Voici la déclaration 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; }; 

Vous pouvez voir qu'il hérite de BaseComponentContainer , qui est défini comme ceci:

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

Le seul but de cette classe de base est de pouvoir stocker toutes les instances de ComponentContainer dans un conteneur.

Voyons maintenant la définition des méthodes.

Considérons d'abord le constructeur: il obtient une référence à un conteneur contenant des ensembles de bits d'entité. Cette classe l'utilisera pour vérifier la présence d'un composant dans une entité et pour mettre à jour l'ensemble de bits d'une entité lors de l'ajout ou de la suppression d'un composant:

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

La méthode get est simple, nous utilisons simplement mEntityToComponent pour trouver l'index d'un composant d'entité dans mComponents :

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

La méthode add utilise ses arguments pour insérer un nouveau composant à la fin de mComponents , puis elle prépare des liens pour passer d'entité en composant et de composant en entité. À la fin, il définit le bit de l' entity bits d' entity qui correspond au composant sur 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; } 

La méthode remove définit le composant binaire correspondant sur false , puis déplace le dernier composant mComponents à l'index de celui que nous voulons supprimer. Il met à jour les liens vers le composant que nous venons de déplacer et supprime l'un des composants que nous voulons détruire:

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

Nous pouvons effectuer un mouvement à temps constant en déplaçant le dernier composant à l'indice que nous voulons détruire. Et en fait, alors nous avons juste besoin de supprimer le dernier composant, ce qui peut être fait dans std::vector en temps constant.

La méthode tryRemove vérifie si une entité a un composant avant d'essayer de le supprimer:

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

La méthode getOwner renvoie l'entité propriétaire du composant, pour cela, elle utilise l'arithmétique du pointeur et mComponentToEntity :

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

La dernière méthode est reserve , elle a le même objectif que la méthode similaire dans EntityContainer :

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

Le système

Examinons maintenant la classe System .

Chaque système possède un ensemble de bits mRequirements qui décrit les composants dont il a besoin. En outre, il stocke un ensemble d'entités mManagedEntities qui satisfont à ces exigences. Je le répète, afin de pouvoir implémenter toutes les opérations en temps constant, nous avons besoin d'un moyen de passer d'une entité à son index dans mManagedEntities . Pour ce faire, nous utiliserons std::unordered_map mEntityToManagedEntity appelé mEntityToManagedEntity .

Voici à quoi ressemble la déclaration 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 utilise une expression de convolution pour définir les valeurs des bits:

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

getManagedEntities est un getter qui sera utilisé par les classes générées pour accéder aux entités en cours de traitement:

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

Il renvoie une référence constante afin que les classes générées n'essaient pas de modifier mManagedEntities .

onManagedEntityAdded et onManagedEntityRemoved sont vides. Ils seront redéfinis ultérieurement. Ces méthodes seront appelées lors de l'ajout d'une entité à mManagedEntities ou de sa suppression.

Les méthodes suivantes seront privées et accessibles uniquement depuis EntityManager , qui est déclaré comme une classe conviviale.

setUp sera appelé par le gestionnaire d'entités pour attribuer un identifiant au système. Ensuite, il peut l'utiliser pour indexer des tableaux:

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

onEntityUpdated est appelé lorsqu'une entité change, c'est-à-dire lors de l'ajout ou de la suppression d'un composant. Le système vérifie si les exigences sont satisfaites et si l'entité a déjà été traitée. S'il répond aux exigences et n'a pas encore été traité, le système l'ajoute. Cependant, si l'entité ne répond pas aux exigences et a déjà été traitée, le système la supprime. Dans tous les autres cas, le système ne fait rien:

 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 est appelé par le gestionnaire d'entités lorsqu'une entité est supprimée. Si l'entité a été traitée par le système, elle la supprime:

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

addEntity et removeEntity sont que des méthodes d'assistance.

addEntity définit le lien pour aller de l'entité ajoutée par son index dans mManagedEntities , ajoute l'entité et appelle onManagedEntityAdded :

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

removeEntity appelle d'abord onManagedEntityRemoved . Il déplace ensuite la dernière entité traitée à l'index de celle qui est supprimée. Il met à jour la référence à l'entité déplacée. Au final, il supprime l'entité à supprimer de mManagedEntities et 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

Toute logique importante se trouve dans d'autres classes. Un gestionnaire d'entité relie simplement tout ensemble.

Jetons un œil à son annonce:

 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 classe EntityManager a trois variables membres: mComponentContainers , qui stocke les std::unique_ptr vers BaseComponentContainer , mEntities , qui n'est qu'une instance de EntityContainer et mSystems , qui stocke les pointeurs unique_ptr vers System .

Une classe a de nombreuses méthodes, mais en fait, elles sont toutes très simples.

Jetons d'abord un œil à getComponentContainer , qui renvoie un pointeur sur un conteneur de composants qui traite les composants de type T :

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

Une autre fonction d'assistance est checkComponentType , qui vérifie simplement que l'ID du type de composant est inférieur au nombre maximal de composants:

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

checkComponentTypes utilise une expression de convolution pour effectuer plusieurs types de vérifications:

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

registerComponent crée un nouveau conteneur de composants du type spécifié:

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

createSystem crée un nouveau système du type spécifié et définit son type:

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

La méthode reserve appelle les méthodes EntityContainer ComponentContainer et 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); } 

La méthode createEntity renvoie le résultat de la méthode create du EntityManager :

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

hasComponent utilise un ensemble de bits d'entité pour vérifier rapidement que cette entité a un composant du type spécifié:

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

hasComponents utilise une expression de convolution pour créer un ensemble de bits indiquant les composants requis, puis l'utilise avec un ensemble de bits de l'entité pour vérifier si l'entité possède tous les composants requis:

 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 demande vers le conteneur de composants requis:

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

getComponents renvoie un tuple de liens vers les composants demandés. Pour ce faire, il utilise std::tie et une expression de convolution:

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

addComponent et removeComponent redirigent la demande vers le conteneur de composants requis, puis appelez la onEntityUpdated système 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); } 

Enfin, getOwner redirige la demande vers le composant conteneur requis:

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

C'était ma première implémentation. Il ne comprend que 357 lignes de code. Tout le code peut être trouvé dans ce fil .

Profilage et benchmarks

Repères

Il est maintenant temps de comparer ma première implémentation ECS!

Voici les résultats:




Le modèle évolue assez bien! Le nombre de traitements par seconde est à peu près le même lors de l'augmentation du nombre d'entités et de la modification des profils (A, AA et AAA).

De plus, il évolue bien avec une augmentation du nombre de composants dans les entités. Lorsque nous parcourons des entités à trois composants, ils se produisent trois fois plus lentement que nous parcourons des entités à un composant. Cela est attendu car nous devons obtenir trois composants.

Cache manque

Pour vérifier le nombre d' échecs de cache, j'ai exécuté l'exemple cachegrind pris à partir d'ici .

Voici le résultat pour 10 000 entités:

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

Voici le résultat pour 100 000 entités:

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

Les résultats sont plutôt bons. C'est juste un peu étrange pourquoi il y a tant de ratés LLd dans 100 000 entités.

Profilage

Pour comprendre quelles parties de l'implémentation actuelle prennent plus de temps, j'ai profilé l'exemple avec gprof .

Voici le résultat:

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&)

Les résultats peuvent être un peu déformés car j'ai compilé avec l'indicateur -O1 que gprof -O1 quelque chose de significatif. Il semble que lorsque le niveau d'optimisation est augmenté, le compilateur commence à tout intégrer de manière agressive et gprof ne dit presque rien.

Selon gprof, le goulot d'étranglement évident dans cette implémentation est std::unordered_map . Si nous voulons l'optimiser, cela vaut la peine d'essayer de s'en débarrasser.

Comparaison avec std::map

Je suis devenu curieux de la différence de performance entre std::unordered_mapet std::map, j'ai donc remplacé tout dans le code std::unordered_mappar std::map. Cette implémentation est disponible ici.

Voici les résultats de référence:




On voit que cette fois l'implémentation ne se déroule pas bien avec une augmentation du nombre d'entités. Et même avec 1000 entités, elle est deux fois plus lente en itérations que la version c std::unordered_map.

Conclusion

Nous avons créé une bibliothèque simple mais déjà pratique du modèle de système entité-composant. À l'avenir, nous l'utiliserons comme base pour des améliorations et des optimisations.

Dans la partie suivante, nous montrerons comment augmenter la productivité en remplaçant std::unordered_mappar std::vector. De plus, nous montrerons comment attribuer automatiquement des types d'ID aux composants.

Remplacement de std :: unordered_map par std :: vector

Comme nous l'avons vu, ils std::unordered_mapconstituaient un goulot d'étranglement dans notre mise en œuvre. Par conséquent, au lieu d' std::unordered_maputiliser des vecteurs mEntityToComponentfor ComponentContaineret in mEntityToManagedEntityfor .Systemstd::vector

Changements

Les changements seront très simples, vous pouvez les consulter ici .

La seule subtilité réside dans le fait que vectordans mEntityToComponentet mEntityToManagedEntityont été assez longtemps pour indexer toute entité. Pour ce faire de manière simple, j'ai décidé de les stocker vectordans EntityContainer, dans lequel nous connaissons l'id maximum de l'entité. Ensuite, je passe les vecteurs aux vectorconteneurs de composants par référence ou pointeur dans le gestionnaire d'entités.

Le code modifié peut être trouvé dans ce fil .

Résultats

Vérifions comment cette version fonctionne mieux que la précédente:




Comme vous pouvez le voir, la création et la suppression avec un grand nombre de composants et de systèmes est devenue un peu
plus lente.

Cependant, l'itération est devenue beaucoup plus rapide, près de dix fois! Et ça évolue très bien. Cette accélération l'emporte largement sur le ralentissement de la création et de la suppression. Et c'est logique: les itérations de l'entité se produiront plusieurs fois, mais elle n'est créée et supprimée qu'une seule fois.

Voyons maintenant si cela a réduit le nombre d'échecs de cache.

Voici la sortie de cachegrind avec 10 000 entités: Et voici la sortie pour 100 000 entités: Nous voyons que cette version crée environ trois fois moins de liens et quatre fois moins d'échecs 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% )

Types automatiques

La dernière amélioration dont je parlerai est la génération automatique d'identificateurs de type de composant.

Changements

Toutes les modifications pour l'implémentation de la génération automatique de types d'ID peuvent être trouvées ici .

Car, pour pouvoir attribuer un identifiant unique à chaque type de composant, vous devez utiliser CRTP et une fonction avec un compteur statique:

 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(); 

Vous remarquerez peut-être que l'ID de type est maintenant généré au moment de l'exécution et qu'il était auparavant connu au moment de la compilation.

Le code après les modifications peut être trouvé dans ce fil .

Résultats

Pour tester les performances de cette version, j'ai effectué des benchmarks:




Pour la création et la suppression, les résultats sont restés à peu près les mêmes. Cependant, vous pouvez voir que l'itération est devenue un peu plus lente, environ 10%.

Ce ralentissement peut s'expliquer par le fait que le compilateur connaissait les identificateurs de type au moment de la compilation, ce qui signifie qu'il pourrait mieux optimiser le code.

L'affectation manuelle des types d'identifiant est un peu gênante et peut entraîner des erreurs. Ainsi, même si nous réduisons un peu les performances, il s'agit tout de même d'une amélioration de l'utilisabilité de notre bibliothèque ECS.

Idées d'améliorations supplémentaires

Avant de conclure cet article, je voudrais partager avec vous des idées pour d'autres améliorations. Jusqu'à présent, je ne les ai pas mis en œuvre, mais je le ferai peut-être à l'avenir.

Nombre dynamique de composants et de systèmes

Il n'est pas commode d'indiquer à l'avance le nombre maximum de composants et de systèmes sous forme de paramètres de gabarit. Je pense qu'il sera possible de remplacer std::arraydans EntityManagerle std::vectorsans une forte dégradation des performances.

Cependant, cela std::bitsetnécessite de connaître le nombre de bits au moment de la compilation. Même si je pense corriger ce problème en remplaçant std::vector<bitset<ComponentCount>>dans EntityContainerle std::vector<char>et libérer un nombre suffisant d'octets pour représenter les ensembles de bits de toutes les entités. Ensuite, nous implémentons une classe légère BitsetViewqui reçoit en entrée une paire de pointeurs vers le début et la fin de l'ensemble de bits, puis effectuons toutes les opérations nécessaires avec std::bitsetdans cette plage de mémoire.

Autre idée: n'utilisez plus de jeux de bits et vérifiez simplement mEntityToComponentsi l'entité a des composants.

Itération simplifiée des composants

Pour le moment, si le système veut faire le tour itératif des composants des entités qu'il traite, nous devons le faire comme ceci:

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

Ce serait plus joli et plus simple si nous pouvions faire quelque chose comme ça:

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

Il sera plus facile de l'implémenter à l'aide de la bibliothèque de plagesstd::view::transform en C ++ 20 . Malheureusement, il n'est pas encore là. Je pourrais utiliser la bibliothèque de plages d'Eric Nibler, mais je ne veux pas ajouter de dépendances. La solution pourrait être d'implémenter une classe qui recevrait les types de composants qui doivent être reçus en tant que paramètres de modèle et une référence d' entité en tant que paramètre constructeur . Ensuite , nous aurions eu seulement à réaliser , et le type de iterator pour obtenir le comportement souhaité. Ce n'est pas très difficile, mais cela prend un peu de temps à écrire.




EntityRangeViewstd::vectorbeginend

Optimisation de la gestion des événements

Dans l'implémentation actuelle, lors de l'ajout ou de la suppression d'un composant d'une entité, nous appelons onEntityUpdatedtous les systèmes. C'est un peu inefficace car de nombreux systèmes ne sont pas intéressés par le type de composant qui vient d'être modifié.

Pour minimiser les dommages, nous pouvons stocker des pointeurs vers des systèmes intéressés par le type spécifié de composants dans la structure de données, par exemple std::array<std::vector<System<ComponentCount, SystemCount>>, ComponentCount>. Ensuite, lors de l'ajout ou de la suppression d'un composant, nous appellerions simplement la méthode des onEntityUpdatedsystèmes intéressés par ce composant.

Sous-ensembles d'entités gérées par le gestionnaire d'entités au lieu de systèmes

Ma dernière idée entraînerait des changements plus importants dans la structure de la bibliothèque.

Au lieu de systèmes qui gèrent leurs ensembles d'entités, un gestionnaire d'entité ferait cela. L'avantage d'un tel schéma est que si deux systèmes sont intéressés par le même ensemble de composants, nous ne dupliquons pas un sous-ensemble d'entités qui satisfont à ces exigences.

Les systèmes peuvent simplement déclarer leurs besoins à un responsable d'entité. Ensuite, le gestionnaire d'entités stockerait tous les différents sous-ensembles d'entités. Enfin, les systèmes interrogeraient les entités en utilisant une syntaxe similaire:

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

Conclusion

Jusqu'à présent, c'est la fin d'un article sur ma mise en œuvre du système entité-composant. Si j'apporte d'autres améliorations, j'écrirai peut-être de nouveaux articles à l'avenir.

L'implémentation décrite dans l'article est assez simple: elle se compose de moins de 500 lignes de code et présente également de bonnes performances. Toutes les transactions sont réalisées pour un temps constant (amorti). De plus, en pratique, il utilise de manière optimale le cache et reçoit et itère très rapidement les entités.

J'espère que cet article vous a été intéressant ou même utile.

Lecture complémentaire

Voici quelques ressources utiles pour une étude plus approfondie du modèle de système entité-composant:

• Michelle Kayney, auteur de entt , écrit une série très intéressante d'articles sur le système entité-composant appelé ECS aller-retour .
• Le Wiki Entity Systems contient des informations et des liens très utiles.