Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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:

alt text

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.

share|improve this question
2  
Good work on figuring that out. I suggest that you post your findings as an answer to your question. –  bummzack Nov 10 '10 at 7:40

5 Answers 5

up vote 43 down vote accepted

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:

alt text

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

alt text

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 ;)

share|improve this answer
4  
This is going to take a while to digest. But wow, amazing answer to your own question. –  AttackingHobo Nov 11 '10 at 17:59
3  
I made an account just to upvote this answer –  rmx Jan 26 '11 at 12:09
    
Have some points my friend. Worked like a charm. Question and answer both Upvoted. –  Jace May 19 at 3:50
    
'i' is multiplied by 0.05, while 'len' was set to 100. this would 't' to be mapped to '0-5' instead of '0-1'. –  Evil Activity Jun 5 at 14:30
    
Gee, this will help me a lot! And it is great that you even linked to the stuff you didn't use, because I may need a precise solution. :) –  Kronos Jun 20 at 12:34

The issue is that a ship would not take that trajectory naturally. So even with it working perfectly it still won't look right.

If you want to simulate the smooth transition between planets I would suggest actually modeling it. The equations are very simple as you only have two significant forces: gravity, and thrust.

You just need to set your constants: Mass of P1, P2, ship

With each game-tick (time: t) you are doing 3 things

  1. Calculate the gravity of p1 on ship and p2 on ship, add the resultant vectors to the thrust vector.

  2. Calculate your new velocity based on your new acceleration from step 1

  3. Move the ship according to your new velocity

Might seem like a lot of work but it can be done in a dozen lines of code and will look very natural.

If you need help with the physics let me know.

share|improve this answer
    
I might consider testing that if you can provide a way of doing this within a function that takes t :) –  Ivo Wetzel Nov 11 '10 at 16:37
    
-but in game programming you don't use t as a variable. You're already basically in a parametric situation, because you're simply calculating the new dx and dy for the ship. Here's an example of orbiting two planets (in Flash) aharrisbooks.net/flash/fg2r12/twoPlanets.html - and here's the same thing in Python: aharrisbooks.net/pythonGame/ch09/twoPlanets.py –  Two pi Nov 13 '10 at 3:09

That kind of modeling is strange, and can produce weird illogical results. Especially if the starting planets speed is really slow.

Model the ships with a thrust power.

When the ships are on their last orbit on the starting planet, accelerate with full thrust.

When the ship gets within a certain distance use reverse thrust to slow the ship down to the target planet's orbit speed.

Edit: Do the entire simulation at once when a node is about to leave the orbit. either send all the data, or send just a few of movement vectors at intervals, and interpolate between them.

share|improve this answer
    
Problem is, this is all tick based, there's no intermediate position. It's a networking multiplayer game and sending all the positions of 600+ ships in a full game will kill all networking. There are only events which transmit a tickOffset, the rest is calculated based on the current world tick and the offset. –  Ivo Wetzel Nov 9 '10 at 20:30
    
I edited my response. –  AttackingHobo Nov 9 '10 at 21:14

If I understand it correctly, your problem is over-constrained.

I believe that you want the spaceship to travel along a specified path between orbits in some time t, and you also want it to accelerate from speed s1 to speed s2 in the same time t. Unfortunately, you can't (in general) find an acceleration that satisfies both of these constraints simultaneously.

You're going to have to relax your problem a bit to make it solvable.

share|improve this answer
2  
Then how to relax it? What I could imagine is modifying the T that I plug into the bezier path stuff. I would need to scale it somehow to first grow slower to 0.5 and then faster to 1. So the ship decelerates from it's original speed to a fixed one at the middle of the curve and then accelerates again from this speed to the speed at the end of the curve? –  Ivo Wetzel Nov 9 '10 at 22:22
    
I think it will look more realistic if the spaceship accelerates from its original speed to somewhere around the midpoint of the transfer and then decelerates to the new orbit. –  Gareth Rees Nov 9 '10 at 22:32
    
Still I'm stuck on how to plug the acceleration into the whole thing, I need to modify the T somehow :/ –  Ivo Wetzel Nov 9 '10 at 23:40

Thanks for your excellent page describing how you solved this problem. I did something somewhat different than you in one detail, as I was deeply memory constrained: I don't build an array, or have to search it for the right 'segment' with a binary search. This is because I always know I am moving from one end of my Bezier curve to another: Therefore, I simply remember the 'current' segment, and if I see that I am going to go out of bounds of that segment to compute my next position, I compute the next (or previous) segment (based on direction of travel.) This works quite well for my application. The only glitch I had to work out was that, in some curves, the size of the segments were so small that my next plot to point was - at rare times - more than one segment ahead of the current one, so instead of just going to the 'next' or 'previous' segment (based on direction), I had to compute segments forward (or back) until I found the one that my next point was 'in'.

Don't know if this quite makes sense, but this certainly helped me.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.