[C++] Unity sistem komponenti

[Belphegor]

Posle duze pauze rek'o da se vratim malo programiranju, a vidim da je i nesto slabo aktivan ovaj deo foruma.

Imao sam priliku da probam malo Unity endzin, posto je postao veoma popularan pa rek'o da vidim i ja o cemu se radi.
Ukratko, mnogo mi se svideo njihov "component system" pa sam probao da implementiram nesto slicno sa C++-som.

Postavicu kod ovde pa cu ispod malo da izkomentarisem.

#include <iostream>
#include <string>
#include <unordered_map>
#include <type_traits>
#include <memory>
#include <cassert>
#include <vector>
#include <algorithm>


template<typename T>
struct type { static void id() { } };

template<typename T>
std::size_t type_id() { return reinterpret_cast<std::size_t>(&type<T>::id); }

class Component
{
public:
    Component() { }
    virtual ~Component() {}
};

class Transform final : public Component
{
public:
    int x, y;
    Transform(int x, int y) : x(x), y(y) {}
};

class Renderable final : public Component
{
public:
    std::string data;
    Renderable(std::string d) : data(d) {}
};

class Other final : public Component
{
public:
};

typedef std::shared_ptr<Transform>  sp_Transform;
typedef std::shared_ptr<Renderable> sp_Renderable;

class RenderSystem
{
private:

    friend class SceneManager;
    typedef std::vector< std::weak_ptr<Renderable> > t_Renderable;
    t_Renderable vRend;

    void AddRenderable(sp_Renderable r)
    {
        vRend.push_back(r);
    }

public:

    void Update()
    {
        for (std::size_t i = 0; i < vRend.size(); ++i)
        {
            if (auto sp = vRend[i].lock()) // not expired
            {
                std::cout << sp->data << std::endl;
            }
            else // component removed, swap - pop_back
            {
                std::swap(vRend[i--], vRend.back());
                vRend.pop_back();
            }
        }
    }
};

class PhysicsSystem
{
private:

    friend class SceneManager;
    typedef std::vector< std::weak_ptr<Transform> > t_Transform;
    t_Transform vTransform;

    void AddTransform(sp_Transform t)
    {
        vTransform.push_back(t);
    }

public:

    void Update()
    {
        for (std::size_t i = 0; i < vTransform.size(); ++i)
        {
            if (auto sp = vTransform[i].lock()) // not expired
            {
                sp->x += 3;
                sp->y += 7;
                std::cout << sp->x << ", " << sp->y << std::endl;
            }
            else // component removed, swap - pop_back
            {
                std::swap(vTransform[i--], vTransform.back());
                vTransform.pop_back();
            }
        }
    }
};

class GameObject;
typedef std::shared_ptr<GameObject> sp_GameObject;

class SceneManager
{
private:

    std::unique_ptr<PhysicsSystem>  psys;
    std::unique_ptr<RenderSystem>   rsys;

public:

    SceneManager()
    {
        psys = std::make_unique<PhysicsSystem>();
        rsys = std::make_unique<RenderSystem>();
    }

    sp_GameObject CreateObject()
    {
        return std::make_shared<GameObject>(this);
    }

    template < typename T >
    void EnqueueComponent(T t)
    { } // do nothing

    void Update()
    {
        psys->Update();
        rsys->Update();
    }
};

template <> // specialization for Renderable
void SceneManager::EnqueueComponent<sp_Renderable>(sp_Renderable t)
{
    rsys->AddRenderable(t);
}

template <> // specialization for Transform
void SceneManager::EnqueueComponent<sp_Transform>(sp_Transform t)
{
    psys->AddTransform(t);
}

class GameObject
{
    SceneManager* smgr;
    std::unordered_map<std::size_t, std::shared_ptr<Component>> components;
public:

    GameObject(SceneManager* s) : smgr(s) {}

