C++ convert base class pointer to derived class, without knowing derived class

Question

I have various types of collider classes (SphereCollider, AABBCollider etc), all inheriting from the base class Collider. I store them using a pointer to the base class in a std::vector.

std::vector<std::shared_ptr<Collider>> colliders;

I then have various functions to work out whether the colliders are intersecting each other or not.

bool Colliding(const SphereCollider& colliderOne, const SphereCollider& colliderTwo);
bool Colliding(const AABBCollider& colliderOne, const AABBCollider& colliderTwo);
bool Colliding(const AABBCollider& colliderOne, const SphereCollider& colliderTwo);
bool Colliding(const SphereCollider& colliderOne, const AABBCollider& colliderTwo);

My idea was to simply iterate through the collider vector, and then compare each collider to the all the others in the list.

for (unsigned int a = 0; a < colliders.size(); ++a)
{
    for (unsigned int b = a + 1; b < colliders.size(); ++b)
    {
        // Store the two colliders we're current comparing
        std::shared_ptr<Collider> colliderOne = colliders[a];
        std::shared_ptr<Collider> colliderTwo = colliders[b];

        // Somehow cast pointers back to correct derived type

        // Check colliding
        if(Colliding(*colliderOneDerived, *colliderTwoDerived))
        {
            // Colliding
        }

    }
}

However to do this successfully, I would need to convert the pointers back to the correct derived type so that the correct function is called, but I do not know what type the collider will be each time.

The base collider class has a Type() function, which correctly returns the derived type from the base pointer.

std::type_index Collider::Type() { return typeid(*this); }

Is there a way I can use this to cast the pointer to the correct derived type?

Answer 1

What you want to do is called double dispatch which is not natively supported by C++. Here are a few options you might consider:

You could implement it with virtual functions which would mean adding virtual functions taking an object of every type to every object. This would result in a comparatively fast look up but the effort to implement it grows quadratically.

class Obj1;
class Obj2;

class Base{
    virtual bool collide(Base* p ) =0;
    virtual bool collide(Obj1*) = 0;
    virtual bool collide(Obj2*) = 0;
};

class Obj1{
    virtual bool collide(Base* p) override { return p->collide(this); }
    virtual bool collide(Obj1* p) override { return colliding(p,this); }
    virtual bool collide(Obj2* p) override;
};

class Obj2{
    virtual bool collide(Base* p) override { return p->collide(this); }
    virtual bool collide(Obj1* p) override { return colliding(p,this); }
    virtual bool collide(Obj2* p) override { return colliding(p,this); }
};

bool Obj1::collide(Obj2* p) override { return colliding(p,this); }

You could also use the Visitor pattern for much the same effect.

You could add one virtual function to each object returning the typeid of the object and make a sorted flat map of function pointers indexed by a pair of std::type_index. This would allow greater flexibility because you could add objects to the map in multiple places in your project.

You could add a unique constexpr index to each object, have a virtual function in each which returns this index and make a meta program which generates a look up table from a list of objects at compile time. This would be almost as fast as my fist example but would only require one virtual function per object and for all object types to be known at one point in the program. The user would be responsible for the uniqueness of the index but double indexes could be detected by the meta program reducing the change of error.

Answer 2

Use dynamic_pointer_cast to get a shared pointer on the derived class. The returned pointer will be nullptr if the derived class is of the wrong type.

std::shared_ptr<SphereCollider> sc = std::dynamic_pointer_cast<SphereCollider>(colliderOne);

sc will be nullptr if colliderOne is not of type SphereCollider. Otherwise it will point to the SphereCollider.

By using this method you can implement your dynamic dispatching.

UPDATE:

Here is an example how you would implement the dynamic dispatch using the smart pointer downcast.

std::shared_ptr<SphereCollider> sc1, sc2;
std::shared_ptr<AABBCollider> aabc1, aabc2;
...

