The X3 Autopilot Guide

General discussions about the games by Egosoft including X-BTF, XT, X², X³: Reunion, X³: Terran Conflict and X³: Albion Prelude.

Moderator: Moderators for English X Forum

User avatar
mrbadger
Posts: 5669
Joined: Fri, 28. Oct 05, 17:27
x3tc

The X3 Autopilot Guide

Post by mrbadger » Sat, 14. Nov 09, 18:32

Before I start, This is not a guide to the actual AI code used by Egosoft, I've never seen that. Rather this is an explanation of the artificial intelligence techniques (I believe) they use, and why they use them. I'm not a games developer, but I do work in the AI field.

This is a long post, so I've put it into a pdf as well, which might make it easier to read

Download


We'll start by understanding what Artificial Intelligence, or AI, actually means. Unfortunately the term is confusing, I would say it should be more accurately termed 'Automatic Task Completion', especially when applied to games. AI can only make decisions based on what it knows and/or remembers of its environment. It can't perform abstract thought like we can, so if anything unexpected occurs, where we might succeed, AI would run out of ideas and fail.

Within this constraint, AI can still be pretty smart, and can outperform humans in some limited tasks. However what might seem at first to be a simple task is often (indeed invariably) far harder than it looks.

Consider how you might fly across a sector in the game. You look ahead, see any obstacles that are fixed (stations, asteroids), and fly with a view to avoiding them. Then there are other ships around, so you alter your course to steer clear of them a long time before you reach them.

This is the behaviour most people want the AI in X3 to mimic, but it obviously can't. Why is that?
Lets go over the example I just gave again.

To fly across the sector you needed several things:

1: Awareness of the position of all other ships nearby.
2: Awareness of the positions of all stations relative to you long before you reached them.
3: The ability to plan a route to take you past currently known obstacles in the sector, and re-plan that path if your original needs changing.
4: Knowing roughly where the ships you see now will be when you reach them.


The 'simple' task has suddenly become a lot more complex. To mimic our traversal of the sector, the AI has to retain and update an awareness of everything in the sector, then plan a route to move past every obstacle, given not only current position, but likely future position of all other obstacles. Also it must react to threats, or be one itself.

Some games do manage this. The classic example, where in-game AI really took off, is in first person shooters. There are obviously other examples, but I have to pick one, this isn't a dissertation after all :)


How other games do it, and how this applies to X3


The AI bot in a modern shooter makes use of a pre-calculated map of a level through which, in many cases, optimal routes have already been found and stored.
They know, because again the information has been provided in this map, where certain objects it can make use of can be found. In some games they also make use of neural networks which have already been trained in many of the tasks they need to perform.
That means they have pre-calculated responses to many things a player might do, and because the neural network is adaptive, meaning it can 'learn' from your reactions to its actions, it can improve during the course of a game. The classic example of this is the Reaper Bot for Quake 1.
This can add up to pretty impressive mimicry of real intelligence, and it is understandable that players in X3 want that same level of performance in their autopilot.

FPS game developers make use of certain tricks to produce this effect. One thing they do is prevent npc characters from becoming active until a trigger region is entered, or deactivate them when the player leaves it. That way they can populate a large map with AI controlled characters, but, through the simple expedient that the player will be killing off npc characters as they meet them, the actual processor load caused by this AI can be kept quite low. Thus the illusion of an active world is created.


The main points of this form of game AI are:

1.The world the npc AI is aware of doesn't change, or changes only slightly.
2.Only part of a level needs to be active at any one time.
3.Only one level is active at a time.
4.The number of active npc characters is only a small number of the total on a level.



So, lets compare these points to X3.


Point one: The world doesn't change


This isn't true of X3. The game is continuously adding and removing stations, ships are moving in all sectors of the game from the first moment you load the game, and you, the player, are also changing the content of sectors, whether by building stations, buying new ships, or killing npc ships and stations.

This means pre-calculated maps of sectors with paths for the AI to follow can't exist. They would be out of date within moments of the first time you load the game. Periodic regeneration of the maps wouldn't work either, since the same thing would happen, they would be out of date too soon.

