Some experiments in pathfinding + AI
Printer-Friendly Version
April 23, 2014
Press Releases
April 23, 2014
PR Newswire
View All

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

Some experiments in pathfinding + AI
by Tyler Glaiel on 10/07/12 08:15:00 pm

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.

Hey there, Tyler here. Having recently completed my first commercial game (Closure), I've been sorta at a loss as to... what do I do next? After a few months of thinking and well, playing games more often than I probably should be doing, I've come up with a concept that I really like and have started prototyping. That's not the important part of this article though. I'm not gonna reveal core details of the game yet, it's way too early, but it IS a perfect chance for me to apply an AI thing I've been experimenting with for a few years now.

I stumbled across this paper a few years ago, which talks about pathfinding and AI using "diffusion" and "scent" as a core part of it. I was very curious about all the emergent behaviors the paper described in regards to pathfinding stuff, but the actual paper was a bit over my head at the time, but I took the time to dig through it and pull out the few concepts regarding AI and pathfinding that led to the emergent behaviors described in that paper, while avoiding all the talk about "diffusion" and the math involved in that.

A bit of background first, to follow this article you'll need a basic understanding of pathfinding. Just the most naieve pathfinding algorithm you know (which is Dijkstra's algorithm). If you don't understand it, picture it as a flood-fill. You start at one grid space and throw all its untouched neighbors onto a queue, repeat with those points and mark them as touched (in the order they were added to the queue). You keep track of which points added which to the queue, and when you find your target, just trace the path backwards from it, and you have your shortest path.

Now, the first core point from that paper is, you need to flip the way you think about pathfinding. By this I mean, store the pathfinding data as its own thing, rather than having each entity run its own pathfind() algorithm to determine which way to go. Here's a simple visualization of what I mean

Pathfinding data is flood-filled throughout the map, starting from the player (and represented by color in this screenshot). This algoritm is SLOWER than running pathfinding normally, because you don't cut it off ever since the goal here isn't to find a "shortest path". But you only need to do it once, not once per enemy. Each tile has a value, which starts at 0 for the tile the player is over, and each newly added tile has its value increased by one (current tile value + 1), so in essence, every tile's value is how many tiles away from the player it is.

This is basically a lookup table for pathfinding. Rather than running an expensive pathfinding operation to find out which way to go for an enemy to reach the player, you simply look up the pathfinding table. If you're over tile 3,4 you just look up the value of that tile,find whichever neighboring tile is closer to the player, and GO THAT WAY. Its simple, and fast, and lets you have a metric shit-ton of enemies pathfinding at any given time without any performance problems.

(In this sample the enemies pick a random position within the tile they want to move towards as their target, to give some variation to the paths they take)

Another thing you might read about when learning pathfinding is giving tiles a COST to path through. Like, maybe going over a river or through mud costs 4 while going over road costs 1. This is a simple change. From before, where you set (current tile value + 1) in the pathfinding algorithm, you change it to (current tile value + current tile cost). You NEED to use a priority queue now as your container, since pulling out tiles in the order they were added is not correct when the costs vary. You want to always pull the tile with the lowest cost out of the available options, and this is what a priority queue is for. You can look up more details on how this works in almost any pathfinding tutorial that covers A*.

This brings me to the second point from that original paper, which is that enemies should have an effect on the pathfinding. Let's do this by using enemies to increase the cost of passing through a tile. My choice here is, each enemy increases the cost of the tile it's over by 1. You can fit ~4 enemies on one tile, which means if a tile is "full", the CHEAPER path is going around it, rather than through it. Look at this diagram for a sample

The green path is longer, but has less cost cause it doesn't need to move through that crowd of enemies. You now get emergent behavior from the AI, since they'll spread out and do a much better job of "surrounding" the player, without ever having to code that in as a specific case. You can see it here, look how fast the gradient changes in the "crowded hallway".

And here's another one, where enemies are so crowded trying to get through a hallway that ones on the outer edge decide to leave and go flank instead, despite that path being a lot longer

Another VERY APPEALING aspect of this, is that in large open areas, enemies don't just face you and walk directly towards you, they tend to spread out a bit while still trying to get close to you, which makes for a far more interesting behavior than simply walking directly towards the player, or even walking directly towards the player with a little randomness. This just feels.... good. They feel like they have some sort of independence to them, the AI seems intelligent when its actually STUPIDER than most AIs.

I love technical stuff like this. Its fun, games are a melding of technology and art, and I love figuring out ways to apply cool technology like this to game stuff. Its where most of my game ideas come from. Its where Closure's idea came from (experimenting with lighting), and it seems to be forming the backbone of this new game too. I'm glad I decided to jump into prototyping this stuff before working on the thing that makes the game SPECIAL (which will remain a secret for a while, at least until I have something more resembling an actual game). Why that is will have to wait for another post.

