Dobule Dispatch und Alternativen

CStoll

Ja, ich schlage dir einen Blick in unser Magazin vor

bzgl der kollision von flächen:

Es wird ein 2d spiel und bisher verwenden wir ausschließlich an den axen ausgerichtete (soll heißen nicht gedrehte) rechtecke.

Aber es geht hier weniger um das FINDEN von Kollisionen als um die BEHANDLUNG, also sowas wie wenn mario auf nen gegner springt, stirbt der gegner, außer wenn es sich z.B. um eine art "igel" handelt, dann braucht man eine spezialbehandlung

Danke für eure Vorschläge!
Bitte melden, falls noch jemand ne Idee hat

Ja, double dispatch ist wirklich hässlich zu implementieren und auch ziemlich überflüssig, wenn z.b. Wände nie mit Powerups kollidieren.

Wenn sich die Anzahl der Behandlungen relativ klein ist, dann schreib die 3 bis 4 if einfach hin. Wenn es viele gibt, dann mach dir so ne map < pair<objectTypeA, objectTypeB>, event >

Gast1337 schrieb:

sowas wie wenn mario auf nen gegner springt, stirbt der gegner, außer wenn es sich z.B. um eine art "igel" handelt, dann braucht man eine spezialbehandlung

Hm, lässt sich das dann nicht in die Spiellogik integrieren? Also statt

void mario::onCollide( object* Other ) {
    if ( igel* Igel = dynamic_cast<igel*>(Other) )
        this->Health -= 10;
    else
        Other->die();
}

lieber

void mario::onCollide( object* Other ) {
    if ( Other->hasSpikesOnBack() )
        this->Health -= Other->getSpikesStrength();
    else if ( Other->isDyingAtJumpOnBack() )
        Other->die();
}

?

Oder du abstrahierst die Kollisionen nochmal in z.B. "berühren", "draufspringen" usw. Eine Möglichkeit dann für die Logik in Stachelsachen:

void thing_with_spiky_back::PlayerJumpsOnYourBack( player* Player ) {
    Player->suffer( this->getSpikeStrength() );
}

class igel : public thing_with_spiky_back {
    ...
};

void mario::suffer( int Strength ) {
    if ( this->IHaveArmor )
        Strength -= this->MyArmorStrength;
    if ( ! this->IHaveAStar )
        this->Health -= Strength;
    if ( this->Health <= 0 )
        this->die();
}

Da musst du wahrscheinlich mal tabellarisch herausarbeiten, was bei welcher Aktion mit welchen Charakteren und Objekten passiert. Wenn du genug Gemeinsamkeiten findest, lässt sich das bestimmt gut zusammenfassen und in Logik gießen.

Dann gehe doch einfach noch ein wenig tiefer mit deiner Dispatchkette, dann brauchst du nur die Sonderfälle behandeln die du möchtest.
Ein Aufruf sähe dann ungefähr so aus:

a.collideWith(b);
-->
<a>
     b->WhoAreYou(this)
</a>
-->
<b>
     a->OkIam(this)
</b>
-->
<a> (in Iam)
     ...
</a>

"OkIam" Sei eine Überladene Methode für die Basisklassen und für jeden Sonderfall einer konkreten Klasse.

So oder so ähnlich kannst du deine Viecher identifizieren, ohne in allen klassen Methoden für alle anderen anbiten zu müssen, da du ja je auch eine Überladung für die Basen hast. In den Methoden für die Basen machst du dann halt das gleiche was du jetzt auch tust.

cu

In OkIam kennst du ja jetzt die konkrete klasse, falls dies erwünscht war und könntest dann natürlilch wieder irgendwas aus b aufrufen, dieses mal auch Methoden die es nur für diese Konkrete Klasse gibt z.B.

ipsec

Das mit dem Igel könnte man lösen, indem die Kollision nicht von Mario, sondern vom Monster behandelt wird:

struct Monster
{
    virtual void jumped_onto(Mario& m)
    {
        die();
    }
};

struct Igel : Monster
{
    virtual void jumped_onto(Mario& m)
    {
        m.take_damage(10);
    }
};

struct Mario
{
    void collide_with(Monster& m)
    {
        m.jumped_onto(*this);
    }
};

Mario ist es egal, auf welches Monster er springt. Lediglich vom Monster hängt es ab, wie es sich verhält (sterben, Schaden austeilen, beides etc.). Und schon gibt es kein Double-Dispatch mehr. Vielleicht gibt es bei anderen Fällen, wo das auftritt, ähnliche Lösungen.

Blöd wirds dann, wenn man neben Mario auf den Steinmenschen Igor spielen kann, der Igel zermalmt. Hier wäre es z.B. möglich, verschiedene Angriffsarten zu definieren (normaler Sprung, Sprung mit Steinhaut usw.), auf welche das Monster dann anders reagiert.
Oder man macht es mit Double-Dispatch, ich bezweifle aber, dass das hier einfacher ist.

hustbaer

@ipsec:
Der Unterschied von deiner Lösung zu Double-Dispatch ist doch nur, ob collide_with virtual ist oder nicht.
Von daher verstehe ich nicht wie eines der beiden einfacher oder weniger einfach sein soll...

Nexus

Die Loki-Bibliothek von Andrei Alexandrescu bietet Templates für Dynamic-Dispatch, diese werden im Buch Modern C++ Design entwickelt. Ist spannend zu lesen, ich hab mir auch mal was Ähnliches gebastelt

Danke für die zahlreichen Antworten.

Ich habe mich noch nicht entschieden, wie ich es langfristig löse.

Falls noch weitere Ideen da sind, bitte melden

Hallo,

ich melde mich mal wieder hierzu, weil es neuigkeiten gibt.

Im eigentlichen Programm haben wir bisher noch nichts geändert, aber wir planen, alles neu zu machen und dann wäre es gut einen geeigneten ansatz zu verwenden.
Beim neumachen soll auch unterstürzung für netzwerk mit rein, und dafür habe ich mir überlegt, dass ich die technik von virtuellen konstruktoren benutzen kann, die ich gerade bei "More Effective C++" gelesen habe.

Also sowas wie

GameObject* GameObject::CreateFromStream(istream& str)
{
   int classID;
   str >> classID;
   //switch case / kaskadierende else ifs zum erstellen eines objekts des jeweiligen typs
   //pointer auf erstelltes objekt zurückgeben
}

Für dieses vorgehen brauche ich etwas wie classID's und dann dachte ich mir, wenn ich die eh schon einführe, um objekte übers netzwerk zu kriegen, dann kann ich die ids noch gleich so designen, dass ich anhand dessen auch die basisklassen rausfinden kann und dann statt double dispatch oder dynamic cast oder ähnlichem einfach je nach classID handeln kann.

Idee für den Aufbau der classID (soll eine riesige enum werden^^) ist dann folgendes:
(GameObject ist basisklasse von allem, davon erben z.B. Enemy und Usable und davon erben wiederrum Crawler und Mushroom)
GameObject -> 1 //erste basisklasse
Enemy -> 11 //erste abgeleitete klasse der ersten basisklasse
Usable -> 12 //zweite abgeleitete klasse der ersten basisklasse
Crawler ->111 //erste konkrete klasse von ...
Mushroom -> 112 //zweite konkrete klasse von...
Also die vorderen ziffern sind dann für die basisklassen und die letzte ist für die konkrete klasse (da brauch man dann evtl. 2 ziffern).
Dann kann man durch geschickte rechnung die einzelnen stellen der zahl extrahieren und dann die basisklassen und konkrete klasse herausfinden und darauf basierend handeln.
Die Zahl für gameobjekt kann man eignetlich auch sparen, weil sowieso alles davon erbt

Ein Nachteil ist vermutlich, dass, wenn man was zur enum hinzufügt, einiges neukompiliert werden muss...

Was haltet ihr davon?
Hat das ganze sonst noch irgenwelchen großen Nachteile?
Gibt es bessere Alternativen?

GorbGorb

Ich würde ein std::bitset verwenden. Jede Klasse erhält einen Eintrag in der erwähnten enum. Dann setzt einfach jede Klasse im Kosntruktor bitset[ID] auf true.
In etwa so:

enum ClassID
{
    ...
    ANYDERIVED,
    ...
    NUMBER_OF_CLASSES
};

class Base
{
protected:
    std::bitset< NUMBER_OF_CLASSES > ids;
};
class AnyDerived
    : public Base
{
public:
    AnyDerived
    {
        ids[ ANYDERIVED ]=true;
    }
};

Danach sollte es ja sehr einfach sein, rauszufinden was in einem bestimmten Objekt alles drinsteckt.

Danke für die Antwort.
Aber würde das nicht dazu führen, dass ich wenn ich mehr als 32 klassen habe der speicherplatz höher wird, weil ein integer für die interne speicherung des bitsets nicht mehr ausreicht?
Übers netzwerk wil ich den transfer möglichst klein halten, also weiß ich nicht, ob das der beste weg ist.

