Tuesday, September 27, 2011

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; }
       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; }
          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 

  // 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;
     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.

Thursday, September 1, 2011

Building Your Own Game Engine - Physics

This is the first one of next two articles that will cover two very close subjects, physics and collision detection. Physics for games for the most part covers moving some bodies in the game world according to the laws of physics. As these bodies occupy some space in the world, we need to detect when collisions among this bodies occur and resolve them. I will assume the reader is familiar with Newton's laws of motion, since you are reading an article about making a game engine and physics in particular.
The Jelly Reef actually uses two somewhat separate physics systems. One used to move objects in the game around and it's completely entangled with the rest of the game. And there is another one, based on particles, used for some specific effects. Our game is not trying to simulate the real word or be realistic, so I decided we take simplistic approach, with plenty of shortcuts. First shortcut was to model the jellies and all other moving objects as point mass and this ignore any actual distribution of mass. Angular movement was not simulated at all, so no torques, no moments of inertia or in fact any physical angular property. This means we treat all objects as particles we can basically reuse the code from the particle. What follows are the properties of the particle class.
public class Particle
  // The position of the particle in world space
  public Vector2D Position;

  // Linear velocity of the particle in world space.
  public Vector2D Velocity;

  // Linear acceleration of the particle
  public Vector2D Accleration;

  // Damping is required to remove energy added
  // through numerical instability in the integrator.
  // Or to act as drag
  public float Damping;

  // Holds the inverse of the mass of the particle.
  // It is more useful to have objects with
  // infinite mass (immovable) than zero mass
  // Also one division less
  public float InverseMass;
  public float Mass
    get { return 1.0f / InverseMass; }
    set { InverseMass = 1.0f / value; }
  public bool HasFiniteMass
    get { return InverseMass != 0.0f; }

  // Force accumulator, for dalamber's principle
  public Vector2D ForceAccum;
Next we need to move these objects. Newtons laws are expressed as differential equations so the values are calculated using numerical integration. For this purpose we use Euler integration as it's very easy to implement, but it is not very precise.
public void Integrate(float dt)
  float duration = dt;

  // Update linear position
  Position += Velocity * duration;

  // Work out the acceleration from the force
  Vector2D resultingAcc = Accleration;
  resultingAcc += ForceAccum * InverseMass;

  // Update linear velocity from the acceleration
  Velocity += resultingAcc * duration;

  // Add drag
  Velocity *= (float)Math.Pow(Damping, duration);

Time is continuous (except maybe in quantum mechanics, which beyond the scope of this article and my brain) and our simulation takes discreet steps into it, so errors get accumulated over time. This imprecision can build up and eventually make the simulation explode and I will return to this later.
Although we are not simulating the angular movement, we still need to know the orientation of the objects for both, gameplay and rendering purposes. The solution was to simply align the object to face their direction of movement. However this looks ugly when the direction of movement changes rapidly over few consecutive frames, so the orientation was in fact interpolated from the current one the desired one limiting the change with maximal angular velocity value. This piece of code was not really elegant of flexible and in future I would consider using spinors for this purpose.
As I mentioned before we also employed a separate particle based physics system. This simple system simulated particles on which some forces can be applied. No contacts or hard constrains were imposed on the particles. The most used part of the system were the spring-damper systems.
The seaweed was implemented with such a system. Each weed modeled as a two particles connected to each other with such a spring, while simultaneously having one of them being attached to the seabed with another spring. A third spring from the base to the tip tries to keep the form of the weed. On the image to the left we see the three springs in red using the debug drawing.
The water motion also imposed forces on all particles in it. The smooth movement of the camera was also implemented using a spring.
Particles were used for the bubbles. Obviously the main aim of this dynamic system was to give feedback to the player while he/she plays by controlling the water.
In an early version of the game the jellies had tentacles, which were modeled with a spring system, exactly like the one on the seaweed. Unlike the seaweed, the jellies move and this adds force to the spring system and tentacles become longer. I tried to remedy this by making the springs stiffer and that is where the Euler integration totally failed. As soon as the spring overextends, a force too large will be applied. In the next iteration the spring will overshoot again and in turn generate and even larger force, until the simulation explodes with the tentacles way outside the screen. This could have been solved by using better integrator like RK4 or Verlet Integration. It turned that the jellies look way better without the tentacles anyhow so I was of the hook.