Dobule Dispatch und Alternativen

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

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

[Gast1337]

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

[Gast1337]

Sry für Doppelpost, aber mir kommt gerade ne Idee:

Ich könnte das problem vll ungefähr so lösen:

//typedefs für kollisionsbehandlungsfunktionen für alle basisklassen
//ich weiß nicht ob die typedefs mit templates so gehen, aber sowas in der art muss doch irgendwie gehen, oder?
template <class T>
typedef void (*EnemyCollisionFunc)(T& t, Enemy& e);
template <class T>
typedef void (*PlayerCollisionFunc)(T& t, Player& p);
template <class T>
typedef void (*UsableCollisionFunc)(T& t, Usable& u);
//...

template<class T>
registerDefaultMapping(EnemyCollisionFunc<T> defaultEnemyHandlerFunc,
PlayerCollisionFunc<T> defaultPlayerHandlerFunc, UsableCollisionFunc<T> defaultUsableHandlerFunc)
{
   //gehe alle klassen durch und registriere eine default funktion
   //z.B.
   dispatcher.Register<T, Ghost>(defaultEnemyHandlerFunc);
   dispatcher.Register<T, Zombie>(defaultEnemyHandlerFunc);
   //..
   dispatcher.Register<T, Mario>(defaultPlayerHandlerFunc);
   //...
   dispatcher.Register<T, Mushroom>(defaultUsableHandlerFunc); 
   //...
   //später können spezialfälle durch neue einträge überschrieben werden
}

Sollte doch funktionieren, oder?

Das bringt mich noch zu einer anderen Frage:
Wenn ich das symmetrisch registiere, liegt es ja nah, dass ich zur behandlung eine freie funktion habe und nicht 2 memberfunktionen aufrufe.
Haltet ihr es für sinnvoll diese freie Kollisionsbehandlungsfunktionen dann in der klassen als friend zu deklarieren/definieren und dann in den freien funktionen die komplette logik zu machen, oder sollte ich memberfunktionen fürs kollidieren haben und dann in der freien handler funktion 2 memberfunktionen aufrufen?
Nochmal mit codebeispiel:
1.Variante:

//Ghost und Mario haben diese funktion als friend deklariert
void handleCollision(Ghost & g, Mario & m)
{
   //irgendne behandlung, z.B. sowas:
   g.changeDirection();
   m.takeDamage(1000);
   //evtl muss man aber auch auf private sachen zugreifen
   m.setAnimationLoop(Mario::HitByGhost);
}

2.Variante:

void handleCollision(Ghost & g, Mario& m)
{
   g.collideWith(m);
   m.collideWith(g);
}

Was haltet ihr für besser?

[Nexus]

Gast1337 schrieb:

Es wäre wünschenswert noch ein "default-mapping" zu haben, dass falls ein eintrag fehlt einfach die funktion für die basisklasse aufzurufen.

So eine Fallback-Funktion habe ich mir auch schon überlegt. Momentan kann man das auf Call-Seite erreichen, indem man die Exception bei Nicht-Finden fängt und dann selbst eine andere Funktion aufruft. Ist natürlich nicht so elegant.

Doch besonders flexibel ist der Fallback-Ansatz nicht, er kommt mir mehr wie ein verzweifelter Versuch vor, dem Derived-To-Base-Problem mindestens etwas näher zu kommen. Wenn ich eine Klassenhierarchie A -> B -> C (C am meisten abgeleitet) habe, nur B und der Fallback für A registriert ist und ich ein C übergebe, wird der Fallback aufgerufen, obwohl eigentlich B richtig wäre.

Ideal wäre wirklich, wenn man Basisfunktionen registrieren könnte, und diese automatisch aufgerufen werden, falls die abgeleitete Version nicht registriert ist. Aber ohne die ganze Klassenhierarchie nochmals manuell anzugeben scheint das nicht zu gehen, zumindest sehe ich keine Möglichkeit. Naja, vielleicht wäre das wirklich die beste Möglichkeit. Wenn jemand andere Ideen hat, nur her damit

Gast1337 schrieb:

Sollte doch funktionieren, oder?

Grundsätzlich wahrscheinlich schon, allerdings wird so eine Funktion registerDefaultMapping mühsam zu implementieren, wenn sie generisch sein soll. Dann bräuchte man wohl Typlisten.

Du könntest allerdings auch für alle Möglichkeiten ein Funktionsobjekt registrieren (z.B. std::tr1::function ), das dann intern weiterdispatcht. So kannst du während der Laufzeit die Zuordnung über einen Schalter ändern.

Gast1337 schrieb:

Was haltet ihr für besser?

