C++: Is there a more elegant solution to this (multiple dispatch) runtime polymorphism?

Question

The main problem is simple, really. Given a base (more abstract) class and multiple derived ones that need to interact with each other, how do you go about doing it?

To give a more concrete example, here is an implementation with hitboxes for a 2d videogame:

#include <stdio.h>
#include <vector>

#include "Header.h"


bool Hitbox::isColliding(Hitbox* otherHtb) {
    printf("Hitbox to hitbox.\n");
    return this->isColliding(otherHtb);
}

bool CircleHitbox::isColliding(Hitbox* otherHtb) {
    printf("Circle to hitbox.\n");

    // Try to cast to a circle.
    CircleHitbox* circle = dynamic_cast<CircleHitbox*>(otherHtb);
    if (circle) {
        return this->isColliding(circle);
    }

    // Try to cast to a square.
    SquareHitbox* square = dynamic_cast<SquareHitbox*>(otherHtb);
    if (square) {
        return this->isColliding(square);
    }

    // Default behaviour.
    return 0;
}

bool CircleHitbox::isColliding(CircleHitbox* otherHtb) {
    printf("Circle to circle.\n");

    // Suppose this function computes whether the 2 circles collide or not.
    return 1;
}

bool CircleHitbox::isColliding(SquareHitbox* otherHtb) {
    printf("Circle to square.\n");

    // Suppose this function computes whether the circle and the square collide or not.
    return 1;
}

// This class is basically the same as the CircleHitbox class!
bool SquareHitbox::isColliding(Hitbox* otherHtb) {
    printf("Square to hitbox.\n");

    // Try to cast to a circle.
    CircleHitbox* circle = dynamic_cast<CircleHitbox*>(otherHtb);
    if (circle) {
        return this->isColliding(circle);
    }

    // Try to cast to a square.
    SquareHitbox* square = dynamic_cast<SquareHitbox*>(otherHtb);
    if (square) {
        return this->isColliding(square);
    }

    // Default behaviour.
    return 0;
}

bool SquareHitbox::isColliding(CircleHitbox* otherHtb) {
    printf("Square to circle.\n");

    // Suppose this function computes whether the square and the circle collide or not.
    return 1;
}

bool SquareHitbox::isColliding(SquareHitbox* otherHtb) {
    printf("Square to square.\n");

    // Suppose this function computes whether the 2 squares collide or not.
    return 1;
}


int main() {
    CircleHitbox a, b;
    SquareHitbox c;
    std::vector<Hitbox*> hitboxes;

    hitboxes.push_back(&a);
    hitboxes.push_back(&b);
    hitboxes.push_back(&c);
    
    // This runtime polymorphism is the subject here.
    for (Hitbox* hitbox1 : hitboxes) {
        printf("Checking all collisions for a new item:\n");
        for (Hitbox* hitbox2 : hitboxes) {
            hitbox1->isColliding(hitbox2);
            printf("\n");
        }
    }

    return 0;
}

with the header file:

#pragma once

class Hitbox {
public:
    virtual bool isColliding(Hitbox* otherHtb);
};

class CircleHitbox : public Hitbox {
public:
    friend class SquareHitbox;

    bool isColliding(Hitbox* otherHtb) override;
    bool isColliding(CircleHitbox* otherHtb);
    bool isColliding(SquareHitbox* otherHtb);
};

class SquareHitbox : public Hitbox {
public:
    friend class CircleHitbox;

    bool isColliding(Hitbox* otherHtb) override;
    bool isColliding(CircleHitbox* otherHtb);
    bool isColliding(SquareHitbox* otherHtb);
};

The main issue I take with this is the "is-a" check that every derived class needs to make in the overridden function.

The alternative I've seen suggested is a visitor design pattern, but that may:

1. Be too complex for this seemingly simple problem.

2. Result in more problems than solutions down the line.

One property that should be conserved from this code is that no derived class is forced to implement its interaction with every (or any, for that matter) other derived class. Another is the ability to store all derived objects in a base type array without any object slicing.

Answer 1

Here is a simplified example (untested) of the classical double dispatch.

struct Circle;
struct Rectangle;

struct Shape {
  virtual bool intersect (const Shape&) const = 0;
  virtual bool intersectWith (const Circle&) const = 0;
  virtual bool intersectWith (const Rectangle&) const = 0;
};

struct Circle : Shape {
  bool intersect (const Shape& other) const override { 
     return other.intersectWith(*this);
  }
  bool intersectWith (const Circle& other) const override {
     return /* circle x circle intersect code */;
  }
  bool intersectWith (const Rectangle& other) const override {
     return /* circle x rectangle intersect code*/;
  }
};

