Minggu ini, saya mulai bekerja pada mesin Vagabond saya dan mulai menerapkan templat entitas-komponen-sistem .

Pada artikel ini saya ingin berbicara tentang implementasi saya, yang tersedia secara bebas di GitHub . Tetapi alih-alih hanya mengomentari kode, saya ingin menjelaskan bagaimana strukturnya dirancang. Oleh karena itu, saya akan mulai dengan implementasi pertama yang saya tulis, menganalisis kekuatan dan kelemahannya, dan kemudian menunjukkan bagaimana saya memperbaikinya. Pada akhirnya saya akan daftar daftar aspek yang juga dapat ditingkatkan.

Pendahuluan

Motivasi

Saya tidak akan berbicara tentang manfaat ECS atas pendekatan berorientasi objek, karena banyak orang sebelum saya telah melakukan ini dengan baik. Scott Bilas adalah salah satu yang pertama berbicara tentang ECS ​​di GDC 2002 . Pengantar penting lainnya untuk topik ini termasuk bab Mike West's Evolve Your Hierarchy dan Components dari buku Game Programming Patterns Robert Nistrom yang menakjubkan.

Singkatnya, saya akan mengatakan bahwa tugas ECS adalah menciptakan pendekatan berorientasi data ke entitas permainan dan pemisahan data dan logika yang nyaman. Entitas terdiri dari komponen yang berisi data. Dan sistem yang mengandung proses logika komponen-komponen ini.

Jika Anda masuk ke detail, alih-alih pewarisan , komposisi digunakan dalam ECS. Selain itu, pendekatan yang berorientasi pada data ini membuat penggunaan cache lebih baik, yang berarti ini mencapai kinerja yang sangat baik.

Contohnya

Sebelum mempelajari kode, saya ingin menunjukkan kepada Anda apa yang akan kami desain.

Menetapkan komponen sangat sederhana:

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

Seperti yang Anda lihat, kami akan menggunakan template CRTP .

Kemudian, untuk alasan teknis, yang akan saya jelaskan nanti, kita perlu memperbaiki jumlah komponen dan jumlah sistem:

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

Selanjutnya, Anda dapat menentukan sistem yang akan mengambil semua entitas yang memiliki kedua komponen dan memperbarui posisi mereka:

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

Sistem hanya menggunakan metode setRequirements untuk setRequirements komponen-komponennya yang setRequirements . Kemudian, dalam metode update , ini dapat memanggil getManagedEntities untuk secara berulang melintasi semua entitas yang memenuhi persyaratan.

Akhirnya, mari kita buat manajer entitas, daftarkan komponen, buat sistem dan beberapa entitas, lalu perbarui posisi mereka menggunakan sistem:

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

Tingkatan yang dicapai

Saya tidak akan berpura-pura membuat perpustakaan ECS terbaik. Saya hanya ingin menulisnya sendiri. Selain itu, saya hanya mengerjakannya selama seminggu.

Namun, ini bukan alasan untuk membuat sesuatu yang sama sekali tidak efektif. Jadi mari kita instal tolok ukur:

• Yang pertama akan membuat entitas;
• Yang kedua akan menggunakan sistem untuk melintasi berulang entitas;
• Yang terakhir akan membuat dan menghancurkan entitas;

Parameter dari semua tolok ukur ini adalah jumlah entitas, jumlah komponen untuk setiap entitas, jumlah maksimum komponen dan jumlah maksimum sistem. Dengan cara ini, kita bisa melihat seberapa baik skala implementasi kita. Secara khusus, saya akan menunjukkan hasil untuk tiga profil berbeda:

• Profil A: 32 komponen dan 16 sistem;
• Profil AA: 128 komponen dan 32 sistem;
• Profil AAA: 512 komponen dan 64 sistem.

Terlepas dari kenyataan bahwa tolok ukur ini akan memberi kita gambaran tentang kualitas implementasi, mereka cukup sederhana. Misalnya, dalam tolok ukur ini kami hanya menggunakan entitas yang homogen, dan komponennya kecil.

Implementasi

Esensi

Dalam implementasi saya, sebuah entitas hanyalah sebuah id:

 using Entity = uint32_t; 

Selain itu, di Entity.h kita juga akan mendefinisikan Index alias, yang akan berguna nanti:

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