Ich würde eine globale Funktion mit direkter Berechnung nehmen. Je nachdem, wie deine Klasse gekapselt ist, muss die Funktion nicht mal ein friend sein.

[Gast1337]

Danke für deine Hilfe.
Wenn ich darauf achte, dass wirklich alles registriert wird, sollte das aber eigentlich hinauen.

Eine weitere sache über die ich nachdenke ist wie ich das mit der serialisierung mache.
Wenn ich das selbst schreibe, würde ich eine enum machen, die für jede Klasse einen eintrag hat.
wird dann ein objekt serialisiert, wird zuerst ein element der enum in den stream geschrieben, dann das eigentliche objekt.
Beim Empfänger hat man dann eine map, die enum-werte auf virtuelle konstruktoren mappt (mit virtuellen konstruktoren ist sowas gemeint:

GameObject * createXY(sf::Packet & packet);

)

Das problem ist wieder:
Jede klasse muss zugriff auf die enum haben, damit man objekte der klasse "fragen" kann (virtuelle methode), welchen typ sie haben.
Also müssen alle klassen neukompilieren, wenn eine neue dazukommt...
Das wollte ich ja gerade vermeiden, deswegen überlege ich mir das ja auch mit deinem double dispatcher anstatt normalem double dispatching.

Ich habe mir boost::serialization angeguckt, aber einige sachen stören mich daran:
Die Archive sind entweder textbasiert (z.B. xml), haben also ne menge overhead, oder binär, aber dann nicht portabel (endianess ist das (haupt-)problem, denk ich mal).
Und zur Unterstützung für serialisierung von objekten durch basisklassenpointer:
Das funktioniert damit im prinzip schon, aber auch da muss man registrieren).

Evtl. kann ich das aber auch selbst mithilfe von dieser "registrierung" hinbekommen?
Ich könnte dann in einer funktion die direkt am anfang von main aufgerufen wird alle klassen registrieren und dann typeinfo auf die enum mappen zum serialisierung und die enum auf virtuelle konstruktoren mappen zum deserialisieren, oder so.

Ich überlege auch noch, ob es überhaupt sinnvoll ist, rücksicht auf sowas wie endianess zu nehmen, weil doch eigentlich eh fast alle computer auf denen man spiele spielen würde little endianess haben soweit ich weiß.

[Nexus]

Du meinst wahrscheinlich sowas?

struct B { virtual ~B() {} };
struct D1 : B {};
struct D2 : B {};
struct D3 : B {};

enum Type {d1, d2, d3};

Type GetType(D1*) { return d1; }
Type GetType(D2*) { return d2; }
Type GetType(D3*) { return d3; }

int main()
{
	SingleDispatcher<B*, Type> sd;
	sd.Register<D1>(&GetType);
	sd.Register<D2>(&GetType);
	sd.Register<D3>(&GetType);

	B* b = new D3;
	Type t = sd.Call(b);
}

Ja, das sollte gehen. Wobei du auch eine std::map<TypeInfo, Type> nehmen könntest, wobei TypeInfo ein std::type_info -Wrapper ist. Mit dem Dispatcher hättest du das halt schon fertig.

Ansonsten wäre eine Möglichkeit auch, andere IDs als ein enum zu nehmen, z.B. Strings. Klassen wären dann durch ihren Klassennamen + evtl. Namespace eindeutig. Du hast damit kleinere Abhängigkeiten, verlierst aber ein wenig Typsicherheit zur Kompilierzeit.

[Gast1337]

Funktioniert das wirklich so?
Wodurch weiß der & operator bei
&GetType, welche überladung er nehmen soll?

[Nexus]

Ja, das funktioniert und ist recht praktisch. Der Funktionszeiger ergibt sich aus dem Kontext, durch das Template-Argument bestimmen wir den Parametertypen von Register() .

Du kannst ja auch sowas machen:

void Fn(int);
void Fn();

int main()
{
	void (*fptr)(int) = &Fn;
}

[Nexus]

Ich bin momentan gerade dabei, Derived-To-Base-Konvertierungen zu implementieren. Der Benutzer muss zwar einmal manuell die Klassenhierarchie angeben, anschliessend sollten aber automatische Konvertierungen wie bei Funktionsüberladung möglich sein. Beim Double-Dispatch ist die Umsetzung allerdings nicht ganz einfach, da ich im Prinzip einen vereinfachten Algorithmus zur Überladungsauflösung schreiben muss. Und das auch noch halbwegs effizient, schliesslich darf nicht jeder Aufruf ewig dauern...

Falls du das hier liest und überhaupt noch interessiert bist, könntest du mir eine E-Mail schreiben, dann kann ich dich auf dem Laufenden halten.