Computing Space Travel - Implementation

This is the Java code implementing the space travel solution I described in the previous post.

(The vector and point classes it uses are very similar to Java 3D's vecmath and it would be straight-forward to modify this code to use vecmath instead.)

Computing Space Travel

How can a 3D-autopilot be implemented in a space opera game? How do you compute the optimal trajectory from A to B in a solar system using classical mechanics?

This has been one of the tougher problems I've encountered in the MMO game project I'm working on. No other space game I've played has had a solution for this. The problem is usually avoided by either inventing other physics or hiding or skipping the actual travel. But I aim higher than that. I want it to feel like piloting a ship in space.

Since it's a space opera game, the simulation primarily involves classical mechanics, i.e. Newtonian physics. (Einsteinian relativity I consider non-practical from an implementation point-of-view. I don't say this only because it's harder physics... and the light-speed limit would definitely limit game design!) In the game, celestial orbits, space ship movement, thrust engine power, fuel consumption etc are all derived with Newtonian physics.

A lot of such behavior can be computed using high school level physics. But planning an optimal (or at least fairly efficient) space trajectory path to reach a given destination proved to be a considerably more difficult problem. It took much longer to solve it than I had expected. In this post I thought I'd describe what I came up with. It is an interesting problem and the solution can perhaps be useful to others.

Defining the Problem

The objective is to plan the space trajectory needed to rendezvous with a given destination within the solar system. It is needed to implement the game's autopilot which is used by both computer-controlled ships and players. The trajectory must be computed in advance since simply going in the direction of the destination would result in arriving with a speed very different from that of the destination object. We need to know beforehand when to 'gas' and when to 'break', and in what precise directions to do this.

The planned trajectory should be fairly efficient (primarily regarding travel time, but also regarding fuel consumption) and preferably not cheat by using different physics than the player experiences with the manual controls. It must also be fairly fast to compute - it's an MMO game and there can be many thousands of travelling ships.

The formal problem is: The travelling spaceship, at current position P in space and with current velocity V, is to travel and rendezvous with a destination object (a planet, another ship etc) which is at current position Q and with current velocity W. Since it's a rendezvous (e.g. docking or landing) the travelling spaceship must have the same velocity W as the destination upon arrival.

The above diagram is in absolute frame coordinates (sometimes called the inertial frame). However since we're adhering to Newtonian physics we can simplify the problem by defining it relative to the travelling ship's starting position and velocity instead. The next diagram shows the same case but in relative frame coordinates.

                                           P₀ = 0                Q₀ = Q - P                ΔV = W - V

A game space ship travels using its thrust engine, which accelerates the vessel in whatever direction it is pointing. The planned trajectory should be expressed as a sequence of thrust applications, each describing a trajectory leg:

1. From time 0 to t1 apply thrust X
2. From time t1 to t2 apply thrust Y
3. ...

The technical problem is: Find the trajectory legs (each expressed as a thrust vector and a length of time) that as soon as possible will move the ship to the same position and velocity as the destination, so that:

P(t) = Q(t);     velocity = ΔV;      t as small as possible