2d - Moving ships between two planets along a bezier, missing some equations for acceleration

OK, I already posted this over at math.stackechange.com but didn't get any answers :(

First of here's a picture of my problem, the description follows afterwards:

So I got all the points and values set up.

The ship starts out moving around the left planet P1 with S=0.27 Degrees per gametick, when it reaches Point A it starts following the bezier curve till it reaches Point D, then it travels around the right planet P2 with S=0.42 Degrees per game tick. The difference in S is so that the travel with the same movement speed around the planets.

So far so good, I got that up and running, now my problem.

When S P1 and S P2 differ to much, the ship jumps between the two speeds when it reaches it's destination, which looks pretty bad. So I need to accelerate the ship between Point A and Point D from S P1 to S P2.

The thing I'm missing are in purple, those are:

• 
  

  A way to calculate the ticks it takes the ship to move along the bezier considering the acceleration.

  
  


• 
  

  And a way to find a position on the bezier curve based on T, again considering the acceleration.

  
  
  

ATM I calculate the length of the bezier by calculating the distance between N of its points. So what I think I need, is a way to scale the T I need to put into my bezier calculation accordingly to the acceleration.

Answer

OK, I've got everything working, it took forever, so I'm going to post my detailed solution here.
Note: All code samples are in JavaScript.

So let's break down the problem into the basic parts:

1. 
   

   You need to compute the length of, as well as points between 0..1 on the bezier curve

   
   
   


2. 
   

   You now need to adjust the scaling of your T to accelerate the ship from one speed to another

   
   

Getting the Bezier right

Finding some code for drawing a Bezier curve is easy, there are a number of different approaches though, one of them is the DeCasteljau Algorithm, but you can also just use the equation for cubic Bézier curves:

// Part of a class, a, b, c, d are the four control points of the curve
x: function (t) {
    return ((1 - t) * (1 - t) * (1 - t)) * this.a.x

           + 3 * ((1 - t) * (1 - t)) * t * this.b.x
           + 3 * (1 - t) * (t * t) * this.c.x
           + (t * t * t) * this.d.x;
},

y: function (t) {
    return ((1 - t) * (1 - t) * (1 - t)) * this.a.y
           + 3 * ((1 - t) * (1 - t)) * t * this.b.y
           + 3 * (1 - t) * (t * t) * this.c.y
           + (t * t * t) * this.d.y;

}

With this, one can now draw a bezier curve by calling x and y with t which ranges from 0 to 1, let's take a look:

Uh... that's not really an even distribution of the points, is it?
Due to the nature of the Bézier curve, the points on 0...1 have different arc lenghts, so segments near the beginning and the end, are longer than the ones which are near to the middle of the curve.

Mapping T evenly on the curve AKA arc-length parameterization

So what to do? Well in simple terms we need a function to map our T onto the t of the curve, so that our T 0.25 results in the t that's at 25% of the length of the curve.

How do we do that? Well, we Google... but it turns out that the term isn't that googleable, and at some point you'll hit this PDF. Which sure is a great read, but in the case that you've already forgotten all the math stuff you learned back in school(or you just don't like those mathematical symbols) it's pretty useless.

