Thoughts on AI, collision avoidance

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

This entry was posted on Friday, July 8th, 2011 at 4:08 pm and is filed under Development. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.

13 Comments:

  1. It’s very nice, I especially want to see how this pans out with the slower capital ships. However, will all ships react like the one in the video when missiles are coming at it? Maybe missile speed and maneaverability should be touched up since missiles in that video seem to be wholly ineffective against ships like that.

    by Horrigan
  2. I was particularly impressed in 0:28, where the AI was able to re-position itself to a better angle while avoiding what looked like a series of sure hits…. That was very smart

    by d
  3. @Horrigan: The ship in the video is the fastest in the game right now – it’s supposed to be that good at avoiding LRMs and other bad things in general.

    Rest assured, these missiles are effective vs slower ships, including other frigates that aren’t quite as fast as the Tempest-class (the one in the video).

    The LRMs are definitely a support weapon, though – if a ship can focus on evading or shooting them down with PD, they won’t be effective. Combined with other attacks, they can be devastating.

    By the way, you can see smaller, faster missiles in the video (“Swarmer” class SRMs, ideal vs fighters) that have a much easier time catching up to the Tempest, which then stops them with shields – say, at 0:20.

    by Alex
  4. Thanks for the article! I have just started working on AI for my little space game I am making.

    I am quite impressed :D

    by cloakdood
  5. Wow that ai has some technique! Would scalable skill levels be possible? What I mean is, would it be possible to be able to face captains of varying skill levels as well as upgrade your own captain’s skill over time?

    by IMakeWeirdThings
  6. The plan is that your (and other captains’) skills impact the attributes of the ship being piloted – it gets a little faster, more maneuverable, etc.

    by Alex
  7. Sounds like a very uninteresting article and turns out to be completely the opposite! Can you leave the ability to turn on and off those arcs and vectors in the final game?

    by Tubs
  8. Excellent article, and good work on the new algorithm! This is really unlike any other approach I’ve seen.

    by Trylobot
  9. @Tubs: To be honest, it’s easier to just keep the toggle for it in the code for now.

    @Trylobot: Thanks! Glad you found it interesting.

    by Alex
  10. Very interesting article, please do more of these, they are very educational for other developers. : )

    A bit unrelated, but I must say that the backgrounds in your game feel really out of place. If I’m not mistaken, those look like photos. They feel somewhat overly colorful and dead. I’d strongly suggest creating the background and its element using the same style you used to make the ships. It would feel more consistent and better overall.

    by Reactorcore
  11. Thanks for your feedback. It’s a bit hard for me to be objective about the backgrounds, having stared at them for such a long time by now, but I’ll keep it in mind.

    I should say that in general, impressions about the backgrounds have been positive, though there’s probably a selection bias there.

    by Alex
  12. Would it be possible to include a shipmodule or subsystem in the game, that projects those “dangerarcs” as an aid for human players?

    Sort of like a battlecomputer upgrade?

    Because I´d totally buy one for my Flagship.

    by currzwurst
  13. Hmm. I don’t know that that’d be particularly useful. Not being an AI yourself, you can actually see the stuff coming at you an avoid it :) Other battle-computer type upgrades are quite likely, though.

    by Alex