Calculus: Network prediction, calculating distance over time

I've actually found that I rarely need to use any calculus in most game programming I run into. Games are generally frame-based, and as such you can generally just update variables each frame by the elapsed time. One of the main benefits of calculus is when you need to know what a value is at any given point in time, so it's very valuable when you're trying to predict where something will be after a given amount of time, and prediction is very common in any networked game.

I used a similar method to this while developing LEGO Universe's moving platform system, a system which lets the player ride upon a moving object to travel short or long distances. If a client's program had hitched for a small amount of time while on the platform, the platform would naturally see a larger gap of time had elapsed, and Havok's physics would usually accurately calculate where the platform should end up. However, we had to limit how much time we were able to skip all at once because if the client make their game hitch for a long period of time, say 5 seconds, and we let Havok just move everything ahead 5 seconds based on their current velocity, we could potentially have the player going places where they shouldn't be able to go. I can go into more detail some other time on this subject, but suffice to say we couldn't always just allow the game to move objects large distances because a large time had elapsed between frames.

The moving platform system had unique prediction algorithms because it had invisible predefined rails it had to stay on, and at each waypoint it had a speed it must be traveling at the moment it got to that point. Based on defined points on these paths, and speeds at those points, we should be able to determine exactly where a moving platform should be after any amount of elapsed time.

The image below represents a simple path for a moving platform to follow, and at each point I've labeled the speed that moving platform must be going at the time it reaches at point. So basically what this image says is when the platform leaves P1, it will be moving at 5 meters per second, and it will have a constant acceleration all the way to P2, and by the time it reaches P2 it will be moving at 10 meters per second. As it leaves P2 it will decelerate constantly such that it will be moving at 5 meters per second as it reaches P3. Long story short, it speeds up until it gets to P2, and then slows down again as it reaches P3.

In order to calculate where a platform could be at any time we need to know its acceleration. If the platform wasn't accelerating, calculating it's position at any time would be extremely simple, and would just be:
Position += Velocity * Time;

But because velocity is constantly changing as the platform speeds up and slows down along its journey, we'll need calculus to tell us what the acceleration is between the two points a platform currently lies, and then we can use that acceleration to calculate the distance traveled.

So to keep the scenario as simple as possible, lets just calculate where the platform will be after 1 second if it begins at P1.

Difference vector from P1 to P2 = (10 - 0, -3 - 0) = (10, -3)
Length of difference vector = √(10² + -3²) = √(100 + 9) = √109 = 10.440306 meters

The formula for calculating constant acceleration is:

v(f) is final velocity, v(i) is the initial velocity, and 'd' is distance it will be travelling.

The code for this is:

float CalculateConstantAccel(const float initVelocity, 
                             const float finalVelocity,
                             const float distance)
{
    if ( distance <= 0.0f )
    {
        return 0.0f;
    }
    
    float finalVelocitySqr = finalVelocity * finalVelocity;
    float initVelocitySqr = initVelocity * initVelocity;
    
    return (finalVelocitySqr - initVelocitySqr)
           / (2 * distance);
}

Plugging our values in we get:

Acceleration = (10² - 5²) / (2 * 10.440306) = (100 - 25) / 20.880612 = 3.591849

Knowing our constant acceleration, we can now calculate where the platform will be in 1 second. Here's the formula for calculating distance over time given a constant acceleration:

'd' is distance, v(i) is the initial velocity, 't' is time, and 'a' is the acceleration we already calculated above.

The code for this is:

float CalcDistanceOverTime(const float initVelocity, 
                           const float constantAccel,
                           const float timeDelta)
{
    return  (initVelocity * timeDelta)
          + (0.5f * constantAccel * (timeDelta * timeDelta);
}

Plugging our values in we get:

Distance = 5 * 1 + ( 0.5 * 3.591849 * 1² ) = 5 * 1.7959245 = 8.9796225

So the moving platform will have traveled 8.9796225 meters after 1 second, which puts it pretty close to P2, which was 10.440306 meters away. In fact, we know the direction between P1 and P2, so if we want to put the platform where is should be we can move it there based on the distance we calculated. Our difference vector from P1 -> P2 was (10, -3). We need to unitize it to make it a direction vector, and we already have the length of the vector so that saves us another step. Inverse length is = 1 / 10.440306 = 0.0957826 Unitized difference vector is ( 10 * 0.0957826, -3 * 0.0957826 ) = (0.957826, -0.2873478) And now we just multiply our direction vector by the distance we need to travel and then add it to P1: P1 + ( distance * ( direction )); New position = (0, 0) + ( 8.9796225 * (0.957826, -0.2873478)) = ( 8.600916, -2.5802747 ) So as you can see, our position after 1 second is approx ( 8.6, -2.58 ), which puts it close to P2, which is at (10, -3).

That concludes this blog post, but here's some food for thought: What if the client's game had hitched for 2 seconds? That would've put them far past P2, so you end up needing an algorithm to figure out how much time it took to reach P2, then based on the remain time left from the original 2 seconds you have to figure out how far they went between P2 and P3. Stay tuned for the solution to this in the next blog post.