Collision detection by detecting ...no-collision

What can destroy your game? A bad collision detection algorithm that either returns error results or it is slow or both of them. What if you have hundreds of objects in a scene that have to be checked for collisions using an algorithm hungry for CPU resources?

In this tutorial I am presenting a way that I believe covers the needs of the 90% of the game developers. I am showing you how to perform very quick collision detection in 2D assuming that every object that carry collision dynamics in your game universe can be consider either as a rectangle or as a circle.

If there are special reasons to perform collision detection between objects that are of any kind of shape then you can approach them by splitting them in rectangles/circles or ...re-thing if you really need all this geometry. And if you finally decide to proceed with this then after you have prayed and sacrificed to Zeus...

... you have to befriended with trigonometry but remember: Never call trigonometric functions (sin(x), cos(x), tan(x), etc). Create instead (use this excel spreadsheet) an array (or more) with all possible angles that your game uses and get from there whatever you need.

Checking if two rectangles DO intersect can lead to a complex system of inequalities that has to be checked one-by-one, no escape, no 'break's, no 'return's, for each pair of objects, in each cycle of the game loop.

I don't even want to reproduce here the nightmare of such an inequalities system. Just take a pencil and a (large) piece of paper and draw all possible relative positions of two objects to understand the underlying complexity.

Instead of doing this it is much simpler to find whether two objects DO NOT collide at all. See the sketches bellow. There are only four cases:

To understand the simplicity, I want you to forget for one moment that there are programming languages in this world. Staring at these four pictures it makes sense that if you detect that you belong to one of these cases, then there is absolute no reason to check the remaining cases and you simply return with a result like COLLISION_NO. But if you end up by realizing that you are not in any case of them then only one result remains for you to accept: COLLISION_YES

And exactly this is the logic that I am going to implement. So, assume we have two rectangles A and B and call (x, y) the coordinates of the upper left corner. By knowing also the width and the height of each rectangle we can easily detect all other sides of it. It is very easy to get width & height in the loading procedure of the (image-)resources since almost every graphics library offers functions like getWidth() and getHeight() for its supported images.

So, I am repeating the sketch above by adding in each case the algebraic condition

Picture 1
A.x + A.width < B.x

Picture 2
A.x > B.x + B.width

Picture 3
A.y + A.height < B.y

Picture 4
A.y > B.y + B.height

Now, pack these conclusions in a function, let's call it “getCollisionResult”, that takes two rectangles as arguments and returns COLLISION_NO or COLLISION_YES that can be (#)defined as integers(0 or 1) , booleans(false or true) or whatever other primitive type you like.

result getCollisionResult ( rectangle A, rectangle B)
{   
   // picture 1   
   if ( A.x + A.width < B.x ) // 1 math operation (addition), 1 comparison
      return COLLISION_NO;      
   // picture 2   
   if ( A.x > B.x + B.width )      
      return COLLISION_NO;      
   // picture 3   
   if ( A.y + A.height < B.y )      
      return COLLISION_NO;      
   // picture 4   
   if ( A.y > B.y + B.height )      
      return COLLISION_NO;      

   // reaching at this point means that the rectangles overlap
      return COLLISION_YES;
}

As you see with a little luck you can end up a cycle of the game loop by doing very few CPU-operations for performing collision detection between two rectangles, 4 at the worst case plus 4 comparisons. There is another implementation of this function to reduce the operations to 2 but I leave it as an exercise for you.

This is not the main function that is going to realize your wishes when a collision is detected, but it is a helper function instead. The main function would look like this

result_type HandleCollision( )
{   
   for ( i = 0; i < objectsInGame; i++ )   
   {      
      for ( j = i+1; j < objectsInGame; j++ )//why j=i+1 ???      
      {         
         // before proceeding with checking for a collision,
         // see if these objects don't even need to be checked.
         if  ( checkObjects(obj[i],obj[j] ) == true)
         {            
            if (getCollisionResult(obj[i].rect,obj[j].rect)
                                         == COLLISION_YES)            
            {               
               // ...do whatever you want.            
            }         
         }       
      }  // END for ( j = ... )   
   } // END for ( i = ... )
}

What happens now if your have circles?Then also in this case you can use the function getCollisionResult by passing to it the rectangles that contain these circles. But it may be not accurate enough since it is possible to fall in this case:

The solution for this is to add another argument in the getCollisionResult function so that also the kind of the shapes is known now to the function. So, if the four “if”s are passed without returning NO, then the rectangles collide and only from now on is the best time to check the circles themselves by applying in our calculations the following lemma from the Euclidean geometry:Two circles collide only if the distance of their centers is less or equal to the sum of their radius as it can be seen in the following picture:

But given the centers (cx1,cy1) and (cx2,cy2) of two circles with radius r1 and r2 respectively the distance d between the centers is

And to check if our circles are far away from each other then it has to be check if

To strike the CPU with a square root is not the most gently you can do to it. It is a heavy operation and could lead to unnecessary delays. To avoid this take the square of the above relationship and you finally have to check this inequality:

where there is no square root. After all these, dive into coding and extend the function getCollisionResult like this:

...
radius_A = (A.width)/2;
radius_B = (B.width)/2;
...

result getCollisionResult ( rectangle A, rectangle B,
                            int shape )
{   
   // picture 1   
   if ( A.x + A.width < B.x ) 
      return COLLISION_NO;      
   // picture 2   
   if ( A.x > B.x + B.width )
      return COLLISION_NO;
   // picture 3
   if ( A.y + A.height < B.y )
      return COLLISION_NO;
   // picture 4
   if ( A.y > B.y + B.height )
      return COLLISION_NO;

   // reaching at this point means that the rectangles overlap
   if ( shape == CIRCLE )
   {      
      centerA_x = A.x + radius_A;
      centerA_Y = A.Y + radius_A;
      centerB_x = B.x + radius_B;
      centerB_y = B.y + radius_B;   
   }      
   distance_square = (centerA_x - centerB_x)^2 +
                     (centerA_y - centerB_y)^2;
   if ( distance_square > (radius_A + radius_B)^2 )
      return COLLISION_NO;

   return COLLISION_YES;
}

As it is clear when looking into the if ( ...CIRCLE ) section it would be very painful for the CPU to consider from the beginning the two circle-objects as circles and proceed directly with the if ( shape == CIRCLE ) section. At least do it once the container-rectangles collide which is extremely lighter to find it out.Of course you can optimize this new variation of the function getCollisionResult but I leave it as an exercise.