Advice on class structure in a collision detection system

Question

C++ is the first language I've used at all extensively that uses object-orientation, so I'm still a bit new to the idea. I'm trying to port a game library I was working on from Go (which uses interfaces instead of a true OOP system) to C++.

I have a collision system that uses four types: A point, a bounding, a line, and a polygon. What I'd like to do is have all of these be abstract-able into a "Collider" class and have a function that is able to take two Collider objects and test for a collision. It would look something like this:

bool Collides(Collider obj1, Collider obj2);

Originally I was thinking I could have methods for each collision type that would test for a collision given another type (i.e. methods OnPoint, OnBounding, OnLine, and OnPolygon) and then have "Collider" be a virtual class that requires all these methods, but then I realized that would be impossible in C++ because it would make classes depend on each other for compilation (right?).

I'm a little bit at a loss about what else I can do. Is my design idea a pipe dream?

Answer 1

What you want is a function which dispatches not only on the first argument, but also on the second, i.e. a double dispatch. This not directly supported in C++, but can be emulated.

class Point;
class Line;

class Collider {
public:
  virtual bool Collides(Collider const& x) const = 0;

protected:
  virtual bool Collides(Point const& p) const = 0;
  virtual bool Collides(Line const& l) const = 0;

  friend class Point;
  friend class Line;
};

class Point: public Collider {
public:
  virtual bool Collides(Collider const& x) const {
    // here, the type of this is now Point
    // now, find out what x is and call the overload on this type
    return x.Collides(*this);
  }

protected:
  virtual bool Collides(Point const& p) const {
    return false;
    // we now know that we are a point and checking vs. another point
  }

  virtual bool Collides(Line const& l) const {
    return false;
    // we now know that we are a point and checking vs. a line
  }
};

class Line: public Collider {
public:
  virtual bool Collides(Collider const& x) const {
    // here, the type of this is now Line 
    return x.Collides(*this);
  }

protected:
  virtual bool Collides(Point const& p) const {
    return false;
    // we now know that we are a line and checking vs. a point
  }

  virtual bool Collides(Line const& l) const {
    return false;
    // we now know that we are a line and checking vs. another line
  }
};

Now, checking two objects will do two runtime dispatches:

Collider* p = new Point();
Collider* l = new Line();

p->Collides(*l);
// first dynamically dispatches on p to call Point::Collides
// in Collides, this (which is p) now has the static Point. 
// now do the second dispatch on l and use *this as the parametet
// to find the overload.

This is e.g. used in the Visitor design pattern. If your set of objects is fixed, but you expect that the operations done on them is going to change or be extended, Visitor is a good choice.