• Advertisement
Sign in to follow this  

collsion testing and polymorphism

This topic is 4158 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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?

Share this post


Link to post
Share on other sites
Advertisement
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
If your language does not have overloading, you can easily provide that yourself using one extra step of indirection.

1.Create meaningful functions for each collision type, e.g.


void TestCollision_rect_rect(...)
void TestCollision_rect_circ (...)

2. Then create a single redirecting function with a signature:
void TestColision (Shape* shape1, Shape* shape2);

3. Within the implementation of this function, retrieve the object's 'type' using a call such as:

int shape1_type_enum = shape1->get_type_enum();
int shape2_type_enum = shape2->get_type_enum();

4. Then do a double switch on these int types like this:

switch (shape1_type_enum):
case CIRCLE:
{
switch (shape2_type_enum):
case CIRCLE:
// here both types are now known .. call the
// correct collision method!

case RECT:



case RECT:

etc ...


And you only have to write this function once, and this is the only place where you will need to change the collision code.

This is a simple double dispatch implementation in the absense of vfns. If vfns werer there, the base class would have the vfn signatures as follows:

virtual void test_collision (Shape*)
virtual void test_collision_with_circ (Circ*)
virtual void test_collision_with_rect (Rect*)

The first one is the redirector. Its implementation KNOWs what is the ACTUAL (true) type of the 'this' argument (the first shape, i.e.). Therefore its implementation in each class simply turns around and calls one of the other collision methods on the arguments. E.g. for a circle class, the test_collision () method is written as:

virtual void test_collision (Shape* sh)
{
sh->test_collision_with_circ(this);
}

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement