Gamasutra: The Art & Business of Making Gamesspacer
arrowPress Releases
October 31, 2014
PR Newswire
View All
View All     Submit Event

If you enjoy reading this site, you might also want to check out these UBM Tech sites:

Baddie AI in Lost Outpost
by Richard Myles on 09/17/13 12:46:00 pm   Featured Blogs

The following blog post, unless otherwise noted, was written by a member of Gamasutra’s community.
The thoughts and opinions expressed are those of the writer and not Gamasutra or its parent company.


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, and it's not looking good for our hero.

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.

Not the most impressive screen grab ever.

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.

He's coming...

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.


Rich "Squize" Myles.


Lost Outpost is currently pending sponsorship and Greenlight approval.

Related Jobs

The Workshop
The Workshop — Marina del Rey, California, United States

InnoGames GmbH
InnoGames GmbH — Hamburg, Germany

Mobile Developer C++ (m/f)
Activision Publishing
Activision Publishing — Santa Monica, California, United States

Tools Programmer-Central Team
Amazon — Seattle, Washington, United States

Sr. Software Development Engineer - Game Publishing


Bryson Whiteman
profile image
Thanks for the clear breakdown of how the AI works. I'd like to try something similar to it.

From the image with the nodes, are you laying out those yellow blocks for collision or is the collision generated from a tilemap? What data is the line of sight routine checking against?

Is there a logic to prevent all of the enemies from checking the paths at the same time? Or is the frame-skip checking done at a random interval?

Richard Myles
profile image
Hey mate, thanks for the comment / questions.

For ease of getting the post done I used an old screen grab, where those yellow blocks were used for the tile based collision. Basically we have up to something like 7 different mc's / layers for each level, so we have the background, the walls, tile map, shadows etc. and the game just loops through them getting all it needs.

In terms of the tile map, it's a mc where we just lay down 32x32 blocks by hand ( Thanks snap to grid :) ), then at run time we loop through those and plot them into a small bitmap ( Basically each tile = 1 pixel ). That way we can re-use the same bitmap for the in-game motion tracker and for the LOS stuff ( We just "Draw" a line between two points on this bitmap tile map, if nothing blocks the line then we're good. It's not mega accurate like casting a ray as it's still tile based, but it's "good enough" ).
If you were using a proper tile map editor it would be a two minute job.

There's no check to see if every baddie is hitting the path finder at once, as in theory I think it'll be pretty rare as they're all triggered at different times, and then have simple flip flops like counters running in them, e.g.

//do our thing

So say we have 40 baddies running, I think it'd be very rare for even 5 to be hitting the path finder on the same frame. I guess you could queue requests for the path finder simply enough, it was a case of it not needing that extra overhead.

The way we've approached this is very blunt force, it'd never work for say a RTS, but for moving lots of semi-smart objects around where a hint of randomness is a benefit, then it works well. The big speed boost is letting each node pre-calc all the distances so at run time we're not running distance checks, just simple comparisons.

Hope that clarifies things a little, path finding is murder to explain well :)

Speak to you soon mate.

Jeff Fulton
profile image
Really awesome. Thanks, guys! Great work. Happy birthday, Olli!

cyril guichard
profile image
Loved knowing how the AI was handled in that game! Please post more of those! :)

Akeem Adkins
profile image
I love the fact that they decided to change the AI instead of saying "as long as it works, we're fine." i feel like that can sometimes get overlooked in games. This actually game me some tips on how I can approach a personal project. Can't wait to play it!

Emory Myers
profile image
Was there a reason you didn't use the Floyd-Warshall algorithm? I think it would let you store less data, perform faster pathing (indexing into arrays) and get optimal paths. I feel like you could also avoid the calculation where you're determining which node the player/enemy is closest to by precomputing that for every tile.