Saturday, November 12, 2011

Calculus: Network prediction, calculating time to travel a distance

In the last post we talked about how we could calculate how far something traveled over a specific amount of time based on its velocity and acceleration. In that post we were left with a problem, we know our origin and destination positions, and how much time has elapsed, and after a certain amount of time we found we had past the destination. What we really need to know now is how long it will take us to get to our destination given our velocity and acceleration, that way we know how much time is left after we got to the destination.


Given the path above, we had calculated that after 1 second we were almost to P2 if we had started at P1. But what if the client's game had stuttered for 2 full seconds? Where would we put them along the way then? Well, to know that we need to know how long it takes to get from P1 to P2.

Here is the formula for calculating how long is takes to travel a specific distance given an initial velocity and a constant acceleration:

't' is time, v(i) is initial velocity, 'a' is acceleration, and 'd' is the distance between the points.

Our initial velocity is 5 meters per second.
Our constant acceleration is 3.591849, which we calculated in the last blog post.
Distance is 8.9796225, which was also calculated in the last blog post.

If we plug the numbers in we get:
Time = ( -5 + √(5² + 2 * 3.591849 * 9.9796225) ) / 3.591849
        = ( -5 + √(25 + 71.690594) ) / 3.591849
        = ( -5 + √96.690594 ) / 3.591849
        = ( -5 + 9.8331375 ) / 3.591849
        = 4.8331375 / 3.591849
Time = 1.3455868 seconds

And here's the code:
float CalcTimeOverDistance( float initVelocity, 
                            float constantAccel,
                            float distance )
{
    if ( distance <= 0.0f )
    {
        return 0.0f;
    }

    // If there is an acceleration present
    if ( constantAccel != 0.0f )
    {
        float initVelSqr = initVelocity * initVelocity;

        return (-initVelocity 
                + sqrt(initVelSqr + (2*constantAccel*distance))
                / constantAccel;
    }
    else  // No acceleration was present
    {
        if ( initVelocity == 0.0f )
        {
            // No velocity or acceleration means infinite
            // time required, just return 0.0f, or whatever
            // value you want to return in this case.
            return 0.0f;
        }
        else
        {
            return ( distance / initVelocity );
        }
    }
}
So now we can see that the platform will reach P2 in only 1.3455868 seconds, and because the client stuttered for 2 seconds that leaves us 0.6544132 seconds we need to predict. The next step is to see how much time it takes to get from P2 to P3, and if that is greater than 0.6544132 seconds than we need know we're not to P3 yet and we can calculate how far we've traveled between P2 and P3. 

Alright, time to figure out some values:
Difference vector between P2 and P3 = (18 - 10, 5 - -3) = (8, 8)
Length of difference vector = √(8² + 8²) = √128 = 11.3137085
Constant accel = (5² - 10²) / (2 * 11.3137085) = (25 - 100) / 22.627417 = -3.3145630

Notice our constant acceleration was negative, that is because we slow down when going from P2 to P3. Now that we have all of our values we can calculate the time it takes to travel distance from P2 to P3 given the initial velocity, and the acceleration we just calculated.

Time = (-10 + √(-10² + 2 * -3.3145630 * 11.3137085) ) / -3.3145630
         = (-10 + √(100 + -75.0) ) / -3.3145630
         = (-10 + 5 ) / -3.3145630
         = -5 / -3.3145630

Time = 1.5084944 seconds

We can clearly see that the time we have remaining (~0.65 seconds) isn't enough to reach P3 (~1.51 seconds), so lets see how far we make it.

Distance = 10 * 0.6544132 + (-3.3145630 * 0.6544132² * 0.5)
               = 6.544132 + (-3.3145630 * 0.4282566 * 0.5)
               = 6.544132 + -0.7097417

Distance = 5.8343903 meters

And now we need to figure out the direction, which we have some of the data for from earlier:

Inverse length of difference vector = 1 / 11.3137085 = 0.08838835
Unitized difference vector from P2 to P3 = (8 * 0.08838835, 8 * 0.08838835)
                                                                 = (0.7071068, 0.7071068)

And now that we have distance and direction, we multiply them and add it to P2 to get our final position after 2 seconds:

Position = P2 + ( distance * direction )            
              = (10, -3) + ( 0.7071068 * 5.8343903, 0.7071068 * 5.8343903 )
              = (10, -3) + ( 6.5414971, 6.5414971 )

Position = ( 16.5414971, 3.5414971 )

And there we have it, we just predicted the position of a platform 2 seconds into the future along a strict path.

1 comment:

  1. Hi, great couple of blog posts!

    I think there's a mistake: you use the distance you calculated over 1 sec on the last page to plug in as the distance in the equation for time on this page; but in this case you want the total distance between points P1 and P2. So you actually want the magnitude of the whole difference vector between them, which is 10.440306, not the calculated distance for one second of traversal which was 8.9796225 (or 9... as you typed on this page).

    Thanks again for the posts! It was interesting for me to work out on the last page how the equation for distance can be derived from the solution to the dif eq for the location of an object subject to a constant gravitational force, and how the equation for acceleration can be derived from the work energy theorem!

    ReplyDelete