Double dispatch in C++ not working

Question

I'm writing a rogue-like game in C++ and have problems with double dispatch.

   class MapObject {
        virtual void collide(MapObject& that) {};
        virtual void collide(Player& that) {};
        virtual void collide(Wall& that) {};
        virtual void collide(Monster& that) {};
    };

and then in derived classes:

void Wall::collide(Player &that) {
    that.collide(*this);
}

void Player::collide(Wall &that) {
    if (that.get_position() == this->get_position()){
        this->move_back();
    }
}

And then I try to use the code:

vector<vector<vector<shared_ptr<MapObject>>>> &cells = ...

where cells is created like:

objs.push_back(make_shared<Monster>(pnt{x, y}, hp, damage)); //and other derived types
...
cells[pos.y][pos.x].push_back(objs[i]);

And when I try to collide player and wall:

cells[i][j][z]->collide(*cells[i][j][z+1]);

The player collides with the base class, but not with the wall. What am I doing wrong?

Answer 1

This is more complex than just solving your problem. You are doing manual double dispatch, and you have bugs. We can fix your bugs.

But the problem you have isn't your bugs, it is the fact you are doing manual double dispatch.

Manual double dispatch is error prone.

Every time you add a new type, you have to write O(N) new code, where N is the number of existing types. This code is copy-paste based, and if you make mistakes they silently continue to mis-dispatch some corner cases.

If you continue to do manual double dispatch, you'll continue to have bugs whenever you or anyone else modifies the code.

C++ does not provide its own double dispatch machinery. But with c++17 we can automate the writing of it

---

Here is a system that requires linear work to manage the double dispatch, plus work for each collision.

For each type in the double dispatch you add a type to pMapType. That's it, the rest of the dispatch is auto-written for you. Then inherit your new map type X from collide_dispatcher<X>.

If you want two types to have collision code, write a free function do_collide(A&,B&). The one easier in the pMapType variant should be A. This function must be defined before both A and B are defined for the dispatch to work.

That code gets run if either a.collide(b) or b.collide(a) is run, where A and B are the dynamic types of a and b respectively.

You can make do_collide a friend of one or the other type as well.

Without further ado:

struct Player;
struct Wall;
struct Monster;

using pMapType = std::variant<Player*, Wall*, Monster*>;

namespace helper {
  template<std::size_t I, class T, class V>
  constexpr std::size_t index_in_variant() {
    if constexpr (std::is_same<T, std::variant_alternative_t<I, V>>{})
      return I;
    else
      return index_in_variant<I+1, T, V>();
  }
}
template<class T, class V>
constexpr std::size_t index_in_variant() {
  return helper::index_in_variant<0, T, V>();
}

template<class Lhs, class Rhs>
constexpr bool type_order() {
  return index_in_variant<Lhs*, pMapType>() < index_in_variant<Rhs*, pMapType>();
}

template<class Lhs, class Rhs>
void do_collide( Lhs&, Rhs& ) {
  std::cout << "Nothing happens\n";
}

struct MapObject;
template<class D, class Base=MapObject>
struct collide_dispatcher;

struct MapObject {
  virtual void collide( MapObject& ) = 0;

protected:
  template<class D, class Base>
  friend struct collide_dispatcher;
  virtual void collide_from( pMapType ) = 0;

  virtual ~MapObject() {}
};

template<class D, class Base>
struct collide_dispatcher:Base {
  D* self() { return static_cast<D*>(this); }
  virtual void collide( MapObject& o ) final override {
    o.collide_from( self() );
  }
  virtual void collide_from( std::variant<Player*, Wall*, Monster*> o_var ) final override {
    std::visit( [&](auto* o){
      using O = std::decay_t< decltype(*o) >;
      if constexpr( type_order<D,O>() ) {
        do_collide( *self(), *o );
      } else {
        do_collide( *o, *self() );
      }
    }, o_var );
  }
};