Saya memutuskan untuk menggunakan uint32_t bukan tipe 64-bit atau std::size_t untuk menghemat ruang dan meningkatkan optimasi cache. Kami tidak akan kehilangan begitu banyak: tidak mungkin seseorang akan memiliki miliaran entitas.

Komponen

Sekarang mari kita mendefinisikan kelas dasar untuk komponen:

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

Kelas template sangat sederhana, hanya menyimpan tipe id, yang akan kita gunakan nanti untuk mengindeks struktur data dengan tipe komponen.

Parameter templat pertama adalah jenis komponen. Yang kedua adalah nilai yang dikonversi ke std::size_t , yang akan berfungsi sebagai id jenis komponen.

Sebagai contoh, kita dapat mendefinisikan komponen Position sebagai berikut:

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

Namun, pencacahan mungkin lebih nyaman:

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

Dalam contoh pengantar, hanya ada satu parameter templat: kita tidak perlu menentukan id jenis secara manual. Nanti kita akan melihat bagaimana memperbaiki struktur dan menghasilkan pengenal tipe secara otomatis.

EntityContainer

Kelas EntityContainer akan bertanggung jawab untuk mengelola entitas dan std::bitset untuk masing-masing. Set bit ini akan menunjukkan komponen yang dimiliki entitas.

Karena kita akan menggunakan entitas untuk mengindeks wadah, dan khususnya std::vector , kita perlu id sekecil mungkin dan menggunakan lebih sedikit memori. Oleh karena itu, kami akan menggunakan kembali id ​​entitas yang hancur. Untuk melakukan ini, id gratis akan disimpan dalam wadah yang disebut mFreeEntities .

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

Mari kita lihat bagaimana metode diimplementasikan.

getEntityToBitset dan getBitset adalah getter kecil yang biasa:

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

Metode create lebih menarik:

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

Jika ada entitas bebas, ia menggunakannya kembali. Kalau tidak, metode menciptakan entitas baru.

Metode remove cukup menambahkan entitas yang akan dihapus di mFreeEntities :

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

Metode terakhir adalah reserve . Tugasnya adalah untuk menyimpan memori untuk berbagai wadah. Seperti yang kita ketahui, mengalokasikan memori adalah operasi yang mahal, jadi jika kira-kira kita mengetahui jumlah entitas masa depan dalam game, maka memori cadangan akan mempercepat pekerjaan:

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

Selain cadangan memori sederhana, ini juga mengisi mFreeEntities .

ComponentContainer

Kelas ComponentContainer akan bertanggung jawab untuk menyimpan semua komponen dari tipe yang ditentukan.

Dalam arsitektur saya, semua komponen dari tipe tertentu disimpan bersama. Artinya, ada satu array besar untuk setiap jenis komponen, yang disebut mComponents .

Selain itu, untuk dapat menambah, menerima atau menghapus komponen dari suatu entitas dalam waktu yang konstan, kita memerlukan cara untuk berpindah dari suatu entitas ke suatu komponen dan dari komponen ke entitas. Untuk melakukan ini, kita memerlukan dua struktur data lagi yang disebut mComponentToEntity dan mEntityToComponent .

Berikut ini adalah deklarasi 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; }; 

Anda dapat melihat bahwa itu mewarisi dari BaseComponentContainer , yang ditetapkan seperti ini:

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

Satu-satunya tujuan kelas dasar ini adalah untuk dapat menyimpan semua instance dari ComponentContainer dalam sebuah wadah.

Sekarang mari kita lihat definisi metode.

Pertama, pertimbangkan konstruktor: itu mendapatkan referensi ke wadah yang berisi set bit entitas. Kelas ini akan menggunakannya untuk memeriksa keberadaan komponen dalam suatu entitas dan untuk memperbarui sekumpulan bit entitas ketika menambah atau menghapus komponen:

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

Metode get sederhana, kami hanya menggunakan mEntityToComponent untuk menemukan indeks komponen entitas di mComponents :

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

Metode add menggunakan argumennya untuk menyisipkan komponen baru di akhir mComponents , dan kemudian menyiapkan tautan untuk berpindah dari entitas ke komponen dan dari komponen ke entitas. Pada akhirnya, ini menetapkan bit entity bit yang cocok dengan komponen menjadi 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; } 