PEACE OUT
- Tyler

bonus video

### Related Jobs

Turbine Inc. — Needham, Massachusetts, United States
[04.23.14]

Director, Analytics Platform Development
Gameloft Toronto — Toronto, Ontario, Canada
[04.23.14]

Technical Artist
Muti Labs — Santa Monica, California, United States
[04.23.14]

Senior Game Engineer
Digital Extremes — London, Ontario, Canada
[04.23.14]

Programmers

 k s
 Interesting idea, thanks for posting.

 Marwane KA
Vid or it didn't happen ;) I'd love to see your prototype in action!

Great tip by the way, I love how simple tweaks to a classic pathfinding algorithm can make a whole IA much more believable.

 Tyler Glaiel

 Michael Joseph
Thanks for the article Tyler.

What about multiple classes of goals for the AI?

Let's say the first class of goal for enemy AI is to seek out and kill human players. A single lookup table should accommodate arbitrary human players. But now let's say there are health packs laying around too and when an AI's health is low it should try to take a route that will take it to a health pack. Do we need a seperate lookup table for AIs to use when their basic class of goal changes? (eg kill player vs heal up). And if so, the number of seperate tables needed when many different classes of goals are required for thet AI to seek depending on their state (find cover, find ammo, find a better weapon, etc, etc, etc) could be relatively high and if the world maps are large enough might this take up exhorbitant amounts of memory? Or am I completely misunderstanding something?

And I'm not necessarily even speaking about a sprawling FPS or MMO I'm thinking of a large tile based RPG like Fallout 2 or Fallout Tactics.

 Tyler Glaiel
 You can seed multiple targets into the initial pathfinding queue, they'll find the closest one. You can vary their initial weights too to give stuff priority. Its not the same as seeking out specific targers, but I'd rather focus on what CAN I do with this pathfinding stuff, rather than what CAN'T it do. Like, design around the technology, rather than going towards some goal.

 Michael Joseph
 Thanks. Im not trying to highlight the limitations I'm trying to understand the limitations and ways of working around them.

 Guerric Hache
 This is actually very interesting! I remember doing my own implementation of A*, and while it worked well, I never got around to making the AI units path around each other. This system seems more intuitive. I wonder, though, whether it could be adapted to work in situations where the AI agents are looking for arbitrary points on a map, such as in an RTS where the agent might be sent anywhere, or after any other unit. I can't see how it would be, without becoming bloated and unwieldly - in such a case, we'd be better off using A* or similar, correct? Though for games like ARPGs and Tower Defence games, this seems like it would indeed provide a superior solution to the problem. Thanks for introducing me to this approach! I'm definitely favoriting this, as I'm working on an ARPG prototype at the moment.

 Erwan Bancal
 "What about multiple classes of goals for the AI? " Yea I am curious about that too !

 Krishna israney
 One quick way I perceive for having multiple goals is to keep track of multiple such weighted maps (one for player, one for health , etc) and then have AI logic over it to decide between which goals have more priority and perform that task first.

 Lars Doucet
 Wow, this is definitely what I should be doing in my next game (RPG/Tower Defense mashup). There's only ever a single exit point (at most two in super special levels).... so why the heck am I still calculating paths individually??? This would let me get rid of all my icky optimization hacks and let me easily support real-time terrain deformation and path destruction/construction, to boot! Brilliant!

 Mathieu MarquisBolduc
 Seems tech is meant to be forgotten and re-discovered every few decades. It scales badly with the size of the map. But if your map is small and you have the memory to spare, instead of your distance map you can even pre-compute a shortest-path matrix: A matrix that contains at point (A,B) the next node you have to go through in order to reach node B from node A. Then you can pathfind From and To anywhere in your map for "free", and you dont even need to refresh it if the player moves, but only if the levels changes.

 Andy Wallace
 Really cool. Do you have any examples of code or pseudo-code for the pathfinding that avoids other enemies? I am curious as to how it can be done quickly as the enemies continue to move and change the values of the tiles. Even if not, this gives me a lot of fun techniques to play with. Thanks!

 Kyle Jansen
Very interesting, and it even offers some interesting abilities.

For instance, say you add a sniper or archer enemy type. You can have them seek out a point where distanceFromPlayer == 20 instead of distanceFromPlayer == 0, and get enemies that keep their distance at essentially no cost, reusing all but one line of code.

And multiple players might be simple, as others have mentioned. Simply have the pathfinding flood stop when it hits any player, rather than "the" player. This could give a very interesting, especially as it never guarantees that players will be attacked equally. One player could very well get swarmed (although having the enemies count as a slight obstacle should limit the number swarming any one, at some point).

You could even handle multiple enemy movement types straightforwardly, although not for free - just repeat the pathmap build for each class. So if you have, say, amphibious enemies that can go through water, they have their own pathfinding map, separate from those who cannot swim.