Space Navigation

_{This is a technical essay for beginners on the subject of AI navigation in space games.}

A few weeks ago, I tried to build a space-fleet-combat-game. In the process, I learned a whole lot about how to get an AI to navigate in space. Recently, one of my friends tried the same thing, and I realized it might be worth doing an introductory essay on space navigation, plotting intercept courses, taking into account gravity wells, etc.

Proper space games, whether Star Control 2-style or Wing Commander-style, have a few factors that make them completely different from other games. First, the main engines point directly backwards and turning isn't instant. Second, you keep going on the same vector: no (or very low) friction.

This totally destroys the old fashioned interception calculations that you might use for a first-person-shooter or RPG, because as time passes, the target will be in a different location relative to you (whether it's you, he, or both that are moving).

The easiest way I found to calculate out a basic intercept course is as follows:

Get the distance between you and your target. Divide it by your average speed. That is the ETA.

Calculate the new positions of you and your target at ETA, but cap your vector at a certain constant number of seconds (3 is good for most action space games). IE, if the enemy is moving x+1m/s, in ten seconds he'll be at x+10m. However, if you are moving at x+1m/s, in ten seconds you'll be at x+3m, because your vector vanishes after three seconds. We negate our own vector because we plan on changing it radically.

Now, determine how long it would take to reach these virtual positions. IE, how quickly you can turn to the proper heading and close at speed. Do not bother taking into account your current vector. This is the estimated course (EC).

If the EC is roughly the same length as the ETA, go for it. If it's significantly different, increase or decrease your ETA significantly and try again until you find an EC that works or your ETA becomes stupid (error out).

This system works in most space games because most space games have a maximum speed cap. If your maximum speed is 100m/s and you're traveling at x+100m/s, accelerating along the z axis will make you arc away from that and to z+100m/s, no x velocity at all. This is true both of 2D and 3D space games: most of them impose this artificial speed cap so that people have a hope of being able to navigate intuitively.

The slower you turn and the longer it takes to reach your maximum speed, the more of a factor your current velocity will be, and the longer your personal velocity cut-off time should be. In addition, when calculating your estimated course (EC), you should take into account that your average speed will be lower than your maximum speed because you have to accelerate - and if your acceleration is slow, that will be more important. Obviously, the longer the thrust, the closer to your maximum speed your average speed will be.

...

Now, if you're like me, you're the sort of person who doesn't want a speed cap. If you're traveling at x+100m/s and you start thrusting along z, you'll reach x+100m/s & z+100m/s. No speed cap except maybe light speed.

This makes navigation difficult because you have to factor in your vector much more strongly, often moving to negate it. On the surface, you should just be able to do away with the velocity cutoff. However, it's not quite that simple.

First, you need to calculate not just where the enemy ship will be at ETA based on his current vector, but also based on his acceleration. If a ship is accelerating away, you need to take that into account or you'll be hopelessly off course.

Second, this system produces radically inappropriate intercept speeds. You'll blow by your enemy doing 0.3c, you won't even see the bastard as he blips by. So you need to put in some kind of rough vector matching mixed into the basic intercept package. It's possible to program, but the actual physics of the matter make it highly difficult: unless your ship has many times the thrust of the ship you're intercepting, it will take you a long, long time to close and match vectors. And if you've got any human-controlled ships, forget it!

Another factor in this kind of game is the light-speed cap, which is a common thing to want to include. The idea is that the speed cap is light speed, and the closer you get to light speed, the more thrust it takes to change your vector.

There are a lot of problems with this. In basics, this means that your current velocity will screw up your acceleration. Plotting an intercept course may involve having to slow down so you can accelerate along another vector.

Of course, the truth is that the issue is radically more complex than that, because you're always operating from your own frame of reference. You aren't going 0.9c: everything else is. The light speed limit is no good for gameplay unless you (A) are a physicist or (B) throw away any realism it may have had.

...

With the described system, basic navigation is possible. However, most games want more advanced navigation: they want to be able to orbit planets, do gravitational slingshots, present broadsides, interpose specific faces of their ships, ram (and avoid ramming), etc, etc, etc.

Each of these things requires some pretty significant tweaking... and, of course, the basic calculations presented here are not exactly optimized. They give pretty rough (but functional) intercepts.

There's the basics. Hope it helps.