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): 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]

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.

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.

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/

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:



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.

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:



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.

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:



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.

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.

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.



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.