Sign in to follow this  
aWG

2D Collision Response - Multiple Dispatch

Recommended Posts

Hello! Long time since I've posted on here, and this is an incredibly long read about some design problems I'm having with collision detection in 2d. If you're up to the challenge, please read along and help me solve my problems ;). I've been writing my own 2D Mario clone from scratch to familiarize myself with design of an engine rather than actually making a game. Anyhow, I've come into a problem when trying to detect collisions and none of the articles on the web are really helping. The reason that is, is because the articles are usually about the math behind it where my problem is actually about handling the collision in the update loop. I'll go on to describe my problem / proposed solution in more detail. I would like some input or a better solution (I'm sure one exists): I want my Mario character to be able to "bump" tiles and also land on them. These appear to me to be two different problems. One is Mario bumps into a solid object (falling onto a block) and one is jumping into a non-static object (so he doesn't just stop at the block, he rises a bit with it as he bumps it). So for now let's say there's two different types: Static Collisions and (for lack of a better word) Dynamic Collisions (collisions with dynamic objects that can move). Let's name three classes right now to clarify my discussion: Mario, StaticTile, BumpableTile. But of course, theres tons of different block types so we can't limit it to just these three. That leads me to my first problem: I cannot think of a way to share code between these collisions for the classes. For instance Mario colliding with a BumpableTile is not the same as Mario colliding with a StaticTile. I believe someone who's done collision detection before might have a solution here already (if so, please do tell). But I'll continue on with my problem/solution steps. Now, I took a two-step approach to this solution. First I made it so a BumpableTile consists of a Static Collision (most of the tile) and a Dynamic Collision (on the bottom). So now when mario hits the bottom of a BumpableTile, I can treat that differently. I still have the code paths problem. Scott Meyers uses an example of Multiple Dispatch to solve this problem, so I solved it the same way (but using different code). It's probably time I start spewing out some code to help discussion from diverging to wildly different solutions. So here's a quick dump (of non-working code, but you get the idea):

class BoundingBox; // every collision is done using bounding boxes
class Mario; class BumpableTile; class StaticTile;
class StaticCollisions; class DynamicCollisions;

// these functions would handle collisions between the different types
void HandleCollisions( Mario* p, StaticCollision* ) {
    p->FixMyPositionSomehow();
}
void HandleCollisions( Mario*, DynamicCollision* p ) {
    p->BumpMyTileOrSomething();
}

void Mario::Update() {
    ... blah blah blah ...
    g_Collision<StaticCollisions>.CheckCollisions( this, oldPosition, newPosition );
}



