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:
If we know the velocity at which we should change acceleration direction, we can derive everything else. Call this vm (for “midpoint,” although it isn't at any particular time or distance). The trip duration is the total change in velocity divided by the acceleration. Since currently we're treating acceleration as one, the total trip time t is:
The acceleration directions are from v0 to vm, and from vm to vf.
The distance traveled is the integral over the two velocity-space line segments:
This is the equation we need to solve to find vm. Fun, huh?
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:
When this base displacement directly produces the desired r, any vm between v0 and vf will do; it will just lie on the line between v0 and vf. If the base displacement is greater than the desired amount, then vm will be less than both v0 and vf. If the base displacement is less than the desired amount, then vm will be greater than both v0 and vf:
When r is less than rbase:
When r is greater than rbase:
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:
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)));
}
return turns;
}
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[0], start.vel[0], end.pos[0], end.vel[0]);
int cost_y = estimated_cost(start.pos[1], start.vel[1], end.pos[1], end.vel[1]);
int cost_xy = estimated_cost(start.pos[0] + start.pos[1], start.vel[0] + start.vel[1],
end.pos[0] + end.pos[1], end.vel[0] + end.vel[1]);
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:
Solving this equation for vm is what I've been stuck on for some time now. If you've got any insights, I'd love to hear them.
No comments:
Post a Comment