Entity Component System v C++20

Zkouším navrhnout Entity Component System v využitím šablon v C++20. 

Moje setkání s ECS

Nejprve se musím přiznat, že jsem vůbec nevěděl, že něco takového existuje, takže tenhle článek nebude mít edukativní charakter, ale spíš půjde o moje pokusy-omyly. Můj zájem o vývoj v oblasti herního průmyslu skončil někdy v roce 2007, což tak nějak koresponduje s tím, že jsem opustil Bohemia Interactive Studio a nastoupil na práci vývojáře v Seznamu. A celý můj další profesní vývoj se točil kolem serverů na linuxu. Má jediná zkušenost z plnohodnotného vývoje her je právě skrze hru Brány Skeldalu. Na dalších hrách, tedy na Operation Flashpoint a Arma Assault jsem se přímo nepodílel, můj příspěvek v týmu byl ve formě nástrojů na práci s modely – příprava 3D grafiky. Přechodem do Seznamu toto padlo

Na ECS mne upozornila umělá inteligence, když jsem při portaci hry Brány Skeldalu přemýšlel o rozšíření. Je třeba říct, že v době vývoje hry jsem znal jen následující jazykové nástroje: struktury a pole struktur.  Samozřejmě jsem věděl něco o databázích, ale ty jsem považoval za velké pomalé obry, které se v efektivitě začnou vyplácet od milionu položek výše. S přechodem na C++ jsem byl plně pohlcen objektovým programováním, což z dnešního pohledu asi nebylo úplně nejšťastnější – nicméně nechci OOP úplně zatracovat. Protože předtím to byly struktury a pole struktur, potom to byly objekty, což je pořád velký krok pro programátora mého stylu. Nicméně že by existovaly jiné organizace dat mne asi hned nenapadlo.

… tedy já vím, že existují relační databáze, E-R schémata, organizace v tabulkách, 3. normální forma, atd. ale nic z toho se mi nehodilo pro hry. 

Konkrétní dotaz: Jak hra Dungeons & Dragons Online managuje herní pravidla (postavená nad DnD), které obsahuje tisíce různých abilit, atributů zbraní, stejně velké množství kouzel, ale co je hlavní, vývojáři tento systém byly schopni časem rozšiřovat a to v rámci krátkého vývojového cyklu. Protože jsem jeden čas byl vášnivý hráč tohoto MMO, tak mne to samozřejmě zajímalo a fascinovalo. 

Entity Component Systém je odpověď 

(teď nevím, jestli DDO používá přesně ECS, nebo nějakou variaci, takže mne netahejte za slovo)

Dnes už vím, že to není jediná hra, že prakticky všechny hry staví na ECS. Protože nějaká forma ECS je dnes nedílnou součástí herních engine, jako Unity a Unreal. Takže by bylo asi nošení dříví do lesa ho zde podrobně představovat (i tak to udělám). Co mne tedy spíš zajímá, jak to že jsem ho tehdy nepoužil. Protože v roce 1996 prakticky neexistoval

První použití ve hře je právě až v roce 1998 ve hře Thief: The Dark Project. Zajímavý, že ECS nebyl použit ani Operation Flashpoint až do verze Dragon Rising v roce 2007 od Codemasters. Takže proč jsem ho nepoužil, jednoduše jsem ho neznal…

Co je ECS (Entity Component System)

Pokud jde o obecné pojetí, jde o organizaci dat. Stejně jako v obecném E-R schématu, i tady jde o nějaké schéma. Nejedná se tedy o knihovnu, ani samostatně běžící server. Je to jen další alternativa třeba k OOP (k objektům). Toto schéma se skládá ze tří částí

