Building Your Own Game Engine - Collisions

This article discusses collision detection and resolution. It directly follows my previous article on physics. I have decided for two separate articles so that the text doesn't run longer than your (and mine as well) attention span.

Most physics engines combine collision detection system with the rest of the engine, but many also allow the one to used without the other. In the case of The Jelly Reef, both of the systems are simple and completely separated except for the objects they act upon. Basically, first all the forces are applied and paths integrated. Then using the new positions collisions are found and resolved.

To do collision detection we first need to have bodies that collide. Early on, we decided that for all objects in the game the collision shape will be approximated with either a disk or a rectangle. Moreover, every objects stores both and the two are always in sync. The disk is also circumcircle of the rectangle at all time. Having a disk around the rectangle allows for early outs when doing collision checking, as disk to disk is a very cheap test to do.

public class BaseGameEntity : ISceneNode
{
  // Some code...

  [Description("Bounding radius of the entity. Used for collision detection")]
  public float BoundingRadius
  {
    get { return boundingRadius; }
    set
    {
       float s = value / boundingRadius;   // scale
       boundingRadius = value;
       scale *= s;
     }
  }
  protected float boundingRadius;

  [Description("Half dimensions in a single vector.")]
  public Vector2D Dimensions
  {
      get { return scale; }
      set
      {
          scale = value;
          // Set the bounding radius so that a recatangle with the given
          // dimensions will fit in the disk.
          boundingRadius = (float)Math.Sqrt(value.X * value.X + value.Y * value.Y);
       }
  }
  protected Vector2D scale;   

  // some more code...
}

The game also features some static geometry in the form of walls and these were created from linear segments.

The collision system every frame over the objects and tests for collision among them and collisions against the walls. Each collision is stored in a array of Contact structures. The structure holds all the data that is needed to handle this contact.

public struct Contact
{
  // Holds the first bodie in the contact
  public BaseGameEntity FirstBody;
  
  // The second of these can be null, for contacts with the level
  public BaseGameEntity SecondBody;

  // Holds the direction of the contact in world coordinates.
  public Vector2D ContactNormal;

  // Holds the depth of penetration at the contact.
  public float Penetration;

  // A mechanism to detect collisions to raise event but 
  // not reslove in the physics engine
  public bool Resolved;        

  // A hash code uniquely defining the contact of these two entities
  // Makes sure that each pair of entities is checked exactly once
  public override int GetHashCode()
  {
     int hash = firstBody.GetHashCode();
     if (secondBody != null)
        hash ^= secondBody.GetHashCode();
     return hash;
  }
}

For performance reasons we set a predetermined number of contacts that we can have in a single frame, all others will have to wait for the next frame. We also store all the contacts in a preallocated array so that we avoid allocating new objects every frame and strain the garbage collector.

As I mentioned we have two shapes for collision geometry. With the linear segments for the walls this gives us 3 object types that can collide. Walls will not collide with walls, that leaves us with five combinations of shapes we need to handle. For all cases we use the separating axes theorem.
The theorem states that if the two convex objects are not interpenetrating there is an axis for which the projections of the two object will not overlap. This test is very robust and general, straight forward to implement and easy to debug. It also gives much of the needed information we need for resolution. The contact normal is the axis itself and the interpenetration is the amount of overlap along it.

The problem is of course to find this axis. For polygons such axises run through the vertices or are perpendicular the the line segments. For an intersection test among two rectangles that would yield 16 potential separating axises to be tested. We tackled the problem of optimizing the number of axises for each of the cases separately.

As a en example I will explain a very straight forward test from the game on the drawing below, an axis aligned rectangle against a linear segment.

From the drawing we see that one testing axis is aligned with the line segment and the other one is perpendicular to it. The rectangle and its projections are drawn in blue while the line segment and its projections in red. On the drawing we can see that the projection on the axis perpendicular to the line segment there is no overlap, so we have found the separating axis. The drawing also clearly shows that I have a cool whiteboard, but enough of that, lets show the code for this test.

