Pathfinding in Space, part 3

Last week I ended with the vector equation I've been stuck trying to solve. v_m is the unknown:

The equation describes accelerating at a constant rate of 1 from a starting velocity v₀ to an intermediate velocity v_m, and then at the same rate of 1 (but possibly in a different direction) from v_m to a final velocity v_f. The desired displacement resulting from this trip is r.

Essentially we have position and velocity endpoint conditions, and a limit on how fast we can accelerate. My hypothesis is that the quickest path connecting the endpoints will be two parabolas (with the max acceleration on each) that fit the ends and match position and velocity where they meet.

I will probably put this problem on the back burner for a bit, but before doing so I thought I'd at least produce some graphs to get a better feel for it. I wrote a quick program that uses OpenGL to produce graphs of velocity space.

The program takes in a v₀ and v_f pair. Each point on the graph is a candidate v_m; the program uses it to evaluate the right-hand side of the equation to give the r corresponding to that solution.

Lines of constant r_x are drawn in red and lines of constant r_y in green. If they were labeled, you could find a rough solution by locating the red line and green line that correspond to the desired r, and then locating an intersection between them. The position of the intersection is the value for v_m that solves the equation.

Here is the simplest case, where the starting and ending velocities are both zero:

(0, 0) to (0, 0)

The program dices the screen up into squares a few pixels on a side. For each square, it evaluates r at the four corners, then draws two textured quads additively over it. The first is drawn in red and uses r_x as the Z coordinate. I've set OpenGL to map the Z value into a repeating one-dimensional texture which contains a few white pixels followed by a bunch of black ones. This creates the periodic lines. The texture is mipmapped to cut down on aliasing, so when the lines get really thin they fade out rather than dissolving into sparkles. The second quad is drawn in green, using r_y as the Z coordinates for the quad corners.

Here's a slightly more complicated example, with starting velocity of zero:

(0, 0) to (8, 0)

It looks like there is still a unique solution for every given displacement. The exception to this is on the line from (0, 0) to (8, 0) itself (drawn in yellow and faintly visible over the green); any point on there will give the same r.

Let's mix things up a bit more:

(6, -2) to (6, 2)

Now there are closed loops of constant r_x. There are some green and red lines that cross each other twice, indicating that for those values of r there are two solutions.

Here's a diagonal movement in velocity space:

(5, 0) to (10, 5)

Now there are some red and green lines that cross each other three times! So there are at least some cases that have three solutions. I don't know if there are situations with four solutions. The minimum-time solution is the one closest to v₀ and v_f.

If nothing else, this would make a really wild screensaver, if you animated v₀ and v_f to bounce around the screen.

Review: Dragon Quest Heroes: Rocket Slime

I just finished playing Dragon Quest Heroes: Rocket Slime, a Nintendo DS game from Square Enix. It was a blast; neither too long nor too difficult for me. The art is very clean and colorful; the writing is chock-full of atrocious puns (Fort Knight: Not Too Weak!); the controls are simple and well executed.

Rocket Slime is an action-adventure game. Its closest relatives are probably the Zelda series, although it is simpler and sillier than a Zelda. You play a blue slime, out to rescue the rest of your town's slimes from kidnapping by a nefarious mob run by two-tailed platypi.

There are two modes of gameplay. The first consists of bouncing around, bopping enemies, catching them on your head, and depositing them on a train cart bound for town. Once there, they see the errors of their ways and join your cause. You can also scoop up various items and ship them home.

The second mode is tank battles. These tanks are large, multi-story affairs. Your job is to bounce around the interior, bopping enemies and items, catching them on your head, and depositing them in one of the tank's cannons to be fired at the opposing tank. Once you've inflicted enough damage on a tank its mechanical heart is exposed, and you can dash over and give it a good whack to finish the battle. Different items have different effects as ammunition, so there's a small amount of strategy. You can even fire yourself over to the enemy tank; if you make it in you can sabotage it from within.

The items and enemies you collect during your adventures become available for use during the tank battles. Other activities in the game include upgrading the tank, performing alchemy to make valuable items out of lesser ones, and various minigames.

Only a couple of minor things bothered me. The most consistent was the tedious, bog-standard save protocol that afflicts most Japanese games:

"Do you want to save?" (Yes)
"Do you want to overwrite your previous game?" (Yes!)
"OK, I'm saving. Hang on!"
(big pause)
"Do you want to continue playing?"

...all delivered with each letter of dialogue spit out one at a time and no option to skip. All you need is a magic spot on the floor; when you run over it your game is saved. Teach the player how to use it once at the start of the game and you're good to go. The Sly Cooper games have demonstrated that there's no need for the actual saving to interrupt the game at all.

