What is a good method for collision detection, where I check a collision, instead of all collisions

Question

The collision system for my game currently works fine; it lets me test a collision with an entity or specified rectangle, but that's not enough. I use to use Game Maker, and it had collision events that were simple. What I want to do is not check collision with everything, but check for a collision with everything.

Using the former method would probably be really expensive, checking all other objects, per object, per frame. What is a good method for collision detection, where if I am colliding with something, I get it's class, and can decide what to do with it?

Answer 1

Read Real-time Collision Detection. By far the best on the subject imho.

• Implement Spacial Partitioning of the objects in your scene. (kd-tree or octree or etc...) This is by far one of your most important components (when it comes to simulation [like col. det.] or rendering)

• Implement a Bounding Volume Hierarchy (BVH) for your objects - grouping the objects in the scene in clusters depending on their proximity one to another.

Using those two together has already increased your performance by a few orders of magnitude (more or less).

Then there are many collision detection optimisation tricks which you can further implement, here are just a few that come to mind:

• Object hierarchy - is very similar to the BVH described above, however depending on your implementation of BVH it could/could not be included. It is basically BVH on an object level. So if you have complex objects in your scene... obviously you don't want to check all their triangles against all the triangles of the other object being checked... You have a bounding box for the object, then a bounding box for each of it's components, etc... thus you will only check the triangles in the two colliding bboxes (b/n the 2 objects) of the lowest level, too see if there actually is a collision.

• The Raycasting check. Casting a ray from the centre/corners of an object in its direction of travel, to see if they hit any other object... Thus you can easily discard further collision detection of that object for that frame if nothing was hit, or if object hit is too far away (you'll have to check their velocities for that one)

• Start your crude checks with simpler containers. eg Use bounding spheres rather than bboxes for crude checking then fall into more detailed containers.

  Sphere -> Box -> Convex hull -> Concave hull -> ...

Those principles are completely language independent.

Answer 2

If I understand your intention correctly, you are trying to figure out how to reduce the number of collisions to check for, which is basically in the realm of 'potentially collidable set reduction'. If so, you'd do well to research spatial subdivision and/or nearest-neighbour search algorithms (such as octrees, KD trees, BSP and the like). One (or more in concert) of these should allow to to figure out which collisions are likely to have occurred before doing the full collision step.

Answer 3

What you're looking for is "spatial partitioning". You want to break up your world space into smaller chunks to cut down on how many objects you detect collision against. Since you're just doing 2D you'll probably want to use a "quad tree". There are other options including BSP trees but in my experiences quad trees are the best all around solution.

As for determining which class you're colliding with C++ doesn't handle that as nicely as C# or Java do. You can either use a "dynamic cast" to cast a generic collider class to a more specific collider class or you can store a hash of the specific type id in the generic collider to know which class to statically cast to.

Answer 4

Spatial partitioning is most definitely the way to go. The book 'Game Programming Patterns' has a very accessible chapter on the subject (http://gameprogrammingpatterns.com/spatial-partition.html) so I'd highly suggest reading that, as well his chapters on the game loop and update method.

Also, if I understand your comment correctly, each different type of object has an id (so all powerups have id=1). I'd suggest instead to let each individual object have an id, and then keep an array (or map) between an id and the instance of its class. Along with that, put in one common function (I use 'update') for each entity type so that when you detect a collision you can simply call

id=collision_result();
id2class(id).update();

and then update() different classes can respond accordingly.