Splines 'n Such

A large part of game development/programming/etc... relies on one's ability to map functions/graphs to intents. The most obvious cases involve those of movement:

"I want my character's position to move to the left at a constantly increasing rate".

From that description, you should easily be able to envision the general shape of a graphed x position over time.

Similarly, you can imagine the graphical mappings of all sorts of interesting things: difficulty curves over time, required experience to 'level up' getting greater across levels, particles easing out their transparency, enemies that oscillate in interesting ways, etc...

So you have in your head the graph of some non-trivial mathematical representation of an idea you want implemented. What's the next step? Draw from a large repitoire of esoteric mathematical functions* committed to memory? Maybe. Or, you can rely on one, generalized esoteric mathematical function:

What is a spline? In what ways are they useful? In what ways are they restrictive/cumbersome? These questions will be answered later- so feel free to skip down the page. But first, you need to understand one fundamental concept- Interpolation.

Interpolation is simply the parameterized continuous change from one value to another. That is, given a start value a, an end value b, and a parameter dictating how far along the change is t, you get a resulting value between start and end r.

To keep things simple, the parameter is restricted to a value between 0.0 (where r will equal a) and 1.0 (where r will equal b). You can 'move' the interpolation along by supplying an increasing/decreasing t value.

Though the above example is trivial (from 0 to 10), linear interpolation can be applied between arbitrary values. It can also be applied across multiple dimensions simultaneously, for some more useful results.

The above example is simply interpolating between two sets of values ((xa to xb) and (ya to yb)) with the same t, and using the results as the x and y components of a point. You can think of interpolation across multiple dimensions as asking "What is the point t percent of the way from a to b?"

So how does this interpolation happen? The equation is as follows:

A quick explanation: a + (b - a) could be read as "a plus the distance between a and b". Clearly this is equivalent to b. However, we don't necessarily want to go the

To interpolate between n-dimensional points, you simply apply the above math across each of the dimensions individually.

Note: This will be the one mathematical function from which the rest of this page will build, so I strongly reccommend you gain a firm grasp of what is going on before continuing.

We have the ability to interpolate between values, and we can interpolate between multiple values simultaneously to interpolate between points. Next, we interpolate between multiple

On it's own that's not very interesting. But if we restrict the set of initial points to a 'chain' of length n, and interpolate between each point m and m+1 (0 <= m <= n-2), we get another 'chain' of points, length n-1.

To simplify, let's take an example with a chain of 3 points-

a = (0,1), b = (0,0), and c = (1,0). If we simultaneously interpolate between (a and b), and (b and c), we will get a resulting chain of 2 points, shown in green below.

What do 2 points make? A line! What have we learned to do across 2 points? Interpolate! What does interpolation across a single line (2 points) get us? A point! We can then plot this point to a graph to get a beautiful parameterized curve! (click and drag the points to get a feel for how this can be generally applied)

Ok. So we went a bit fast there- let's slow down and recap: From our initial chain of 3 points, we consider each adjacent pair of points individually. At any given time slice, we pass in a t (between 0.0 and 1.0) to each of these point pairs and interpolate (that is, find the point t percent of the way from one point to the next). With these two derived points (one from each pair), we can form a line. Now, we interpolate across this resultant line with

Some important things to note: the same t must be used for the entirety of one timeslice calculation to get a smooth curve. That means that the t that derives the 'line' is the same as the t calculating the point from that line. A side effect of this is that the derived line is completely thrown away and must be re-derived for every new t (don't worry- it's cheap).

In the above example, we used a chain of 3 points. From that we derived a line, and from that we derived a point. But before all that I implied that we can use chains of arbitrary length- so what happens if we start with 4 points?

As you can see above, from the initial 4 points we derive 3; from there, we simply apply our previous process. Where before we threw away the derived line for every t calculation, we now throw away the derived 3 point chain as well- the only thing constant across calculations is the set of initial points (and the rule still applies that you must use the same t at every level of a given calculation).

4 is one of the most commonly used chain-lengths for spline calculations (for reasons expressed later), but there's no need to stop there! The more points, the more control of the curve. Here's one with 6: (try reproducing one of those graphical mappings you were imagining at the start of this post!)

Splines are hella cool, but when ought you practically use them? This question is best answered by considering some of the properties of splines that separate them from traditional game math calculations:

We'll start with the obvious use case- drawing a path for an enemy. For this, we'll use 2 4-length splines. (Why 2 * 4-length splines and not 1 * 8-length spline? Review the "Why/When Splines?" section and see if you can figure it out yourself!).

Here, all we're doing is taking the x and y positions of the spline and directly applying them to the character's position. Since we are using multiple splines, when t hits 1.0, we switch splines and reset t to 0.0.

You'll notice that the end of the first spline needs to be identical to the beginning of the second for any hope of smooth motion. Further, the