void do_collide( Player& lhs, Wall& rhs );
void do_collide( Player& lhs, Monster& rhs );
struct Player : collide_dispatcher<Player> {
  friend void do_collide( Player& lhs, Wall& rhs ) {
    std::cout << "Player hit a Wall\n";
  }
  friend void do_collide( Player& lhs, Monster& rhs ) {
    std::cout << "Player fought a Monster\n";
  }
};

void do_collide( Wall& lhs, Monster& rhs );
struct Wall : collide_dispatcher<Wall> {
  friend void do_collide( Wall& lhs, Monster& rhs ) {
    std::cout << "Wall blocked a Monster\n";
  }
};
void do_collide( Monster& lhs, Monster& rhs );
struct Monster : collide_dispatcher<Monster> {
  friend void do_collide( Monster& lhs, Monster& rhs ) {
    std::cout << "Monster Match!\n";
  }
};

Live example.

While the plumbing here is complex, it does mean that you aren't manually doing any double-dispatching. You are just writing endpoints. This reduces the number of places you can have corner-case typos.

Test code:

int main() {
  MapObject* pPlayer = new Player();
  MapObject* pWall = new Wall();
  MapObject* pMonster = new Monster();

  std::cout << "Player:\n";
  pPlayer->collide(*pPlayer);
  pPlayer->collide(*pWall);
  pPlayer->collide(*pMonster);

  std::cout << "Wall:\n";
  pWall->collide(*pPlayer);
  pWall->collide(*pWall);
  pWall->collide(*pMonster);

  std::cout << "Monster:\n";
  pMonster->collide(*pPlayer);
  pMonster->collide(*pWall);
  pMonster->collide(*pMonster);
}

Output is:

Player:
Nothing happens
Player hit a Wall
Player fought a Monster

Wall:
Player hit a Wall
Nothing happens
Wall blocked a Monster

Monster:
Player fought a Monster
Wall blocked a Monster
Monster Match!

You could also create a central typedef for std::variant<Player*, Wall*, Monster*> and have map_type_index use that central typedef to determine its ordering, reducing the work to add a new type to the double dispatch system to adding a type at a single location, implementing the new type, and forward declaring the collision code that is supposed to do something.

What more, this double dispatch code can be made inheritance friendly; a derived type from Wall can dispatch to Wall overloads. If you want this, you have to make collide_dispatcher method overloads non-final, allowing SpecialWall to reoverload them.

This is c++17, but current versions of every major compiler now supports what it needs. Everything can be done in c++14 or even c++11 but it gets much more verbose and may require boost.

While it takes a linear amount of code to define what happens, the compiler will generate a quadratic amount of code or static table data to implement the double dispatch. So take care before having 10,000+ types in your double dispatch table.

---

If you want MapObject to be concrete, split off the interface from it and remove final from the dispatcher and add MapObject to pMapType

struct Player;
struct Wall;
struct Monster;
struct MapObject;

using pMapType = std::variant<MapObject*, Player*, Wall*, Monster*>;

namespace helper {
  template<std::size_t I, class T, class V>
  constexpr std::size_t index_in_variant() {
    if constexpr (std::is_same<T, std::variant_alternative_t<I, V>>{})
      return I;
    else
      return index_in_variant<I+1, T, V>();
  }
}
template<class T, class V>
constexpr std::size_t index_in_variant() {
  return helper::index_in_variant<0, T, V>();
}

template<class Lhs, class Rhs>
constexpr bool type_order() {
  return index_in_variant<Lhs*, pMapType>() < index_in_variant<Rhs*, pMapType>();
}

template<class Lhs, class Rhs>
void do_collide( Lhs&, Rhs& ) {
  std::cout << "Nothing happens\n";
}

struct collide_interface;
template<class D, class Base=collide_interface>
struct collide_dispatcher;

struct collide_interface {
  virtual void collide( collide_interface& ) = 0;

protected:
  template<class D, class Base>
  friend struct collide_dispatcher;
  virtual void collide_from( pMapType ) = 0;