    template < typename C, typename... Args >
    void AddComponent(Args&&... args)
    {
        assert("Already have that component!" && components.count(type_id<C>()) == 0);
        auto c = std::make_shared<C>(std::forward<Args>(args)...);
        smgr->EnqueueComponent(c);
        components.insert({ type_id<C>(), c });
    }

    template < typename C >
    bool HaveComponent()
    {
        return components.count(type_id<C>()) != 0;
    }

    template <typename C>
    std::shared_ptr<C> GetComponent()
    {
        assert("No such component!" && HaveComponent<C>());
        return std::static_pointer_cast<C>(components[type_id<C>()]);
    }

    template <typename C>
    void RemoveComponent()
    {
        components.erase(type_id<C>());
    }
};

int main()
{
    auto s = std::make_unique<SceneManager>();

    auto o1 = s->CreateObject();
    o1->AddComponent<Transform>(5, 9);
    o1->AddComponent<Renderable>("Hello obj1!");

    auto o2 = s->CreateObject();
    o2->AddComponent<Transform>(11, 22);
    o2->AddComponent<Renderable>("Hello obj2!");
    
    //auto z = o1->GetComponent<Other>(); // error 

    //auto r = o1->GetComponent<Renderable>();
    //auto p = o1->GetComponent<Transform>();

    s->Update();
    o1->RemoveComponent<Transform>();
    s->Update();

    return 0;
}

Skoro naletim na ovaj intersantan tred (zadnji kod tag), gde se unikatan id po tipu (kompnenti) moze dobiti na osnovu adrese funkcije oslanjajuci se na "one definition rule".
Znaci imam GameObject koji sadrzi listu unikatnih komponenti koristeci unordered_map, gde je key size_t tip (koristeci type_id funkciju iz navedenog treda) a value je shared_ptr Component (bazna klasa svih komponenti), dodavanje/pristup komponenti bi trebalo biti veoma efikasno.
Onda imam "sisteme" koji operisu na specificnim komponentama (RenderSystem, PhysicsSystem...) i SceneManager koji azurira ove sisteme i kreira objekte.
final kljucnu rec na izvedene klase sam koristio jer sam cuo da moze biti hint kompajleru da uradi devirtualizaciju a i ne ocekujem neko daljnje nasledjivanje.

Ne svidja mi se sto sam morao da embedujem pokazivac na SceneManager u sam GameObject jer moram nekako da ubacim komponente i u sisteme, a ne bih da menjam "sintaksu" koriscenja ovog sistema.
Da li vidite neki fejl u kodu, da li ste radili nesto slicno, imate neke predloge?

Posto sam radio u VS 2013 okruzenju, a zna se da VS nije uvek u saglasnosti sa c++ standardom, moze da se desiti da kod ne bude radio sa drugim kompajlerima.

[Andross]

Zezah se ja sa tim prosle godine, kod sam brisnuo sa harda ali je ostala neka pocetna verzija na SFML forumu, mozes proci kroz taj thread: http://en.sfml-dev.org/forums/index....75815#msg75815

[Geomaster]

Ovde je dat interesantan (doduše kratak) pregled kako se sistem baziran na komponentama može integrisati u data-oriented dizajn endžina (za više o data-oriented dizajnu, evo ga jedan moj tekst koji bi (kao) trebalo da bude dobar uvod). Evo i nešto malo duže na sličnu temu. Nisam siguran koliko je relevantno, samo dodajem ono što sam ja čitao o tome

