Diese Woche begann ich mit der Arbeit an meiner Vagabond-Engine und begann mit der Implementierung der
Entity-Component-System- Vorlage.
In diesem Artikel möchte ich über meine Implementierung sprechen, die auf
GitHub frei verfügbar ist. Aber anstatt den Code einfach zu kommentieren, möchte ich erklären, wie seine Struktur entworfen wurde. Daher werde ich mit der ersten Implementierung beginnen, die ich geschrieben habe, ihre Stärken und Schwächen analysieren und dann zeigen, wie ich sie verbessert habe. Am Ende werde ich eine Liste von Aspekten auflisten, die ebenfalls verbessert werden können.
Einführung
Motivation
Ich werde nicht über die Vorteile von ECS gegenüber dem objektorientierten Ansatz sprechen, da viele Leute vor mir dies gut gemacht haben. Scott Bilas war einer der ersten, der auf der
GDC 2002 über ECS sprach. Weitere berühmte Einführungen in das Thema sind Mike Wests
Evolve Your Hierarchy und das Kapitel
Components aus Robert Nistroms atemberaubendem Buch
Game Programming Patterns .
Kurz gesagt, ich werde sagen, dass die Aufgabe von ECS darin besteht, einen datenorientierten Ansatz für Spieleinheiten und eine bequeme Trennung von Daten und Logik zu entwickeln. Entitäten bestehen aus Komponenten, die Daten enthalten. Und Systeme, die Logik enthalten, verarbeiten diese Komponenten.
Wenn Sie auf Details eingehen, wird anstelle der
Vererbung die Komposition in ECS verwendet. Darüber hinaus nutzt dieser datenorientierte Ansatz den Cache besser, was bedeutet, dass eine hervorragende Leistung erzielt wird.
Beispiele
Bevor ich mich mit dem Code befasse, möchte ich Ihnen zeigen, was wir entwerfen werden.
Das Zuweisen von Komponenten ist sehr einfach:
struct Position : public Component<Position> { float x; float y; }; struct Velocity : public Component<Velocity> { float x; float y; };
Wie Sie sehen können, verwenden wir die
CRTP- Vorlage.
Dann müssen wir aus technischen Gründen, die ich später erläutern werde, die Anzahl der Komponenten und die Anzahl der Systeme festlegen:
constexpr auto ComponentCount = 32; constexpr auto SystemCount = 8;
Als Nächstes können Sie ein System angeben, das alle Entitäten mit beiden Komponenten übernimmt und ihre Positionen aktualisiert:
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; };
Das System verwendet einfach die
setRequirements Methode
setRequirements seine
setRequirements Komponenten zu
setRequirements . Anschließend kann es in der
update getManagedEntities um iterativ alle Entitäten zu durchlaufen, die die Anforderungen erfüllen.
Zuletzt erstellen wir einen Entitätsmanager, registrieren die Komponenten, erstellen ein System und mehrere Entitäten und aktualisieren dann ihre Positionen mithilfe des Systems:
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
Ich werde nicht so tun, als würde ich die beste ECS-Bibliothek erstellen. Ich wollte es nur selbst schreiben. Außerdem habe ich nur eine Woche daran gearbeitet.
Dies ist jedoch kein Grund, etwas völlig Unwirksames zu schaffen. Installieren wir also die Benchmarks:
- Der erste erstellt Entitäten.
- Der zweite verwendet das System, um Entitäten iterativ zu durchlaufen.
- Letzteres wird Entitäten erschaffen und zerstören;
Die Parameter aller dieser Benchmarks sind die Anzahl der Entitäten, die Anzahl der Komponenten für jede Entität, die maximale Anzahl der Komponenten und die maximale Anzahl der Systeme. Auf diese Weise können wir sehen, wie gut unsere Implementierung skaliert. Insbesondere werde ich die Ergebnisse für drei verschiedene Profile zeigen:
- Profil A: 32 Komponenten und 16 Systeme;
- AA-Profil: 128 Komponenten und 32 Systeme;
- AAA-Profil: 512 Komponenten und 64 Systeme.
Trotz der Tatsache, dass diese Benchmarks uns eine Vorstellung von der Qualität der Implementierung geben, sind sie recht einfach. In diesen Benchmarks verwenden wir beispielsweise nur homogene Einheiten, und ihre Komponenten sind klein.
Implementierung
Essenz
In meiner Implementierung ist eine Entität nur eine ID:
using Entity = uint32_t;
Darüber hinaus definieren wir in
Entity.h auch einen Alias-
Index , der später nützlich sein wird:
using Index = uint32_t; static constexpr auto InvalidIndex = std::numeric_limits<Index>::max();
Ich habe mich entschieden,
uint32_t anstelle des 64-Bit-Typs oder
std::size_t zu verwenden, um Platz zu sparen und die Cache-Optimierung zu verbessern. Wir werden nicht so viel verlieren: Es ist unwahrscheinlich, dass jemand Milliarden von Unternehmen hat.
Komponente
Definieren wir nun die Basisklasse für die Komponenten:
template<typename T, auto Type> class Component { public: static constexpr auto type = static_cast<std::size_t>(Type); };
Die Vorlagenklasse ist sehr einfach. Sie speichert lediglich die Typ-ID, die wir später zum Indizieren von Datenstrukturen nach Komponententyp verwenden werden.
Der erste Vorlagenparameter ist der Komponententyp. Der zweite ist der in
std::size_t konvertierte Wert, der als ID des Komponententyps dient.
Zum Beispiel können wir die
Position wie folgt definieren:
struct Positon : Component<Position, 0> { float x; float y; };
Eine Aufzählung kann jedoch bequemer sein:
enum class ComponentType { Position }; struct Positon : Component<Position, ComponentType::Position> { float x; float y; };
Im Einführungsbeispiel gibt es nur einen Vorlagenparameter: Wir müssen die Typ-ID nicht manuell angeben. Später werden wir sehen, wie die Struktur verbessert und Typkennungen automatisch generiert werden können.
EntityContainer
Die
EntityContainer Klasse ist für die Verwaltung der Entitäten und des
std::bitset für jede dieser Entitäten verantwortlich. Dieser Satz von Bits gibt die Komponenten an, die der Entität gehören.
Da wir Entitäten zum Indizieren von Containern und insbesondere von
std::vector , muss die ID so klein wie möglich sein und weniger Speicherplatz beanspruchen. Daher werden wir die ID der zerstörten Entitäten wiederverwenden. Zu diesem
mFreeEntities wird die freie ID in einem Container namens
mFreeEntities gespeichert.
Hier ist die
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; };
Mal sehen, wie die Methoden implementiert werden.
getEntityToBitset und
getBitset sind die üblichen kleinen Getter:
std::vector<std::bitset<ComponentCount>>& getEntityToBitset() { return mEntityToBitset; } const std::bitset<ComponentCount>& getBitset(Entity entity) const { return mEntityToBitset[entity]; }
Die Methode
create ist interessanter:
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; }
Wenn es eine freie Einheit gibt, verwendet er sie wieder. Andernfalls erstellt die Methode eine neue Entität.
Die Methode
remove fügt einfach die zu entfernende Entität in
mFreeEntities :
void remove(Entity entity) { mFreeEntities.push_back(entity); }
Die letzte Methode ist
reserve . Seine Aufgabe ist es, Speicher für verschiedene Container zu reservieren. Wie wir vielleicht wissen, ist das Zuweisen von Speicher eine kostspielige Operation. Wenn wir also ungefähr die Anzahl zukünftiger Entitäten im Spiel kennen, beschleunigt die Reservespeicherung die Arbeit:
void reserve(std::size_t size) { mFreeEntities.resize(size); std::iota(std::begin(mFreeEntities), std::end(mFreeEntities), 0); mEntityToBitset.resize(size); }
Neben einer einfachen Speichersicherung werden auch
mFreeEntities .
ComponentContainer
Die
ComponentContainer Klasse ist für das Speichern aller Komponenten des angegebenen Typs verantwortlich.
In meiner Architektur werden alle Komponenten eines bestimmten Typs zusammen gespeichert. Das heißt, es gibt ein großes Array für jeden Komponententyp,
mComponents .
Um eine Komponente in konstanter Zeit zu einer Entität hinzufügen, empfangen oder entfernen zu können, benötigen wir außerdem eine Möglichkeit, von einer Entität zu einer Komponente und von Komponente zu Entität zu wechseln. Dazu benötigen wir zwei weitere Datenstrukturen mit den Namen
mComponentToEntity und
mEntityToComponent .
Hier ist die
ComponentContainer Deklaration:
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; };
Sie können sehen, dass es vom
BaseComponentContainer erbt, der wie folgt festgelegt ist:
class BaseComponentContainer { public: virtual ~BaseComponentContainer() = default; virtual void reserve(std::size_t size) = 0; virtual bool tryRemove(Entity entity) = 0; };
Der einzige Zweck dieser Basisklasse besteht darin, alle Instanzen des
ComponentContainer in einem Container speichern zu können.
Betrachten wir nun die Definition von Methoden.
Betrachten Sie zunächst den Konstruktor: Er erhält einen Verweis auf einen Container, der Sätze von Entitätsbits enthält. Diese Klasse überprüft damit das Vorhandensein einer Komponente in einer Entität und aktualisiert den Satz von Bits einer Entität beim Hinzufügen oder Entfernen einer Komponente:
ComponentContainer(std::vector<std::bitset<ComponentCount>>& entityToBitset) : mEntityToBitset(entityToBitset) { }
Die
get Methode ist einfach. Wir verwenden nur
mEntityToComponent , um den Index einer Entitätskomponente in
mEntityToComponent zu finden:
T& get(Entity entity) { return mComponents[mEntityToComponent[entity]]; }
Die
add Methode verwendet ihre Argumente, um eine neue Komponente am Ende von
mComponents einzufügen, und bereitet dann Links vor, um von Entität zu Komponente und von Komponente zu Entität zu gelangen. Am Ende wird das Bit des
entity Sets, das der Komponente entspricht, auf
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; }
Die Methode
remove setzt die entsprechende Bitkomponente auf
false und verschiebt dann die letzte
mComponents Komponente an den Index der Komponente, die entfernt werden soll. Es aktualisiert die Links zu der Komponente, die wir gerade verschoben haben, und entfernt eine der Komponenten, die wir zerstören möchten:
void remove(Entity entity) { mEntityToBitset[entity][T::type] = false; auto index = mEntityToComponent[entity];
Wir können eine zeitkonstante Bewegung ausführen, indem wir die letzte Komponente an den Index verschieben, den wir zerstören möchten. Und tatsächlich müssen wir nur die letzte Komponente entfernen, was in
std::vector in konstanter Zeit möglich ist.
Die
tryRemove Methode überprüft, ob eine Entität über eine Komponente verfügt, bevor versucht wird, diese zu entfernen:
virtual bool tryRemove(Entity entity) override { if (mEntityToBitset[entity][T::type]) { remove(entity); return true; } return false; }
Die
getOwner Methode gibt die Entität zurück, der die Komponente gehört. Dazu werden Zeigerarithmetik und
mComponentToEntity :
Entity getOwner(const T& component) const { auto begin = mComponents.data(); auto index = static_cast<std::size_t>(&component - begin); return mComponentToEntity[index]; }
Die letzte Methode ist
reserve . Sie hat denselben Zweck wie die ähnliche Methode in
EntityContainer :
virtual void reserve(std::size_t size) override { mComponents.reserve(size); mComponentToEntity.reserve(size); mEntityToComponent.reserve(size); }
Das System
Schauen wir uns nun die Systemklasse an.
Jedes System verfügt über einen Satz von
mRequirements Bits, die die benötigten Komponenten beschreiben. Darüber hinaus wird eine Reihe von
mManagedEntities Entitäten
mManagedEntities , die diese Anforderungen erfüllen. Ich wiederhole, um alle Operationen in konstanter Zeit implementieren zu können, brauchen wir eine Möglichkeit, von einer Entität zu ihrem Index in
mManagedEntities . Dazu verwenden wir
std::unordered_map mEntityToManagedEntity Namen
mEntityToManagedEntity .
So sieht die Systemdeklaration aus:
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 verwendet einen
Faltungsausdruck , um die
setRequirements :
template<typename ...Ts> void setRequirements() { (mRequirements.set(Ts::type), ...); }
getManagedEntities ist ein Getter, der von den generierten Klassen verwendet wird, um auf die zu verarbeitenden Entitäten zuzugreifen:
const std::vector<Entity>& getManagedEntities() const { return mManagedEntities; }
Es wird eine konstante Referenz zurückgegeben, damit die generierten Klassen nicht versuchen,
mManagedEntities zu ändern.
onManagedEntityAdded und
onManagedEntityRemoved sind leer. Sie werden später neu definiert. Diese Methoden werden aufgerufen, wenn eine Entität zu
mManagedEntities oder gelöscht wird.
Die folgenden Methoden sind privat und nur über den
EntityManager zugänglich, der als freundliche Klasse deklariert ist.
setUp wird vom Entitätsmanager aufgerufen, um dem System eine ID zuzuweisen. Dann kann es damit Arrays indizieren:
void setUp(std::size_t type) { mType = type; }
onEntityUpdated wird aufgerufen, wenn sich eine Entität ändert, d. h. beim Hinzufügen oder Entfernen einer Komponente. Das System prüft, ob die Anforderungen erfüllt sind und ob die Entität bereits verarbeitet wurde. Wenn es die Anforderungen erfüllt und noch nicht verarbeitet wurde, fügt das System es hinzu. Wenn die Entität die Anforderungen jedoch nicht erfüllt und bereits verarbeitet wurde, löscht das System sie. In allen anderen Fällen tut das System nichts:
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 wird vom Entitätsmanager aufgerufen, wenn eine Entität gelöscht wird. Wenn die Entität vom System verarbeitet wurde, wird sie gelöscht:
void onEntityRemoved(Entity entity) { if (mEntityToManagedEntity.find(entity) != std::end(mEntityToManagedEntity)) removeEntity(entity); }
addEntity und
removeEntity sind nur
removeEntity .
addEntity legt den Link von der hinzugefügten Entität anhand seines Index in
mManagedEntities , fügt die Entität hinzu und ruft
onManagedEntityAdded :
void addEntity(Entity entity) { mEntityToManagedEntity[entity] = static_cast<Index>(mManagedEntities.size()); mManagedEntities.emplace_back(entity); onManagedEntityAdded(entity); }
removeEntity ruft zuerst
onManagedEntityRemoved . Anschließend wird die zuletzt verarbeitete Entität an den Index der zu löschenden Entität verschoben. Es aktualisiert den Verweis auf die verschobene Entität. Am Ende wird die zu löschende Entität aus
mManagedEntities und
mEntityToManagedEntity gelöscht:
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
Alle wichtige Logik ist in anderen Klassen. Ein Entity Manager verbindet einfach alles miteinander.
Werfen wir einen Blick auf seine Anzeige:
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; };
Die
EntityManager Klasse verfügt über drei Mitgliedsvariablen:
mComponentContainers , in dem
std::unique_ptr auf
BaseComponentContainer ,
mEntities , die nur eine Instanz von
EntityContainer und
mSystems , in dem
unique_ptr Zeiger auf
System mSystems sind.
Eine Klasse hat viele Methoden, aber tatsächlich sind sie alle sehr einfach.
Schauen wir uns zunächst
getComponentContainer , der einen Zeiger auf einen Komponentencontainer
getComponentContainer , der Komponenten vom Typ
T :
template<typename T> auto getComponentContainer() { return static_cast<ComponentContainer<T, ComponentCount, SystemCount>*>(mComponentContainers[T::type].get()); }
Eine weitere
checkComponentType ist
checkComponentType , mit der einfach überprüft wird, ob die Komponententyp-ID unter der maximalen Anzahl von Komponenten liegt:
template<typename T> void checkComponentType() const { static_assert(T::type < ComponentCount); }
checkComponentTypes verwendet einen Faltungsausdruck, um verschiedene Arten von Überprüfungen durchzuführen:
template<typename ...Ts> void checkComponentTypes() const { (checkComponentType<Ts>(), ...); }
registerComponent erstellt einen neuen Container mit Komponenten des angegebenen Typs:
template<typename T> void registerComponent() { checkComponentType<T>(); mComponentContainers[T::type] = std::make_unique<ComponentContainer<T, ComponentCount, SystemCount>>( mEntities.getEntityToBitset()); }
createSystem erstellt ein neues System des angegebenen Typs und legt dessen Typ fest:
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()); }
Die
reserve ruft die
reserve der
EntityContainer ComponentContainer und
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); }
Die
createEntity Methode gibt das Ergebnis der
create Methode des
EntityManager Managers zurück:
Entity createEntity() { return mEntities.create(); }
hasComponent verwendet eine Reihe von Entitätsbits, um schnell zu überprüfen, ob diese Entität eine Komponente des angegebenen Typs enthält:
template<typename T> bool hasComponent(Entity entity) const { checkComponentType<T>(); return mEntities.getBitset(entity)[T::type]; }
hasComponents verwendet einen Faltungsausdruck, um einen Satz von Bits zu erstellen, die die erforderlichen Komponenten bezeichnen, und verwendet ihn dann mit einem Satz von Bits der Entität, um zu überprüfen, ob die Entität alle erforderlichen Komponenten enthält:
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 leitet die Anforderung an den erforderlichen Komponentencontainer weiter:
template<typename T> T& getComponent(Entity entity) { checkComponentType<T>(); return getComponentContainer<T>()->get(entity); }
getComponents gibt ein Tupel von Links zu den angeforderten Komponenten zurück. Dazu werden
std::tie und ein Faltungsausdruck verwendet:
template<typename ...Ts> std::tuple<Ts&...> getComponents(Entity entity) { checkComponentTypes<Ts...>(); return std::tie(getComponentContainer<Ts>()->get(entity)...); }
addComponent und
removeComponent leiten die Anforderung an den erforderlichen Komponentencontainer um und rufen dann die
onEntityUpdated auf:
template<typename T, typename... Args> void addComponent(Entity entity, Args&&... args) { checkComponentType<T>(); getComponentContainer<T>()->add(entity, std::forward<Args>(args)...);
Schließlich leitet
getOwner die Anforderung an die erforderliche Containerkomponente weiter:
template<typename T> Entity getOwner(const T& component) const { checkComponentType<T>(); return getComponentContainer<T>()->getOwner(component); }
Das war meine erste Implementierung. Es besteht aus nur 357 Codezeilen. Der gesamte Code befindet sich in diesem
Thread .
Profilerstellung und Benchmarks
Benchmarks
Jetzt ist es an der Zeit, meine erste ECS-Implementierung zu bewerten!
Hier sind die Ergebnisse:
Die Vorlage skaliert gut genug! Die Anzahl der pro Sekunde verarbeiteten Objekte ist ungefähr gleich, wenn die Anzahl der Entitäten erhöht und Profile geändert werden (A, AA und AAA).
Darüber hinaus lässt es sich gut skalieren, wenn die Anzahl der Komponenten in Entitäten zunimmt. Wenn wir Entitäten mit drei Komponenten durchlaufen, treten sie dreimal langsamer auf als Entitäten mit einer Komponente. Dies wird erwartet, weil wir drei Komponenten benötigen.
Cache fehlt
Um die Anzahl der Cache-
Fehler zu überprüfen, habe ich das hier verwendete
Cachegrind- Beispiel ausgeführt.
Hier ist das Ergebnis für 10.000 Entitäten:
==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% )Hier ist das Ergebnis für 100.000 Unternehmen:
==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% )Die Ergebnisse sind ziemlich gut. Es ist nur ein wenig seltsam, warum es bei 100.000 Unternehmen so viele LLd-Fehler gibt.
Profilerstellung
Um zu verstehen, welche Teile der aktuellen Implementierung länger dauern, habe ich das Beispiel mit
gprof profiliert.
Hier ist das Ergebnis:
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&)Die Ergebnisse können etwas verzerrt sein, da ich mit dem Flag -O1 kompiliert
-O1 gprof etwas Sinnvolles
-O1 . Es scheint, dass der Compiler mit zunehmender Optimierungsstufe anfängt, alles aggressiv einzubetten, und gprof sagt fast nichts.
Laut gprof ist der offensichtliche Engpass in dieser Implementierung
std::unordered_map . Wenn wir es optimieren wollen, lohnt es sich, sie loszuwerden.
Vergleich mit std::map
Ich wurde neugierig auf den Leistungsunterschied zwischen std::unordered_mapund std::mapund ersetzte alles im Code std::unordered_mapdurch std::map. Diese Implementierung finden Sie hier.Hier sind die Benchmark-Ergebnisse:Wir können sehen, dass die Implementierung dieses Mal mit zunehmender Anzahl von Entitäten nicht gut skaliert werden kann. Und selbst bei 1000 Entitäten ist die Iteration doppelt so langsam wie bei Version c std::unordered_map.Fazit
Wir haben eine einfache, aber bereits praktische Bibliothek der Entity-Component-System-Vorlage erstellt. In Zukunft werden wir es als Grundlage für Verbesserungen und Optimierungen verwenden.Im nächsten Abschnitt werden wir zeigen , wie die Produktivität steigern durch Ersetzen std::unordered_mapauf std::vector. Darüber hinaus zeigen wir, wie Komponenten automatisch ID-Typen zugewiesen werden.Ersetzen von std :: unordered_map durch std :: vector
Wie wir gesehen haben, waren sie std::unordered_mapein Engpass in unserer Implementierung. Daher verwenden std::unordered_mapwir stattdessen in mEntityToComponentfür ComponentContainerund in mEntityToManagedEntityfür SystemVektoren std::vector.Änderungen
Die Änderungen werden sehr einfach sein, Sie können sie hier ansehen .Die einzige Feinheit liegt in der Tatsache , dass vectorin mEntityToComponentund mEntityToManagedEntityjede Einheit lange genug Index gewesen. Um dies auf einfache Weise zu tun, habe ich beschlossen, diese vectorin zu speichern EntityContainer, in denen wir die maximale ID der Entität kennen. Dann übergebe ich die Vektoren als vectorReferenz oder Zeiger im Entitätsmanager an die Komponentencontainer.Geänderter Code finden Sie in diesem Thread .Ergebnisse
Lassen Sie uns überprüfen, wie diese Version besser funktioniert als die vorherige:Wie Sie sehen, ist das Erstellen und Löschen mit einer großen Anzahl von Komponenten und Systemen etwaslangsamer geworden.Die Iteration ist jedoch viel schneller geworden, fast zehnmal! Und es skaliert sehr gut. Diese Beschleunigung überwiegt bei weitem die Verlangsamung der Erstellung und Löschung. Und das ist logisch: Iterationen der Entität werden viele Male auftreten, aber sie werden nur einmal erstellt und gelöscht.Nun wollen wir sehen, ob dies die Anzahl der Cache-Fehler verringert hat.Hier ist die Ausgabe von Cachegrind mit 10.000 Entitäten: Und hier ist die Ausgabe für 100.000 Entitäten: Wir sehen, dass diese Version etwa dreimal weniger Links und viermal weniger Cache-Fehler erstellt.==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% )Automatische Typen
Die letzte Verbesserung, über die ich sprechen werde, ist die automatische Generierung von Komponententyp-IDs.Änderungen
Alle Änderungen zur Implementierung der automatischen Generierung von ID-Typen finden Sie hier .Um jedem Komponententyp eine eindeutige ID zuweisen zu können, müssen Sie CRTP und eine Funktion mit einem statischen Zähler verwenden: 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();
Möglicherweise stellen Sie fest, dass die Typ-ID jetzt zur Laufzeit generiert wird und zur Kompilierungszeit bereits bekannt war.Der Code nach den Änderungen befindet sich in diesem Thread .Ergebnisse
Um die Leistung dieser Version zu testen, habe ich Benchmarks durchgeführt:Beim Erstellen und Löschen blieben die Ergebnisse in etwa gleich. Sie können jedoch feststellen, dass die Iteration mit etwa 10% etwas langsamer geworden ist.Diese Verlangsamung kann durch die Tatsache erklärt werden, dass der Compiler zur Kompilierungszeit Typkennungen kannte, was bedeutet, dass er den Code besser optimieren könnte.Die manuelle Zuweisung von ID-Typen ist etwas unpraktisch und kann zu Fehlern führen. Selbst wenn wir die Leistung etwas reduzieren, ist dies dennoch eine Verbesserung der Benutzerfreundlichkeit unserer ECS-Bibliothek.Ideen für weitere Verbesserungen
Bevor ich diesen Artikel abschließe, möchte ich Ihnen Ideen für weitere Verbesserungen mitteilen. Bisher habe ich sie nicht implementiert, aber vielleicht werde ich es in Zukunft tun.Dynamische Anzahl von Komponenten und Systemen
Es ist unpraktisch, die maximale Anzahl von Komponenten und Systemen im Voraus in Form von Vorlagenparametern anzugeben. Ich denke , dass es möglich sein wird, zu ersetzen std::arrayin EntityManagerauf std::vectorohne eine starken Leistungseinbußen.Es ist jedoch std::bitseterforderlich, die Anzahl der Bits zur Kompilierungszeit zu kennen. Während ich denke , dieses Problem beheben , indem Sie ersetzen std::vector<bitset<ComponentCount>>in EntityContainerauf std::vector<char>und lassen eine ausreichende Anzahl von Bytes , die die Sätze von Bits aller Einheiten zu repräsentieren. Dann implementieren wir eine Lightweight-Klasse BitsetView, die am Eingang ein Paar von Zeigern auf den Anfang und das Ende des Satzes von Bits empfängt und dann alle erforderlichen Operationen mit std::bitsetin diesem Speicherbereich ausführt .Eine andere Idee: Verwenden Sie keine Bitmengen mehr und prüfen Sie nur, mEntityToComponentob die Entität Komponenten enthält.Vereinfachte Komponenteniteration
Wenn das System im Moment die Komponenten der von ihm verarbeiteten Entitäten iterativ umgehen möchte, müssen wir dies folgendermaßen tun: for (const auto& entity : getManagedEntities()) { auto [position, velocity] = mEntityManager.getComponents<Position, Velocity>(entity); ... }
Es wäre schöner und einfacher, wenn wir so etwas tun könnten: for (auto& [position, velocity] : mEntityManager.getComponents<Position, Velocity>(mManagedEntities)) { ... }
Implementieren Sie wird es einfacher als die Verwendung std::view::transformin C ++ 20von Bereichen Bibliothek .Leider ist es noch nicht da. Ich könnte die Bereichsbibliothek von Eric Nibler verwenden , möchte aber keine Abhängigkeiten hinzufügen.Die Lösung könnte darin bestehen, eine Klasse zu implementieren EntityRangeView, die die Komponententypen empfängt, die als Vorlagenparameter empfangen werden müssen, und eine std::vectorEntitätsreferenz als Konstruktorparameter . Dann würden wir nur mussten erkennen begin, endund die Iteratortyp das gewünschte Verhalten zu erreichen. Das Schreiben ist nicht sehr schwierig, aber etwas zeitaufwändig.Event Management Optimierung
In der aktuellen Implementierung rufen wir beim Hinzufügen oder Entfernen einer Komponente zu einer Entität onEntityUpdatedalle Systeme auf. Dies ist etwas ineffizient, da viele Systeme nicht an der Art der Komponente interessiert sind, die gerade geändert wurde.Um Schäden zu minimieren, können wir beispielsweise Zeiger auf Systeme speichern, die an dem angegebenen Komponententyp in der Datenstruktur interessiert sind std::array<std::vector<System<ComponentCount, SystemCount>>, ComponentCount>. Wenn wir dann eine Komponente hinzufügen oder entfernen, rufen wir einfach die Methode der onEntityUpdatedSysteme auf, die an dieser Komponente interessiert sind.Teilmengen von Entitäten, die vom Entitätsmanager anstelle von Systemen verwaltet werden
Meine letzte Idee würde zu umfangreicheren Änderungen in der Struktur der Bibliothek führen.Anstelle von Systemen, die ihre Entitätsgruppen verwalten, würde dies ein Entitätsmanager tun. Der Vorteil eines solchen Schemas besteht darin, dass zwei Systeme, die an derselben Gruppe von Komponenten interessiert sind, keine Teilmenge von Entitäten duplizieren, die diese Anforderungen erfüllen.Systeme könnten ihre Anforderungen einfach einem Entity Manager melden. Dann würde der Entitätsmanager alle verschiedenen Teilmengen von Entitäten speichern. Schließlich würden Systeme Entitäten mit einer ähnlichen Syntax abfragen: for (const auto& entity : mEntityManager.getEntitiesWith<Position, Velocity>()) { ... }
Fazit
Bisher ist dies das Ende eines Artikels über meine Implementierung des Entity-Component-Systems. Wenn ich andere Verbesserungen vornehme, schreibe ich möglicherweise in Zukunft neue Artikel.Die im Artikel beschriebene Implementierung ist recht einfach: Sie besteht aus weniger als 500 Codezeilen und weist auch eine gute Leistung auf. Alle Transaktionen werden für eine (amortisierte) konstante Zeit realisiert. Darüber hinaus nutzt es in der Praxis den Cache optimal und empfängt und iteriert Entitäten sehr schnell.Ich hoffe, dieser Artikel war interessant oder sogar nützlich für Sie.Zusätzliche Lektüre
Hier sind einige nützliche Ressourcen für eine eingehendere Untersuchung des Entity-Component-System-Musters: