Baddie AI in Lost Outpost

When it came to adding the baddies to Lost Outpost ( The sequel to Outpost:Haven ) we knew that due to the law of sequels ( "Bigger, Better, More" ) the original code just wasn't going to be able to cope with what we wanted, so a total re-write was needed that would make our aliens appear to be fairly smart whilst not sucking up all the CPU time.

Node Based Pathfinding [ The dirty way ]

We knew that A* wasn't going to work, even with splitting up checks to spread the load, it's really expensive and would hurt other areas of the game.

Swarm mode. It's not going to end well for our hero

Key for us was having as many baddies as possible, so it was time to look at other path finding approaches.

We're lucky in a way that most of our baddies are aliens. They're basically zombies just with a different sprite, so the AI doesn't need to be able to beat us in a game of chess, they just need to appear not totally dumb.

As the levels are laid down in Flash, dropping down and positioning nodes was very straight forward ( The one part of the level building that was, but that's for a different post. A more bitter post ).
I'm trying to keep this fairly generic, but in terms of Flash, we're just placing MovieClips on the stage.

The nodes are the beautifully rendered brown circles

When we create a new level we simply go through each node, get it's x/y postion and store it away.

So we've got a lovely array of Node objects, which so far contain their x/y and nothing else. We then get the very first node and run a distance check to every other one. These are stored and sorted, so that the closest one is at the top of the array and so on.

This then continues for each node. At the end of this every node object knows the distance to every other one in the level ( What we're doing here is basically Dijkstra's algorithm ).
Cool, that's the boring heavy lifting out of the way.

The Actual AI Part

When a baddie is spawned he's basically waiting until the player is close enough to him to bother moving, in an idle state. This is really low cost due to using a very simple state machine, and much less expensive that creating a whole baddie object just in time for it's appearance.

Once the player hits that sweet spot he springs into life, a ton of muscle and armour and teeth and claws, just wanting to get at the player.

Firstly we perform a line of sight test. The levels are a hybrid of "Art Style" and tile based, so for this we just use a simple Bresenham line algorithm as it's nice and quick ( The tile based level data is stored in a bitmap rather than the more usual 2D arrays ). If the baddie has a clear line of sight towards the player then we're all good, just move him towards the player and our work here is done.

The majority of the time though there's a wall in the way, which is where our path finding kicks in.

Every couple of frames ( It's not needed every one, and I'm a huge fan of running things on alternate frames ) the game works out which node is closest to the player, and sorts an array based on that ( So array[0] is the closest ).

When the baddie needs to find a path it calculates which node it's closest to. I don't check all the possible nodes on a level as that's a waste, if it's more than 10 nodes to get the player then the baddie is more than likely well off screen and we can just get him moving in generally the right direction. Now we know the nearest node, and we know that the destination node is always closest to the player ( array[0] ) we just run a simple check to find out a path from the baddies node to the players based on the pre-stored distances. He then walks from node to node until he gets to the end and then he'll start again.

You don't want to be in the dark with one of those things.

As you can see from the grab he's already gone past node 0 ( The one closest to his starting position ) and his working his way down the path.

One glaring thing you'll notice straight away is that he's not following the shortest path. Our path finding is about speed more than the best results. I know some of you as coders will wince at that, but remember the whole zombie / they don't need to be the smartest things in the world anology earlier ?
With this approach we can have flanking with no extra code, think of it as a weakness in the path finder that gives us a free gift. It just works in the context of this game, unpredicatble scary aliens moving around a space station.

As he's following the path we also run the line of sight ( LOS ) test every couple of frames, we don't ever want the baddie to ignore the player because he's so intent on reaching his predetermined goal. Like wise, if the baddie loses LOS to the player for x number of frames he flips over to path finding.

Now as the player is constantly moving we don't want to be looking too far ahead, all we want is a clean LOS, so we're saving cpu time by not checking every node.

And I think that's it. There's more to it of course, but let's not let this turn into just a massive wall of dry text.
Please feel free to ask any questions below, as I know this is just a quick glance into how it all fits together.

Cheers,

Rich "Squize" Myles.

Lost Outpost is currently pending sponsorship and Greenlight approval.
Trailer: http://www.youtube.com/watch?v=t3Hq0mmJ1AI
Greenlight: http://steamcommunity.com/sharedfiles/filedetails/?id=177695239