Also, in X3, a sector is a 3D region, and every part of it can be visited. Even if pre-calculated maps were used, they would be vast


Point two: Only part of a level needs to be active at any one time


In X3, every sector, and every ship in the game is active as soon as you first start a new game. Egosoft manage this by having different methods for in-sector and out of sector path finding and ship/station interaction code. When out of sector AI is in use, collisions are off, thus obstacles don't exist, and an almost straight line path can be followed. I've seen ships still fly round stations, so there must be some form of collision avoidance, but this is almost certainly just to try and prevent ships being inside stations when you turn up in a sector.

I can tell this doesn't always work. Ever arrived in a sector only to hear/see a massive explosion as a ship explodes? That's an OOS obstacle avoidance code failure, hardly surprising when there are so many ships and other objects in the game. It works a lot more often then it fails though.


Point three: Only one level is active at a time


We've already covered this, the OOS code reduces the problem slightly, but this option simply isn't available.


Point four: The number of active npc characters is only a small number of the total on a level


In X3, all npc ships are active as soon as you enter a sector, so that optimisation isn't available.


What all this adds up to is that the artificial intelligence methods used in FPS games among many others, just don't apply to a game like X3.

So what methods are available? We'll look just at in-sector AI for this, and assume, as I believe is the case, that the AI used by npc ships is the same as that used for the autopilot of the players own ship.

We'll go back again to the problem of crossing a sector. The npc AI could make itself aware, on entering a sector, of the contents of that sector, including all the ships, then note which obstacles are stationary, and which moving. Then it could exclude the area's containing non moving objects from its list of available paths.
Once this was completed it could establish which ships in the sector are close enough to enter its proposed flight path. If not, they could be discarded.
That leaves us with only the ships close enough to be an obstacle, so we start to look at them. What speed are they moving at, and in which direction? Are they hostile? These are all factors that can be handled by competent AI, so a route could be planned that kept the need to alter it to a minimum.


This all sounds great, and I'm sure Egosofts' programmers could achieve it, so why haven't they? Why isn't X3 so smart that we get stuck outside our flagship begging it to open the pod bay doors?


The simple answer is that the game is too big. There are, as I mentioned, thousands of ships in the game, hundreds of sectors that need to be kept 'live', and anywhere from tens to hundreds of ships in the same sector as the player at a time. Introduce the combat element and it just gets worse, because each bullet and missile also needs to be tracked.

Wonderfully capable AI would, in this situation, drag the game down to the point that it wouldn't just be unplayable, it wouldn't even be possible to develop it in the first place.

The choice of making the game smaller to allow for this great AI isn't open, because the whole point of the X series is that they are vast sandbox games. Give players, say, ten sectors with no more than 20 ships in each sector, and it might be possible. It would also be pointless, because no-one would play it.

It's all about trade-off. The best known demonstration of this is 'Fast, Cheap, Good. Pick two', a phrase that can be applied to almost any solution to a problem.

So we've looked at what the AI in X3 needs to do, and also at how other games do it, and covered why Egosoft can't just use those methods. Lets move on to how the AI they do use works.


The X3 AI, how they do it


We know now what the AI needs to do to fly around without pancaking against asteroids, and the methods it can't use. What's left then? Happily there remains one class of algorithm for path-finding that solves many of these problems, the greedy search, also known as the greedy algorithm.

Greedy search could be described as 'fast and cheap', possibly with the caveat 'and good enough most of the time'. If you're interested, it seems that the route planning used when decided which sectors a ship should go through to reach a destination sector in the shortest time is another kind of greedy algorithm called 'Dijkstra's shortest path algorithm'.

Most of what we discussed thus far requires knowledge of the entire level to work, but a greedy method does not. All it cares about is whether the next move improves on its current state. It doesn't look beyond that, and has no awareness of the results of past choices. That's why your Split Nemesis will happily pound itself to death on a station while trying to dock by repeatedly trying the same bad move until it blows up (a reference to bad day I had in Reunion long ago).

Under autopilot, your ship will note where you want it to go, point itself in that direction and head off at top speed. It won't check to see what other ships are doing when it does this. As it encounters an obstacle, be it a ship, asteroid, rock or station that is close enough for a collision to happen, it will begin a local search for a path round this obstacle which will provide it with a new straight line path to its target.