Was ist eigentlich Double Dispatching? Finde da keine wirklich verstaendliche Erklaerung...

GorbGorb

[quote="Gast1337"]Danke für die Antwort.
Aber würde das nicht dazu führen, dass ich wenn ich mehr als 32 klassen habe der speicherplatz höher wird, weil ein integer für die interne speicherung des bitsets nicht mehr ausreicht?
Übers netzwerk wil ich den transfer möglichst klein halten, also weiß ich nicht, ob das der beste weg ist.[/quote]

Du hast schon Recht. Ich würde jetzt aber erst mal versuchen, das Programm fertig zu schreiben und mir erst dann Gedanken über einen int mehr oder weniger zu machen. Es ist gut möglich, dass dein Bottleneck wo ganz anders sein wird, dann wäre das hier verschwendete Zeit. Nur für den Fall würde ich dem Mechanismus, den du jetzt wählst, einen Wrapper verpassen damit du nicht viel neu schreiben müsstest.

Ich find das relativ schwierig zu erklären, was double dispatch ist.
Ich versuchs mal in kurzform:
Man will beim aufruf von überladenen methoden dafür sorgen, dass der laufzeittyp von beiden beteiligten objekten berücksichtigt wird.
Also ruft man erst eine virtuelle methode auf dem ersten objekt auf, um den laufzeittyp des ersten objekts zu ermitteln und in dieser methode ruft man eine methode auf dem anderen objekt auf um den laufzeittyp des anderen objekts zu bestimmen.
Beim zweiten aufruf übergibt man das erste objekt, dessen laufzeittyp dann bekannt ist als parameter.
Vermutlich ist das so nicht verständlich^^
Ansonsten wikipedia / google

So also ich hab mir das ganze nochmal überlegt und tendiere nun doch dazu, double dispatch zu verwenden.

Ich wollte das dann so machen:

class GameObject
{
    void initiateCollision(GameObject& obj) = 0;
    void collideWith(Enemy& enemy) = 0;
    void collideWith(Usable& usable) = 0;
    void collideWith(Player& player) = 0;

    void collideWith(Crocodile& croc); // nicht = 0!
    void collideWith(Mushroom& mushroom); //nicht = 0!
    //...
};

Also erstmal initiateCollision muss von jeder erbenden Klasse überschrieben werden und dadrin einfach machen

void XY::initiateCollision(GameObject& obj)
{
   obj.collideWith(*this);
}

Die collideWith mit den Basisklassen müssen von jedem überschrieben werden (deswegen = 0) und irgendein standardverhalten für kollision mit objekten von dieser basisklasse festlegen.

Alle anderen (mit konkreten basisklasse) sind bei GameObject nach dem muster implementiert:

void GameObject::collideWith(Crocodile& croc)
{
   collideWith(static_cast<Enemy&>(croc));
}

Ich hoffe mal, dass das so funktioniert.

Alle abgeleiteten Klassen müssen also die methoden für die Basisklassen überschreiben, alle weiteren für konkrete Klassen sind optional und werden nur überschrieben, wenn für diese klasse eine sonderbehandlung nötig ist.
Falls eine methode nicht überschrieben wird, sorgt die geerbte methode von GameObject dafür, dass die Behandlung für die Basisklasse aufgerufen wird.

Das problem dabei ist nur, dass wenn ich eine neue Klasse hinzufüge, ich bei GameObject eine neue Methode reintun muss und deswegn alle abgeleiteten Klassen neu kompilieren müssen...
Ich hab mir überlegt, evtl. alle abgeleiteten Klassen zum pImpln um das problem zu vermindern, bin mir aber nicht sicher, ob das in diesem fall möglich/angebracht ist.
Normalerweise tut man alles was zur pImpl-Klasse gehört in eine cpp-datei inkl der pImpl-Klassendefinition.
Ich würde das dann so modifizieren, dass ich die pImpl-Klassendefinition in einen eigenen header tue und 2 cpp-dateien habe, eine für die richtige klasse mit weiterleitungsmethoden und eine für die pImpl-Klasse.
Wenn ich dann die Basisklasse ändere, muss nur die "richtige" klasse die weiterleitungsfunktionen neu kompilieren und die pImpl-Klasse mit der eigentlichen logik bleibt unberührt (so zumindest habe ich mir das gedacht :-).

Was meint ihr?

Nexus