Another minor issue is that the map screen font had me confused for a while about whether I was seeing a 0 or 1 for the number of objectives remaining in an area.

Honestly, though, those are the only things I've got to criticize. It's an extremely well-made game, and I recommend it highly.

Pathfinding in Space, part 2

Our story so far

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 r₀, initial velocity v₀, final position r_f, final velocity v_f, and maximum acceleration a, find the minimum travel time t. This is the cost estimate for getting from (r₀, v₀) to (r_f, v_f).

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 r₀ is zero. Replace r_f 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.

There are two properties that I believe hold for minimum-time paths, but have not proved:

1. Acceleration magnitude is held constant at maximum for the entire flight; the only thing that varies is the acceleration direction.


2. 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_m (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 v₀ to v_m, and from v_m to 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_m. Fun, huh?

The first thing to do is to integrate directly from v₀ to v_f. 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 v_m between v₀ and v_f will do; it will just lie on the line between v₀ and v_f. If the base displacement is greater than the desired amount, then v_m will be less than both v₀ and v_f. If the base displacement is less than the desired amount, then v_m will be greater than both v₀ and 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_m, the two-dimensional case is almost identical to the one-dimensional case. The displacement r, velocities v₀, v_f, and v_m 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 v_m is what I've been stuck on for some time now. If you've got any insights, I'd love to hear them.

Pathfinding in Space

Sorry for the missing week. I threw out my back and was away from the computer for almost all of that time. I'm recovering nicely now.

During my week lying down I returned to a math problem I had been working on some time ago. Despite making some progress I still haven't solved it, so this entry will be a report on work in progress. Some background is in order, though.

Triplanetary board game

Triplanetary was a 1973 boardgame about flying and fighting in the inner solar system. I stumbled onto it on Board Game Geek's Elegant Simulations GeekList, and then again over at the wonderful Project Rho website (the centerpiece is Atomic Rockets). The chief attraction is its elegant Newtonian-ish movement system. It's actually pretty similar to a graph-paper race car game I played a bit as a kid, but on a hex grid instead of a rectangular one. Without acceleration, rockets continue on the same course each turn. Acceleration can come from burning fuel, or from flying near a planet, and (for simplicity) is made in whole-hex increments. A cute side effect of the rules is that there is a one-hex-radius orbit around each planet which, once entered, can be maintained indefinitely without expending fuel.

I haven't ever played one of these Newtonian space games; I don't know how fun they'd be live. I suspect you might need more turns than is typical for a board game session in order for the movement system to play out in interesting ways. As a result, you'd want to trim the turn time down to an absolute minimum. Nigel Hodge's Vector V5 game has a two-marker system that I think would probably work pretty well for tracking spacecrafts' present and future positions. Unfortunately, these sorts of games tend to pile on lots of weapon and defense systems that I'd expect would tend to lengthen turns considerably. Also, with “realism” once you're in for a penny there's a tendency to go in for a pound, and some games like Attack Vector: Tactical have added the third dimension to the fray, which I would expect to slow things down even more. Again, I haven't actually played any of these, though, so I can't really criticize.

Newtonian-movement games seem ideally suited to computer form, though; the computer takes care of all the bookwork so turns can fly by as fast as you can bang the keys. I started thinking about writing an AI for playing Triplanetary, so I could see for myself (and by myself) what's fun and what's not.

Here's the Triplanetary map, as represented in my test program. The squiggles in the middle are Asteroids; you take damage if you pass through them with a speed greater than one hex per turn. I don't usually run it with the name labels up. Currently they are placed with no regard to what they might be covering; Jupiter is under Callisto's label. Map labeling is an algorithm for another day...



Path planning in space

A key problem is creating a suitable path planning algorithm. How does a rocket get from one place to another? This has proved to be an interesting challenge and is behind the math problem I've been working on.

Essentially, this sort of thing is done all the time in typical computer games. The world can be thought of as a graph. Each node in the graph represents a state of the game; for simplicity, it usually represents just the essential state of one vehicle, and ignores the others. The edges connecting nodes represent legal moves that the vehicle can make. Creating a path involves finding a sequence of edges (moves) that goes from the current state to the desired state. Usually, you want a “best” path. Short length usually makes for a better path, and there may be other factors as well. These factors can be expressed with costs on the edges, and designing the search to find a sequence of edges with minimum total cost. The standard search algorithm for doing this is called A*, and is well-covered on the Internet.

There are some key differences that make the Triplanetary problem harder than the average game:

• State is more complicated. Most games assume the vehicle moves at low speed and can turn on a dime, so they don't count velocity as part of the state. For Triplanetary, both position and velocity are part of the state, and fuel needs to be as well. (Ships carry limited fuel, so if there are two paths that go the same place in the same amount of time, but one uses less fuel, it's better.) Because state is more complicated, the state space is correspondingly much larger. There isn't just one node in the graph per location on the map; there's a node for each combination of position, velocity, and fuel level. Since there's no upper limit on velocity, there are an infinite number of nodes per map location!


