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")]
{
set
{
float s = value / boundingRadius;   // scale
scale *= s;
}
}

[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

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

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

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;