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.
