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:

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. Linear Interpolation (also known as 'lerp') is one simple form of this where changes to the parameter supplied are linearly proportional to the changes to the resulting value.

     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:

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

     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!


* These are actually really interesting and useful functions as well. Although the spline more generally solves the issue of arbitrary graph-mapping, bias and gain, impulse, exStep, etc..., are simple, consise, and efficient alternatives.