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 positionFurther simplifying assumptions:r, initial velocity_{0}v, final position_{0}r, final velocity_{f}v, and maximum acceleration_{f}a, find the minimum travel timet. This is the cost estimate for getting from (r,_{0}v) to (_{0}r,_{f}v)._{f}

- 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
*r*is zero. Replace_{0}*r*with_{f}*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

*v*(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

_{m}*t*is:

The acceleration directions are from

*v*to

_{0}*v*, and from

_{m}*v*to

_{m}*v*.

_{f}The distance traveled is the integral over the two velocity-space line segments:

This is the equation we need to solve to find

*v*. Fun, huh?

_{m}The first thing to do is to integrate directly from

*v*to

_{0}*v*. This velocity change is required, so compute the amount of ground that will be covered while doing so:

_{f}When this base displacement directly produces the desired

*r*, any

*v*between

_{m}*v*and

_{0}*v*will do; it will just lie on the line between

_{f}*v*and

_{0}*v*. If the base displacement is greater than the desired amount, then

_{f}*v*will be less than both

_{m}*v*and

_{0}*v*. If the base displacement is less than the desired amount, then

_{f}*v*will be greater than both

_{m}*v*and

_{0}*v*:

_{f}When

*r*is less than

*r*:

_{base}When

*r*is greater than

*r*:

_{base}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;

}

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.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

*v*, the two-dimensional case is almost identical to the one-dimensional case. The displacement

_{m}*r*, velocities

*v*,

_{0}*v*, and

_{f}*v*all become 2D vectors, and the lengths between velocities have to be evaluated using vector magnitude, which involves a square root:

_{m}Solving this equation for

*v*is what I've been stuck on for some time now. If you've got any insights, I'd love to hear them.

_{m}
## No comments:

Post a Comment