This article may not be reprinted commercially without the express permission of the author.
Copyright (C) 2000 Nicholas Van Caldwell

A common problem when writing networked virtual environments is overcoming the lag inherent to the Internet; players seem to jerk about the field of play as new data packets are incorporated. Common solutions include increasing the frequency of packets sent, reducing packet size through compression, and most importantly, dead reckoning. This article will attempt to explain a technique for eliminating the "jerk" of lag by employing the power of cubic splines in a dead-reckoning algorithm.

What is Dead Reckoning?

Before jumping straight into cubic splines, a brief description of dead reckoning is required. Programmers use this technique to reduce the effects of lag in a game by trying to guess that an object takes. Dead reckoning makes its guess based on the object's characteristics. For example, if an object has a known starting position and velocity then its path can be created using simple physics. The paths created can be applied to the object, creating the illusion of smooth motion. Cubic splines are a kind of dead reckoning that creates a smooth transition between two data points.

Possible Forms of Dead Reckoning

What the programmer wants to do is take a current position for an object and form a smooth path to where the object is supposed to be. Several techniques are available.

The most basic form of dead reckoning is the "point-to-point" method. As its name implies, this method involves only moving a player to a new point when a data-packet arrives. Given an average Internet lag of 200-300 ms this creates a noticeably "jerky" player. This method is by far the worst because unless a remote player is absolutely still, his onscreen representation is completely erroneous. The reason for the error is that data packets in a fast quake-style game arrive only 5-10 times per second, while even a slow game updates at 30 frames per second. The only way to make players move smoothly is to send one packet for every game frame. This is a terrible strain on bandwidth, thus the point-to-point updating method is nearly impossible to effectively implement in a real-time game.

NewPosition = OldPosition

The next level of precision is the "linear" method. This method involves creating a straight-line path to the next position. In terms of physics, this means that the velocity of an object is used to decide where it should next appear. This method reduces jitters caused by lag but has a tragic flaw: it assumes people will only move with a constant velocity. Thus, the generated and actual paths vary noticeably (although the game will be much improved over the "point-to-point" method). When playing a game that uses this method, players will seem to move in straight lines. Further, whenever a player starts a new linear path his velocity could change abruptly. The end result is a thoroughly unrealistic game.

NewPosition = OldPosition + Velocity*Time

A smart programmer might now ask, "why not just add acceleration to your path equations?" Such a method is possible, and will result in even smoother game play. This is called the "quadratic" method because the path created follows a quadratic function. Without detailing the math, this method also fails because even though a player's motion is represented more realistically, his final velocity is likely to be incorrect. This is because quadratic functions do not employ what physicists call "jerk", or the change in acceleration over time. This leads to the final solution: the cubic spline.

NewPosition = OldPosition + Velocity*Time + Acceleration*(time)[sup]2[/sup]

Cubic splines offer one of the most realistic methods for creating a dead reckoning path. This is because they account for the starting position\velocity and the ending position\velocity. As a result, objects following a cubic spline path have no jitters, unless lag is especially severe.

Using Cubic Splines

Using cubic splines to create a path is a matter of simple algebraic equations. The input for these equations are four (x,y) coordinates. The first coordinate represents the object's starting position. Similarly, the fourth coordinate signifies the object's ending position. Usually the end position is a new (x,y) coordinate that has just arrived in a data packet. The most important coordinates are the second and third; they represent the object's velocity. For the second coordinate, calculate where the object will appear after 1 second with its current velocity. For the third coordinate, reverse the object's end velocity, and calculate where it would appear after 1 second. This is the same as traveling back in time for 1 second (assuming constant velocity). In summary:

1. Coordinate 1 = Starting position
   
   Coordinate 2 = Position after 1 second using starting velocity
   = Coordinate1 + StartVelocity
   
   Coordinate 3 = Position after 1 second using reversed ending velocity
   = Coordinate4 - EndVelocity
   
   Coordinate 4 = Ending position
2. Here are the parametric equations used to form the spline.
   
   x = At[sup]3[/sup] + Bt[sup]2[/sup] + Ct + D
   y = Et[sup]3[/sup] + Ft[sup]3[/sup] + Gt + H
   
   t is the time variable. It ranges from 0 at the initial point to 1 at the end point.
3. Formulating the rest of the variables.
   
   A = x[sub]3[/sub] - 3x[sub]2[/sub] +3x[sub]1[/sub] - x[sub]0[/sub]
   B = 3x[sub]2[/sub] - 6x[sub]1[/sub] + 3x[sub]0[/sub]
   C = 3x[sub]1[/sub] - 3x[sub]0[/sub]
   D = x[sub]0[/sub]
   
   E = y[sub]3[/sub] - 3y[sub]2[/sub] +3y[sub]1[/sub] - y[sub]0[/sub]
   F = 3y[sub]2[/sub] - 6y[sub]1[/sub] + 3y[sub]0[/sub]
   G = 3y[sub]1[/sub] - 3y[sub]0[/sub]
   H = y[sub]0[/sub]
4. Once the equation is created, the next step is deciding how to implement it in the game. The following method is simple and effective.
   1. Allow an object to move according physical laws (account for velocity and acceleration).
   2. When a data packet arrives begin creating a spline to the next position.
   3. Coordinates 1 and 2 of the spline can be found using the current position and velocity.
      
      Coord2 = x[sub]old[/sub] + v[sub]old[/sub]
   4. Coordinates 3 and 4 are more difficult to get. Decide on the number of steps the object will take on the spline before it reaches the final position. Let this number be time T. For coordinate 4, use the new data packet to calculate the final position after t seconds. The same information can be used to calculate the velocity at the new time.
      
      Coord3 = x[sub]packet[/sub] + v[sub]packet[/sub]*t + .5*a[sub]packet[/sub]*t[sup]2[/sup]
      Coord4 = Coord3 - (V[sub]packet[/sub] + a[sub]packet[/sub]*t)
      
      This method combines two forms of dead reckoning: a cubic spline, and quadratic motion. The result is more realistic.
   5. Make the object travel along the spline for T frames.
   6. At the end of the spline resume at step 1.

The result will look something like the following:

Conclusion

This article has covered some of the basics of cubic splines and provided psuedocode for use in any game using 2d Newtonian physics. The provided equations can also be easily extended into use for three-dimensional games. While creating cubic splines is easy, actually implementing them introduces several problems that must be left to the reader to explore on his own.

Happy Coding,
Nick Caldwell
Massachusetts Institute of Technology
Class of '03