What is the best approach to 2D collision detection on the iPhone?

Question

Been working on this problem of collision detection and there appears to be 3 main approaches I could take:

1. Sprite and mask approach. (AND the overlap of the sprites and check for a non-zero number in the resulting sprite pixel data).

2. Bounding circles, rectangles or polygons. (Create one or more shapes that enclose the sprites and do the basic maths to check for overlaps).

3. Use an existing sprite library.

The first approach, even though it would have been the way I would have done it in the old days of 16x16 sprite blocks, it appears that there just isn’t an easy way of getting at the individual image pixel data and/or alpha channel within Quartz (or OPENGL for that matter). Detecting the overlap of the bounding box is easy, but then creating a 3rd image from the overlap and then testing it for pixels is complicated and my gut feel is that even if we could get it to work would be slow. Am I missing something neat here?

The second approach involves dividing up our sprites into several polygons and testing them for overlaps. The more polygons the more accurate the collision detection. The benefit is that it is fast, and can be accurate. The downside is it makes the sprite creation more complicated. i.e., we have to create the polygons for each sprite. For speed the best approach is to create a tree of polygons.

The 3rd approach I’m not sure about as it involves buying code (or using an open source licence). I am not sure what the best library to use is or whether this would make life easier or give us a problem integrating this into our app.

So in short I am favouring the polygon and tree approach and would appreciate you views on this before I go and write lots of code.

Best regards

Dave

Answer 1

Consider polygonizing your sprites. Keep a polygonal representation for your sprites "in the background" and do collision testing with the polygonized version of your game world. This produces some overhead and additional complexity, but is often very rewarding in terms of additional possibilities. (dynamic shadows, lighting effects, collision detection independent of sprite graphics, many more collision detection methods, polygonal intersection etc.)

Otherwise you are stuck with the pixel based approach you described, which is also not bad. (ORing the overlap) You can just do it on your own or let OpenGL do it in the frame buffer. (I can't remember the calls, think it was called z-masking (?), ... sorry. For small sprites this might even be slower...) Consider using binary space partitioning techniques in order to optimize some of it:

Quad trees for example, allow you to quickly find the candidate sprites for collision testing. They are applicable on both the pixel and vertex based approach. Or just use BSPTrees.

Btw: I think pixel precision on collision detection is actually a nice feature, I used it a lot in Jump'n Runs. Maybe not applicable to your game, though.