  virtual ~collide_interface() {}
};

template<class D, class Base>
struct collide_dispatcher:Base {
  D* self() { return static_cast<D*>(this); }
  virtual void collide( collide_interface& o ) override {
    o.collide_from( self() );
  }
  virtual void collide_from( pMapType o_var ) override {
    std::visit( [&](auto* o){
      using O = std::decay_t< decltype(*o) >;
      if constexpr( type_order<D,O>() ) {
        do_collide( *self(), *o );
      } else {
        do_collide( *o, *self() );
      }
    }, o_var );
  }
};

struct MapObject:collide_dispatcher<MapObject>
{
    /* nothing */
};

live example.

as you want Player to descend from MapObject you have to use the Base argument of collide_dispatcher:

void do_collide( Player& lhs, Wall& rhs );
void do_collide( Player& lhs, Monster& rhs );
struct Player : collide_dispatcher<Player, MapObject> {
  friend void do_collide( Player& lhs, Wall& rhs ) {
    std::cout << "Player hit a Wall\n";
  }
  friend void do_collide( Player& lhs, Monster& rhs ) {
    std::cout << "Player fought a Monster\n";
  }
};

void do_collide( Wall& lhs, Monster& rhs );
struct Wall : collide_dispatcher<Wall, MapObject> {
  friend void do_collide( Wall& lhs, Monster& rhs ) {
    std::cout << "Wall blocked a Monster\n";
  }
};
void do_collide( Monster& lhs, Monster& rhs );
struct Monster : collide_dispatcher<Monster, MapObject> {
  friend void do_collide( Monster& lhs, Monster& rhs ) {
    std::cout << "Monster Match!\n";
  }
};

Answer 2

Looks like small mistake.

if (that.get_position() == this->get_position())

This is never true. What is more I think You don't need it but this is not a question. I think You need to change this line

cells[i][j][z]->collide(*cells[i][j][z+1]);

into

player[i][j][z+1]->collide(*cells[i][j][z+1]);

And player will hit the wall.

Answer 3

Your base class should be:

class MapObject {
public:
    virtual ~MapObject () = default;
    virtual void collide(MapObject& that) = 0; // Dispatcher

    virtual void collide(Player& that) = 0;  // Both types known
    virtual void collide(Wall& that) = 0;    // Both types known
    virtual void collide(Monster& that) = 0; // Both types known
};

and your Player class should be something like:

class Player {
public:
    void collide(MapObject& that) override { that.collide(*this); } // dispatch done,
                                                        // call true virtual collision code

    // Real collision code, both types are known
    void collide(Player& that) override  { PlayerPlayerCollision(*this, that);}
    void collide(Wall& that) override    { PlayerWallCollision(*this, that);}
    void collide(Monster& that) override { MonterPlayerCollision(that, this);}
};

If your base class is not abstract and mean to have its own collision, then you have to rename to differentiate dispatcher from true collision code:

class MapObject {
public:
    virtual ~MapObject () = default;
    virtual void collide_dispatcher(MapObject& that) { that.collide(*this); }

    // Real collision code, both types are known
    virtual void collide(MapObject& that) { MapObjectMapObjectCollision(*this, that);}
    virtual void collide(Player& that)    { MapObjectPlayerCollision(*this, that);}
    virtual void collide(Wall& that)      { MapObjectWallCollision(*this, that); }
    virtual void collide(Monster& that)   { MapObjectMonsterCollision(*this, that); }
};

and your Player class should be something like:

class Player {
public:
    virtual void collide_dispatcher(MapObject& that) { that.collide(*this); }

    // Real collision code, both types are known
    void collide(MapObject& that) override { MapObjectPlayerCollision(that, *this);}
    void collide(Player& that) override    { PlayerPlayerCollision(*this, that);}
    void collide(Wall& that) override      { PlayerWallCollision(*this, that);}
    void collide(Monster& that) override   { MonterPlayerCollision(that, this);}
};