• Entity - představuje věc, což může být cokoliv, aniž by bylo se řešilo, jaké to má vlastnosti. Entita je prakticky reprezentována jako identifikátor. Ten ale nesmí nijak napovídat typ entity. Entitou by třeba mohl být soubor v souborovém systému, jen jméno, bez přípony – ta by už definovala typ
• Component - zpravidla se jedná o popis vlastnosti, která je svázaná s entitou. V zásade určuje, že entita má nějakou vlastnost a také přímo obsahuje parametry této vlastnosti. Protože komponenty často bývají struktury (nemusí), můžeme se dál bavit o atributech komponenty. Komponenta může mít pevný formát, ale i dynamický (asociativní pole). Nicméně uvažuje se jen o jednom rozměru, vnořené struktury už nejsou komponenty v této definici. Na rozdíl od objektu komponenta nedefinuje chování
• System - představuje kolekci operací nad entitami a komponentami. Dává komponentám význam, definuje chování entit mající dané komponenty. Zpravidla je reprezentován programem, skriptem, atd.

ECS se výrazně liší od OOP. Zatímco v OOP máme objekt, jehož vlastnosti definuje třída, která poskytuje metody definující chování a tato třída může být děděna a to v případě v C++ ve vztahu N:M. Klasická představa OOP hierarchie „objekt<-živý objekt<-zvíře<-pes<-jezevčík<-můj pes“ se tady neuplatňuje. Naopak ECS víc připomíná duck typing. Entita „můj pes“ bude mít komponenty „štekot“, „pohyb“, „vrtění ocasem“, „tvar těla“,… atd… mezi nimi není žádná hierarchie. 

Typické operace, které nad ECS provádíme je zpravidla dotazy: „dej mi všechny entity, které štěkají“. Případně kombinace dotazů: „dej mi všechny entity, které štěkají, a zároveň umí vrtět ocasem“. V těchto dotazech často ani nepotřebujeme vědět konkrétní identitu entity, stačí mi, že entita má společné vlastnost. Praktičtější příklad může být: „dej mi všechny entity, které mají mesh a polohu ve scéně“. Tenhle dotaz položí engine před tím, než se rozhodne vykreslit  scénu. Jaké konkrétní entity to jsou, přitom není rozhodující, důležité jsou  hodnoty v komponentách. Všechny úlohy, které musí systém řešit, jako je třeba právě rendering, ale i herní logika nad skupinou entit se smrskne na vhodně položený dotaz

Další odlišností od OOP je, že přiřazení komponent je dynamické. Entity tak mohou získávat a přicházet o komponenty a tím měnit význam. Udělám z psa kočku tím, že mu odeberu nějaké entity a jiné mu přidám.

                     ┌──────┐ ┌──────┐ ┌──────┐
                     │ Ent- │ │ Ent- │ │ Ent- │
                     │ ti-  │ │ ti-  │ │ ti   │
┌────────────┐       │ ty 1 │ │ ty 2 │ │ ty 3 │
│            │       │      │ │      │ │      │
│  Registry  │       │      │ │      │ │      │
├──────┬─────┤    ┌────────────────────────────┐
│ id_C1│ ────┼───►│   ComponentPool<C1>        │
├──────┴─────┤    └────────────────────────────┘
│            │       │      │ │      │ │      │
│            │       │      │ │      │ │      │
│            │       │      │ │      │ │      │
├──────┬─────┤    ┌────────────────────────────┐
│ id_C2│ ────┼───►│   ComponentPool<C2>        │
├──────┴─────┤    └────────────────────────────┘
│            │       │      │ │      │ │      │
│            │       │      │ │      │ │      │
│            │       │      │ │      │ │      │
├──────┬─────┤    ┌────────────────────────────┐
│ id_C3│ ────┼───►│   ComponentPool<C3>        │
├──────┴─────┤    └────────────────────────────┘
│            │       │      │ │      │ │      │
└────────────┘       │      │ │      │ │      │

Implementace ECS v C++

Pro implementaci ECS v C++ lze použít knihovnu EnTT. 

Ale sami víte, že takhle nefunguju. Musím totiž potrénovat mozek. Mozek je totiž sval a i ve stáří ho člověk musí používat. Mně příští rok bude půl století a nerad bych zakrněl. Já se prostě nespokojím jen s tím, že něco má řešení. Já sámsi musím vyzkoušet to vyřešit!

