Dobule Dispatch und Alternativen

[Gast1337]

Hallo,

ich arbeite zurzeit mit einem Freund an einem Spiel, bei dem ich (mit dem bisherigen design) periodisch nach kollisionen suche und dann bei der kollisionsbehandlung je nach typ der beteiligten objekte etwas bestimmtes mache.

Also ich habe ungefähr sowas an Klassen:
- GameObject (Basisklasse für alle folgenden Klassen)
- Enemy (Basisklasse für Gegner)
- Immortal(Basisklasse für Wände/Bläcke / etc.)
- Usable (Basisklasse für Powerups etc.)
- und paar mehr...

und dann gibt es eine Reihe von konkreten Klassen, die jeweils von Enemy,Immortal,Usable oder weiteren Basisklassen ableiten.

Ich suche dann in einer Liste von GameObjects nach Kollisionen und wenn ich was finde mache ich ungefähr sowas:

a.collideWith(b); b.collideWith(a);

Und je nach typ des jeweils anderen muss dann eine von der konkreten klasse festgelegte behandlung erfolgen.

Bisher machen wir das so, dass ich für jede der Basisklassen eigene container nehme und dann dann kollisionen immer zwischen zwei containern checke und dann beim aufruf direkt die für die basisklasse überladene methode aufgerufen wird beim anderen objekt.

Alerdings erlaubt das nur spezielles verhalten für jede Basisklasse, manchmal brauch ich auch besonderes Verhalten für konkrete Klassen.

Bisher regeln wir das durch dynamic cast... allerdings finde ich das nicht besonders toll.
Also ungefähr so:

if((a = dynamic_cast<Yoshi>(b))
{
   //Spezialbehandlung für Yoshi
}

Ich kenne die Möglichkeit double dispatch zu verwenden, aber dann muss JEDE klasse eine methode für JEDE andere klasse haben, was ich nicht besonders toll finde...
Meistens sind die Behandlungen für die Basisklassen gleich.
Dann hab ich mir noch überlegt, man kann sich ne virtuelle methode machen, wie
getTypeId() oder die eingebauten typeinfos oder so verwenden und dann maps verwenden um auf die funktionen zu mappen.
So richtig hat mich das aber auch nicht überzeugt...

Hat jemand Vorschläge?

[volkard]

Gast1337 schrieb:

Hat jemand Vorschläge?

Mein Vorschlag: Einfach beim normalen Double Dispatching bleiben.

Aber Du wirst mecp lesen wollen. Da läßt er sich in aller Ausführlichkeit zu diesem Themenkomplex aus.
http://www.amazon.de/Effektiv-programmieren-Verbesserung-Programme-Entwürfe/dp/3827312752

[Vorschläger]

Double-Dispatching ist doch schon ganz gut. Höchstwahrscheinlich kannst du da aber gut was reduzieren, z.B. steckst du die Kollisionen in die (oder spezielle) Formen und nicht in die Spielobjekte.

In typischer 3D-Umgebung hat man ja Flächen (Ebenen, rechteckige, radiale, ...), Polygonnetze und geometrische Körper; dann per Komposition auch Zusammengesetztes. Hier musst du dann "nur noch" die einzelnen Formen kollidieren lassen (also Fläche<->Polygonnetz, Kugel<->Quader, ...), das ist noch handhabbar per Double-Dispatching.

[CStoll]

Ja, ich schlage dir einen Blick in unser Magazin vor

[Gast1337]

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

[theearthfenomina]

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 >

[Vorschläger]

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.

[Ka-Mensch]

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

[Ka-Mensch]

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

[Gast1337]

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

[Gast1337]

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.

[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.

[Frager..]

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.

[Gast1337]

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;

[Gast1337]

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.