Thursday, March 4, 2010

2D Collision Detection: Part 1

 
Last night, I completed my simple 2D collision detection function and tested it.  It works!  Before I divulge the details of my algorithm, I'll show you my process.  When I was researching algorithms, I came across some common ones people were using:
 
  1. Bounding Box algorithm: put each object into a bounding box and then determine if two boxes intersect each other  

  2. Bounding Circle algorithm: put each object into a bounding circle and then determine if two circles intersect each other (offhand, this one seems quicker and possibly more accurate for more organic shapes than the bounding box algorithm)  

  3. SAT using convex polygons: This one is more complex than the other two and requires significant work beforehand.  Basically, you need to create a convex polygon for all objects (likely a manual task), and then you can use SAT (Separating Axis Theorem) to determine if two polygons intersect each other.  My thought is that using SAT will be the most accurate algorithm, but I got scared off by the thought of having to calculate normals for each edge and the shear number of projections involved.  Also having to manually set up polygons for each object seemed like just too much work.

I figured that I would start simple, so it would have to be either bounding box or bounding circle.  The basic algorithm would be:


Given box A and B and vector V that represents the movement from A to A':
  1. move box A to A'. 
  2. if A' intersects B, then reverse A' to the point where it no longer intersects B.
 
The problem here is: what if B is between A and A' and V is large enough such that A' passes B? 

 

In such a case, A would simply move right through B.  I looked online for solutions on this and the only solution I found was: keep vector V relatively small (ie: Don't move A so fast!).  I could understand that in most cases, this would not be an issue.  But what if B was skinny? 

 
In such a case, it would not take V to be very large before this problem occurred.  I was determined to find an algorithm that would not only account for the starting and ending position of A, but also the path of A to A' (the darker red area below).
 
 Next time I will look into the strategy of how to implement this.

 


2 comments:

  1. great post.. given me more insight.. trying to implement a simple collision for a pinball like game..

    ReplyDelete
  2. These common algorithms for 2D collision detection are great beginning points for developers. The visuals you provide are similarly helpful for conceptualizing the process of Android game development. Your technical information is simple and clear, I'll look forward to your next post about implementation strategies.

    ReplyDelete