Kromě toho, EnTT neřeší úplně všechny požadavky, které na ECS mám, například snadné propojení s C nebo se skriptovacími enginy (Dá se to, ale není to tak čitelné a intuitivní). Kromě toho EnTT je maličko bloatware, obsahuje věci, které v ECS vyloženě nepotřebuji, nebo které jsem si schopen realizovat jinak, jinou knihovnou. No a úplně na závěr, EnTT staví na C++17. Hodně staví na RTTI (runtime type information), které navíc různě ohýbá, protože se v praxi ukázalo, že jej často uživatelé ve svých projektech vypínají. S příchodem C++20 se přitom hodně věcí v jazyce změnilo a dělá se to dnes jinak a lze se obejít bez RTTI úplně(a s příchodem C++26 se můžeme těšit na další skopičiny, jako například reflexi).

Takže jsem si napsal vlastní knihovnu ECSTL. A i tady jde o header only, na šablony bohatou a constexpr kompatibilní záležitost určenou pro C++20 a výše. Zbytek článku bude hlavně o tom, jaké problémy jsem řešil a jak jsem se s tím vypořádal

Použití ECSTL

Tady je jeden lehce pitomý příklad „hello world“

#include "../ecstl/ecstl.hpp"
#include <iostream>

using namespace ecstl;

struct Greeting {
    std::string text;
};


int main() {
    Registry rg;
    Entity greeter = rg.create_entity();

    rg.set<Greeting>(greeter, {"Hello world"});

    for (const auto &[e, c1] : rg.view<Greeting>()) {
        std::cout << e << ": " << c1.text << std::endl;
    }
    return 0;
}

V příkladu zavádím Registry což je objekt, který drží celou „databázi“ všech entit a komponent. Na dalším řádku pak vytváříme entitu. Je zde reprezentovaná objektem Entity. Interně jde o automatické číslo, tohle je důležité jen při vypisování, ale jinak se prakticky s interní reprezentací nepracuje. Metodou rg.set nastavujeme komponentu Greeting právě vytvořené entitě i s hodnotou. A poslední operací je vypsání všech entit, které mají danou komponentu včetně hodnot

#1: Hello world

Komponenta = Struktura (ale ne povinně)

V tomto bodě to mám navrženo stejně jako v EntT. Předpokládáme, že komponenta je struktura. Obecně může být použit jakýkoliv běžný typ jako komponenta. Vždycky, když pracuji s komponentou, používám parametr šablony pro její specifikaci. Např.

• rg.set<C> – nastavení komponenty
• rg.emplace<C>  – nastavení komponenty emplace
• rg.get<C> – získání komponenty
• rg.remove<C> – odstranění komponenty
• rg.all_of<C> – získání všech entit komponenty
• rg.view<C…> – entity mající dané komponenty
• rg.contains<C…> – test, zda entita obsahuje komponenty

Varianty komponent

Jak jsem psal výše, řešil jsem rozšiřitelnost hry Brány Skeldalu. Tato hra je napsaná v C, a proto, pokud bych chtěl přidělat nějaké rozšíření, musel bych si napsat nějaké C API. Ovšem v C přicházím o typovou informaci. Stejný problém nastane i u skriptovacích jazyků. Například pokud bych například rozšířil ECS na Python scripting, pak budu všechny jeho implementované komponenty typy PyObject (nebo wrapper kolem PyObject), což mi v compile time nepomůže.

Knihovna EnTT toto přímo moc neřeší. Přímo pro Python se to dá dělat tak, že konečný počet komponent definuji tak, že dědím Python wrapper, každá komponenta má jinou třídu, ale naprosto stejný základ. To znamená, že musím dopředu znát komponenty které může python script používat. Vlastní komponenty (a systém) si script přidat nemůže.

 Já jsem na to šel jinak. Kromě typu lze totiž definovat i variant ID, kdy každá komponenta má variantu. Toto je volitelná funkce a pokud ji nepoužiju, všechny komponenty mají typ varianty s ID = 0. Příklad nastavení varianty pro greetera

constexpr auto anglicky = ComponentTypeID("anglicky");
constexpr auto cesky = ComponentTypeID("cesky");


Registry rg;
Entity greeter = rg.create_entity();

