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;

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

ForceAccum.Clear();
}
```
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.