How do you implement 2D collision detection?

I would like to know the best or most efficient way to test for 2D collision.

I am currently using AABBs, but the problem with this, is that your objects will be hitting things when they shouldn't. On top of this, AABBs cannot be rotated.

I was considering using per pixel collision, but I feel that it would lag on large bitmaps, since there would be a lot of pixels to check.

What I would like to know, is how I can allow my bounding boxes to be rotated, and use any polygon instead of just rectangles for collision. Also, is there a way of creating circular collision bounds that aren't just approximations of circles?

-
Why would you use `atan2()` for circle vs. circle? – bummzack Feb 20 '12 at 10:18
For circle circle collision, all that you have to do is check whether the distance between the centers is less than the sum of the radiuses. Also, avoid atan2() if you can - the function is incredibly slow. – mdkess Feb 20 '12 at 15:23
@mdkess thanks for the tip : ) – Aidan Mueller Mar 7 '12 at 17:27

1 Answer

So it depends on what you are trying to do.

If you want something simple, I recommend stick with axis aligned AABBs for most things - they make collision detection really easy.

Generally when you're writing collision code you'll have to write specialized cases for all pairs of shapes (ie. line-line, line-circle, line-box, circle-line, circle-box, circle-circle, box-box).

For 2D, the main principle is called the Separating Axis Theorem. This is an excellent guide to it.

Typically another trick that people use is to have multiple layers of collision detection to speed things up. Circle-Circle collision might be expensive, but if you check whether the two circles AABBs are overlapping first, you can potentially save a lot of time.

If you are really wanting to have more advanced physics and response, I would recommend that you go with an already made physics engine. JBox2D is a port of the popular Box2D engine, and is generally quite good. That said, I would still recommend reading through those two articles so that you have an understanding of what is going on behind the scenes with collision detection and response.

-
Thank you so much – Aidan Mueller Feb 20 '12 at 5:09