How can I navigate to a target between bodies moving along fixed paths?

Question

The problem: An autonomous ship starts at the outskirts of a solar system, and wants to move to a moving target, which is one of the planets. There are also many other planets moving at the same time, and these should be considered the only obstacles. I want to find the optimal path to the target. To keep it simple, the world is 2D, and the planets are moving in uniform circular motion around the sun as opposed to how planets actually behave. Also, assume the ship knows pretty much everything about the world. Most importantly, the location, speed, and orbit radius of every planet.

With complete knowledge, this seems conceptually simple. For any planet and any time, you can find its location by doing some fairly simple math. But how would you apply this to pathfinding? Would it be just to pathfind in 3 dimensions: x, y, and t? In theory this makes sense, but I think working that out to an actual solution would involve a lot of complications. Is it really as simple as 'setup a* on a grid with x,y,t values'?

Answer 1

Without precision requirements, there's no way to get an optimal solution, because traditional pathfinding must consider the time / space discretely at some level. But I don't recommend traditional pathfinding for this problem anyway, at least not for the entire problem. It won't look particularly realistic, and it will use a lot of resources.

Assuming the motion of the target planet is described by planet(t), ignoring obstacles, there is a closed form solution to find the intersection:

position + velocity * t  = planet(t)

Doing some basic algebra,

velocity * t             = (planet(t) - position)
||velocity|| * speed * t = (planet(t) - position)
||velocity||             = (planet(t) - position) / (speed * t)

Space is mostly empty and that holds true of most space games as well; 99% of the time, the ship can simply follow that vector to intercept the planet. This equation is trivial to solve in both CPU time and memory required.

To avoid collisions, I would use steering behaviors, notably obstacle avoidance. Once obstacles are avoided, you evaluate the equation again.

This is much lighter-weight than A*, and probably better approximates what an actual pilot would do. It also works even if there are unpredictable obstacles, and for targets following any motion function, regardless of whether it is circular or not.

Answer 2

In my experiment, i tried to do something like Joe Wreschnig is sugesting. Important thing is, find out WHEN i want intercept target. I do it simply by iterating coputing how long will it take to target, where it will be by then and how long it will take there.

But my ships have inertia. But i combined collision avoidance and seeking. Basicaly, ship want to 1) be where target is 2) avoid everything else. From relative position RP to other things i compute position where ship want be (POS + k1*RP*(1/RP.length^n), (n something around 3-5) + k2*(RP.x,-RP.y)*(1/RP.length^m) so other things affect ship only little if far enough (and ship have limited sight, so most does not affect it at all) and ship want to avoid them by flying away and sideways from them, so even if it cannot even break before impact, it can miss.

Then I combine 1) and 2), so ship goes to target and once it see obstacle, it starts evading it. As obstacles gets nearer, ship evades more strongly and once it gets far, target seeking becomes dominant again.

Answer 3

Joe has already pointed out the important issue with the difference between discrete states and continuous states, so I'll just ignore that problem and pretend that you can pick a discrete time-step that is big enough to not be too expensive to use and small enough to have the precision you need.

Conceptually, there's no problem with your approach. Remember that A* is not a "pathfinding" algorithm - it is a search algorithm. It doesn't require that the states it searches through correspond to geography in any way. In this case, each node of the search would include not only the ship's position but also the position of every other body in the system. (But as you already figured out, you don't need to store their positions for each node, as you can derive them from the current time, so you could store that instead.)

Formulating a good heuristic can be a bit more tricky - if your ship moves fast enough, then the planets won't move much during the path and so the estimated distance will decrease fairly linearly as the ship approaches. But if the ship is slow compared to the planets, you'll need a better approximation. An iterative solution is probably good here: you can estimate the time to arrive at the planet assuming it doesn't move, recalculate where the planet will actually be at that time, then estimate the actual time to reach that position, estimate where the planet will be at that second time, and so on. Hopefully the values will converge after a few iterations towards something useful - but you'll need to test this. If the values don't converge then it implies the planet is moving too fast to track and a different high-level strategy is needed (eg. pathfind to the orbit and then move along it to the destination.)

Answer 4

A* is an optimization of the simpler Dijkstra algorithm, in it's base form that optimization assumes that the target is standing still. Basic Dijkstra is perfectly applicable to a moving system. You could try to gain some of A*'s advantage by calculating a simple interception vector to use instead of distance in A*.

Though all this does assume that your spaceship moves in a simple grid, the problem will be much harder if it has a more complex movement structure.