This search runs as follows:

Step 1: Reduce speed.

Step 2: Pick a direction away from the obstacle.

Step 3: Travel in that direction for a short distance.

Step 4: Calculate a new straight line path and follow it.



If by step 4 the obstacle is gone, the autopilot will continue, not remembering that it just performed the avoidance move. If not, it returns to step 1.

To get a good example of the search it does in action, go to Terran space and set the autopilot to fly you from one gate to another. You'll see the ship repeatedly make the same 'sidestep' move as it tries to get past those huge stations. It almost always stops too soon, when just going a little further would mean it could avoid the obstacle altogether, but instead it cycles through steps 1-4 many times, each time performing a small avoidance manoeuvre.

Flying through a large group of asteroids will also provide a good example.

This approach has issues. Sometimes the direction it chooses is a bad one. This often occurs when the area it's negotiating is packed with obstacles. The AI can only handle one obstacle at a time (remember, no awareness of the rest of the sector is possible with this method), and if it's too close, it may be that every choice is a bad one. Also, the other obstacle may be a ship, and it's also going to choose an avoidance direction, if it has time, so you might both move in the same direction anyway, and collide.

Using SETA while the autopilot is active makes even this simple avoidance method worse, because there is less time available for the ship to make its avoidance direction choice. After all, the game engine is handling many ships in the sector as well as your own. That's why using SETA to negotiate a dense asteroid belt is all but suicidal, and why collisions are far more likely under SETA when you are close to many other ships.

Have you noticed that the game won't let you turn on the autopilot when too close to a station? That's one of the ways they found to reduce the problem of collision with stations. They also made it so SETA will shut off if you're flying unguided past some large object without the autopilot active and pass within what would be 'avoidance routine' triggering distance for the AI, which can give you chance to either activate it, or steer yourself out of trouble.

I've listed a lot of problems with the method, so why do they use it? Well I've mentioned this as well. It's fast. This AI model is why we can have the vast sandbox game we have, with so many ships. In fact I'm astonished that they managed to make a game so big even using the method they do.

So, how do you prevent this minimal AI from costing you lost ships and reloads from collision deaths? I have a few tips:

Don't let the AI fly you through asteroid fields

If there are lots of ships around, take over and steer the ship yourself.

NEVER use SETA when there are other ships you own in the same sector as you.

When docking with the autopilot, check to see if there are other ships already docked. If there are, you might find them undocking while you approach, which may well mean an unavoidable collision.

Don't use the autopilot in Terran space unless you area long way from stations or gates. The same applies to any sector with a large amount of ships, or a battle you are involved with.
Last edited by mrbadger on Sat, 16. Jan 10, 01:44, edited 4 times in total.
If an injury has to be done to a man it should be so severe that his vengeance need not be feared. ... Niccolò Machiavelli

Doktor Teufel
Posts: 221
Joined: Wed, 22. Mar 06, 23:32
x3tc

Post by Doktor Teufel » Sat, 14. Nov 09, 20:28

What an excellent and informative explanation!

Thank you for taking the time to write this, mrbadger. I understand the AI's behavior, its strengths and weaknesses, the challenges and limitations of implementing AI in a game of this nature, and the tradeoffs that must be made for playability a whole lot better now.

It all fits together and makes sense. Without a perspective on how game AI actually works, it's hard for your typical layman like me to grasp why the AI can't be better, though of course I've always known that keeping track of the X universe during play is an amazing task in and of itself.

User avatar
RandomBandit
Posts: 877
Joined: Tue, 16. Jun 09, 23:21
x3tc

Post by RandomBandit » Wed, 25. Nov 09, 07:12

:o
Bravo

It does bring to mind one smallish thought...It should be possible to give our personal ship better AI, at the least...or maybe our wingmen too? heh heh

I am surprised more people have not replied to this post, it makes good points...any devs feel like elaborating?...ya know you wanna... :D
<X3tc 2.0> patched up to 3.1 (No BonusPack)
<X3ap>
I do not use scripts/mods.