rg.set<Greeting>(greeter, anglicky, {"Hello world"});
rg.set<Greeting>(greeter, cesky, {"Ahoj svete"});

for (const auto &[e, c1] : rg.view<Greeting>({cesky})) {
    std::cout << e << ": " << c1.text << std::endl;
}
for (const auto &[e, c1] : rg.view<Greeting>({anglicky})) {
    std::cout << e << ": " << c1.text << std::endl;
}

Tímto způsobem mohu registrovat dvě komponenty typu Greeting na entitě, každá s jiným ID varianty. Všechny metody, které adresují komponenty tak mají ještě navíc parametr pro variantu, který je ve výchozím stavu 0 a takto lze nastavit jinou variantu.

Dotazy

Při návrhu rozhraní pro dotazy jsem se snažil maximálně se přizpůsobot existující knihovně ranges v C++ . Tato knihovna byla schválena do C++20 a povyšuje iterace a filtrace výsledků na nový level. Určitě doporučuji nastudovat. Objekt Registry tak v zásadě poskytuje přístup ke zdrojovým pohledům, které lze následně použít ve výrazech nad rozsahy (ranges)

• rg.all_of<C>(variant=0) – vytvoří pohled (ranges::view), který obsahuje všechny entity a instanci komponent pro danou komponentu C a variant variant. Výsledek se předává jako pair
• rg.view<C1,C2,C3>({v1,v2,v3}) – vytvoří pohled (ranges::view), který obsahuje všechny entity obsahující vyjmenované komponenty a instance všech zmíněných komponent. Varianty se zadávají jako inicializer list a pokud je kratší, zbytek je doplněn nulami. Pořadí uvedených komponent pak určuje pořadí ve výsledku, který se předává jako tuple, přičemž první prvek je Entity

Obě metody jsou jak v const tak v non-const variantě. V non-const variantě tak získáme referenci na obsah komponenty a ten lze měnit. Metody lze tedy použít nejen na čtení, ale i na modifikace

Typické použití je následující

for (auto &[e,c1,c2,c3] : rg.view<C1,C2,C3>({var_c1, var_c2,var_c3})) {
   //e je entity, delej cokoliv s c1,c2,c3
}

Varianty var_c1, var_c2 a var_c3 mohou být vynechány pro výchozí variantu (případně lze uvést jen některé)

for (auto &[e,c1,c2,c3] : rg.view<C1,C2,C3>()) {
   //e je entity, delej cokoliv s c1,c2,c3
}

Pokud potřebujeme výsledek dál filtrovat, lze použít ranges::filter

rg.view<C1,C2>() | std::ranges::views::filter(
       [&](const auto &item){
           return std::get<1>(item).x > 42;
});

Implementace úložiště

Efektivita ECS stojí a padá na vhodně zvoleném úložišti. To musí být optimalizované zejména pro dotazy na komponenty napříč entitami. Cílem je mít data co nejvíc u sebe a maximalizovat využít CPU cache, proto je vhodné jednotlivé komponenty entit držet ve vektoru, který alokuje lineární prostor. K tomu se nehodí použít ani std::map ani std::unordered_map.  Navíc protože se předpokládá, že komponenty mohou obsahovat vektorová data (3D engine), je seznam entit oddělen od seznamu komponent pro lepší aligmnent. Podobně funguje i flat_map z C++23, mimochodem tato šablona je dobrým kandidátem na úložiště, protože výše uvedené splňuje. Protože však se pohybuju v C++20 a mám s úložištěm ještě jiné záměry, implementoval jsem si vlastní variantu –  IndexedFlatMap

Tato implementace používá dvou vektorů a jedné hashovací tabulky. Hashovací tabulka funguje jako index. Ve vektorech jsou uložené klíče (entity) a hodnoty (komponenty). Při iteraci se prochází současně oba vektory lineárně tak jak jsou data uložena. To řeší lokalitu dat. Hashovací tabulka slouží k rychlému vyhledání komponenty podle Entity. Obsahuje entity id a index komponenty ve vektoru. 

