collsion testing and polymorphism
Author
Say I have a 2D physics engine that has retangular and circular particles. The collision test for rect vs rect is different than that of circ vs circ, and rect vs circ. Since the collision is specific to two types of particles, I cant really assign the collision test responsibility to the particles. Rather, it seems I would need a more top level class -- lets call it the CollisionTester class.
The problem here is I cant really figure out how to use polymorphism since the CollisionTester must check the types of each particle to know how to handle the collision test. Then I end up with the hallmark of bad OOP: the if/then block that tests for object types.
If the responsibility of the checking was with the particle, I could just have a checkCollision method (ie, required by an IParticle interface) that was implemented specific to the relevant particle, but its not really possible to do it that way for functional reasons, as above.
Does anyone know a good design solution for this?
Not sure this is what you want, but here we go.
class rect
class circ
class CollisionTester::Test(rect, rect);
class CollisionTester::Test(rect, circ);
class CollisionTester::Test(circ, rect);
class CollisionTester::Test(circ, circ);
that should cover it.
theTroll
class rect
class circ
class CollisionTester::Test(rect, rect);
class CollisionTester::Test(rect, circ);
class CollisionTester::Test(circ, rect);
class CollisionTester::Test(circ, circ);
that should cover it.
theTroll
This is, quite literally, a text book example of double dispatch. One of the more accessible descriptions of implementing double dispatch in C++ is in "Modern C++ Design" by Alexander Alexandrescu. Otherwise googling for "double dispatch" should give you a number of leads.
Author
Thanks for the reply. I should have mentioned that the language I'm working in (actionscript) doesnt allow method overloading. I guess that automatically negates the first reply, which would have worked well.
I checked into the double dispatch pattern. As far as I can tell, it wouldn't be useable without the ability to have some method overloading...ie, it augments method overloading, not replaces it. Is that right?
I checked into the double dispatch pattern. As far as I can tell, it wouldn't be useable without the ability to have some method overloading...ie, it augments method overloading, not replaces it. Is that right?
Overloading is resolved at compile-time and this is a run-time problem so it won't help solve it.
You could try a base class method that accepts two base class pointers/references and uses some form of RTTI to determine the concrete class of each one and then vectors to 1 of 4 possible collision functions (which can probably be reduced to 3 cir-rect, rect-rect, cir-cir, nix rect-cir).
You can see how this would get out-of-hand with lots of concrete classes which is the problem double-dispatch is designed to combat.
You could try a base class method that accepts two base class pointers/references and uses some form of RTTI to determine the concrete class of each one and then vectors to 1 of 4 possible collision functions (which can probably be reduced to 3 cir-rect, rect-rect, cir-cir, nix rect-cir).
You can see how this would get out-of-hand with lots of concrete classes which is the problem double-dispatch is designed to combat.
If you can't use double dispatch (the lesser of many evils in this case, speaking from experience), then one logical solution to the problem is not to have multiple collision geometries.
Instead of Circle and Square (and Triangle and Whatever Else you may have a need for), try approximating these shapes with a convex polygon. A rectangle is a polygon. But with enough sides, so is a circle (12-16 usually does a decent job). If you only use polygons, you have ONE collision test, ONE collision response, and it's handled by ONE class.
If you want to get into it more, i suggest looking up "Separation Axis" algorithm. Specifically, Oliii's "polycoly" tutorials are fabulous.
Instead of Circle and Square (and Triangle and Whatever Else you may have a need for), try approximating these shapes with a convex polygon. A rectangle is a polygon. But with enough sides, so is a circle (12-16 usually does a decent job). If you only use polygons, you have ONE collision test, ONE collision response, and it's handled by ONE class.
If you want to get into it more, i suggest looking up "Separation Axis" algorithm. Specifically, Oliii's "polycoly" tutorials are fabulous.
Shannon Barber, I might be missing something here. Yes I know we can't do it in this case because of the limitation of the software he is using but couldn't you just dynamically cast to use overloading?
Create a base class with a function that returns the type of the inherited class. You can then dynamically cast the base class pointer to the inherited class pointer and then call the collision function. Am I missing something here?
theTroll
Create a base class with a function that returns the type of the inherited class. You can then dynamically cast the base class pointer to the inherited class pointer and then call the collision function. Am I missing something here?
theTroll
Quote:Original post by leiavoia
If you can't use double dispatch (the lesser of many evils in this case, speaking from experience), then one logical solution to the problem is not to have multiple collision geometries.
Instead of Circle and Square (and Triangle and Whatever Else you may have a need for), try approximating these shapes with a convex polygon. A rectangle is a polygon. But with enough sides, so is a circle (12-16 usually does a decent job). If you only use polygons, you have ONE collision test, ONE collision response, and it's handled by ONE class.
If you want to get into it more, i suggest looking up "Separation Axis" algorithm. Specifically, Oliii's "polycoly" tutorials are fabulous.
Actually, I think you can use real circles and still take the "single geometry" approach. What you do is give the Shape interface a collection<LineSegment> getSeparationAxes(Shape& other) function. For polygons, 'other' is ignored, and the returned axes are parallel to each side. For circles, the returned axes are parallel and perpendicular to the line connecting this.centre to other.centre. Then you simply have LineSegment projectIn(LineSegment& axis), and you're off to the races.
Quote:Original post by drvannostrand
I checked into the double dispatch pattern. As far as I can tell, it wouldn't be useable without the ability to have some method overloading...ie, it augments method overloading, not replaces it. Is that right?
No, double dispatch is independent of function overloading. You can implement it more easily with function overloading in C++, but the concept itself is independent of implementation language. The key is that you determine at runtime the types of the two objects and then somehow call a function based on the types. I'm not familiar with ActionScript, so I can't say how you would best do it, but worst comes to worst, you can do a massive nested switch statement that calls the respective functions based on type IDs.
Quote:Original post by TheTroll
Shannon Barber, I might be missing something here. Yes I know we can't do it in this case because of the limitation of the software he is using but couldn't you just dynamically cast to use overloading?
Create a base class with a function that returns the type of the inherited class. You can then dynamically cast the base class pointer to the inherited class pointer and then call the collision function. Am I missing something here?
theTroll
I suspose you could do that, and then have an overloaded collision function, one for IRectangle and one for ICircle?
Not sure I like it... but it would work.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
