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):

Read the rest of this entry »