2d trajectory planning of a spaceship with physics

Question

I'm implementing a 2D game with ships in space.

In order to do it, I'm using LÖVE, which wraps Box2D with Lua. But I believe that my question can be answered by anyone with a greater understanding of physics than myself - so pseudo code is accepted as a response.

My problem is that I don't know how to move my spaceships properly on a 2D physics-enabled world. More concretely:

A ship of mass m is located at an initial position {x, y}. It has an initial velocity vector of {vx, vy} (can be {0,0}).

The objective is a point in {xo,yo}. The ship has to reach the objective having a velocity of {vxo, vyo} (or near it), following the shortest trajectory.

There's a function called update(dt) that is called frequently (i.e. 30 times per second). On this function, the ship can modify its position and trajectory, by applying "impulses" to itself. The magnitude of the impulses is binary: you can either apply it in a given direction, or not to apply it at all). In code, it looks like this:

function Ship:update(dt)
  m = self:getMass()
  x,y = self:getPosition()
  vx,vy = self:getLinearVelocity()
  xo,yo = self:getTargetPosition()
  vxo,vyo = self:getTargetVelocity()
  thrust = self:getThrust()

  if(???)
    angle = ???
    self:applyImpulse(math.sin(angle)*thrust, math.cos(angle)*thrust))
  end
end

The first ??? is there to indicate that in some occasions (I guess) it would be better to "not to impulse" and leave the ship "drift". The second ??? part consists on how to calculate the impulse angle on a given dt.

We are in space, so we can ignore things like air friction.

Although it would be very nice, I'm not looking for someone to code this for me; I put the code there so my problem is clearly understood.

What I need is an strategy - a way of attacking this. I know some basic physics, but I'm no expert. For example, does this problem have a name? That sort of thing.

Thanks a lot.

EDIT: Beta provided a valid strategy for this and Judge kindly implemented it directly in LÖVE, in the comments.

EDIT2: After more googling I also found openSteer. It's on C++, but it does what I pretended. It will probably be helpful to anyone reaching this question.

Answer 1

It's called motion planning, and it's not trivial.

Here's a simple way to get a non-optimal trajectory:

1. Stop. Apply thrust opposite to the direction of velocity until velocity is zero.
2. Calculate the last leg, which will be the opposite of the first, a steady thrust from a standing start that gets the ship to x0 and v0. The starting point will be at a distance of |v0|^2/(2*thrust) from x0.
3. Get to that starting point (and then make the last leg). Getting from one standing point to another is easy: thrust toward it until you're halfway there, then thrust backward until you stop.

If you want a quick and dirty approach to an optimal trajectory, you could use an iterative approach: Start with the non-optimal approach, above; that's just a time sequence of thrust angles. Now try doing little variations of that sequence, keeping a population of sequences that get close to the goal. reject the worst, experiment with the best -- if you're feeling bold you could make this a genetic algorithm -- and with luck it will start to round the corners.

If you want the exact answer, use the calculus of variations. I'll take a crack at that, and if I succeed I'll post the answer here.

EDIT: Here's the exact solution to a simpler problem.

Suppose instead of a thrust that we can point in any direction, we have four fixed thrusters pointing in the {+X, +Y, -X, -Y} directions. At any given time we will firing at most one of the +/-X and at most one of the +/-Y (there's no point in firing +x and -X at the same time). So now the X and Y problems are independent (they aren't in the original problem because thrust must be shared between X and Y). We must now solve the 1-D problem -- and apply it twice.