struct Rectangle : Shape {
  bool intersect (const Shape& other) const override { 
     return other.intersectWith(*this);
  }
  bool intersectWith (const Circle& other) const override {
     return /* rectangle x circle intersect code */;
  }
  bool intersectWith (const Rectangle& other) const override {
     return /* rectangle x rectangle intersect code*/;
  }
};

As you can see you weren't too far off.

Notes:

1. return intersectWith(*this); needs to be repeated in each derived class. The text of the method is the same every time, but the type of this is different. This can be templatized to avoid repetition, but it probably isn't worth it.
2. The Shape base class (and, naturally, each of its derived classes) needs to know about all Shape-derived classes. This creates a cyclic dependency between classes. There are ways to avoid it but these do require casting.

This is not the solution of the multiple-dispatch problem, but it is a solution. A variant-based solution may or may not be preferable, depending on what other stuff you have in your code.

Answer 2

The interaction could be managed by the base class itself. Something like this:

struct CircleHitBox;
struct SquareHitBox;

struct HitBox
{

template <class HITBOX>
bool is_colliding(HITBOX) const
{
    if constexpr (std::is_same_v<HITBOX, CircleHitBox>)
    {
        std::cout << "A CircleHitBox hit me.\n";
        return true;
    }
    else if constexpr (std::is_same_v<HITBOX, SquareHitBox>)
    {
        std::cout << "A SquareHitBox hit me.\n";
        return true;
    }
}            
};

Also, each subclass could register itself in a map or some structure, so you could use a loop (scanning the map) instead of the if elsestatements.

Answer 3

With C++ 17 there is a simple and elegant solution which allows you run-time polymorphism without virtual functions overhead:

#include <iostream>

namespace hitbox
{
    struct rectangle
    {
        double h,
                w;
    };

    struct circle
    {
        double r;
    };
}

bool is_colliding(const hitbox::rectangle &, const hitbox::circle &) {
    std::cout << "Rectangle + Circle" << std::endl;
    return true;
}

bool is_colliding(const hitbox::rectangle &, const hitbox::rectangle &) {
    std::cout << "Rectangle + Rectangle" << std::endl;
    return true;
}

bool is_colliding(const hitbox::circle &, const hitbox::circle &) {
    std::cout << "Circle + Circle" << std::endl;
    return true;
}

#include <variant>

using hitbox_variant = std::variant<hitbox::rectangle, hitbox::circle>;

bool is_colliding(const hitbox_variant &hitboxA, const hitbox_variant &hitboxB)
{
    return std::visit([](const auto& hitboxA, const auto& hitboxB)
                      {
                          return is_colliding(hitboxA, hitboxB);
                      }, hitboxA, hitboxB);
}

int main()
{
    hitbox_variant rectangle{hitbox::rectangle()},
            circle{hitbox::circle()};

    is_colliding(rectangle, rectangle);
    is_colliding(rectangle, circle);
    is_colliding(circle, circle);

    return 0;
}

https://godbolt.org/z/KzPhq5Ehr - your example

---

Your problem comes from your assumtion about the necessity for types being erased. When you erase types (in your case by reducing them to a base abstract class), you erase info about their attributes (like their geometrics).
But why do you use type erasure in the first place?
Because you want to store references to all the needed objects in one container which requires them to be of the same type.
Well, do you need to? This is a poorly chosen abstraction for your particular problem of collision calculation between the types of objects that are known during the compile time. So, unless you don't get the types of object that are "created" during the run-time, don't erase the type.

Store your objects in several containers for purposes when you need to know the types. It will reduce the redundant costs for run-time reflection (be it via dynamic_cast, enums, etc).

// you HAVE to implement them because your program KNOWS about them already
bool has_collision(const CircleHitBox& circle, const CircleHitBox& circle);
bool has_collision(const CircleHitBox& circle, const SquareHitbox& square);
bool has_collision(const SquareHitbox& square, const SquareHitbox& square);

struct scene
{  
  template <typename T>
  using ref = std::reference_wrappet<T>;
  std::vector<ref<const CircleHitBox>> circleHitBoxes;
  std::vector<ref<const SquareHitbox>> squareHitBoxes;
  std::vector<ref<const HitBox>> otherHitBoxes;
};

// here you create an object for your scene with all the relevant objects of known types
void calc_collisions(scene s)
{
  // do your calculations here
}

You can use some kind of a registry like in an Entity Component System (EnTT).

---

Bare in mind:
You are solving a collision problem here, so you have to know about specific object's atttributes. This mean that you can't have a Run-Time Polymorphism here without violating the Liskov Substitution Principle. LSP implies that each and every object behind the abstarct base class is interchangeable and has exactly the same attributes - and those are not the same until you do some type casting.

Also, HitBox type is better to be just a POD type to store data. You don't need any non-static member functions there, especially virtual functions. Don't mix data and behavior, unless you need to (stateful functional objects, for example).