If you’ve been keeping up with the ongoing patch notes, you probably know I’ve spent most of the last week re-working large parts of the ship AI.

A week ago, it was in a decidedly “if it ain’t broke, don’t fix it” state. In fact, it was quite good, except for a few dumb things it sometimes did. Still, Starfarer is a single-player game, so good AI is critically important, and these needed to be fixed. Armed with a list that I’ve been updating based on player feedback and my own experiences, I decided to devote a few days to eliminating them.

As an aside, making the AI not do dumb things is as important to the experience than making it do smart things, maybe more so. Seeing it do something ridiculous – such as repeatedly ramming a friendly ship in an attempt to escape some other danger – is immersion breaking. But if it tries to do something smart, you better make sure its plans actually come off, or it will look silly anyway – since as the player, you usually won’t know what smart thing it was trying to do, but will see it fail. The payoff for doing something smart is lower than the penalty for doing something inane.

It is wholly a matter of perspective, though. If your goal is to have the AI maneuver more strategically, you might state it as “avoid being surrounded” (negative – don’t be stupid!) or “keep enemy ships in one general direction from itself” (positive – do something smart!). Notice that the negative goal is easier to state – and if it’s easier to state, chances are it’s easier to approach when it comes time to implement it.

Incidentally, almost every new gameplay addition breaks the AI – either by making it easily abusable, or worse – so AI work is always going on behind the scenes to keep up with features.

Collision Avoidance
So, after fixing most of the items on my list, I realized that there was a big problem there wasn’t a quick solution to – collision avoidance. The algorithm I had implemented initially had some issues that could not be easily fixed. I know that, because I spent almost a whole day trying! It was time to toss it out and start fresh.

The main trouble with the old algorithm was that it wasn’t context-aware. Collision avoidance isn’t something you want to be doing all the time – generally, a ship is trying to do something else that’s actually useful, like attacking an enemy or getting out of danger – but then you also want it to not run into things while doing these. The old algorithm was an all-in proposition – if you were in danger of hitting something, it took over without regard for what the ship was trying to do at the time. Oftentimes, it would end up on the wrong side of a broadside as a result of successfully avoiding a minor asteroid.

The challenge was to come up with a collision algorithm that could incorporate current ship preferences into its response to potential collisions.

The first part, expressing ship preferences, was easy – the ship AI simply keeps track of which direction it wants to be going, and tells the collision avoidance module. For example, if it’s strafing around an enemy ship, it wants to go away from it if it’s too close, and towards it if it’s too far.

The hard part was coming up with an algorithm that could both be successful at avoiding collisions and could accept this preference as an input. Instead of talking about it in great detail, I recorded and annotated a video showing it in action first, with overlays that tell you what the AI is thinking at any given time. Seeing it will really help make sense the explanation that follows.

In the video, the blue line shows where the ship wants to go. The yellow line shows where the collision avoidance algorithm actually tells it to go. Green arcs show potential collision dangers. The arcs turn red when the danger is imminent and the ship is actively avoiding it.

Here’s a high-level breakdown of what the algorithm does (continued):

• Evaluate all nearby objects and figure out a “danger arc” for each one, based on its size, location, and relative velocity.
• See if any objects are dangerous enough that it actually needs to bother avoiding anything (is collision response “triggered”)
• Find gaps in the arcs
• Pick a direction, in one of the gaps, that’s closest to the actual direction the ship wants to go
• Move in that direction, utilizing strafing/turning/acceleration backwards & forward as appropriate

That’s it. Now, if you’ve got some experience in development, you’re probably saying to yourself: “That’s way too clean, no way it works as-is. I want the dirty details – what really makes this tick?” Very well, then, you asked for it!

First of all, the algorithm really is pretty clean. The above flow isn’t hacked to pieces anywhere, there are just a few special cases that it needs to handle.

There are actually two levels of triggering the collision response – “do something” and “do something drastic”. In the latter case, the ship ignores the preferred direction it wants to go in and focuses purely on avoiding the collision. Imminent collision danger really does require a fully committed response to avoid.

Then, there are missiles. Moving directly away from something faster than you isn’t going to avoid it if it’s trying to follow you – so if there is imminent danger from a missile, the ship will pick an angle, still within a gap, that’s close to the edge of that gap. The result is that it’ll move sideways to get out of a missile’s path, instead of trying to outrun it. The other part is ignoring some missiles that aren’t dangerous enough to bother with – such as anti-fighter SRMs.

The algorithm can also be told to ignore certain objects – rather, make them not trigger any level of response, but still be avoided if a response is triggered by something else. This is useful when a ship is strafing a target, and explicitly controls itself with respect to it so there is no danger of collision, even though it might look like it to the algorithm.

Finally, there’s the question of what to do if there are no gaps. There, the approach is minimalistic – simply slow down. Oftentimes, that’s actually a good decision. If it’s not, it still better than actively doing something that’s not effective. On the whole, this situation doesn’t come up much – ships usually do a good enough job of avoiding such situations to begin with.

Overall, having collision response be aware of other tactical concerns is a huge step to making the AI behave more intelligently in a wide variety of situations. It also opens the door to more enhancements along the same lines – for example, adding a preferred facing that the ship can maintain while still avoiding collisions, if its current maneuver so desires.

Well, that about wraps it up. I hope you guys found this interesting!

Tags: ai, algorithms, artificial intelligence, collisions, development, missiles, ship ai