Što se kôda tiče, @Belphegor, sintaksa mi deluje baš fino, posebno sa AddComponent<T> i bratijom. I sviđa mi se korišćenje C++11, baš kôd postaje primetno lepši i lakše se rade neke stvari. Ne znam jesi li razmišljao da implementiraš neki event dispatch sistem između ovih različitih komponenti, ali bilo bi zanimljivo da mogu da šalju poruke međusobno. Npr. entitet koji predstavlja NPC može da ima AI komponentu koja može da odgovara na eventove tipa "collision" iz physics komponente. U svakom slučaju, ako hoćeš, možeš da pogledaš neko rešenje za delegate (kao u C#-u), mogu da budu brži od virtuelnih funkcija, boilerplate je mnogo manji i kôd na kraju ispadne lepši (bar meni). Ovde sam nešto piskarao o tome (ignorisati nesmešne opaske i klinačke komentare), evo ga i kôd za te Delegate klase. Nije gotov, i verujem da s nekom metaprogramming mađijom može da se sredi da sintaksa bude još lepša, ali kapiram da je fina referenca.

delegate.h

template<typename R, typename... Args>
class Delegate<R(Args...)> {
public:
  Delegate() : mObject(nullptr), mStub(nullptr)
  {

  }
  Delegate(const Delegate& Other) = default;

  Delegate& operator=(const Delegate& Other) = default;

  R operator()(Args... Arguments)
  {
    return (*mStub)(mObject, Arguments...);
  }

  template<class T, R (T::*Method)(Args...)>
  static Delegate fromMethod(T* Object)
  {
    Delegate d;
    d.mObject = Object;
    d.mStub = &methodStub<T, Method>;

    return d;
  }

protected:
  typedef R (*Stub)(void* Object, Args...);

  void* mObject;
  Stub mStub;

  template<class T, R (T::*Method)(Args...)>
  static R methodStub(void* Object, Args... Arguments)
  {
    return (static_cast<T*>(Object)->*Method)(Arguments...);
  }
};

eventsource.h

template<typename T> std::vector<T> Vector;
template<typename K, typename V, blablabla> std::map<K, V, blablabla> Map;

template<typename... Args>
class EventSource {
public:
  typedef uint Handle;

  Handle addHandler(const Delegate<void(Args...)>& Handler)
  {
    Handle nh = mNextHandle++;
    mHandlers.push_back(Handler);
    mHandleMap[nh] = mHandlers.size() - 1;

    return nh;
  }

  void removeHandler(Handle H)
  {
    typename HandleMap::iterator it = mHandleMap.find(H);
    if (it == mHandleMap.end())
      throw exceptions::NoSuchEventHandler(H);

    typename HandlerList::size_type i = it->second, last = mHandlers.size() - 1;
    std::swap(mHandlers.at(i), mHandlers.back());
    mHandlers.pop_back();

    for (auto& p : mHandleMap)
      if (p.second == last) {
        p.second = i;
        break;
      }
  }

  void clearHandlers()
  {
    mHandlers.clear();
  }

  void fire(Args... Arguments)
  {
    for (auto& d : mHandlers)
      d(Arguments...);
  }

protected:
  typedef Vector<Delegate<void (Args...)>> HandlerList;
  typedef Map<Handle, typename HandlerList::size_type> HandleMap;

  HandlerList mHandlers;
  HandleMap mHandleMap;
  Handle mNextHandle;
};

Dakle fora je da jednostavno emiteri ponude EventSource klasu i ti njoj samo zakačiš svoj delegat kad hoćeš da se subscribe-uješ na evente (i posle ga otkačiš kad ti ne treba više, razume se). Onda emiteri pozivaju fire(...) i svi registrovani delegati bivaju pozvani. Zato što nema nikakav setup overhead u kôdu, možeš da nudiš EventSource za svaki tip eventa, ili da napraviš neku klasu koja sadrži grupu takvih emitera, pa da nju ponudiš iz komponente... Ne znam kako bi se to uklopilo u tvoj komponentski sistem, ali eto, neka ga tu, nek bleji. Izvinjavam se za off, ovo su samo neke ideje koje sam ja nekad imao i koje bih voleo da zažive u nekom obliku, pa ih poturam ljudima

[Belphegor]

Hvala za linkove.

Imam jedno pitanje u vezi "branch mispredictions" koje si pomenu u blogu, vezano za ovaj kod:

void MyEngine::queueRenderables()
{
  for (auto it = mRenderables.begin(); it != mRenderables.end(); ++it) {
    if ((*it)->isVisible()) {
       queueRenderable(*it);
  }
}

Citao sam o tome i ranije ali ne vidim kako zaobici ovaj problem?
Mogao bih uraditi nesto ovako kao preproces:

auto endVisible = std::partition(std::begin(vRenderable), std::end(vRenderable), [](R r){ return r.visible; });

for_each(beg, endVisible, [](R r){queueRenderable(r);});

Ali da li se uopste isplati? Jer bih morao onda da sortiram ili da pravim novu listu.

EDIT: nvm. Mislim da ovo objasnjava.

[Geomaster]

std::рartition bi učinio više štete nego koristi, cenim. Moja poenta je bila da možeš da držiš listu trenutno vidljivih entiteta, i samo kroz nju prođeš. Kada treba da sakriješ entitet, izbaciš ga iz te liste, kad treba da se ponovo pojavi, opet ga ubaciš, dakle sem glavnog skupa entiteta na sceni držiš i još jednu strukturu koja ti govori koji su trenutno vidljivi. Tako imaš implicitni boolean (da li je u listi vidljivih ili ne?) umesto eksplicitan (Entity::mVisible). Ako skroz izbaciš taj visibility boolean, onda je isVisible sporiji od O(1), ali koliko često uhvatiš sebe da ti stvarno treba da li je neki entitet vidljiv ili ne? Sve ovo je poenta existence-based procesinga, objašnjeno, npr. ovde.

[Belphegor]

Kada treba da sakriješ entitet, izbaciš ga iz te liste...

Gde opet imam brancovanje, jer moram testirati da bi znao da li treba da se izbaci iz liste.
No otom-potom, nista bez profilisanja, probacu vise stvari pa cu proceniti sta mi odgovara.

[Geomaster]

Da, ali sakrivanje entiteta se dešava mnogo, mnogo ređe nego prolaženje kroz sve vidljive entitete (što se verovatno dešava više puta u toku jednog frejma). Nije poenta da se izbaci svako grananje, poenta je da se izbace ona grananja koja se dešavaju dovoljno često i dovoljno su teška za predikciju da bi njihovo izbacivanje uopšte napravilo neku razliku. Zato nije efektivno izbaciti grananja samo u toj queueRenderables metodi (npr.) nego je potrebno naći sve takve delove i refaktorisati ih, i onda će generalno sve početi da radi brže. Pogledaj review fajla OgreNode.cpp koji je uradio Majk Ekton, tu se baš vide neki dobri kandidati za refaktorisanje, imaš link na kraju onog mog Tuts+ posta.

[Belphegor]

Nisam stigao ranije da pogledam tvoj kod (implementacija bazirana na kodu Sergey Ryazanov-a ?).

Ovo mi nije jasno sta si radio?

template<typename R, typename... Args>
class Delegate<R(Args...)>
...

Iskasapio sam malo ovu Delegate klasu, gde drzim direktno pokazivac na metodu umesto fukcije, a i ne vidim zasto bi koristio void* ako imam tip objekta.

template<typename T, typename R, typename... Args>
class Delegate
{
private:
    typedef T* t_pointer;
    typedef R(T::*t_method)(Args...);

    t_pointer m_object;
    t_method  m_pmethod;

public:

    Delegate(t_pointer obj, t_method m)
        : m_object(obj), m_pmethod(m)
    {}

    Delegate(const Delegate& Other) = default; // delete
    Delegate& operator=(const Delegate& Other) = delete;

    R operator()(Args&&... args)
    {
        return (m_object->*m_pmethod)(std::forward<Args>(args)...);
    }
};
...
SomeClass s;
    auto d = Delegate<SomeClass, void, int, double>(&s, &SomeClass::Fun);

Gde sam prvi put naleteo na jedan snag, ne razumem zasto mu treba copy konstruktor ako ga ne poziva nigde?

[Geomaster]

Ne razumem ovo što si uradio. Možda je do toga što sam dočekao 7 sati budan, doduše, ali bi svejedno valjalo da mi razjasniš

Dodao si template parametar za tip klase kojoj pripada metod u Delegate klasu da bi mogao da držiš pointer-to-method, ali sada su ti delegati, koliko sam ja shvatio, neupotrebljivi za ono za šta sam ih ja koristio. Da bi ih koristio za bilo kakav publish-subscribe pattern, moraju svi delegati s istim argumentima da imaju isti tip. Moju EventSource klasu sada ne možeš da implementiraš, jer ne možeš da napraviš vektor delegata, jer su svi različitog tipa. Poenta mojih delegata i event sistema je da možeš da uradiš ovo:

GameClass::nešto():

PhysicsObject *po = ...;
po->getCollisionEventSource()->addHandler(Delegate<void(parametri za event, nije ni bitno)>::fromMethod <GameClass, &GameClass::handleCollision>(this));

I baš zbog toga što tip klase ne može da bude template parametar, mora da se drži void* pokazivač ka objektu i da ga onda "method stub" kastuje. Poenta je da method stub bude jedini koji zna tip klase i metod ka kome se drži pokazivač, a da ga delegat poziva pomoću pokazivača ka funkciji, čiji tip ne zavisi od tipa klase.

Nadam se da si razumeo šta sam hteo da kažem. Dakle poenta je da delegati budu templatizirani samo po potpisu funkcije koju implementiraju, da bi mogli da se svi tretiraju isto i budu pozvani "na gomili" iz event sors klase, pomoću fire(). A da bi se to uradilo, mora postojati neki kôd koji zna tačan metod i klasu koju da pozove, a taj kôd mora da bude dostupan iz klase koja ne zna ništa o tome. Dakle zato koristimo ovaj method stub (originalno, kao što rekoh, Sergej Razanov predložio) i onda pozivamo njega. To je nažalost jedan dodatni poziv ka funkciji, ali možemo da se potrudimo da to rešimo tako što se nadamo da će kompajler biti dovoljno pametan da vidi da je stub samo poziv metode objekta i ništa drugo, i onda za methodStub<T, Method>() emituje direktan poziv metode te klase ili vtable lookup + poziv metode. A konstruktor kopije se poziva recimo u EventSource::addHandler (nem pojma da l' ima još negde, mrzi me da gledam sad).

[Belphegor]

Geomaster kaže:

Ne razumem ovo što si uradio. Možda je do toga što sam dočekao 7 sati budan, doduše, ali bi svejedno valjalo da mi razjasniš

Mislio sam na onaj deo koda koji mi lici na specijalizaciju, ali onda moras imati i primarni/bazni templejt.

template ...
class Delegate <R(Args...)>

ali verovatno mi nesto fali posto to kod mene ne radi (vs 2013), a ne mogu naci ni neku dokumentaciju za ovaj primer.
Predpostavljam da je cilj da bi imao ovu sintaksu?

Foo<void(int, double)>

umesto:

Foo<void, int, double>

btw. Sta radis tako kasno nocu? Spavaj malo, neces nista posebno propustiti.

Da, da, nisam obratio paznju na EventSource klasu.

EDIT: nvm. radi

template <typename T, typename R>
class Delegate {};

template<typename T, typename R, typename... Args>
class Delegate <T, R(Args...)>

Mada bih voleo da procitam nesto vise o ovome.

[ivan90BG]

Ту синтаксу сам приметио пре неколико месеци и тражио по интернету. То је синтакса за функцијске типове. Када се напише

typedef float Potpis1(const char*, int);

није декларисан показивач на функцију, нити било какав тип који има величину у меморији. Декларисан је и именован потпис функције. Ако се као тип параметра неке функције наведе Potpis1 то је као да је декларисан показивач на функцију као параметар.

float uradiNesto(Potpis1 func) {
    return func("blabla", 42);
}

Али ако се декларише члан класе овог типа то је исто као да је декларисана метода са тим потписом:

struct A {
    Potpis1 metoda;
};
float A::metoda(const char* str, int num) {
    //...
}
int main() {
    A a;
    a.metoda("bla bla", 42);
}

Али ово не ради ако је тип добијен као темплејт аргумент. Следећи код ће проузроковати компајлерску грешку при инстанцирању темплејта:

template<typename T> struct B {
    T clan;
};
int main() {
    B<void()> b;
    b.clan();
};

Није могуће да се из темплејт параметра на овај начин узме потпис методе јер нема начина да се дефинише тело методе. Једино је могуће помоћу форе са парцијалном специјализацијом за екстрактовање елемената потписа из темплејт аргумента, коју је Belphegor написао.

[Geomaster]

Da, možda valja napomenuti da sam ja sav ovaj kôd koji sam postavio ovde morao da kompajliram GCC-om, jer VS2013 (u to vreme, verovatno je sad bolja situacija) nije razumeo dobar deo C++11, čak i sa onim apdejtom za kompajler. Doduše ionako sam više sreće imao sa GCC-om i njegovim toolchainom tako da mi nije žao. ivan90BG je dobro objasnio funkcijske tipove kao template parametre, nemam šta da dodam. Znam da se pod GCC-om kompajlovalo bez problema za unit test kôd i prolazilo sve testove. Nemoj mnogo da veruješ VS-u, mene je znao opasno da opeče. I i dalje mi nije jasno zašto imaš tri mesto dva template parametra.

[Belphegor]

Geomaster kaže:

I i dalje mi nije jasno zašto imaš tri mesto dva template parametra.

Ostalo je tako kao test dok nisam provalio kako da prosledim kao "funkcijski" tip.
Ako se ne varam, ne svidja mi se to sto EventSource moze da drzi delgate samo sa istim tipovima argumenata, a i sa istim parametrima se i pozivaju.
Videcu jos, polako dok ne prostudiram i napravim nesto sto odgovara mojim potrebama.

[ivan90BG]

Istražujući davno mogućnost za implementaciju delegata u C++-u (onakvih kakvi su u .NET-u) naišao sam na ovo: http://www.codeproject.com/Articles/...stest-Possible, a evo maločas i na ovo: http://www.codeproject.com/Articles/...st-C-Delegates.

[Belphegor]

^ Zapravo Geomasterov kod se bazira na kodu sa drugog linka.

[Geomaster]

Belphegor kaže:

Ako se ne varam, ne svidja mi se to sto EventSource moze da drzi delgate samo sa istim tipovima argumenata, a i sa istim parametrima se i pozivaju.
Videcu jos, polako dok ne prostudiram i napravim nesto sto odgovara mojim potrebama.

I dalje ne shvatam zašto bi ovo bio problem. Jedan EventSource odgovara tačno jednom tipu eventa (mouse event, frame event, keyboard event, script event, bla bla bla) i ovakvi eventi po pravilu imaju iste tipove argumenata, pogledaj implementaciju recimo u Irrlicht-u, OGRE-u ili u Urho3D-u. Kada pozivaš fire() sa nekim parametrima taj event (definisan tim parametrima) se broadcastuje svima koji su trenutno subscribeovani (publish—subscribe pattern).

Ako uspeš da napraviš neke delegate koji mogu da se drže u homogenom kontejneru a da budu sličnih performansi kao ovi Sergejevi, postavi ovde, interesuje me, pošto meni ne pada nikakva ideja na pamet kako u tom slučaju izbeći dinamičku alokaciju i biti brži od recimo std::bind.

[voodoo_]

Thread hijack

Ako ste zainteresovani za eventualnu saradnju sa jednom domaćom firmom, a saradnja bi se svodila na "portovanje" njihovog postojećeg endžina na Unity, kontaktirajte me na PM.