Metode remove menetapkan komponen bit yang sesuai ke false , dan kemudian memindahkan komponen mComponents terakhir pada indeks yang ingin kita hapus. Ini memperbarui tautan ke komponen yang baru saja kami pindah, dan menghapus salah satu komponen yang ingin kami hancurkan:

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

Kita dapat melakukan pergerakan waktu konstan dengan memindahkan komponen terakhir pada indeks yang ingin kita hancurkan. Dan pada kenyataannya, maka kita hanya perlu menghapus komponen terakhir, yang dapat dilakukan dalam std::vector dalam waktu yang konstan.

Metode tryRemove memeriksa untuk melihat apakah suatu entitas memiliki komponen sebelum mencoba untuk menghapusnya:

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

Metode getOwner mengembalikan entitas yang memiliki komponen, untuk ini ia menggunakan pointer aritmatika dan mComponentToEntity :

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

Metode terakhir adalah reserve , ia memiliki tujuan yang sama dengan metode serupa di EntityContainer :

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

Sistem

Sekarang mari kita lihat kelas System .

Setiap sistem memiliki satu set bit mRequirements yang menjelaskan komponen yang dibutuhkannya. Selain itu, ia menyimpan satu set entitas mManagedEntities yang memenuhi persyaratan ini. Saya ulangi, agar dapat mengimplementasikan semua operasi dalam waktu yang konstan, kita perlu cara untuk berpindah dari suatu entitas ke indeksnya di mManagedEntities . Untuk melakukan ini, kita akan menggunakan std::unordered_map disebut mEntityToManagedEntity .

Seperti apa deklarasi System itu:

 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 menggunakan ekspresi konvolusi untuk menetapkan nilai bit:

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

getManagedEntities adalah pengambil yang akan digunakan oleh kelas yang dihasilkan untuk mengakses entitas yang sedang diproses:

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

Ini mengembalikan referensi konstan sehingga kelas yang dihasilkan tidak berusaha untuk memodifikasi mManagedEntities .

onManagedEntityAdded dan onManagedEntityRemoved kosong. Mereka akan didefinisikan ulang nanti. Metode ini akan dipanggil ketika menambahkan entitas ke mManagedEntities atau menghapusnya.

Metode berikut akan bersifat pribadi dan hanya dapat diakses dari EntityManager , yang dinyatakan sebagai kelas ramah.

setUp akan dipanggil oleh manajer entitas untuk menetapkan id ke sistem. Kemudian dapat menggunakannya untuk mengindeks array:

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

onEntityUpdated dipanggil saat entitas berubah, mis. saat menambah atau menghapus komponen. Sistem memeriksa apakah persyaratan terpenuhi dan apakah entitas sudah diproses. Jika memenuhi persyaratan dan belum diproses, maka sistem menambahkannya. Namun, jika entitas tidak memenuhi persyaratan dan telah diproses, maka sistem akan menghapusnya. Dalam semua kasus lain, sistem tidak melakukan apa-apa:

 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 dipanggil oleh manajer entitas ketika entitas dihapus. Jika entitas diproses oleh sistem, ia menghapusnya:

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

addEntity dan removeEntity hanyalah metode pembantu.

addEntity menetapkan tautan untuk pergi dari entitas yang ditambahkan dengan indeksnya di mManagedEntities , menambahkan entitas, dan panggilan onManagedEntityAdded :

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

removeEntity panggilan pertama onManagedEntityRemoved . Kemudian memindahkan entitas yang diproses terakhir pada indeks yang sedang dihapus. Ini memperbarui referensi ke entitas yang dipindahkan. Pada akhirnya, itu menghapus entitas yang akan dihapus dari mManagedEntities dan 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(); } 

Manajer Entitas

Semua logika penting ada di kelas lain. Seorang manajer entitas hanya mengikat semuanya.

Mari kita lihat iklannya:

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

Kelas EntityManager memiliki tiga variabel anggota: mComponentContainers , yang menyimpan std::unique_ptr ke BaseComponentContainer , mEntities , yang merupakan turunan dari EntityContainer dan mSystems , yang menyimpan pointer unique_ptr ke System .

Kelas memiliki banyak metode, tetapi sebenarnya semuanya sangat sederhana.