The important thing to note is that g_Collision contains collisions for the template I give it (so far StaticCollisions and DynamicCollisions). But can create a new collision "manager" for any type (lets say I want to test against turtles, I could g_Collision<Turtle>). This is my method to figure out the double-dispatch types for the HandleColisions functions. Does anyone have a more elegant solution? This seems fairly inelegant having a different 'manager' for every type in the game that can collide, but also seems the most flexible (that I've thought of). Your input and experience would be greatly appreciated. Thanks! [Edited by - aWG on September 28, 2006 1:52:40 AM]

Share this post


Link to post
Share on other sites
I'd do it this way.

One collision check.

if (Obstacle.Static)
//collision check here, then return pos.
Plumber.Pos = newPos;
else
if (Plumber.Pos.y+Plumber.Height < Obstacle.y+Obstacle.radius &&
Plumber.Pos.y+Speed.y > Obstacle.y+Obstacle.radius)
{
Obstacle.Destroy;
Plumber.Pos = newPos;
}
else
Plumber.Pos = newPos;



etc.

/Robert

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
This seems a tad overcomplicated considering the facilities C++ provides (I've forgotten, thankfully, most things I knew about C++, but this should apply).

A collision is a collision, you're conflating functionality and complicating your code by inventing static and dynamic collisions and what have you. What varies is how to HANDLE that collision depending on the types of colliding objects.

First, you have your collision DETECTION routine, which shouldn't care about the classes much: it only needs to know about a class's position, bounding box and velocity. Presumably, all your tile, character etc. classes all have those attributes (even if velocity is 0) so you only need 1 function that acts on objects of this most general superclass.

Your collision detection routine might return a list of pairs of objects which have collided. (eg. ( (mario, tile), (yoshi, tile), (turtle, turtle), ...)

Now, for each pair you have to call the collision HANDLER for those particular classes of objects. This is the ideal candidate for dispatch-on-types, as you point out, via function overloading for example, because the states of the objects after colliding depend on BOTH object types.

It may make sense to further subclass these types (into dynamic and static collisions) but I doubt it: each collision will probably have different functionality, even if it is dynamic: (mario, tile) is different from (turtle, turtle), so subclassing them into a dynamic_collisions class is useless because there's no shared functionality...

So why not write is this way? You can call handle_collision(object1, object2) on every pair of objects returned by detect_collisions(), and let handle_collision() decide what it should do based on the object types: you don't have to worry about figuring out explicit object types anymore, because that information resides in the overloaded handle_collision() functions.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Blech, I forgot that C++ overloading is static. Just remembered another reason I stopped using it. ;)

But the same approach applies to whatever homebrew dynamic dispatch you decide to use, I think.

Share this post


Link to post
Share on other sites
check out this tutorial. it helped me when i was doing my 2d side scroller and ran into the same issues you are having.

http://jnrdev.72dpiarmy.com/en/jnrdev3/

Share this post


Link to post
Share on other sites
Thanks for all the responses so far.

Rasmadrak, I don't think that would give me enough flexibility for responding to the collision (which is also an important part, not just detecting).

Anonymous, yes, I see what you're saying about the classes instead of Dynamic/Static. I came to a similar conclusion last night, but the same solution applies. Since you can create a g_Collision object for each type it's just a matter of creating a new object and calling it like:


g_Collision<Turtle>.CheckCollisions( this, oldPosition, newPosition );
g_Collision<Goomba>.CheckCollisions( this, oldPosition, newPosition );



etc. But I'm glad you agree on the multiple-dispatch solution. It just seems very odd that I can't think up another combination that would get the same results. I was thinking along the lines of having each class contain polymorphic collisionResponse object they could pass to g_Collision. But then I quickly run into the same multiple dispatch problem again (just another implementation).

Tont, I do not have time to read that link you sent right now, but I certainly will. I love playing that Super Mario Wars game and wasn't aware that the source was available.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Hmm, maybe I wasn't very clear.

I think you're overcomplicating this by making collisions methods of a particular class, when in fact they are symmetric: they belong to TWO types at once, so making them belong to one object is unnatural and cumbersome. That's what multiple dispatch captures, and it avoids all this juggling of classes and subclasses that results from making this unnatural design choice.

Step back for a moment, forget templates and objects and think of how you might implement dispatch-on-types procedurally. Suppose you want a handle_collision(object1, object2) function. Suppose also that each object has a type attribute which you can interrogate directly.

Then you would simply write separate functions for handling each pair of types, and use handle_collision() to do the runtime dispatch. This is the old-fashioned way. In pseudocode:


void handle_mario_bumpable(object1 mario, object2 bumpable) { ... }

void handle_mario_turtle(object1 mario, object2 turtle) { ... }

void handle_mario_wall(object1 mario, object2 wall) { ... }


...


void handle_collision(object1 general_object, object2 general_object)
{
if object1.type == mario and object2.type == bumpable then handle_mario_bumpable(object1, object2)
else
if object1.type == mario and object2.type == turtle then handle_mario_turtle(object1, object2)
....}



Now ask yourself, is your current approach actually clearer or safer than this? Does it have any advantage over this besides that it uses loads of templates and classes and thus is 'cooler'? If it doesn't, you should rethink it.

Share this post


Link to post
Share on other sites
Well, I always just assume I'd have a large amount of classes that would need to interact.

If I did it the "old fashioned" way, it would require adding to that "if" statement everytime I added a new class, then static_cast'ing the objects everytime those functions were called. For instance, every function would be like:


void handle_mario_wall(object1* mario, object2* wall)
{
Mario* blah = static_cast<Mario*>( mario );
Wall* blah2 = static_cast<Wall*>( wall );
...
}



Or would be cast from within the handle_colllisions function. Also, I don't want those if statements to be executed everytime a collision occurs, using rtti. Not using rtti would require injecting extra code in each class.

The templates themselves are not something I'm worried about. To me using multiple-dispatch via long if statements, a Visitor-like pattern (Meyers), Typelists (Alexandrescu), or through template type resolution are all the same.

I'm wondering if there's a way I'm missing that doesn't use these multiple dispatch tricks, but would still be able to keep the functionality. I think I'll have to look at the Super Mario Wars source.

Thanks again.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
No there is no way. The only way which comes to my mind is through metadata, with which you can describe and represent all type of objects and their behaviour when a collision occurs. But then adding such an if statement is much simpler and faster.

Share this post


Link to post
Share on other sites
Implement double dispatch?

Well, virtual functions solve the single dispatch problem. Double dispatch usually requires manual code. I share your dislike for "large switch statements" -- so how to avoid it?

Well, the class/instance pattern isn't restricted to the compiler. You can use it as well.

With a nod to plato:

class essence {
public:
typedef GUID uid; // or whatever you want to use
typedef enum {less_than=-1, equal_to=0, greater_than=1} compare_result;
static compare_result uid_compare( uid const& left, uid const& right ) {
// ...
}

virtual uid examine_uid() const = 0;
bool operator<(const essence& other) const {
return less_than == uid_compare( this->examine_uid(), other.examine_uid() );
}
bool operator==(const essence& other) const {
return equal_to == uid_compare( this->examine_uid(), other.examine_uid() );
}
// do all the comparison operators
// ...
};

class instance {
public:
virtual essence const& instance_of() = 0;
// ...
};


Now make every C++ class an "instance" of some "essence". The essences will be created statically and persist for the length of your execution.

Our goal is to make a double-virtual (or more) function.

Such a function is a map from (essence x essence) to a function pointer. Some such maps should be symmetric.


typedef std::pair<essence const&, essence const&> essence_pair;
inline essence_pair sym_essences(essence const& left, essence const& right) {
essence const& first = (left<right)?left:right;
essence const& second = (left<right)?right:left;
return essence_pair(first, second);
}

template<typename func_signature>
struct binary_symmetric_virtual_essence_function {
private:
typedef std::pair<essence_pair, func_signature*> map_contents;

func_signature* base;
std::map< essence_pair, func_signature* > overload_map;
typedef overload_map::iterator iterator;
typedef overload_map::const_iterator const_iterator;

public:
bool add_overload( essence_pair essences, func_signature* overload ) {
// TODO: checking for duplicates and error
overload_map.insert( map_contents( essences, overload ) );
return false
}
func_signature* get_func( essence_pair essences ) {
const_iterator it = overload_map.find(essences);
if (it == overload_map.end()) return base;
return it->second;
}
};



Now, the above could be done with type_ids -- but then you wouldn't have nearly as much control. Two classes couldn't have the same essence -- while now you can say "both player 1 and player 2 are different objects -- even classes, but are both treated as players".

In addition, you can add inheritance rules to the essence code. Each essence would have a pointer to the parent -- and you'd want to replace the simple search code with some kind of "best fit" type code.

The addition of inheritance makes the above extremely strong. All of a sudden you can add new essences that inherit from old essences and, except for the behaviour you want changed, they behave like their parents.


You can also add multiple essence heirarchies (just add some template tagging) so the essence<colllision> heirarchy is completely different than the essence<rendering> heirarchy.


The pattern of "object/instance" from the C++ language was designed -- including virtual functions, virtual function tables, and all that jazz -- because it was a decent pattern. People implemented "object/instance" in C before C++ existed. You can implement your own "object/instance" within C++, when C++ fails you.


For single-dispatch, I'd keep myself to using C++ -- ie, don't bother having "essence<name>" -- instead have a name interface with a virtual function you can call.

Use:

class A: public virtual instance { /* ... */ };

typedef bool bool_A_A( A* left, A* right );

binary_symmetric_virtual_essence_function<bool_A_A>* test_double_virtual_dispatch() {
static binary_symmetric_virtual_essence_function<bool_A_A> dispatch;
return &dispatch;
}

bool test_double_virtual(A* left, A* right) {
essence_pair essences = sym_essences(left, right);
bool_A_A* func = test_double_virtual_dispatch()->get_func( essences );
if (!func) { // assert, throw, panic!
}
return func(left, right);
}


On top of the above, you have registration of the doubly-virtual functions and the like.

It is an interesting problem. I should poke at it more.

Share this post


Link to post
Share on other sites
Very interesting solution NotAYakk. This is very similar to Andrei Alexandrescu's "constant-time" multiple dispatch solution in that you can get constant-time execution by inserting function pointers into a map and looking it up based on an ID (or essence, in your case).

I agree that your solution is a lot more flexible and powerful. I'm a bit weary of injecting my classes with different essences. Mostly because I'm worried about managing these different classes and the code to do so overcomplicating or overshadowing my initial problem. But it's certainly something I'll keep in mind if I need this multiple-dispatch problem anywhere else other than collision (since the system would facilitate that nicely).

It was these kinds of responses I was looking for, and I greatly appreciate the thoroughness and effort put into your solution.

Share this post


Link to post
Share on other sites
I havn't taken the time to read all the posts, but double dispatch is pretty easy. You just call a virtual function on one of the objects, which calls an overloaded virtual function on the other, passing itself as a parameter. Like this:

class Box;
class Sphere;

class Collider
{
virtual bool CheckCollision(Collider* other) = 0;
virtual bool Collide(Box* other) = 0;
virtual bool Collide(Sphere* other) = 0;
};

class Box
{
virtual bool CheckCollision(Collider* other)
{
return other->Collide(this);
}
virtual bool Collide(Box* other)
{
//Box box collision.
}
virtual bool Collide(Sphere* other)
{
//Box sphere collision.
}
};



There. Done. Saves you pretty much nothing, you end up just calling free functions in the Collide() things to save implementing everything twice.

Share this post


Link to post
Share on other sites
Razor, you would also want to add default implemantation, instead of pure virtualization:


// Collider.h:
class Box;
class Sphere;

class Collider
{
virtual bool CheckCollision(Collider* other) = 0;
virtual bool Collide(Collider* other) = 0;
virtual bool Collide(Box* other);
virtual bool Collide(Sphere* other);
};

// In Collider.cpp:
#include <Box.h>
#include <Sphere.h>
//...
bool Collider::Collide(Box* other_) {
Collider* other = other_;
return Collider(other);
}
bool Collider::Collide(Sphere* other_) {
Collider* other = other_;
return Collider(other);
}

// Box.h:
class Box: public Collider
{
virtual bool CheckCollision(Collider* other)
{
return other->Collide(this);
}
virtual bool Collide(Collider* other)
{
// default implementation
}
virtual bool Collide(Box* other)
{
//Box box collision.
}
// Boxes and spheres collide using the default code:
// virtual bool Collide(Sphere* other)
};



The above adds in inheritance semantics to your code -- if a new class is added to the heiarchy with a known parent, classes that don't override the method will act as if the object is colliding with the parent.

However, you will note that whenever you add a new class, you have to add boilerplate code in lots and lots of seperate places -- you have to add O(n) glue code.

And symmetric double-dispatch functions have to be done manually, and are fragile.

Lastly, N-ary dispatch (two objects collide on a particular level, for an example of 3-ary dispatch) gets hellishly complicated I think under your model.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this