User avatar
mrbadger
Posts: 5669
Joined: Fri, 28. Oct 05, 17:27
x3tc

Post by mrbadger » Wed, 25. Nov 09, 09:15

RandomBandit wrote::o
Bravo
It does bring to mind one smallish thought...It should be possible to give our personal ship better AI, at the least...or maybe our wingmen too? heh heh
Your personal ship already has better AI, you... :)
As for Wingmen, yes I can see where just improving the lot of a small number of ships might appeal, but wingmen wouldn have an even harder job with their better AI if they had it, since they would be having to be near you, the least predictable ship in the game for a lot of the time.
RandomBandit wrote: I am surprised more people have not replied to this post, it makes good points
It's not really something that I expected people to reply to, I put it into a pdf as well, and that gets downloaded a fair bit.
Last edited by mrbadger on Wed, 25. Nov 09, 12:33, edited 2 times in total.
If an injury has to be done to a man it should be so severe that his vengeance need not be feared. ... Niccolò Machiavelli

Smyde
Posts: 85
Joined: Sat, 29. Aug 09, 23:26
x3tc

Post by Smyde » Wed, 25. Nov 09, 10:16

This is really interesting, something I had never thought about before. Would it be possible to do the more complex method once when the ship enters the active sector or is given a new command while IS then revert to the current method for anything that comes along after that.

jlehtone
Posts: 17268
Joined: Sat, 23. Apr 05, 21:42
x4

Post by jlehtone » Wed, 25. Nov 09, 11:59

:thumb_up:

But it wont prevent recycled rants.

LordForrester
Posts: 499
Joined: Mon, 21. Sep 09, 23:33

Post by LordForrester » Wed, 25. Nov 09, 17:32

IT is a great post mrbadger thanks.

Can we have it made a Sticky?

Bothersome
Posts: 834
Joined: Thu, 26. Jul 07, 20:58
x3tc

Re: The X3 Autopilot Guide

Post by Bothersome » Wed, 25. Nov 09, 18:52

mrbadger wrote: This search runs as follows:

Step 1: Reduce speed.

Step 2: Pick a direction away from the obstacle.

Step 3: Travel in that direction for a short distance.

Step 4: Calculate a new straight line path and follow it.

Uh, I've bitched about this before (for years now), and this is the part that makes the auto-pilot an auto-idiot.

The actual steps in X3R and TC are

Step 1: Apply full throttle.

Step 2: Pick a direction away from the obstacle.

Step 3: Travel in that direction for a short distance.

Step 4: Check if distance away is really close now. If so come to complete stop and go to step 2 again.

Step 5: If away, calculate a new straight line path and follow it, else go to step 2 again.

The error is in Step 1. And I can't get anyone at Egosoft to even consider changing it.
"The difference between fiction and reality? Fiction has to make sense." - Tom Clancy

User avatar
mrbadger
Posts: 5669
Joined: Fri, 28. Oct 05, 17:27
x3tc

Re: The X3 Autopilot Guide

Post by mrbadger » Wed, 25. Nov 09, 19:13

Bothersome wrote:
Uh, I've bitched about this before (for years now), and this is the part that makes the auto-pilot an auto-idiot.

The actual steps in X3R and TC are

Step 1: Apply full throttle.

Step 2: Pick a direction away from the obstacle.

.......

The error is in Step 1. And I can't get anyone at Egosoft to even consider changing it.
The Autopilot definatelly slows the ship before turning on the new vector when trying to get round something.

Sometimes, true, it doesn't reduce speed while changing direction during flight, but when in an avoidance manouver the ship slows first. I've not observed any other behaviour.

Try flying across Ockracokes Storm, that's the best place to see it happening.

Or, are you referring to the times when your ship is suddenly faced with another coming through a gate or when you've just come through and there's a bigship on the other side?
The times when this has happened to me I've always taken over from the autopilot, so in that case it may be that high speed course changes happen and I've never seen them.
If an injury has to be done to a man it should be so severe that his vengeance need not be feared. ... Niccolò Machiavelli

LordForrester
Posts: 499
Joined: Mon, 21. Sep 09, 23:33