• The graph connectivity can be large. Disregarding the “overload” maneuver for the time being, there are seven legal moves a spacecraft can make: it can coast, or it can change its velocity by one hex per turn in any of the six directions. This compares favorably with a typical grid-based game, where each node connects to its eight neighbors. However, overload allows a ship to make one two-hex acceleration between repairs. This adds an additional twelve edges leaving each node, and a flag at each node indicating whether overload is available.


• It's much harder to come up with a good search heuristic. A* relies on being able to estimate for any given state how expensive it will be to reach the target state. When velocity is not part of the state, a simple distance measurement is a reasonable estimate; the idea is that the cost goes up more-or-less linearly with the distance to be traveled.

Finding a Search Heuristic

An ideal search heuristic keeps the search from examining any nodes that aren't on a best path. Of course, if you've got an ideal heuristic there is no need to search; it will infallibly tell you which way to go is best at each step. Because Triplanetary's state space and connectivity are relatively large, though, it is important to try to get as close as possible to the ideal.

To simplify the initial problem, I'm ignoring a few things:

• Fuel consumption. In theory this should be straightforward to add. It will have the effect of cutting off transitions later in the search, once the spaceship has run out of fuel and can only coast.


• Overload. Overload has the effect of greatly increasing the number of edges that must be examined at each node, so it may slow down the search and increase its memory usage. Again, though, it doesn't add anything conceptually difficult to the search.


• Obstacles. This is a usual omission from heuristics. The search space is considered to be wide-open and regular. For Triplanetary this is not a bad assumption. The asteroids will eventually cause real paths to be more expensive than the estimates, but that will not be a problem (other than causing the search to look at more nodes as it tries to get around them).


• Gravity. Gravity only affects the hexes adjacent to planets, which is a tiny fraction of the game map. This omission is a little worrying because it will make my naïve heuristic overestimate the cost when gravitational “slingshot” maneuvers are possible, but I will worry about that later. With gravity out of the picture, the only force operating on the vehicle is its own acceleration.

With these simplifications, the cost estimate will simply be the number of turns it's likely to take to get from one state to another.

I'm just about out of time so I will have to continue next week, hopefully bringing out the charts and diagrams. I'll leave you with a couple of hints as to where I'm going.

It's instructive to consider the one-dimensional problem first: given an initial position and velocity, and a desired final position and velocity, how quickly can you get there, given that your acceleration can't exceed 1? This problem turns out to have an exact, closed-form solution.

Once you've solved the one-dimensional case, it turns out you can do path planning for the race car game I mentioned earlier! It's played on square graph paper, and the X and Y accelerations are independent. (Thus, you can accelerate 40% more diagonally than you can horizontally or vertically.) This reduces the problem to two independent one-dimensional problems; whichever one takes the longest is a good estimate of how long it will take to reach the destination.

It also simplifies things to consider the continuous rather than the discrete version of the problem. The discrete version has some interesting features that complicate things. For instance, let's say your initial and final velocities are zero. You might expect that the logical thing to do is to accelerate toward the target until you hit the halfway mark, then turn around and decelerate until you arrive. For the continuous case this is true. However, the discrete case introduces some quantization because it evaluates things in whole turns. In some cases it's possible to coast a bit (thus saving fuel) while still reaching the destination in the same number of turns as if you'd accelerated the whole way.

An example is traveling ten units (with zero velocity at the endpoints). This takes seven turns. The “greedy” acceleration method moves these amounts on each turn: 1 2 3 2 1 1 0. It's more fuel-efficient to do these moves instead: 1 2 2 2 2 1 0.

That's all for today. Next week I'll go into the math for the one-dimensional case, then talk about the continuous two-dimensional case. See you then!

Life Advice

James McNeill can't come to the computer right now. He wanted to talk to you all about Pathfinding. What he should tell you is that everyone needs to spend just a little less time each day at their desk, and a little more time exercising. See a doctor before a problem becomes a major problem.