To illustrate a much more subtle use for splines, we'll use one to calculate the required amount of experience to obtain a given level. We're not sure exactly how we want the distribution to look, and would like to play around with different options. To make it more interesting, we'll also say that there's only a total of 100xp in this world, and we want to divide it across 10 levels.

In this example, we completely throw out the y value (you can see that moving any point in the y direction has no effect on the resulting xp calculations). In fact, this could be done with a spline of 1-dimensional points; I only kept the y dimension visible for visualization purposes. So, the entire calculation is only based on where the middle point is between the outer points- the closer to the left point, the harder to gain later levels. If the middle point is directly in the middle of the outer two, there is a perfectly even distribution. (Note that because I haven't fixed the end points in this example, you can do some...

I've left out much of the common terminology in order to distill the concepts down to their simplest form, while not scaring people away with big words. For further reading that's actually mathematically rigorous, I reccommend checking out the various spline related wikipedia pages- Here is a good start.

The spline library used for the above demonstrations is js-spline. It is unfinished and poorly documented, but completely free to use! The canvas-based spline renderer is also available, and comes with the same cautions. All code-contributions are welcome!

"I want my character's position to move to the left at a constantly increasing rate".

From that description, you should easily be able to envision the general shape of a graphed x position over time.

Similarly, you can imagine the graphical mappings of all sorts of interesting things: difficulty curves over time, required experience to 'level up' getting greater across levels, particles easing out their transparency, enemies that oscillate in interesting ways, etc...

So you have in your head the graph of some non-trivial mathematical representation of an idea you want implemented. What's the next step? Draw from a large repitoire of esoteric mathematical functions* committed to memory? Maybe. Or, you can rely on one, generalized esoteric mathematical function:

The Spline

What is a spline? In what ways are they useful? In what ways are they restrictive/cumbersome? These questions will be answered later- so feel free to skip down the page. But first, you need to understand one fundamental concept- Interpolation.

Interpolation

Interpolation is simply the parameterized continuous change from one value to another. That is, given a start value a, an end value b, and a parameter dictating how far along the change is t, you get a resulting value between start and end r.

*(also known as '***L**inear Int**erp**olation*') is one simple form of this where changes to the parameter supplied are linearly proportional to the changes to the resulting value.***lerp**To keep things simple, the parameter is restricted to a value between 0.0 (where r will equal a) and 1.0 (where r will equal b). You can 'move' the interpolation along by supplying an increasing/decreasing t value.

a=0
b=10
t=0.1

Though the above example is trivial (from 0 to 10), linear interpolation can be applied between arbitrary values. It can also be applied across multiple dimensions simultaneously, for some more useful results.

xa=-2
xb=2
ya=-1
yb=1
t=0.1

The above example is simply interpolating between two sets of values ((xa to xb) and (ya to yb)) with the same t, and using the results as the x and y components of a point. You can think of interpolation across multiple dimensions as asking "What is the point t percent of the way from a to b?"

So how does this interpolation happen? The equation is as follows:

r = a + ( ( b - a ) * t )

A quick explanation: a + (b - a) could be read as "a plus the distance between a and b". Clearly this is equivalent to b. However, we don't necessarily want to go the

*whole*distance to b- we only want to go t percent of that distance, so we multiply the entire distance by the 'percent' t.To interpolate between n-dimensional points, you simply apply the above math across each of the dimensions individually.

Note: This will be the one mathematical function from which the rest of this page will build, so I strongly reccommend you gain a firm grasp of what is going on before continuing.

From Interpolation to Splines

We have the ability to interpolate between values, and we can interpolate between multiple values simultaneously to interpolate between points. Next, we interpolate between multiple

*points*simultaneously and get... more points.On it's own that's not very interesting. But if we restrict the set of initial points to a 'chain' of length n, and interpolate between each point m and m+1 (0 <= m <= n-2), we get another 'chain' of points, length n-1.

To simplify, let's take an example with a chain of 3 points-

a = (0,1), b = (0,0), and c = (1,0). If we simultaneously interpolate between (a and b), and (b and c), we will get a resulting chain of 2 points, shown in green below.

What do 2 points make? A line! What have we learned to do across 2 points? Interpolate! What does interpolation across a single line (2 points) get us? A point! We can then plot this point to a graph to get a beautiful parameterized curve! (click and drag the points to get a feel for how this can be generally applied)

Ok. So we went a bit fast there- let's slow down and recap: From our initial chain of 3 points, we consider each adjacent pair of points individually. At any given time slice, we pass in a t (between 0.0 and 1.0) to each of these point pairs and interpolate (that is, find the point t percent of the way from one point to the next). With these two derived points (one from each pair), we can form a line. Now, we interpolate across this resultant line with

*the same t used to derive the line*. If we feed this system in increasing t, we end up with a curve moving from the beginning of our initial chain to its end, gently following the 'pull' of the middle point.Some important things to note: the same t must be used for the entirety of one timeslice calculation to get a smooth curve. That means that the t that derives the 'line' is the same as the t calculating the point from that line. A side effect of this is that the derived line is completely thrown away and must be re-derived for every new t (don't worry- it's cheap).

We Need To Go Deeper

In the above example, we used a chain of 3 points. From that we derived a line, and from that we derived a point. But before all that I implied that we can use chains of arbitrary length- so what happens if we start with 4 points?

As you can see above, from the initial 4 points we derive 3; from there, we simply apply our previous process. Where before we threw away the derived line for every t calculation, we now throw away the derived 3 point chain as well- the only thing constant across calculations is the set of initial points (and the rule still applies that you must use the same t at every level of a given calculation).

4 is one of the most commonly used chain-lengths for spline calculations (for reasons expressed later), but there's no need to stop there! The more points, the more control of the curve. Here's one with 6: (try reproducing one of those graphical mappings you were imagining at the start of this post!)

Why/When Splines?

Splines are hella cool, but when ought you practically use them? This question is best answered by considering some of the properties of splines that separate them from traditional game math calculations:

- You define the
*exact*start and end points. No matter the length of the initial chain, the spline calculation*will*equal the first point when t = 0.0 and it*will*equal the end point when t = 1.0. When you need precise constraints on some functional mapping- splines are the go-to solution. - Not only do you define the start/end points, you also define the start/end tangents. The tangent at the initial point will be the line from the second point to the initial point (likewise for the end point). This is why splines of length 4 are so popular: each end of the curve has both its own point, and an independent tangent-defining point (pen tool sound familiar?).
- The curve is ONLY guaranteed to pass through the first and last point. Points in the middle only serve to 'pull' the curve in a certain direction, and the more middle points, the less control each individual point exerts. This is another reason why length-4 splines are often considered ideal.
- You
*cannot*easily query the spline for a given x or y (assuming you are plotting to x and y). You can only pass in a t, which is "how far along the curve am I?" If the curve is going right to left, an increase in t will thus return a further-left value. - This however also comes with a positive- the line can cross itself on arbitrary axis. This allows for shapes much more complex than allowed by y = f(x) style equations that are limited to a one-to-one mapping of x to y.
- It is often difficult/cumbersome to apply a spline graph to an entity for which you cannot guarantee control for the entire duration of its spline interpolation. For example, it would be unwise to implement gravity in the general sense with splines, even though a falling object does take a similar trajectory. Gravity is better represented as a force, as it allows for the dynamic summation and application of all applied forces, resulting in more natural/flexible motion.

Examples

We'll start with the obvious use case- drawing a path for an enemy. For this, we'll use 2 4-length splines. (Why 2 * 4-length splines and not 1 * 8-length spline? Review the "Why/When Splines?" section and see if you can figure it out yourself!).

Here, all we're doing is taking the x and y positions of the spline and directly applying them to the character's position. Since we are using multiple splines, when t hits 1.0, we switch splines and reset t to 0.0.

You'll notice that the end of the first spline needs to be identical to the beginning of the second for any hope of smooth motion. Further, the

*tangents*of these points must be identical, or you'll see a large jerk in direction/speed as the character passes that point. It's common to see these chains of 4-length splines restricted such that their connecting points and tangents are identical, making it easy to create long, smooth, winding paths.To illustrate a much more subtle use for splines, we'll use one to calculate the required amount of experience to obtain a given level. We're not sure exactly how we want the distribution to look, and would like to play around with different options. To make it more interesting, we'll also say that there's only a total of 100xp in this world, and we want to divide it across 10 levels.

Level 0: 0xp

Level 1: 6xp

Level 2: 12xp

Level 3: 20xp

Level 4: 28xp

Level 5: 38xp

Level 6: 48xp

Level 7: 59xp

Level 8: 72xp

Level 9: 86xp

Level 10: 100xp

Level 1: 6xp

Level 2: 12xp

Level 3: 20xp

Level 4: 28xp

Level 5: 38xp

Level 6: 48xp

Level 7: 59xp

Level 8: 72xp

Level 9: 86xp

Level 10: 100xp

In this example, we completely throw out the y value (you can see that moving any point in the y direction has no effect on the resulting xp calculations). In fact, this could be done with a spline of 1-dimensional points; I only kept the y dimension visible for visualization purposes. So, the entire calculation is only based on where the middle point is between the outer points- the closer to the left point, the harder to gain later levels. If the middle point is directly in the middle of the outer two, there is a perfectly even distribution. (Note that because I haven't fixed the end points in this example, you can do some...

*interesting*... things with the experience distribution given sufficiently weird splines...)Due Dilligence

I've left out much of the common terminology in order to distill the concepts down to their simplest form, while not scaring people away with big words. For further reading that's actually mathematically rigorous, I reccommend checking out the various spline related wikipedia pages- Here is a good start.

The spline library used for the above demonstrations is js-spline. It is unfinished and poorly documented, but completely free to use! The canvas-based spline renderer is also available, and comes with the same cautions. All code-contributions are welcome!