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:

Be too complex for this seemingly simple problem.
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.

I'd personally completely avoid inheritance and OOP for something like this. Instead I'd just have a "hitbox" struct which stores the data of all possible types of hitboxes (potentially optimized via a tagged union) — UnholySheep
– UnholySheep, Commented Dec 2, 2021 at 19:45
Another option (as is done in e.g.: Box2D) is to store a "type" enum in the base class, then you can easily switch on that (which is a bit more convenient than having an if chain of dynamic_casts) — UnholySheep
– UnholySheep, Commented Dec 2, 2021 at 19:48
What about using a template parameter and avoid the dynamic casting? — mfnx
– mfnx, Commented Dec 2, 2021 at 20:06
You want to read about the visitor pattern. This is a classic use case. In a proper implementation you do not need any casting, dynamic or otherwise. — n. m. could be an AI
– n. m. could be an AI, Commented Dec 2, 2021 at 21:55
@UnholySheep enum and switch solution is not extendable and very error prone. It violates SRP and OCP in a way that one would need to modify ALL the places where a switch is used when adding new enum value. And in a large project one would definetely miss some places... — Sergey Kolesnik
– Sergey Kolesnik, Commented Dec 2, 2021 at 23:01

n. m. could be an AI · Accepted Answer · 2021-12-03 19:07:46Z

3

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:

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.
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.

answered Dec 3, 2021 at 19:07

n. m. could be an AI

122k14 gold badges141 silver badges267 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

Sergey Kolesnik Over a year ago

looks very interesting, but I feel that it will not work with disabled RTTI and (if so) you should mention it in your answer.

Sergey Kolesnik Over a year ago

godbolt.org/z/4onqrd3cP your example (tested). Interestingly that it works with -fno-rtti. Can you explain how it works without rtti?

Sergey Kolesnik Over a year ago

well, I didn't notice at once, but now I see. The implementation class is calling other's method passing *this, therefore the type is known upon the call and no upcasting is required. I very much appreciate your answer!

n. m. could be an AI Over a year ago

@SergeyKolesnik this is actually a completely standard implementation of double dispatch, I feel all C++/OO programmers should know about it.

Sergey Kolesnik Over a year ago

And still it is new to me somehow, and I am very excited to know something like this. Btw, this solution is almost the same as using std::variant, since you have to "introduce" each type to another. Moreover, if OP decides to dynamically change the type of a hitbox, he will have to own a base class thus facing heap allocation penalty. std::variant does not require any heap allocations, but allows runtime configuration.

|

Sergey Kolesnik · Accepted Answer · 2021-12-03 02:58:19Z

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).

I was anxious about receiving an answer like yours :D It is a valid point and a perfectly viable solution for the code I offered. The code is a "distilled" version of the one I tried to implement, which had a game world with entities with members, such location, mesh and hitbox. Some entities were walls, enemies etc., I opted to give them a general Hitbox*, but in the end I ran short on time and used a similar solution to yours. Ideally, hitbox type would be assigned at runtime, and my question's purpose was to learn to do that in the future, not necessarily for this specific example.
@Andrei-Info in this case a safe, simple and robust solution would be somthing like std::variant<HitBoxTypes...> with a visitor. But it would be more complicated since there would need to be a "double visitor", since there are two arguments for a collision function. There also can be a solution with type erasure, but it is only simple for this type. I will try to add some solution with type erasure with as little runtime overhead as possible (without heap allocations)

mfnx · Accepted Answer · 2021-12-03 20:20:58Z

1

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.

edited Dec 3, 2021 at 20:20

answered Dec 2, 2021 at 20:54

mfnx

3,0661 gold badge15 silver badges31 bronze badges

Collectives™ on Stack Overflow

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

3 Answers 3

8 Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

8 Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related