Contents  Introduction  Dead Reckoning  Using Cubic Splines  Printable version

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³ + Bt² + Ct + D
   y = Et³ + Ft³ + 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₃ – 3x₂ +3x₁ – x₀
   B = 3x₂ – 6x₁ + 3x₀
   C = 3x₁ – 3x₀
   D = x₀
   
   E = y₃ – 3y₂ +3y₁ – y₀
   F = 3y₂ – 6y₁ + 3y₀
   G = 3y₁ – 3y₀
   H = y₀
   

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_old + v_old

   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_packet + v_packet*t + .5*a_packet*t²
      Coord4 = Coord3 – (V_packet + a_packet*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