Collision Detection...

There are many ways to do collision detection in games, but only 1 I recommend.  1 method literally prints both images over each other, and checks each border pixel to see if its colliding with another from another object.  Imaginably, this can take a while.  Another checks each boundary as a box and uses basic if statements to determine how effective it is.  The third, and one I will recommend is using a Pythagorean distance checking formula.  First, I’ll get into the bounding boxes, and consider what it takes. 

With bounding boxes, you make the presumption that each of your objects fit within a rectangle.  Each object gets a location vector (Vectors were discussed in a previous article), and a Dimension vector that defines the rectangle’s height and width.  In order to compare the bounding box, we need to find out if any part of the box in inside the other. 

To do that it is somewhat straight forward, but repetitive and with small changes.  Essentially, you need to consider each border. And whether or not it is inside the other box.  Lets Presume, the following Object Fields:  Box.X, Box.Y, Box.Width and Box.Height.

The first part is easy.  Are either of the vertical sides of Box2 to the right of Box1.X.    If either are to the right of the left side of the box, it has the potential of being inside the box.

Boolean CollisionDetection(Box1, Box2)

{

If Box1.X < Box2.X OR Box1.X < Box2.X + Box.Width, Continue checking;

}

               

                Another way to write the same line, is to decide to stop checking, Like so:

Boolean CollisionDetection(Box1, Box2)

{

If NOT (Box1.X < Box2.X OR Box1.X < Box2.X + Box.Width), Return False

}

                Essentially at each validation line of the collision, it can stop processing, to save work, when it has already determined that it can’t be touching.  The line for determining the Top is almost the same as the height.

Boolean CollisionDetection(Box1, Box2)

{

If NOT (Box1.X < Box2.X OR Box1.X < Box2.X + Box2.Width), Return False;

If NOT (Box1.Y < Box2.Y OR Box1.Y < Box2.Y + Box2..Height), Return False;

}

                Detecting the bottom and right sides are similar, and to make it easier, I’ll add a few variables.

Boolean CollisionDetection(Box1, Box2)

{

                Top1 = Box1.Y;

Top2 = Box2.Y;

Bottom1 = Box1.Y + Box1.Height;

Bottom2 = Box2.X + Box2.Height;

Left1 = Box1.X;

Left2 = Box2.X;

Right1 = Box1.X + Box1.Width;

Right2 = Box2.X + Box2.Width;

If NOT (Left1 < Left2 OR Left1 < Right2), Return False;

If NOT (Top1 < Top2 OR Top1 < Bottom2), Return False;

If NOT (Right1 > Right2 OR Right1 > Left2), Return False;

If NOT (Bottom1 > Bottom2 OR Bottom1 > Top2) Return False;

Return True;

}

                So this is checking to see if one box is colliding with the other.  This includes checking if one is inside the other.  Reviewing this code though, it takes at least 4 equations, and at least 8 if statements.  So for every comparison you have 12 steps being processed.  At 2 objects to compare, this happens only once, but with 3 objects, you’ll have to repeat this 3 times, and with 4 objects, 6 times.  Lets presume the game has 20 objects on the screen that you need to detect collisions for, that means it has to run this 190 times.  That means 760 mathematic equations and 1520 comparisons.

                Its easy to see that this builds up quickly.  It also limits your areas to boxes.  Sometimes boxes are exactly what you need.  This is often true of Map based games, where things are set on squares (even if the squares are not so visible to the player).  But in free floating games, like flight simulators, water or space games, using circles is faster and easier.   Don’t worry about Cosines or Tangents, this won’t require any Trigonomic functions.

                Pythagorean Theorem is all that we’ll need.  If you haven’t gotten to it in school, or forgot it, here it is; In a right triangle (it has a 90 degree angle) the hypotenuse (the side opposite the 90 degree angle) is equal to the square root of the sum of the other 2 sides squared.

                In plain mathematics, the triangle below, C = √(A*A+B*B).   In code, that looks like C = Math.SquareRoot(A * A + B * B);.  The order of A and B don’t really matter in this case. 

               

               

                The next question is how to apply this to in our code.  X and Y are also 90 degrees apart.  Lets say X is A and Y is B.  What you need is the X and the Y differences, and you get the points where A and C connect, and where C and B Connect. 

                In our new Game Objects, we will use location and radius or size.

//Game Object

{

                Vector2 Location;

                Float Radius;

}

To test if they impact, we will get the distance, and decide if it is greater than the radius of the 2. 

//Compare Objects

Boolean DetectCollision(GameObject g1, GameObject g2)

{

                Vector2 Diff = g1.Location – g2.Location;

                Float distance = Math.SqRt(diff.X * diff.X + diff.Y * diff.Y);

                If distance > g1.Radius + g2.Radius, return true;

                Return false;

}

                This code is considerably smaller.  Vector2 math uses 2 equations for each equation we use on it.  “g1.Location – g2.Location” is the same as “g1.Location.X – g2.Location.X” and “g2.Location.Y – g2.Location.Y”.  There are 7 equations and 1 comparison when checking 2 objects.  For 3 objects, there is 21 equations and 3 comparisons.  For 20 objects there is 1330 equations and 190 Comparisons.  So that is a significant improvement over bounding box collisions.  (As a reminder, that was 760 Equations and 1520 Comparisons, for 20 objects)

                But part of my statement isn’t true.  Bounding boxes can work better in some conditions.  For instance if the most common collision detection is between the player and everything else, and the player is typically at the bottom.  Your first check can be the top border.  If that fails, it can be only 1 equation and 2 comparisons.  Which means your most average check would only be 190 equations and 380 comparisons for 20 objects.  That is dramatically less.  Bounding box comparisons can leave earlier. 

               

                I recommend implementing both systems for practice, and doing some comparisons early in your game to decide which works best and why.   Do some performance testing on how it effectively works.