🔒 Locked

Polymorphism question

Started by daniel_i_l Apr 9, 2009 at 3:03 PM 18 replies 1.5k views

Original Post

78

Apr 9, 2009 at 3:03 PM

Let's say I have a basic shape class "Shape" and derive from it different shapes like "Rectangle", "Circle" and "Triangle". I need a function "CheckCollision" that checks if two Shapes are colliding. The easy way to do this would be for CheckCollision to check the types of the Shapes it gets, cast them, and then call a more specific method. For example, if the Shapes are Circle and Rectangle then the Shapes would be casted into these types and then CheckCircleRectangle() would be called. I have to cast them because of the fact that each object has a different way of representing its dimensions (Circle - radius, Rectangle - height, width) and CheckCircleRectangle has to be able to use them. But this solution seems kind of messy, for one thing, I'd have to change the "CheckCollision" function whenever I add a new type of object. And also, I'd like to find a solution that doesn't use so many casts. Any ideas? Thanks, Daniel

116

Apr 9, 2009 at 3:05 PM

Use virtual functions.

Author

78

Apr 9, 2009 at 3:24 PM

How would that work? The problem is that a collision function operates on two different types. So even if the Shape had a virtual CheckCollision function that the other shapes implemented those implementations would have to check the type of the other Shape being passed and cast it.
For example, in Circle's implementation of the CheckCollision it'll have to check if the shape being passed to it (circle.CheckCollision() is a Rectangle or a Triangle, cast it, and then pass it on to a more specific function. So I don't understand how virtual functions help here.
Thanks.

Mod

473

Apr 9, 2009 at 3:29 PM

You want double dispatch which is a somewhat non-trivial thing to implement in C++. Doing a search for "double dispatch C++" should give you a number of different ways to approach this, each with different trade-offs.

Author

78

Apr 11, 2009 at 4:36 PM

Thanks, that's exactly what I need.

Author

78

Apr 12, 2009 at 7:45 AM

I tried to test out the double dispatch pattern with the following code:

class base{    public:    base(){}    void collide(base *b){b->collide(this); cout<<"base collide"<<endl;}};class derived_a : public base{    public:    derived_a():base() {}    void collide(derived_a *da){cout<<"a and a"<<endl;}};class derived_b : public base{    public:    derived_b():base(){}    void collide(derived_a *da){cout<<"b and a"<<endl;}    void collide(derived_b *ba){cout<<"b and b"<<endl;}};int main(void){    base *a = new derived_a();    base *b = new derived_b();    a->collide(a);    a->collide(b);    b->collide(b);    cin.get();    return 0;}

but when I ran it I didn't get any output? For example, why doesn't a->collide(a) call
base::collide(base *b) which in turn should call derived_a::collide(derived_a *da)?
Thanks.

136

Apr 12, 2009 at 7:54 AM

Replace the fourth line with this:

void collide(base *b){cout<<"base collide"<<endl;b->collide(this); }

Do you see the problem now?

Author

78

Apr 12, 2009 at 8:08 AM

Yes, I see the problem. In the base class "this" points to a base class type and so the collide function keeps on calling itself. But even when I make the collide(base *b) function virtual void in the base class and implement them in the derived classes like this (in derived_a)

void collide(base *b){cout<<"base collide"<<endl; b->collide(static_cast<derived_a *>(this));}

I get the same behaviour. Is there a way to fix this?
Thanks.

Mod

473

Apr 12, 2009 at 8:41 AM

You seem to be trying to use this variant of double dispatch in C++:

#include <iostream>struct A;struct B;struct Base {  virtual void collide(Base & b) = 0;    virtual void actual_collide(A & a) = 0;  virtual void actual_collide(B & b) = 0;    virtual ~Base() {}};struct A : Base {  virtual void collide(Base & b);    virtual void actual_collide(A & a);  virtual void actual_collide(B & b);};struct B : Base {  virtual void collide(Base & b);    virtual void actual_collide(A & a);  virtual void actual_collide(B & b);};void A::collide(Base & b) {  b.actual_collide(*this);}void A::actual_collide(A & a) {  std::cout << "a and a\n";}void A::actual_collide(B & b) {  std::cout << "a and b\n";}void B::collide(Base & b) {  b.actual_collide(*this);}void B::actual_collide(A & a) {  std::cout << "b and a\n";}void B::actual_collide(B & b) {  std::cout << "b and b\n";}int main(void) {  Base * a = new A;  Base * b = new B;    a->collide(*a);  a->collide(*b);  b->collide(*a);  b->collide(*b);  return 0;}

Author

78

Apr 12, 2009 at 8:52 AM

Is there any way to do it without having to list all the derived types in the base class?
Thanks.

136

Apr 12, 2009 at 8:59 AM

As a last resort, you could also do the dispatching yourself ;)