std::unordered_map<K, std::size_t, Hasher, Equal> _index;
std::vector<K> _keys;
std::vector<V> _values;

                 ┌───┬───┬───┬───┬───────────────────┐
     Index       │E1 │E2 │E3 │E4 │                   │
(unordered_map)  │───┼───┼───┼───┼───────────────────│
                 └─┬─┴─┬─┴─┬─┴─┬─┴───────────────────┘
                   │   │   │   │
                   └──┐│   │   └─────────┐
                      │└───┼─────┐       │
                      │    └─┐   │       │
                      ▼      ▼   ▼       ▼
                ┌────────────────────────────────────┐
     Klíče      │E5  E1  E7  E3  E2  E6  E4          │
                ├────────────────────────────────────┤
     Hodnoty    │C5  C1  C7  C2  C3  C6  C4          │
                └────────────────────────────────────┘

Protože jak entity tak komponenty jsou uložené v lineárním seznamu, je iterace velice jednoduchá a rychlá

Pohledy

Pohledy (view) obsahuje komponenty, které mají společné entity. Je to podobně jako JOIN operace v SQL jazyce. Pohledy lze procházet iterátory (zpravidla fungují jako input_iterator nebo forward_iterator)

V mém případě se používá iterate-and-lookup Před zahájením iterace se vybere to uložiště pro komponenty, které má nejmenší mohutnost. Tedy pokud napíšu rg.view<C1,C2,C3>(), zjistí se, ve které komponentě z C1, C2 a C3 je nejméně entit, a ta se začne iterovat. Každá entita se pak hledá v ostatních uložištích přes hashovací tabulku. Pokud není nalezena, přeskočí se a pokračuje se další entitou

Skupiny a archetypy

Pojmenování archetyp jsem poprvé viděl v Unity. Myšlenka za archetypy je taková, že komponenty, jejichž pohled se často vytvářejí ve stejné konfiguraci by bylo vhodné držet pospolu už tako sloučené, aby se to nemuselo slučovat při každém volání znova. Tímto sloučením vznikne archetype. Unity používá archetype chunks, a jednotlivé komponenty často různě přesouvá mezi chunky podle toho, jak se zrovna používají.

V rámci zachování nějaké jednoduchosti jsem se vůbec nepokoušel něco takového replikovat, ale určitou jemnou optimalizaci jsem přeci jen zavedl. Týká se seskupování entit pro dané konfigurace pohledu tak, aby šly ve stejném pořadí. 

Optimistická lineární iterace pohledem předpokládá, že úložiště (pooly) mohou být optimalizované tak, že entity sdílející stejnou konfiguraci komponent budou ve všech těchto úložištích ve stejném pořadí. Pokud tomu tak je, hashmapa se použije jen pro první hledání a následně se prochází úložiště lineárně. Pokud je toto narušeno, pro vyhledání dalšího výsledku se použije lookup přes hashmapu. Je tedy výhodné pokud pořadí je optimalizované

Pořadí vkládání komponent - může hrát roli. Je výhodné pokud vznikají entity, které mají nějakou konfiguraci komponent, aby vznikly současně a aby přiřazení komponent proběhlo také ve stejném pořadí. Například budu vytvářet 20 entity a každá bude mít 5 komponent, pak je ideální to dělat v pořadí: „vytvořit entitu a přiřadit komponenty, vytvořit entitu a přiřadit komponenty“. Pak mohou být současně iterovány v rámci optimistické iterace.

Operace group -  je funkce rg.group<C1,C2,C3…>(), která provede interní reorganizaci komponent napříč entitami tak, aby výše uvedena optimistickou iteraci bylo možné použít. Toto není triviální operace, takže se ji vyplatí provést až na usazeném systému, a to pro všechny potřebné konfigurace komponent.

┌─────────────────────┐
│ E10 E11 E8  E3  E2  │
│ X10 X11 X8  X3  X2  │
└┬──────────────────┬─┘
 │                  │
 └───────┐          └───────┐
         │                  │
         │                  │