if (sc1 = std::dynamic_pointer_cast<SphereCollider>(colliderOne))
{
    if (sc2 = std::dynamic_pointer_cast<SphereCollider>(colliderTwo))
        Colliding(*sc1, *sc2);
    else if (aabc2 = std::dynamic_pointer_cast<AABBCollider>(colliderTwo))
        Colliding(*sc1, *aabc2);
    ...
}
else if (aabc1 = std::dynamic_pointer_cast<AABBCollider>(colliderOne))
{
    if (sc2 = std::dynamic_pointer_cast<SphereCollider>(colliderTwo))
        Colliding(*aabc1, *sc2);
    else if (aabc2 = std::dynamic_pointer_cast<AABBCollider>(colliderTwo))
        Colliding(*aabc1, *aabc2);
    ...
}
...

Optimizing the dynamic dispatch by using a hash table

If you have many different types of Collider classes, the above code might not be very efficient. It performs a linear seach in the classes to perform the dispatching.

By adding a field to the Collider classes that return the class name, you could concatenate the two class names to build a key. You would then use an std::unordered_map with a lambda as associated value. The lambda would receive the two std::shared_ptr<Collider> as argument. It would do the down cast and call the Collider function.

I'll show the code if you need it.

Answer 3

Another way is to move your Colliding functions into the classes and use the Double Dispatch method to resolve the dynamic types.

This works in case of c1.collideWith(c2); as follow:

1. c1 is a reference and thus resolved to its dynamic type (here: SphereCollider). Therefore the method SphereCollider::collideWith(Collider& c ) gets called.

2. To also resolve the type of c2 that now resides in c we again call a member function (this time on c2) to force the type resolution. We pass *this as the argument that now is of type SphereCollider. This will invoke the method AABBCollider::collideWith(SphereCollider& c ).

So the only thing you need are two references to your object and this method will work. An example is given below.

#include <iostream>

class SphereCollider;
class AABBCollider;

class Collider {
public:
  virtual bool collideWith(Collider& c ) {
    std::cout << "Collider <> Collider" << std::endl;
  };
  virtual bool collideWith(SphereCollider& c ) {};
  virtual bool collideWith(AABBCollider& c ) {};
};

class SphereCollider : public Collider {
public:
  virtual bool collideWith(Collider& c ) {
    c.collideWith(*this);
  }

  virtual bool collideWith(SphereCollider& c ) {
    std::cout << "SphereCollider <> SphereCollider" << std::endl;
  }

  virtual bool collideWith(AABBCollider& c ) {
    std::cout << "AABBCollider <> SphereCollider" << std::endl;
  }
};

class AABBCollider : public Collider {
public:
  virtual bool collideWith(Collider& c ) {
    c.collideWith(*this);
  }

  virtual bool collideWith(AABBCollider& c ) {
    std::cout << "AABBCollider <> AABBCollider" << std::endl;
  }

  virtual bool collideWith(SphereCollider& c ) {
    std::cout << "SphereCollider <> AABBCollider" << std::endl;
  }
};

int main( int argc, char **argv ) {

  Collider& c1 = * new SphereCollider;
  Collider& c2 = * new AABBCollider;

  c1.collideWith(c1);
  c1.collideWith(c2);
  c2.collideWith(c2);
  c2.collideWith(c1);

  return 0;
}

The output looks as follows:

SphereCollider <> SphereCollider
SphereCollider <> AABBCollider
AABBCollider <> AABBCollider
AABBCollider <> SphereCollider

Answer 4

You could provide a general Colliding function for the base class Collider that will be called inside your loop. This general function does the differentiation based on the dynamic type of the passed objects and thus simulates overloading based on the dynamic types. A more or less ugly macro can help reducing the code.

#define call_dynamic(T1,T2,o1,o2) if( dynamic_cast<T1*>(&o1) && dynamic_cast<T2*>(&o2) ) return Colliding( *((T1*)&o1),*((T2*)&o2) )

bool Colliding(const Collider& colliderOne, const Collider& colliderTwo) {
  call_dynamic(SphereCollider,SphereCollider,colliderOne,colliderTwo);
  /***/
  call_dynamic(SphereCollider,AABBCollider,colliderOne,colliderTwo);
  /* this line should never be reached */
  return false;
}

Depending on the number of classes you have, this still needs some lines of code. If performance matters this also won't be an optimal solution. But at least this is one possibility to solve the issue.

If the order of in which the objects are passed to the function does not matter, some improvements are possible.