struct base{    virtual int type() const = 0;};struct derived_a : public base{    int type() const { return 0; }};struct derived_b : public base{    int type() const { return 1; }};void a_with_a(base* x, base* y){    cout << "a with a\n";}void a_with_b(base* x, base* y){    cout << "a with b\n";}void b_with_a(base* x, base* y){    cout << "b with a\n";}void b_with_b(base* x, base* y){    cout << "b with b\n";}void (*dispatch[])(base*, base*) = {a_with_a, a_with_b, b_with_a, b_with_b};void collide(base* x, base* y){    int index = x->type() << 1 | y->type();    dispatch[index](x, y);}int main(){    base *a = new derived_a();    base *b = new derived_b();    collide(a, a);    collide(a, b);    collide(b, a);    collide(b, b);    cin.get();    return 0;}

Mod

473

Apr 12, 2009 at 9:27 AM

You can also use dynamic_casts in the collide functions like so:

struct Base {  virtual void collide(Base & base) = 0;  virtual ~Base() {}};struct A : Base {  virtual void collide(Base & base);};struct B : Base {  virtual void collide(Base & base);};void A::collide(Base & base) {  if (A * a = dynamic_cast(&base)) {    std::cout << "a and a\n";  } else if (B * b = dynamic_cast(&base)) {    std::cout << "a and b\n";  }}void B::collide(Base & base) {  if (A * a = dynamic_cast(&base)) {    std::cout << "b and a\n";  } else if (B * b = dynamic_cast(&base)) {    std::cout << "b and b\n";  }}

As I said, there are multiple ways to do this each with different trade-offs.

Author

78

Apr 12, 2009 at 9:29 AM

Thanks for the replies. But just so that I understand what's actually happening, how come the second block of code that I posted didn't work? Why didn't the call to collide go to the correct overloaded function even though the "this" pointer was of the derived_a type and not the base type?
Thanks.

Mod

473

Apr 12, 2009 at 9:31 AM

None of your functions were virtual.

Author

78

Apr 12, 2009 at 9:45 AM

So the problem was that when I did b->collide(this) it was calling base::collide(base* b) since that was the only collide function declared for base types?
In general, if I pass a derived type to a function that only takes a base type then will it automatically use the base of the derived type?
Thanks.

Mod

473

Apr 12, 2009 at 9:52 AM

If you pass a derived type to a function that accepts a base type, what will happen depends on what that function does and if the type hierarchy has virtual functions. If the function that accepts the base type calls virtual functions, then it will behave like a derived type since virtual functions depend on the dynamic type of the object. If it doesn't then it will behave like an object of the static type.

Author

78

Apr 12, 2009 at 10:03 AM

Thank you for the explanation.
From what I understood, if I make all the overloaded collide functions in A and B virtual then the following should happen:
if a and b are as defined in the main function that I posted above the a->collide(b) should call derived_a::collide(base *b) which in turn calls b->collide(this). But since b is of type derived_b and derived_b::collide(derived_a *da) is now virtual then it's the function that should be called.
But I still get the infinite loops. Do I have to declare the overloaded functions in the base class so that the compiler knows to look for them?
Thanks.

Mod

473

Apr 12, 2009 at 10:07 AM

Post your current code.

Author

78

Apr 12, 2009 at 10:13 AM

class base{    public:    base(){}    virtual void collide(base *b)=0;};class derived_a : public base{    public:    derived_a():base() {}    virtual void collide(base *b)    {        b->collide(this);    }    virtual void collide(derived_a *da)    {        cout<<"a and a"<<endl;    }    virtual void collide(derived_b *bd)    {        cout<<"a and b"<<endl;    }};//basically same as derived_aclass derived_b : public base{    public:    derived_b():base(){}    virtual void collide(base *b){cout<<"base collide"<<endl; b->collide(this);}    virtual void collide(derived_a *da){cout<<"b and a"<<endl;}    virtual void collide(derived_b *ba){cout<<"b and b"<<endl;}};int main(void){    base *a = new derived_a();    base *b = new derived_b();    a->collide(a);    a->collide(b);    b->collide(b);    cin.get();    return 0;}

Here it is.
Thanks.

Mod

473

Apr 12, 2009 at 10:18 AM

When you call a->collide(a) it calls void A::collide(Base *). However, in this function you end up calling collide() on the Base pointer, which is actually still void A::collide(Base *), since Base doesn't have an overload for collide() that accepts a derived_a *.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.