Special interaction between derived objects (i.e. mutiple dispatch)

Question

So, I have a list of base class pointers:

list<Base*> stuff;

Then, at some point one of the objects will look through all other objects.

Base * obj = ...; // A pointer from the 'stuff'-list.
for (list<Base*>::iterator it = stuff.begin(); it != stuff.end(); it++)
{
    if (obj == *it)
        continue;

    // Problem scenario is here
   obj->interact(it);
}

What I want to achieve is that depending on what derived typeobj and *it are, they will interact differently with each other, i.e. DerivedA will destroy itself if it's interacting with DerivedB, but only if DerivedB has set the property bool c = true;. So something like:

struct Base 
{
    virtual void interact(Base * b); // is always called
};
struct DerivedA : public Base 
{
    virtual void interact(Base * b){} // is never called
    virtual void interact(DerivedB * b) // is never called
    {
        if (b->c)
            delete this;
    }
};
struct DerivedB : public Base 
{
    bool c = false;
    virtual void interact(Base * b){} // is never called
    virtual void interact(DerivedA * a) // is never called
    {
        c = true;
    }
};
// and many many more Derived classes with many many more specific behaviors.

At compile time, they are both Base-pointers and will not be able to call each other and expect the type to magically appear. If this was a one way relation, i.e. I knew what type of one of them, I could use the Visitor pattern. I believe I should use some kind of Mediator pattern but can't really figure out how since the mediator too will hold Base-pointers and thus it won't make a difference.

I haven't got a clue on how to continue... anyone?

---

Background:

I'm creating a game, this problem originates from the Room class who keeps track of it's contents, i.e. what GameObjects are currently in the room.

Sometimes, an object moves (for example, the player). The room will then loop over all objects that are on the soon-to-be-moved-upon floor tile (the loop above) and will check if the objects will interact with eachother.

For example, if it's a Troll the Player would want to hurt it. Or he would just like to hurt any Character (both Troll and Player are derived from Character) that originates from any another "team" (which can be accessed from the function getAlignment(), which all Characters implement).

Answer 1

First: Why do you use struct instead of class?

Second: If you use class instead of struct you could (must) do something like this:

class Base 
{
    virtual void interact(Base * b); // see the VIRTUAL word (explained down)
}; 
class DerivedA : public Base 
{
    virtual void interact(DerivedB * b)
    {
        if (b->c)
            delete this;
    }
};
class DerivedB : public Base 
{
    bool c = false;
    virtual void interact(DerivedA * a)
    {
        c = true;
    }
};

Using virtual keyword is wath you need (I guess). If you define a method as virtual you are telling "Hey! this maybe has been override someplace" so.. when you code this:

DerivedA* a = new DerivedA();
DerivedB* b = new DerivedB();
a.interact(b); // here instead of calling Base::interact(Base*) call the override method in DerivedA class (because is virtual)

EDIT:

Forget that answer.. (didn't see the comment of the virtual)

EDIT 2:

Please, see catwalk and Frerich Raabe answers.

Answer 2

Your interact() functions don't have the same signature: In the derived classes they should also be

virtual void interact(Base * b);

The virtual is optional, of course, but for clarity I'd put it in there.

To find out whether DerivedA::interact() should do something with it's parameter, you can implement another virtual functions in your base class:

virtual canDoX(Base * b);
virtual canDoY(Base * b);

Then in the derived implementations it could look like this:

// DerivedA
void interact(Base * b)
{
    if (b->canDoX() && b->c)
        delete this;
}

// DerivedB
void interact(Base * b)
{
    if(b->canDoY())
        c = true;
}

Update: Since you liked Frerich Raabe's answer, let me explain why I think my approach is a bit better.
Following his advice, one has to create an interact() method for each derived class in the base and all other derived classes that can interact with a certain class.
With my solution one would have to add methods for certain properties, that can also be combined. If you have a Troll it would return true in its canBeKilled() method. An apple canBeEaten() and a tasty wild animal canBeKilled() and then canBeEaten().
If you can combine the properties, you have to add fewer functions.

Furthermore: If the troll drank some elixir making it invulnerable for a period of time, it returns canBeKilled() == false and that's it. You don't have to check the isInvulnerable() flag in each other interacting class.

Answer 3

If you can, grab a copy of "More Effective C++", and have a look at item #31 which is about implementing multiple dispatch, which is basically what you're looking for here. Meyers discusses several approaches to the problem and their various trade-offs. (He even uses a game as an example.)

Perhaps the best advice he gives, however, is to try and redesign your code to avoid requiring this facility. In the text, a non-member function approach is also explored, which has the added bonus of eliminating the question of to which object each function describing an interaction should belong.

Answer 4

I think your problem is well discussed in Scott Meyer's Effective C++ which is like as follows:

Rule : Don't try access array of derived class objects using base class pointer -->the result would be undefined.

I will give you an example of it:

struct Base{

virtual void print() { //in base }

virtual ~Base() {} //

}

struct Derived : public Base {

virtual void print(){ //in derived }

}

void foo(Base *pBase,int N) {

for(int i=0; i<N ; i++)
   pBase[i].print(); // result will be undefined......

}

int main() {

 Derived d[5];
 foo(&d,5);

}

The reason for it such behaviour is that compiler find next elements at the jump of sizeof(Base) bytes....

I think you got my point....

Answer 5

I think your suggested idea (with the Base::interact) function is almost complete. It seems that the only missing part is this:

In your Base, you need to have all the interact overloads for the sub-types. Consider this extension to your Base structure:

struct DerivedA;
struct DerivedB;
struct Base 
{
    virtual void interact(Base * b); // *<->Base interaction
    virtual void interact(DerivedA * da); // *<->DerivedA interaction
    virtual void interact(DerivedB * db); // *<->DerivedB interaction
};

This is a painful thing about implementing double-dispatch in C++: if you add a new sub-type, you have to touch the base of the hierarchy.

Answer 6

you will need to implement all possible combinations of types interacting with each other as virtual functions on top of hierarchy. Here's an example that tests all possible interactions:

#include<iostream>
void say(const char *s){std::cout<<s<<std::endl;}
struct DerivedA;
struct DerivedB;
struct Base{
  virtual void interact(Base *b) = 0;

  virtual void interactA(DerivedA *b) = 0;
  virtual void interactB(DerivedB *b) = 0;

};
struct DerivedA : public Base 
{
  virtual void interact(Base *b){
    b->interactA( this ); 
  }
  virtual void interactA(DerivedA *b){
     say("A:A");
  }
  virtual void interactB(DerivedB *b){
     say("A:B");
  }
};
struct DerivedB:public Base{
  virtual void interact(Base *b){
    b->interactB( this ); 
  }
  virtual void interactA(DerivedA *b){
     say("B:A");
  }
  virtual void interactB(DerivedB *b){
     say("B:B");
  }
};

void interact(Base *b1,Base *b2){
  b1->interact( b2 );
}
main(){
  Base *a = new DerivedA;
  Base *b = new DerivedB();

  interact(a,b);
  interact(b,a);
  interact(a,a);
  interact(b,b);
}