How and when to choose which objects to run collision tests on?

Question

This might be problem with plenty of good solutions, but it's all not very clear to me, so I though I could ask and probably get some good hints. I'm having trouble figuring out how to handle interaction between objects in a platformer. Basically it's supposed to have two kinds of collision detection: one for solid objects that's based on line tests, and another to detect when ordinary objects touch.

These are some solutions that I know of, but they all have some serious problems:

• Store global references to the player and to solid objects, and have all other objects manually detect collisions with them.

  Good: trivial to implement, efficient

  Bad: limiting, since you can't easily have two non-player objects interact on collision; object implementations are strongly coupled to the player object's implementation

• Let objects ask for a list of objects of a certain type, and check for collisions in that list.

  Good: simple to use; useful for other things such as finding all solid objects

  Bad: I don't know how to implement it nicely (especially in a statically typed language); it requires use of inheritance to classify object types; objects in the same update priority interact slightly differently depending on which one updates first

• Let objects send and receive messages, and have a central collision detection system that runs after the update methods and sends messages to all colliding objects.

  Good: update order does not matter; object types need to know little, if anything, about each other

  Bad: must use the shapes provided by the collision system (no custom tests); most collision tests and messages will be wasted since collisions between most object types are ignored; a separate way to list all solid objects is still needed

So, any suggestions for improvements, alternatives, or good links to read? Suggestions that also simplify related problems like off-screen objects or objects positioned relative to other objects would be appreciated, too.

EDIT: To be clearer, I'm not asking about how to detect a collision given two objects, but about how the two objects can find out about each other in the first place.

Answer 1

Personally, I use a spin on the first option you listed. When checking if A collides with B, however, a series of disqualifiers (or a singular disqualifier) can be used to reduce the computation required for each iteration of your collision checker. For example:

if((b.y >= a.y && b.y <= (a.y + a.h)) || ((b.y+b.h) >= a.y && (b.y+b.h) <= (a.y+a.h)))
{
  bool collide = checkCollision(a,b);
}

Obviously enough, if a collision-enabled object does not come within vertical range of another collision-enabled object, the collision system wont even both to run the numbers. There's tons of ways to implement this, too. If your system is texel based, you could even use raycasting as an accurate qualifier which might, in some cases, be simpler.