┌────────┼──────────────────┼─────────┐
│ E7  E5  E10 E11 E8  E3  E2  E1  E9  │
│ Y7  Y5  Y10 Y11 Y8  Y3  Y2  Y1  Y9  │
└────────────────┼──────────┼─────────┘
                 │          │
     ┌───────────┘          │
     │           ┌──────────┘
     │           │
┌────┼───────────┼────────┐
│ E22 E8  E3  E2  E17 E55 │
│ Z22 Z8  Z3  Z2  Z17 Z55 │
└─────────────────────────┘

Vím, že to není archetype, ale podle mne to pomůže. Neměřil jsem to.

Constexpr a testy

Už od počátku bylo v plánu aby celé Registry pracoval plně v constexpr. Na první pohled to moc nedává smysl, je to dynamický systém. Ale constexpr implementace umožňuje použít Registry pro výpočet jiných staticky alokovaných dat. Samotný Registry ale nejde v constexpr připravit aby se dal použít v runtime, tak daleko se svět constexpr ještě nedostal.

Druhým důvodem je agresivnější optimalizace. Constexpr výrazy dávají překladači do rukou nástroje na lepší optimalizace a výpočty, kde některé výsledky lze získat již během překladu.

A posledním důvodem jsou testy. Cílem bylo, aby testy se spouštěly během kompilace. Více o tomto způsobu testování najdete v mém článku „Nechte testovat překladač“. Shrnu jen výhody: 

Komplikace při vývoji constexpr

Ukázalo se, že C++20 uběhlo velký kus cesty k plné podpoře constexpr kompilací, ale ještě zdaleka není u cíle. Některé věci v C++20 nejde vyřešit nad STL a vyžaduje custom implementaci. To je asi největší zádrhel

• std::unordered_map není constexpr
• std::string není constexpr
• std::unique_ptr není constexpr
• std::hash není constexpr
• RTTI nejde použít v constexpr
• některé iterátory nefungují v constexpr v MSVC 17.13
• překladače GCC a MSVC 17.13 měly problém s constexpr virtuálním destruktorem
• překladač MSVC 17.13 měl problém v kombinaci union-std::pair-delete pointer a použití std::destroy_at
• std::atomic není constexpr, globální counter nefunguje v constexpr (generátor entit)

Postupné vychytávání much probíhalo přenášením částí zdrojového kódu do godbolt a překlad ve všech dnešních překladačích současně. Většinou jsem musel sáhnout po vlastní implementaci

Vznikl adresář pollyfill/ ve kterém jsem implementoval unique_ptr<T>, tato implementace je má vlastní jen pro C++20, protože od C++23 už je constexpr definován.

Stejně tak jsem definoval hash<T> pro některé typy, které v knihovně používám, typicky hash<std::string_view>, používá FNV-1a hash

Náhradu unordered_map jsem vyřešil implementací vlastní hashovací mapy s otevřenou adresací plně constexpr kompatibilní. Vzhledem k tomu, že se používá k ukládání indexu, tak tato implementace stačí. 

Náhrada RTTI

Jako náhradu RTTI jsem použil nový mechanismus generování hashe z názvu třídy. Použije se source_location což je nový objekt v C++20. Funkce current() vrací  const char * s názvem funkce, ve které se volání nachází a to včetně názvy třídy, jejíž metoda je součástí… a pokud jde o šablonu, pak místo parametru pak najdeme třídu, jejíž jméno hledáme.

Velice jednoduše se dá generovat hash z názvu třídy takto:

template<typename T>
struct ClassIdent {
    static constexpr std::string_view get_ident_string() {
        return std::source_location::current().function_name();
    }
    static constexpr std::size_t get_hash() {
        hash<std::string_view> hasher;
        return hasher(get_ident_string());
    }
};

template<typename T>
constexpr auto class_hash = ClassIdent<T>::get_hash();
template<typename T>
constexpr auto class_ident_string = ClassIdent<T>::get_ident_string();

Pohrát si s tím můžete zde:  godbolt

Závěr

Tak tohle je moje uchopení ECS v C++. Celou knihovnu najdete samozřejmě na githubu. Klidně napište, co by se dalo přidat, co jsem pochopil špatně a jaké další funkce by měla knihovna umět.