It turns out the best trajectory involves thrusting in one direction, then the other, and not going back to the first one again. (Coasting is useful only if the other axis's solution will take longer than yours so you have time to kill.) Solve the velocity problem first: suppose (WLOG) that your target velocity is greater than your initial velocity. To reach the target velocity you will need a period of thrust (+) of duration

T = (Vf - Vi)/a

(I'm using Vf: final velocity, Vi: initial velocity, a: magnitude of thrust.)

We notice that if that's all we do, the location won't come out right. The actual final location will be

X = (Vi + Vf)T/2

So we have to add a correction of

D = Xf - X = Xf -(Vi+Vf)T/2

Now to make the location come out right, we add a period of thrust in one direction before that, and an equal period in the opposite direction after. This will leave the final velocity undisturbed, but give us some displacement. If the duration of this first period (and the third) is t, then the displacement we get from it is

d = +/-(at^2 + atT)

The +/- depends on whether we thrust + then -, or - then +. Suppose it's +. We solve the quadratic:

t = (-aT + sqrt(a^2 T^2 + 4 a D))/2a

And we're done.

Answer 2

In the absence of additional info, we can assume there are 3 forces acting upon the spaceship and eventually dictating its trajectory:

• "impulses" : [user/program-controlled] force.
  The user (or program) appear to have full control over this, i.e. it controls the direction of the impulse and its thrust (probably within a 0-to-max range)
• some external force: call it gravity, whatever...
  Such force could be driven by several sources but we're just interested in the resulting combined force: at a given time and space this external force acts upon the ship with a given strengh and direction. The user/program has no control over these.
• inertia: this is related to the ship's current velocity and direction. This force generally causes the ship to continue in its current direction at its current speed. There may be other [space-age] parameters controlling the inertia but generally, it is proportional to both velocity and to the ship's mass (Intuitively, it will be easier to bring a ship to a stop if its current velocity is smaller and/or if its mass is smaller)

Apparently the user/program only controls (within limits) the first force.
It is unclear, from the question, whether the problem at hand is:

• [Problem A] to write a program which discovers the dynamics of the system (and/or adapts to changes these dynamics).
  or..
• [Problem B] to suggest a model -a formula- which can be used to compute the combined force eventually applied to the ship: the "weighed" sum of the user-controlled impulse and the other two system/physics-driven forces.

The latter question, Problem B, is more readily and succinctly explained, so let's suggest the following model:

Constant Parameters:
  ExternalForceX   = strength of the external force in the X direction
  ExternalForceY   = id. Y direction
  MassOfShip       = coeficient controlling 
Variable Parameters:
  ImpulseAngle     = direction of impulse
  ImpulseThrust    = force of thrust
Formula:
  Vx[new] = (cos(ImpulseAngle) * ImpulseThrust) + ExternalForceX  + (MassOfShip * Vx[current])
  Vy[new] = (sin(ImpulseAngle) * ImpulseThrust) + ExternalForceY  + (MassOfShip * Vy[current])

Note that the above model assumes a constant External force (constant both in terms of its strength and direction); that is: akin to that of a gravitational field relatively distant from the area displayed (just like say the Earth gravity, considered within the span of a football field). If the scale of the displayed area is big relative to the source(s) of external forces, the middle term of the formulas above should then be modified to include: a trigonometric factor based on the angle between the center of the source and the current position and/or a [reversely] proportional factor based on the distance between the center of the source and the current position.
Similarly, the Ship's mass is assumed to remain constant, it could well be a variable, based say on the mass of the Ship when empty, to which the weight of fuel is removed/added as the game progresses.

Now... All the above assume that the dynamics of the system are controlled by the game designer: essentially choosing a set of values for the parameter mentioned and possibly adding a bit of complexity in the math of the formula (and also ensuring proper scaling to generally "keep" the ship within the display area).

What if instead, the system dynamics were readily programmed into the game (and assumed to be hidden/random), and the task at hand is to write a program which will progressively decide the direction and thrust value of the impulses to drive the ship to its targeted destination, in a way that its velocity at the target be as close as possible to getTargetVelocity()? This is the "Problem A".

This type of problem can be tackled with a PID Controller. In a nuthell, such a controller "decides" which amount of action (in this game's case = which impulse angle and amount of thrust to apply), based on three, weighed, factors, loosely defined below:

• how far-off we are the current values from "set point": this is the P=Proportional part of PID
  
• how fast are we approaching the "set point": this is the D=Derivative part of PID
  
• how long and how much have we been away from the "set point": this is the I=Intergral part of PID

A less sophisticated controller could for example only use the proportional factor. This would result in oscillating, sometimes with much amplitude on either side of the set point ("I'm X units away from where I'm supposed to be: let me yank the steering wheel and press on gas"). Such overshooting of the set point are tempered by the Derivative factor ("Yeah, I'm still not where I'm supposed to be but the progress I made since the last time I check is very big: better slow down a bit"). Finally the Integral part takes into account the fact that all things being equal with regards to the combined Proportional and Derivative part, a smaller or bigger action would be appropriate depending on whether we've been "off-track" for a long time or not and of much off track we've been all this time (eg. "Lately we've been tracking rather close to where we're supposed to be, no point in making rash moves")

We can discuss the details implementing PID controllers for the specific needs of the space ship game, if that is effectively what is required. The idea was to provide a flavor of what can be done.

Answer 3

To just get from the current position to the destination with an initial velocity, then apply thrust along the normalized difference between the shortest path and the current velocity. You don't actually need the angle.

-- shortest path minus initial velocity
dx,dy = x0 - x - vx, y0 - y - vy

-- normalize the direction vector
magnitude = sqrt(dx*dx + dy*dy)
dx,dy = dx/magnitude, dy/mangitude

-- apply the thrust in the direction we just calculated
self:applyImpulse(thrust*dx, thrust*dy)

Note that this does not take the target velocity into account because that gets extremely complicated.

I have a very small Lua module for handling 2D vectors in this paste bin. You are welcome to use it. The code above would reduce to:

d = destination - position - velocity
d:normalize()
d = d * thrust
self:applyImpulse(d.x, d.y)