In the last installment we looked at Triplanetary, a board game with a Newtonian movement mechanism. A computer playing Triplanetary needs to be able to plan rocket routes; the A* graph search algorithm seems to be a reasonable way to do it.
We continue our search for a suitable path cost heuristic to use with A*. We had simplified the heuristic to be the estimated travel time under the rocket's acceleration alone, disregarding gravity, fuel consumption, and obstacles. Briefly stated, then, the problem is:
Given an initial position r0, initial velocity v0, final position rf, final velocity vf, and maximum acceleration a, find the minimum travel time t. This is the cost estimate for getting from (r0, v0) to (rf, vf).Further simplifying assumptions:
- The maximum acceleration is 1. Non-unit acceleration can be added back in without much trouble; leaving it out saves visual clutter in the meantime.
- The acceleration direction can change instantaneously at any time. Some games place limits on how fast a rocket can turn, but Triplanetary, with each turn roughly a day long, doesn't.
- Translate the problem such that r0 is zero. Replace rf with r, the desired displacement in space.
- Consider time and space to be continuous rather than discrete. This allows us to use ordinary calculus. Hopefully we can then adapt the continuous solution to the board game's discrete hexes and turns.
- Acceleration magnitude is held constant at maximum for the entire flight; the only thing that varies is the acceleration direction.
- The function of acceleration direction versus time is a step function with one or two segments. In other words, either we hold the direction constant for the entire flight, or we hold it for a period of time, then change it instantly to a new direction and hold that direction constant for the remainder of the flight. As an example, consider the case where the initial and final velocities are zero. The fastest way to make the trip is to accelerate toward the target until the midpoint, then reverse thrust and decelerate for the remainder.
One-dimensional, continuous version
There are various ways to formulate the one-dimensional version of this problem. I'm going to present it in a way that will extend to the two-dimensional problem later. First, here are the variables we'll be using:
The distance traveled is the integral over the two velocity-space line segments:
The first thing to do is to integrate directly from v0 to vf. This velocity change is required, so compute the amount of ground that will be covered while doing so:
One-dimensional, discrete version
I'm running out of time so I will omit some explanation. If you are attempting to implement this yourself, it is very helpful to graph velocity versus time for a wide variety of cases. Here is code for determining travel time in one dimension:
As stated last week, this one-dimensional function is good enough to use in implementing pathfinding for the race car game, since movement in X and Y are independent. Just project the movement onto the X and Y axes, evaluate the travel time in each, and take the largest.
int estimated_cost(int start_pos, int start_vel, int goal_pos, int goal_vel)
// How far do we need to move (signed)?
int dpos = goal_pos - start_pos;
// How far will we move while accelerating from start_vel to goal_vel?
int dv = goal_vel - start_vel;
int turns = abs(dv);
dpos -= ((start_vel + goal_vel) * turns + (goal_vel - start_vel)) / 2;
// Do additional acceleration as necessary.
if (dpos > 0)
int vel = max(start_vel, goal_vel);
turns += int(ceil(2.0 * (sqrt(vel*vel + dpos) - vel)));
else if (dpos < 0)
int vel = min(start_vel, goal_vel);
turns += int(ceil(2.0 * (sqrt(vel*vel - dpos) + vel)));
Because Triplanetary uses a hex grid, movement in X and Y are not independent, which is closer to what would happen in a continuous world. I've experimented with making my two-dimensional hex travel heuristic out of calls to this function; for instance, taking the max of the cost estimates for projections onto the X and Y axes. I'm not convinced it's always less than the real travel time, though (it's been a while since I did this part), and it is a horribly low estimate in two of the diagonal directions, which causes thousands of additional states to be explored.
Here's my current 2D estimate, which I'm pretty sure goes over the true value in some cases:
static int estimated_cost(const STATE & start, const STATE & end)
int cost_x = estimated_cost(start.pos, start.vel, end.pos, end.vel);
int cost_y = estimated_cost(start.pos, start.vel, end.pos, end.vel);
int cost_xy = estimated_cost(start.pos + start.pos, start.vel + start.vel,
end.pos + end.pos, end.vel + end.vel);
return max(max(cost_x, cost_y), cost_xy);
Two-dimensional, continuous version
By framing the problem as a search for vm, the two-dimensional case is almost identical to the one-dimensional case. The displacement r, velocities v0, vf, and vm all become 2D vectors, and the lengths between velocities have to be evaluated using vector magnitude, which involves a square root: