Hello once again shmup fans. Strap yourself in for another fun filled exhilarating ride through my brain. This time we'll be discussing how you can quickly, easily, and efficiently create super smooth curved motion for your scripted game objects and have them follow in real time. This will let your enemies gracefully swoop in on complex attack vectors and create mind boggling formations with each other as they spin around the screen. At the end of this tutorial I'll be linking it up with the ideas from the last control schemes tutorial so if you haven’t read that already then please do so now. So without further ado lets crack on.
When designing motion for our scripted game objects we don’t want to have to manually specify their positions for every single frame, imagine how long it would take to create all that data. Instead we want to specify only a few key positions for the object and have the computer automatically move the object between those key positions. This is what is known as interpolation and there are many ways we can do it each having different properties and giving different results. Therefore we want to choose an interpolation method which has the properties we desire. For this I'll be considering the two major properties we are concerned about. The first of these is whether the object is forced to move exactly through the key positions we specified or whether these are merely control points for the motion which is approximated between the points. There really isn't much difference between the two methods since the same motion can be represented with both systems but personally I prefer the first option since it gives more intuitive control over the motion and allows us to set up exact locations for things such as formations of multiple enemies etc. Therefore I'll want an interpolation method that satisfies the first option. The second important property is the continuity of the interpolation, i.e.: how smooth the resulting motion is. For example consider the simplest type of interpolation we can perform which is to move the object linearly between the key positions (imagine connecting up the key positions with straight lines). In such a system the position aspect of the object is continuous since there are no sudden teleportations in the position. The objects velocity is discontinuous however since it suddenly changes direction at the key positions giving rise to jagged line motion. This interpolation method is known as zero order continuous because none of the derivatives of the motion are continuous (velocity being the first derivative of position). Now imagine a first order continuous method. In this scheme the objects position and velocities would change smoothly but the objects acceleration (the second derivative) is allowed to change suddenly at the key positions. Therefore such an object would move in smooth curves between key positions but the curvature is allowed to change suddenly between pairs of control points. In a second order continuity method our acceleration is now also continuous and hence the rate of change of curvature must also change smoothly. As you can see the higher the order of continuity the smoother and smoother our motion is going to become. The trade off however is that higher order systems are more computationally expensive and become more restricting on the motion we can produce. The visual improvement you get from using higher order systems drops quickly too so it’s not important to use a high order.
So taking all the above into account, an interpolation method known as Catmull-Rom Splines is widely popular for controlling motion. This is an exact interpolation method (passes directly through key positions) and is first order continuous giving nice smooth curving motion without being too expensive or restrictive. Therefore this is the interpolation method I'll be using throughout this tutorial. So how do we use Catmull-Rom splines? We will consider the spline in segments with the smallest spline we can use containing one segment. There is no cap on the number of segments a spline can contain and hence there is no limit to the maximum size restriction for a Catmull-Rom spline. A spline segment consists of two key positions you want to interpolate between, and the key positions either side of those two key positions:
Therefore the minimum number of key positions a spline must contain is 4 since this equates to one segment. To create longer splines we simply add more key positions onto the end and shift our segment up one key position at a time, thus a spline with 5 key positions has 2 segments, one with 6 key positions has 3 segments, etc. This allows us to interpolate between every pair of key positions with the exception of the [0,1] pair and the [n-1,n] pair where 'n' is the total number of key positions. Therefore when creating a spline you must always add in an extra key position on either end of the desired motion. So how do we do the actual interpolation to determine points on the spline in-between the key positions? Imagine a spline segment with key position p0, p1, p2, and p3. Given the requirements for a segment just discussed this means that for this segment we can interpolate between key positions p1 and p2. Any point between these two key positions can be described by a value 't' which can take any value between 0 and 1 inclusive where t=0 represents key position p1 and t=1 represents key position p2. There t=0.5 would reference a point on the spline half way between key positions p1 and p2. Then for a given value of 't' we are interested in we can calculate the actual x,y coordinates of the point on the spline at that 't' using the following equations:
x = 0.5 * ((2 * p1x) + (p2x - p0x)*t + (2*p0x - 5*p1x + 4*p2x - p3x)*t*t + (3*p1x + p3x - p0x - 3*p2x)*t*t*t)
y = 0.5 * ((2 * p1y) + (p2y - p0y)*t + (2*p0y - 5*p1y + 4*p2y - p3y)*t*t + (3*p1y + p3y - p0y - 3*p2y)*t*t*t)
So one option for us to move our object along a spline is to increment 't' by a constant amount each frame and calculate the objects position from the new value of 't'. When 't' becomes greater than 1 we subtract 1 from the 't' value to put it back in range and move our segment one key position along the spline. This is repeated until the object has reached key position n-1. This will give us nice smooth motion but there is a problem in that the length of each spline segment isn't necessarily equal to the length of all the other spline segments. Even if we spaced our key positions so that they all have the same separation the actual length of the interpolation segments will still vary since they curve by different amounts. In fact due to the mathematics involved you'll find that the speed of our objects will vary even on different portions of the same spline segment. What this means for us is that varying 't' by a constant value doesn't equate to our object moving with constant speed. In fact just using the knowledge we currently have its near impossible for us to control the speed of our objects at all which obviously isn't very good for us. So how do we tackle this problem?
Clearly what we need is some knowledge of the distance our object is covering during interpolation, specifically we need to know about what is called arc length which is the length of a curve if you imagine it stretched out flat. What we need to do is reparameterise the Catmull-Rom equations so that they become functions of arc length rather than 't' (the parametric variable). Often these reparameterisations aren't able to be done analytically and we must use numerical methods. Since we want to keep our spline code efficient we'll be approximating the reparameterisation by using a pre-calculated look up table. We calculate this table for each spline segment by evaluating the position along that segment for lots of small increments of 't'. If our 't' slices are small enough then we can approximate the little slices of curves between each evaluated point as straight lines. What this means is that by adding up the lengths of the straight lines we can get an estimate for the arc length at each value of 't' we evaluated. This pre-calculated table is then loaded into our game so that we can control our objects by incrementing their arc lengths directly giving us absolute control over object speed. The current arc length is then looked up on the table and its corresponding 't' value read off and used to calculate the objects actual new position using the Catmull-Rom spline equations given above.
There is one more complication however. Given a value of arc length for which we want to know our objects position, it’s unlikely that our table will contain this exact value of arc length to read off the exact 't' value. Instead we must blend between the 't' values for the two nearest arc lengths in the table either side of our actual desired arc length. This can be done by following this formula where 'a0' and 'a1' are the two closest tabulated values of arc length our actual desired arc length 'a' lies between, and 't0' and 't1' are the corresponding values of 't' for 'a0' and 'a1' respectively:
t = t0 + ((a - a0) / (a1 - a0)) * (t1 - t0)
So we can now move our object in nice smooth curving motions whilst maintaining absolute control over their velocities. There's really only one more thing I need to mention. Imagine now you control a tank style enemy using such a spline. You'll want the tanks lower body and tank tracks to rotate so that it looks like the tank is actually driving along the path. We can achieve this if we know the angle the spline motion takes to some reference direction and then combine this with our sprite perspective trick from the previous control schemes tutorial. What we need to know is the rate at which the curves position is changing at any point which will give us the direction. For those of you who know anything about calculus this equates to finding the differential of the spline. Don’t worry I'm not going to start giving you a tutorial on calculus, I'll just spit out the answer. So the rate of change of x and y, called 'dx' and 'dy' become:
dx = 0.5 * (p2x - p0x + 2*t*(2*p0x - 5*p1x + 4*p2x - p3x) + 3*t*t*(3*p1x + p3x - p0x - 3*p2x))
dy = 0.5 * (p2y - p0y + 2*t*(2*p0y - 5*p1y + 4*p2y - p3y) + 3*t*t*(3*p1y + p3y - p0y - 3*p2y))
The nice thing about this is that many of the bracketed groups and powers of 't' have already been calculated in the Catmull-Rom spline equations and so we can re-use them. We can now plug these 'dx' and 'dy' values into the atan2 function just like we did in the progear turrets tutorial in order to calculate the direction our object is facing and hence update its sprite accordingly. Well that’s basically it. Welcome to the world of super slinky spline motion, I hope you enjoy it. Sorry this tutorial is a little stunted compared to usual and things maybe aren't explained in the same level as detail as my usual standard but with taking over the website and trying to organise the next compo my time is a little tight. As usual if you want to ask questions please do so.
Thanks for reading
Dan.
SHMUP-DEV » SHMUP DEV FORUMS » Training Grounds » Tutorials
Control Schemes [part 2] : Spline Motion
Print