Pertama-tama mari kita lihat getComponentContainer , yang mengembalikan pointer ke kontainer komponen yang memproses komponen tipe T :

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

Fungsi pembantu lainnya adalah checkComponentType , yang hanya memeriksa bahwa id jenis komponen di bawah jumlah maksimum komponen:

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

checkComponentTypes menggunakan ekspresi konvolusi untuk melakukan beberapa jenis pemeriksaan:

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

registerComponent membuat wadah baru komponen dari tipe yang ditentukan:

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

createSystem membuat sistem baru dari tipe yang ditentukan dan menetapkan tipenya:

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

Metode reserve memanggil metode reserve EntityContainer ComponentContainer dan 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); } 

Metode createEntity mengembalikan hasil dari metode create dari manajer EntityManager :

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

hasComponent menggunakan satu set bit entitas untuk dengan cepat memverifikasi bahwa entitas ini memiliki komponen dari tipe yang ditentukan:

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

hasComponents menggunakan ekspresi konvolusi untuk membuat satu set bit yang menunjukkan komponen yang diperlukan, dan kemudian menggunakannya dengan seperangkat bit entitas untuk memeriksa apakah entitas memiliki semua komponen yang diperlukan:

 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 mengalihkan permintaan ke wadah komponen yang diperlukan:

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

getComponents mengembalikan tupel tautan ke komponen yang diminta. Untuk melakukan ini, ia menggunakan std::tie dan ekspresi konvolusi:

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

addComponent dan removeComponent mengalihkan permintaan ke wadah komponen yang diperlukan, dan kemudian memanggil onEntityUpdated sistem 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); } 

Akhirnya, getOwner mengalihkan permintaan ke komponen kontainer yang diperlukan:

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

Itu implementasi pertama saya. Ini terdiri dari hanya 357 baris kode. Semua kode dapat ditemukan di utas ini.

Pembuatan profil dan tolok ukur

Tingkatan yang dicapai

Sekarang adalah waktu untuk membandingkan implementasi ECS pertama saya!

Inilah hasilnya:




Templat berskala cukup baik! Jumlah yang diproses per detik kira-kira sama ketika meningkatkan jumlah entitas dan mengubah profil (A, AA dan AAA).

Selain itu, ini berskala baik dengan peningkatan jumlah komponen dalam entitas. Ketika kita beralih melalui entitas dengan tiga komponen, mereka terjadi tiga kali lebih lambat daripada iterasi melalui entitas dengan satu komponen. Ini diharapkan karena kita perlu mendapatkan tiga komponen.

Tembolok merindukan

Untuk memeriksa jumlah cache yang hilang, saya menjalankan contoh cachegrind yang diambil dari sini .

Inilah hasil untuk 10.000 entitas:

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

Ini adalah hasil untuk 100.000 entitas:

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

Hasilnya cukup bagus. Hanya sedikit aneh mengapa ada begitu banyak LLD yang hilang pada 100.000 entitas.

Pembuatan profil

Untuk memahami bagian mana dari implementasi saat ini yang membutuhkan waktu lebih lama, saya membuat profil contoh dengan gprof .

Inilah hasilnya:

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

Hasilnya mungkin sedikit terdistorsi karena saya dikompilasi dengan flag -O1 gprof -O1 sesuatu yang bermakna. Tampaknya ketika tingkat optimasi ditingkatkan, kompiler mulai secara agresif menanamkan semuanya dan gprof mengatakan hampir tidak ada.

Menurut gprof, hambatan yang jelas dalam implementasi ini adalah std::unordered_map . Jika kita ingin mengoptimalkannya, maka ada baiknya mencoba menyingkirkannya.

Perbandingan dengan std::map

Saya menjadi penasaran tentang perbedaan kinerja antara std::unordered_mapdan std::map, jadi saya mengubah kode semua std::unordered_mappada std::map. Implementasi ini tersedia di sini.

Berikut adalah hasil benchmark:




Kita bisa melihat bahwa kali ini implementasinya tidak skala dengan baik dengan peningkatan jumlah entitas. Dan bahkan dengan 1000 entitas, iterasi dua kali lebih lambat dari versi c std::unordered_map.

Kesimpulan

Kami telah membuat pustaka yang sederhana namun sudah praktis dari templat entitas-komponen-sistem. Di masa depan, kami akan menggunakannya sebagai landasan untuk peningkatan dan optimalisasi.