public static bool AARectToWall(
   Vector2D centerR, Vector2D halfDimR,
   Vector2D start,       Vector2D end)
{
  // Create first axis 
  Vector2D axis1 = (end - start);
  // Normalization gives interpretation to the intervals 
  axis1.Normalize();

  // Project the line segment by projection the end points
  float Sp = axis1.Dot(start);
  float Ep = axis1.Dot(end);
  // Make the interval 
  CreateInterval(ref Sp, ref Ep);

  // Project rectangle - All four vertices
  float rectLeft;
  float rectRight;
  // First  calculate the vertices
  Vector2D A = centerR + halfDimR;
  Vector2D C = centerR - halfDimR;
  Vector2D B = new Vector2D(A.X, C.Y);
  Vector2D D = new Vector2D(C.X, A.Y);

  float Ap = axis1.Dot(A);      // Project vertex A
  float Bp = axis1.Dot(B);      // Project vertex B
  float Cp = axis1.Dot(C);      // Project vertex C
  float Dp = axis1.Dot(D);      // Project vertex D

  // Cretate inital interval
  rectLeft = Bp;
  rectRight = Ap;
  CreateInterval(ref rectLeft, ref rectRight);
  // Extend it
  AddInterval(ref rectLeft, ref rectRight, Cp);
  AddInterval(ref rectLeft, ref rectRight, Dp);

  // If there is no overlap, we have found the separating axis
 if (IntervalOverlap(Sp, Ep, rectLeft, rectRight)  <= 0.0f)
    return false;

  // Second axis, perpendicular to the segment
  Vector2D axis2 = axis1.Perp;

  // The line segment projects to a single point
  Sp = axis2.Dot(start);

  // Project the vertices
  Ap = axis2.Dot(A);
  Bp = axis2.Dot(B);
  Cp = axis2.Dot(C);
  Dp = axis2.Dot(D);

  // Create the rect interval
  rectLeft = Bp;
  rectRight = Ap;
  CreateInterval(ref rectLeft, ref rectRight);
  AddInterval(ref rectLeft, ref rectRight, Cp);
  AddInterval(ref rectLeft, ref rectRight, Dp);

  // Check if the second axis e separating  
  if (IntervalOverlap(Sp, Sp, rectLeft, rectRight) <= 0.0f)  
    return false;
  else
     return true;   // No axis found, shapes are intersecting
} 

The next step after detection of collisions is to call all the subscribers for each type of collision. This is where gameplay code might be implemented I it was discussed in detail in the article on gameplay. The event can choose to set the resolved flag to true, so the collision manager will not resolve the collision. This can have many uses. When a jelly hits a rapidly rotating propeller for example, the jelly will not bounce back but rather be removed from the scene and replaced with some gooey jelly pieces.
The last step is to resolve the unresolved contacts. This is done by simply moving them along the contact normal. In the case of a collision with the level geometry, the object is simply moved the full penetration depth. In the case of two objects, both are moved by taking their mass into account. The flowing piece of code, adapted from from Game Physics Engine Development, does exactly that.

// Some code ...
BaseGameEntity first = contact.FirstBody;
BaseGameEntity second = contact.SecondBody;
                
// The movement of each object is based on inverse mass, so total that
float totalInverseMass = first.InverseMass + second.InverseMass;
                
// If both have infinite mass, skip this contact
if (totalInverseMass <= 0) return;
                
// Calculate amount of penetration resoluion per total inverse mass
Vector2D movePerInverseMass = contact.ContactNormal *
  (-contact.Penetration / totalInverseMass);
                
// Move 'em
first.Position   += movePerInverseMass * first.InverseMass;
second.Position -= movePerInverseMass * second.InverseMass;
// More code...

Hope this last few articles gave an inside into the bits and pieces of game development that are the not easiest to find information on. The next article is on graphics and will be the last one in the series as well.