Ich finde diese Art, Double Dispatch zu implementieren, äusserst mühsam. Sie ist intrusiv und skaliert schlecht.

Es gibt auch andere Möglichkeiten, z.B. so wie es in der Loki-Bibliothek gemacht wird. Dann musst du nicht einmal die Klassen verändern. Das könnte dann ungefähr wie folgt aussehen, solche Klassen findest du ausser in Loki z.B. hier.

// Polymorphe Klassenhierarchie
class B {...};
class D1 : public B {...};
class D2 : public B {...};

// Überladene Funktionen (abgeleitete Klassen als Parameter!)
void Collision(D1& lhs, D1& rhs);
void Collision(D1& lhs, D2& rhs);
void Collision(D2& lhs, D2& rhs);

// Funktionen registrieren
DoubleDispatcher<B&> dispatcher;
dispatcher.Register<D1, D1>(&Collision);
dispatcher.Register<D1, D2>(&Collision);
dispatcher.Register<D2, D2>(&Collision);

// Aufruf
B* x = new D1;
B* y = new D2;
dispatcher.Call(*x, *y); // Collision(D1& lhs, D2& rhs)
delete x;
delete y;

Was meinst du hier mit skaliert schlecht?
Man hat doch in jedem fall 2-3 virtuelle funktionsaufrufe, also sollte die laufzeit konstant sein.

Und kann ich bei dem was du vorgeschlagen hast auch Basisklassen gleich behandeln, ohne für jede abgeleitete Klasse nen register zu machen?

Das würde einiges an arbeit sparen.

sonst braucht man n*(n+1)/2 (glaube ich) funktionen, wenn man aber nur in sonderfällen ne spezialbehandlung braucht, kann man das stark reduzieren und dann wäre es gut, wenn man auch nicht n*(n+1)/2 mal registrieren muss.

Ich werds mir auf jeden fall mal angucken.

Nexus

Beim Ansatz mit der Dispatcher-Klasse musst du symmetrische Aufrufe f(a,b) und f(b,a) nur einmal registrieren, zudem musst du nicht bei jedem neuen Dispatch-Objekt sämtliche bestehenden Klassen anpassen. Das meinte ich mit "skaliert besser": Du kannst an einer Stelle die Fälle erweitern. Die Laufzeit ist wahrscheinlich bei DoubleDispatcher etwas grösser, da zusätzlich zu den virtuellen Funktionen ein Lookup in einer Map auftritt. Sollte im Normalfall aber verkraftbar sein, gerade wenn die Funktionen selbst etwas komplexer sind.

Für die gemeinsame Behandlung von Klassen als Basisklasse ist mir bisher leider keine Lösung eingefallen, Alexandrescu hatte in seinem Buch diese Funktionalität ebenfalls weggelassen. Das Problem ist, dass die Dispatcher auf der Basis von typeid arbeiten, und in C++ gibt es keine Möglichkeit, eine Vererbungsrelation zur Laufzeit abzufragen. is_base_of aus den Type-Traits ist zwar gut, aber dazu müssen beide Klassen zur Kompilierzeit bekannt sein.

Das Ganze läuft darauf hinaus, dass man in irgendeiner Weise die Vererbungshierarchie manuell angehen muss. Wenn man Metaprogrammierung sinnvoll einsetzt, könnte man eventuell sogar nur eine Liste von Klassen angeben, und der Compiler findet dann heraus, welche wovon erbt. Ich könnte mal etwas tüfteln, denn wie du sagst, wäre eine Derived-To-Base-Konvertierung in manchen Fällen eine enorme Erleichterung.

Nochmal zu deiner Dispatcher-Klasse.

Nehmen wir an, ich habe 99 Klassen und kollisionen zwischen diesen sind alle registriert.
Jetzt füge ich eine 100te Klasse ein.
Jetzt muss ich wirklich 99 neue einträge in die map machen (wenn wir von symmetrie ausgehen, sonst noch mehr)?

Es wäre wünschenswert noch ein "default-mapping" zu haben, dass falls ein eintrag fehlt einfach die funktion für die basisklasse aufzurufen.
Falls jemand eine Idee hat, wie das zu bewerkstelligen ist, bitte her damit
Mit double dispatch ist das ja kein problem, aber dafür muss da alles neu kompilieren, wenn eine klasse dazukommt...

Beides gefällt mir nicht so recht, ich muss mich wohl für das kleiner übel entscheiden, ich bin mir nur noch nicht sicher, welches es ist