Integration: Our Best Friend (Part 1)

In this post, which will be divided in three parts, I'll cover some basic maths that are required for most games. Concretely I'll cover a couple of numerical integration methods. For those of you who don't like maths, I'll advice you to give it a try, because I'll try to keep the explanations as simple as I can. Also, you should not be discouraged if you don't understand something: in the very end, you can (and probably will) use abstraction and use some physics library that includes what we're seeing here. However, as a recommendation, if you're serious about developing games, you should try to understand at least the most basic concepts, and I'll try to help you attain this. 

In the heart of any physics engine we can find the so-called integrator. The goal of an integrator is quite simple: given an acceleration on an object (or a force, as we will see), it calculates how the position is updated accordingly. And you will be wondering: why do I need this?

Well, in the very end, you will have something like this in your code:

object.setPosition(x, y); //Assuming a 2D game

object.draw(window); //It draws the object in the position set before onto the screen

But how is this position calculated? Of course, if the object is your character, the player's input will update the position. For example, you could do this:

if (input.isKeyPressed(RIGHT_KEY)) {
   x = x + 1;
}

If the right arrow is pressed, the x-position is advanced 1 unit or pixel. However, there may be other factors that have an influence on your character. For example, in any traditional platformer, we have to consider gravity. Gravity is an acceleration that pushes all the objects downwards in the y direction. So, if you want gravity to affect your character, you have to figure out the y position of you character from the acceleration induced by gravity after a period of time. Well, here is where an integrator is useful.

This first post will introduce the problem of integration. The second post will explain the Euler integration method, because it is the most simple one. Finally, the last post will describe two of the most widespread methods: Runge-Kuta order 4 (RK4) and Verlet. 

Derivatives or the rate of change

First of all, it is important to know the mathematical relationships between position and velocity, and between velocity and acceleration. (Note: I'm using the term velocity instead of speed because I'm assuming that velocity is a vector. That is, velocity implicitly includes a direction, whereas speed is just a scalar value representing an amount of movement).

Velocity is the derivative of position, and acceleration is the derivative of velocity. Derivatives are a way to measure rate of change of one variable with respect to another variable. Therefore, velocity represents the rate of change in position, and acceleration is the rate of change in velocity. 

For example, assume that the velocity is constant: let's say 5 pixels per second. Let's also assume that the object starts at position 100 along the X-axis (let's assume only one dimension for simplicity). So, after a second, the position of the object will be 105. After another second, the position will be 110, and so on. 

But what happens if we add acceleration to this scenario? Velocity will change also every second. For example, if we choose a constant acceleration of 10 pixels per second and we assume an initial velocity of 0, after one second, the velocity will be 10. After two seconds, the velocity will be 20, etc. And the position would change faster as the time goes by. 

Graphically, the rate of change at one point (i.e. the derivative at one point) corresponds to the slope of the tangent line at that point, as depicted in Figure 1.

Figure 1 (source: Wikipedia)

If velocity is constant (let's say 1), it means that the slope of the tangent line is 1 in every point of the position graph, that is, the position graph is a straight line (y = x), as shown in Figure 2.

Figure 2 (source: http://www.gcse.com)

On the other hand and following with the same example, the velocity graph would be a straight line at y=1 (i.e. without slope). This means that the slope at every point in the velocity graph is 0, meaning that there is no acceleration (it's normal, as we said that velocity is constant). Figure 3 shows the graph of the position (assuming an initial position of 0) (y=x) and the graph of the corresponding velocity (y=1). 

Figure 3 (source: http://www.ltcconline.net)

Maybe now, for those of you who know some maths, it is more clear why we're talking about integrators. Integration is the opposite to differentiation. If we wanted to figure out the velocity from the position, we should differentiate the position. But we want to do the opposite: we want to integrate velocity to figure out the position (and the acceleration to figure out the velocity). 

Analytical integration is usually a tough task. It comprises first finding a primitive and evaluate it over some interval. Sometimes finding such primitive is impossible. However, numerical integration (which is basically what we did in our previous example) is much easier. Numerical integration requires knowing some values for the derivative (e.g. velocity) at some points in time. We know that these values represent the slopes of the tangent lines at those points in time in the position graph.  What both Euler and RK4 do is stepping forward the position in time by a fixed amount, h, on that tangent line. How they do this will be the contents of the next part of this post.

Hope that at least the foundations are more or less clear, and don't hesitate to leave comments or suggestions (or error corrections if it's the case :)). 

See you soon!