Pada bagian selanjutnya, kami akan menunjukkan cara meningkatkan produktivitas dengan mengganti std::unordered_mapdengan std::vector. Selain itu, kami akan menunjukkan cara menetapkan tipe id secara otomatis ke komponen.

Mengganti std :: unordered_map dengan std :: vector

Seperti yang kita lihat, mereka std::unordered_mapadalah hambatan dalam implementasi kami. Oleh karena itu, alih-alih std::unordered_mapkita gunakan mEntityToComponentuntuk ComponentContainerdan dalam mEntityToManagedEntityuntuk Systemvektor std::vector.

Perubahan

Perubahannya akan sangat sederhana, Anda bisa melihatnya di sini .

Satu-satunya kehalusan terletak pada kenyataan bahwa vectordalam mEntityToComponentdan mEntityToManagedEntitytelah cukup lama untuk indeks setiap entitas. Untuk melakukan cara sederhana ini, saya memutuskan untuk menyimpan ini vectordi EntityContainer, di mana kita tahu entitas maksimum id. Lalu saya meneruskan vektor ke vectorwadah komponen dengan referensi atau pointer di manajer entitas.

Kode yang dimodifikasi dapat ditemukan di utas ini .

Hasil

Mari kita periksa bagaimana versi ini bekerja lebih baik daripada versi sebelumnya:




Seperti yang Anda lihat, membuat dan menghapus dengan sejumlah besar komponen dan sistem menjadi sedikit
lebih lambat.

Namun, iterasi telah menjadi jauh lebih cepat, hampir sepuluh kali lipat! Dan itu bersisik dengan sangat baik. Percepatan ini sangat melebihi perlambatan kreasi dan penghapusan. Dan ini logis: iterasi entitas akan terjadi berkali-kali, tetapi dibuat dan dihapus hanya sekali.

Sekarang mari kita lihat apakah ini mengurangi jumlah cache yang hilang.

Berikut ini adalah output dari cachegrind dengan 10.000 entitas: Dan di sini adalah output untuk 100.000 entitas: Kami melihat bahwa versi ini menciptakan sekitar tiga kali lebih sedikit tautan dan empat kali lebih sedikit kehilangan 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% )

Jenis Otomatis

Perbaikan terakhir yang akan saya bicarakan adalah pembuatan pengenal tipe komponen otomatis.

Perubahan

Semua perubahan untuk menerapkan pembuatan otomatis tipe id dapat ditemukan di sini .

Untuk, agar dapat menetapkan satu id unik untuk setiap jenis komponen, Anda perlu menggunakan CRTP dan fungsi dengan penghitung statis:

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

Anda mungkin memperhatikan bahwa id jenis sekarang dihasilkan saat runtime, dan sebelumnya dikenal pada waktu kompilasi.

Kode setelah perubahan dapat ditemukan di utas ini .

Hasil

Untuk menguji kinerja versi ini, saya melakukan benchmark:




Untuk pembuatan dan penghapusan, hasilnya tetap sama. Namun, Anda dapat melihat bahwa iterasi telah menjadi sedikit lebih lambat, sekitar 10%.

Perlambatan ini dapat dijelaskan oleh fakta bahwa kompiler digunakan untuk mengetahui pengenal jenis pada waktu kompilasi, yang berarti dapat lebih mengoptimalkan kode.

Penugasan manual tipe id agak tidak nyaman dan dapat menyebabkan kesalahan. Jadi, bahkan jika kita sedikit mengurangi kinerja, itu masih merupakan peningkatan dalam kegunaan perpustakaan ECS kami.

Gagasan untuk Perbaikan Lebih Lanjut

Sebelum mengakhiri artikel ini, saya ingin berbagi dengan Anda ide untuk peningkatan lainnya. Sejauh ini saya belum mengimplementasikannya, tapi mungkin saya akan melakukannya di masa depan.

Jumlah komponen dan sistem yang dinamis

Sangat tidak nyaman untuk menunjukkan terlebih dahulu jumlah maksimum komponen dan sistem dalam bentuk parameter templat. Saya pikir itu akan mungkin untuk menggantikan std::arraydi EntityManageratas std::vectortanpa penurunan kinerja yang kuat.

