This post is the first in a 4 part series about using splines in real-time applications, such as computer games. Part 2: Closest Point
, Part 3: Arc Length
, and Part 4: Speed Control
can be found at those links.
The emphasis of this discussion is on making splines useful, specifically useful for real-time applications, where update time is critical, and getting stuck in update loops is a big no-no. Splines are a tool that many developers are familiar with, but there is some quirkiness to dealing with splines in practice.
In this first article I will give a short introduction to splines and their usefulness for the wind currents in Seabird. I will also show how to get the slope and sharpness of the spline curve given any place on the spline. In part 2, I will show how to get the total length of the spline, and also how to find the closest point on the spline from any point in the world. In Part 3, I will show how to achieve a constant speed when moving along a spline path, given that you start with a spline where the control points are not at an equal distance from each other along the length of the spline.
To start off, a spline is defined by a set of control points. The placement of these control points give the shape of the spline. Between each consecutive set of control points there is a spline segment. Each segment is usually a cubic polynomial. The construction of a spline is such that all of the ends of these polynomials match up, and their first and second derivatives also match up, so that the spline can be treated like a single continuous parametric curve.
If this is the first segment of the spline, then increasing x from 0 to 1 should interpolate smoothly from the first control point to the second control point. I have written A, B, C, and D as the coefficients for simplicity, but in the 2D case each of these coefficients have x and y components, so this is really 2 equations, one for each dimension:
The equation for a higher dimensional spline segment is the same, given that there is an equation for each additional dimension.
In the cubic polynomial, D is the control point at the beginning of the segment. A, B, and C, are coefficients chosen such that when x is equal to the segment index we get D, the control point for the segment, and when x is equal to the segment index plus one, we get the control point at the beginning of the next segment in the spline. We then switch to using the polynomial of the next segment to smoothly interpolate to the third control point, and so on. The spline is also setup so that the first derivative and second derivative of the polynomials match up, so that moving along the spline path is smooth and continuous.
Splines are useful for the inner workings of the wind paths in my game Seabird. In Seabird, the characters are birds which are able to fly in wind currents that exist throughout the game. It is important that the movement of the characters through the wind currents appear smooth. I use splines to achieve this smooth movement.
One of the first tasks that you may want to do when working with splines is to find a vector facing down the spline from a given place on the spline. In Seabird, the speed the player is able to move faster down the wind current is proportional to how well their user input vector is aligned with the vector facing down the current. The vector facing down the current naturally is the current's slope or first derivative, which we can find by the power rule from calculus:
If we use this equation in place of the original polynomial, then we get the slope at any given point on the spline. Notice how the D coefficient has disappeared. This is because the slope of the spline is not related the placement of the spline in the world. The slope of the spline should be the same no matter whether the spline is in China or Peru.
Another thing we might want to know is whether the spline is pinching tightly. This happens when the path has a sharp change in direction. We can find this by solving for the second derivative of the polynomial:
We have seen the basic idea behind splines, and a few useful tools for knowing a little bit more about how the spline behaves. In the next article we will discuss how to get the total length of the spline. We will also discuss the problem of finding the closest point on the spline to any other point in the world. This can be useful in collision detection, because we need to know if an object is close enough to the spline to determine if it is overlapping.