Collision detections and how efficient they are

Question

How exactly do you implement collision detection? What are the costs involved? Do different platforms(c/c++, java, cocoa/iphone, flash, directX) have different optimizations for calculating collisions. And lastly are there libraries available to do this for me, or some that I can just interpret for my platform of choice?

As I understand it you would need to loop through the collision map and find the area in question and then compair the input thing(e.g. a sprite) to the type of pixel that is in the questioned area. I understand the very basic idea, but I don't understand the underlying implementation or even a higher level one for that matter. It would seem that this type of detection, or any for that matter, is very costly. Tile map? Bit array? How are these created from an image(I would guess looping and doing stuff)?

The reason I ask this question is to get a better understanding of the efficiency behind the scenes and to understand exactly what is going on. Links, references, or examples would be very helpful. I know this question is a bit longwinded so any help or references would be very welcome. Thanks SO!

Answer 1

Check this answer of mine regarding simple bounding box collision detection.

Collision detection is a huge topic, but there are primiarly two areas. Broad phase, and narrow phase detection. Broad phase is quick and dirty, if this passes you move onto narrow phase detection. Narrow phase in turn is more complex, in depth detection. Even if a collision is detected in broad phase detection, the object may not have collided with anything.

The key to being efficient within games is to not do work if you don't have to. In other words, if you don't have to perform collision detection, don't. What I mean by this is imagine a game like GTA4. It would be madness, plus the game would run like a slideshow if you were to check each object against each other object in the world. A variety of methods can be used, but the best method is to limit the amount of checks. Here the world is split via the use of quad/oct/binary/ trees or some other spatial indexing algorithm. This means only nearby objects are checked, and thus the game will run much faster as only possible objects are checked for collisions.

"How are these created from an image(I would guess looping and doing stuff)?"

Yes and no. Per pixel collision detection falls into narrow phase detection, and is costly. In the majority of games it is simply not needed. Take a generic FPS. If you shoot an enemy between the legs say, it sometimes is classed as a hit, this is not pixel perfect, yet it works good enough.

For 2D games, you'd know the size of the sprite, so any calculation would use a bounding volume. The same goes for 3D games, except this bounding volume is now in three dimensions. You can break complex shapes/models down into further bounding volumes. This process is then much, much quicker than checking pixels. Sometimes however, per pixel detection is required. It all depends on the type of game.

As for good links, I'll point you to Gamedev.net. It's an excellent site to get started, should cover a broad variety of topics. A nice tutorial, showing you what further concepts can be applied is based around the development of a game called N and N+. To conclude, a game is an experience and illusion. At anytime if game programmers can make a simplification to speed up development or the game, we take it.