# 2D Game: Most Efficient Collision Detection

• 09-17-2010, 07:00 AM
Bunkai.Satori
2D Game: Most Efficient Collision Detection
Dear all,

2D games most likely occur only in one plane. What is the most efficient collsion detection for them?

Should it be 2D collison detection based only on 2D objects, or would be more efficient to use 3D collsion objects that represent 2D objects as close as possible?

This questions is mostly for Game Development related sites, but possibly somebody can advise solution related to OpenGL ES.

Thank you.
• 10-13-2010, 09:36 PM
SteveBaker
Re: 2D Game: Most Efficient Collision Detection
The extra dimension can only make things more expensive. I'd stick with 2D.

There are a lot of strategies depending on the nature and complexity of your scene content.

The idea is to start off by doing rough comparisons to see if objects are so far apart that they can't possibly collide - then only do detailed tests for things that are close enough to be possible candidates.

A common trick is to do a one-time calculation to figure out the radius of the smallest circle (or sphere, in 3D) that encloses each object. Then each frame, you can calculate the distance between the center of every circle and the center of every other circle and if the distance is greater than the sum of the two radii - then no collision is possible. (Actually, when calculating that distance - presumably using Pythagoras - don't bother to calculate the square root - just figure out the distance-squared and compare that to the sum of the radii - squared...it's faster).

If you have so many objects that even doing a circle-versus-circle test is too much than you need to start doing things like dividing your game world into a coarse grid and creating a list of objects that are within or touching each grid cell (some objects will overlap two or even four grid cells). This data structure must be updated as objects move around. You might also want to maintain a list of non-empty cells as a linked list or something.

With that data structure, you can quickly traverse the non-empty cells and do circle-versus-circle tests on all of the objects within each cell.

The terminology for these various levels of checking are "Broad-phase" (using something like a grid), "Middle-phase" (doing sphere/sphere or circle/circle testing) and "Narrow-phase" (doing the detailed object-versus-object test).

The idea is to test everything super-quickly in broad-phase - use that to narrow down the list of objects to test in mid-phase - and use that to require super-detailed and horribly expensive narrow-phase tests.

The detailed collision test if those two circles overlap is highly dependent on how your objects are described...and in many cases, you can cheat and just say that if the circles overlap then there is a collision. (You'd be amazed at the number of games that get away with nothing more than that!)

But providing you've done the broad and/or middle-phase testing, the number of objects that require the narrow-phase test should be tiny - and therefore approachable.

Other things that can speed things up includes storing the largest circle/sphere that lies entirely INSIDE each object - and testing to see if these overlap in mid-phase. If they do then you know you have a collision without needing to do the narrow-phase test on those objects. You can also optimise things (in some situations) by never testing pairs of objects that have not moved since the last time you tested.

This whole thing is highly application-specific though. If your objects are very long and thin - then using circles or spheres in the mid-phase collision testing is likely to produce too many narrow-phase tests that result in no collisions. In such cases you might want to test rectangles/cuboids instead...it's more costly than testing circle/sphere - but if it saves you enough costly narrow-phase checks - then it might be worthwhile.

-- Steve
• 10-15-2010, 03:46 AM
Bunkai.Satori
Re: 2D Game: Most Efficient Collision Detection
Dear Stevie,

Could you, or anybody else, please advise, if OpenGL ES 2.0 can be helpful, when performing pixel based collision detection?

In some areas of my game, I need really precise collision detection. Using vertex objects (whether circle, ngon, quadrangle) would not be probably the best choice here. The ideal would be checking pixel overlay, but OpenGL is not very fast in reading back the render buffer.

Does OpenGL ES 2.0 has any fast mechanism no how to quickly check pixel overlay in 2D graphics?

Thank you.
• 10-15-2010, 04:41 PM
SteveBaker
Re: 2D Game: Most Efficient Collision Detection
No, it doesn't. Modern full-up OpenGL could do it with a technique called "occlusion query" - but there isn't a standard way to do that in OpenGL-ES without some kind of an occlusion query extension being present.

-- Steve
• 10-15-2010, 04:50 PM
Bunkai.Satori
Re: 2D Game: Most Efficient Collision Detection
Thanks Steve,

probably the best way, for precise 2D collison detection will be 2d ngon.

Regards.