What now? Well go and Google some more(read: 6 hours), and you finally find a great article on the topic(including nice pictures! ^_^"):

http://www.planetclegg.com/projects/WarpingTextToSplines.html

Doing the actual code

In case you just couldn't resist downloading that PDF's although you'd already lost your mathematical knowledge a long, long, time ago(and you managed to skip the great article link), you might now think: "God, this will take hundreds of lines of code and tons of CPU"

No, it will not. Because we do what all programmers do, when it comes to math stuff:
We simply cheat.

Arc-length parameterization, the lazy way

Let's face it, we don't need endless precision in our game, do we? So unless you're working at Nasa and planning on sending people the the Mars, you won't need a 0.000001 pixel perfect solution.

So how do we map T onto t? It's simple and only consists of 3 steps:

1. 
   
   

   Calculate N points on the curve using t and store the arc-length(aka the length of the curve) at that position into an array

   
   


2. 
   

   To map T onto t, first multiply T by the total length of the curve to get u and then search the array of lengths for the index of the largest value that's smaller than u

   
   


3. 
   

   If we had an exact hit, return the array value at that index divided by N, if not interpolate a bit between the point we found and the next one, divide the thing once again by N and return.

   
   

That's all! So now let's take a look at the complete code:

function Bezier(a, b, c, d) {
    this.a = a;
    this.b = b;
    this.c = c;
    this.d = d;

    this.len = 100;
    this.arcLengths = new Array(this.len + 1);
    this.arcLengths[0] = 0;


    var ox = this.x(0), oy = this.y(0), clen = 0;
    for(var i = 1; i <= this.len; i += 1) {
        var x = this.x(i * 0.05), y = this.y(i * 0.05);
        var dx = ox - x, dy = oy - y;        
        clen += Math.sqrt(dx * dx + dy * dy);
        this.arcLengths[i] = clen;
        ox = x, oy = y;
    }
    this.length = clen;    
}

This initializes our new curve and computes the arg-lenghts, it also stores the last of the lengths as the total length of the curve, key factor here is this.len which is our N. The higher, the more precise the mapping will be, for a curve of the size in the picture above 100 points seem to be enough, if you just need a good length estimate, something like 25 will already do the job with being only 1 pixel off in our example, but then you will have a less precise mapping which will result in not so even distribution of T when mapped to t.

Bezier.prototype = {
    map: function(u) {
        var targetLength = u * this.arcLengths[this.len];
        var low = 0, high = this.len, index = 0;
        while (low < high) {
            index = low + (((high - low) / 2) | 0);
            if (this.arcLengths[index] < targetLength) {
                low = index + 1;


            } else {
                high = index;
            }
        }
        if (this.arcLengths[index] > targetLength) {
            index--;
        }

        var lengthBefore = this.arcLengths[index];

        if (lengthBefore === targetLength) {
            return index / this.len;

        } else {
            return (index + (targetLength - lengthBefore) / (this.arcLengths[index + 1] - lengthBefore)) / this.len;
        }
    },

    mx: function (u) {
        return this.x(this.map(u));

    },

    my: function (u) {
        return this.y(this.map(u));
    },

The actual mapping code, first we do a simple binary search on our stored lengths to find the largest length that's smaller then targetLength, then we just return or do the interpolation and return.

    x: function (t) {
        return ((1 - t) * (1 - t) * (1 - t)) * this.a.x
               + 3 * ((1 - t) * (1 - t)) * t * this.b.x

               + 3 * (1 - t) * (t * t) * this.c.x
               + (t * t * t) * this.d.x;
    },

    y: function (t) {
        return ((1 - t) * (1 - t) * (1 - t)) * this.a.y
               + 3 * ((1 - t) * (1 - t)) * t * this.b.y
               + 3 * (1 - t) * (t * t) * this.c.y
               + (t * t * t) * this.d.y;
    }

};

Again this computes t on the curve.

Time for results

By now using mx and my you get an evenly distributed T on the curve :)

Wasn't that hard, was it? Once again, it turns out that a simple(although not perfect solution) will be enough for a game.

In case you want to see the complete code, there's a Gist available:
https://gist.github.com/670236

Finally, accelerating the ships

So all that's left now is to accelerate the ships along their path, by mapping the position onto T which we then use to find the t on our curve.

First we need two of the equations of motion, namely ut + 1/2at² and (v - u) / t

In actual code that would look like this:

startSpeed = getStartingSpeedInPixels() // Note: pixels
endSpeed = getFinalSpeedInPixels() // Note: pixels
acceleration = (endSpeed - startSpeed) // since we scale to 0...1 we can leave out the division by 1 here
position = 0.5 * acceleration * t * t + startSpeed * t;

Then we scale that down to 0...1 by doing:

maxPosition = 0.5 * acceleration + startSpeed;

newT = 1 / maxPosition * position;

And there you go, the ships are now moving smoothly along the path.

In case it doesn't work...

When you're reading this, everything works fine and dandy, but I initially had some problems with the acceleration part, when explaining the problem to someone in the gamedev chatroom I found the final error in my thinking.

In case you haven't forgotten already about the picture in the original question, I mention s there, turns out that s is speed in degrees, but the ships move along the path in pixels and I had forgotten about that fact. So what I needed to do in this case was to convert the displacement in degrees into a displacement in pixels, turns out that this is rather easy:

function rotationToMovement(planetSize, rotationSpeed) {
    var r = shipAngle * Math.PI / 180;
    var rr = (shipAngle + rotationSpeed) * Math.PI / 180;
    var orbit = planetSize + shipOrbit;

    var dx = Math.cos(r) * orbit - Math.cos(rr) * orbit;
    var dy = Math.sin(r) * orbit - Math.sin(rr) * orbit;
    return Math.sqrt(dx * dx + dy * dy);
};

So and that's all! Thanks for reading ;)