Namun, itu std::bitsetmembutuhkan mengetahui jumlah bit pada waktu kompilasi. Sementara saya pikir memperbaiki masalah ini dengan mengganti std::vector<bitset<ComponentCount>>di EntityContaineratas std::vector<char>dan melepaskan dalam jumlah yang memadai byte untuk mewakili set bit semua entitas. Kemudian kami menerapkan kelas ringan BitsetViewyang menerima input sepasang pointer ke awal dan akhir set bit, dan kemudian melakukan semua operasi yang diperlukan dengan std::bitsetdalam rentang memori ini.

Gagasan lain: jangan gunakan set bit lagi dan cukup periksa untuk mEntityToComponentmelihat apakah entitas memiliki komponen.

Iterasi komponen yang disederhanakan

Saat ini, jika sistem ingin mengulangi komponen entitas yang diolahnya secara iteratif, kita perlu melakukannya seperti ini:

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

Akan lebih cantik dan sederhana jika kita bisa melakukan sesuatu seperti ini:

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

Menerapkannya akan lebih mudah daripada menggunakan std::view::transformC ++ 20
dari rentang perpustakaan .

Sayangnya, belum ada di sana. Saya bisa menggunakan perpustakaan rentang Eric Nibler, tapi saya tidak ingin menambahkan dependensi.

Solusinya bisa dengan mengimplementasikan kelas EntityRangeViewyang akan menerima jenis komponen yang perlu diterima sebagai parameter templat, dan referensi std::vectorentitas sebagai parameter konstruktor . Maka kita akan memiliki hanya untuk menyadari begin, enddan jenis iterator untuk mencapai perilaku yang diinginkan. Ini tidak terlalu sulit, tetapi sedikit memakan waktu untuk menulis.

Optimalisasi Manajemen Acara

Dalam implementasi saat ini, ketika menambah atau menghapus komponen dari suatu entitas, kami memanggil onEntityUpdatedsemua sistem. Ini agak tidak efisien karena banyak sistem tidak tertarik pada jenis komponen yang baru saja diubah.

Untuk meminimalkan kerusakan, kita dapat menyimpan pointer ke sistem yang tertarik pada tipe komponen yang ditentukan dalam struktur data, misalnya std::array<std::vector<System<ComponentCount, SystemCount>>, ComponentCount>. Kemudian, ketika menambah atau menghapus komponen, kita cukup memanggil metode onEntityUpdatedsistem yang tertarik pada komponen ini.

Himpunan bagian entitas yang dikelola oleh manajer entitas alih-alih sistem

Ide terakhir saya akan mengarah pada perubahan yang lebih luas dalam struktur perpustakaan.

Alih-alih sistem yang mengelola set entitas mereka, manajer entitas akan melakukan ini. Keuntungan dari skema semacam itu adalah bahwa jika dua sistem tertarik pada satu set komponen, kami tidak menduplikasi subset entitas yang memenuhi persyaratan ini.

Sistem dapat dengan mudah menyatakan persyaratannya kepada manajer entitas. Kemudian manajer entitas akan menyimpan semua subset entitas yang berbeda. Akhirnya, sistem akan meminta entitas menggunakan sintaksis yang serupa:

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

Kesimpulan

Sejauh ini, ini adalah akhir dari sebuah artikel tentang implementasi sistem entitas-komponen saya. Jika saya melakukan perbaikan lain, saya mungkin akan menulis artikel baru di masa depan.

Implementasi yang dijelaskan dalam artikel ini cukup sederhana: terdiri dari kurang dari 500 baris kode, dan juga memiliki kinerja yang baik. Semua transaksi direalisasi untuk waktu yang konstan (diamortisasi). Selain itu, dalam praktiknya, ia menggunakan cache secara optimal dan sangat cepat menerima dan mengembalikan entitas.

Saya harap artikel ini menarik atau bahkan bermanfaat bagi Anda.

Bacaan tambahan

Berikut adalah beberapa sumber daya yang berguna untuk studi yang lebih mendalam tentang pola entitas-komponen-sistem:

• Michelle Kayney, penulis entt , menulis serangkaian artikel yang sangat menarik tentang entitas-komponen-sistem yang disebut ECS bolak-balik .
• Entity Systems Wiki berisi informasi dan tautan yang sangat berguna.