Post by LordForrester » Wed, 25. Nov 09, 20:16

I have noticed that a slow CPU does effect how effective the Auto pilot is. If my fps drop because something in the back ground starts up like my AV then the auto Pilot is less effective.

Normally I can run SATA 10x no problem in auto pilot. Only having problems if something takes resources away from the game.

RainerPrem
Posts: 2970
Joined: Wed, 18. Jan 06, 08:39
x4

Post by RainerPrem » Thu, 26. Nov 09, 10:54

Hi,

GREAT!!! :thumb_up: :thumb_up: :thumb_up: :thumb_up:

Why did I miss it when you wrote it?

It should definitively be sticky!

cu
Rainer

AjaxDude
Posts: 379
Joined: Sun, 30. Mar 08, 21:07
x3tc

Post by AjaxDude » Fri, 27. Nov 09, 08:50

Great post there. Has anyone considered starting a mod to completely redo the autopilot. It would be a massive task, but if they pull it off, it would be great.
How can one player flying one ship defeat a big gang of pirates?

Good flying, or reinforcements. Lots of reinforcements.

Catra
Posts: 7687
Joined: Mon, 12. Oct 09, 21:54

Post by Catra » Sat, 28. Nov 09, 10:39

POSTING FOR GREAT JUSTICE :lol:

nice read, awesome thoroughness, needs more attention :)

TheLastHero
Posts: 87
Joined: Wed, 23. Jan 08, 17:51
x3tc

Post by TheLastHero » Sat, 28. Nov 09, 11:05

and also total crap.

He didnt bother taking into account that the current situation in X3 is that it has to on many ships in a sector at once rework collision detection.

and that it doesnt bother simulating proposed path change before making it.

instead it bullheadedly just attempts to do it once it rearranges the ship to the new path, it then asks is this OK?, which is at about the time the ships RAMMING INTO ANOTHER SHIP OR STATION OR ROCK.
Which not only results in most of the collisions, eats up MORE CPU TIME, then a routine that attempted to work out if its proposed pathchange was infact clear.

Perfect example of how bad this AI is, is in Astroids that are stationary, the Big Rock in the AUldrin sector is the best example EVER of CRAPTASTIC AI.
When your AI code ends up in a nonstop loop to avoid a stationary object which doesnt move, and which you can.. the AI code is flawed.

no excuse at all can ever actually excuse an AI that makes Collision detection and then acts on that, without ever bothering to LOOK if its surposed pathway is clear.

its a noob mistake
it sounds simple
and if you tested it agasint a single small object it would be very efficent.
Stick lots of objects thou..
and its got to CONSTANTLY rerun, not only does it constantly need to rerun, but as its rerunning and causing needless vector changes other ships have to start recaluating.

The end result is a total utter pile of crap code that uses far more CPU power then a slightly more complicated AI routine that actually simulated the proposed changes before applying them to the game world and setting off the dommino effect for a vector change that itself needs recorrecting 100-200ms later.


and you can claim CPU limitation all you like.

BUT

when X-wing
a game on 386's cpu
had decent(it did collide at times) but decent AI
on a cpu is hundreds of thousands of times slower then the current mid range CPUS
The Argument falls apart.

and before I sign off
another perfect example of the craptastic AI code is formation flying.
It neither cheats to form formations, or allow some slack.

The end result is ships in formation constantly attempting to recaluate there position, then speeding up and down constantly reworking vectors because they have to be AT the exact spot they are told to be being 5-10 meters from that spot is not allowed.

the end result is once again more CPU power required when there were options that not only WORK better use less cycles.

User avatar
mrbadger
Posts: 5669
Joined: Fri, 28. Oct 05, 17:27
x3tc

Post by mrbadger » Sat, 28. Nov 09, 11:46

Catra wrote:POSTING FOR GREAT JUSTICE :lol:

nice read, awesome thoroughness, needs more attention :)


I feel it could have done with some accompanying videos, but I don't own any software that could do that.
If an injury has to be done to a man it should be so severe that his vengeance need not be feared. ... Niccolò Machiavelli

Locked

Return to “X Trilogy Universe”