Gamasutra: The Art & Business of Making Gamesspacer
arrowPress Releases
September 1, 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:


 
Some experiments in pathfinding + AI
by Tyler Glaiel on 10/07/12 08:15:00 pm   Expert Blogs   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.

 

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

InnoGames GmbH
InnoGames GmbH — Hamburg, Germany
[09.01.14]

Software Developer JavaScript (m/f)
InnoGames GmbH
InnoGames GmbH — Hamburg, Germany
[09.01.14]

Backend Developer Marketing / CRM (m/f)
InnoGames GmbH
InnoGames GmbH — Hamburg, Germany
[09.01.14]

Software Developer Flash (m/f)
InnoGames GmbH
InnoGames GmbH — Hamburg, Germany
[09.01.14]

Mobile Developer iOS (m/f)






Comments


k s
profile image
Interesting idea, thanks for posting.

Marwane KA
profile image
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
profile image
Here you go http://www.youtube.com/watch?v=GdLayvHDqsU

Michael Joseph
profile image
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
profile image
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
profile image
Thanks. Im not trying to highlight the limitations I'm trying to understand the limitations and ways of working around them.

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

Krishna israney
profile image
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
profile image
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
profile image
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
profile image
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
profile image
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.

Again, a very interesting read.

Mustafa Hanif
profile image
for the multiple enemy type I guess other maps are not necessary, just add another field to each child after cost, such as "isWater", and put a check to land type enemies that if a tile contains isWater=true, cost += 1000, that way it will always avoid it.

Ricky Horwath
profile image
Hey, I hate to revive an old thread but I simply MUST KNOW! Do you re propagate the entire "pathfinding table" every time the character changes position? Isn't that just horrific on memory? Also, what if the terrain changes, say a wall is added, would you re propagate then?

Ferdinand Joseph Fernandez
profile image
Sounds like Collaborative Diffusion/Potential Fields

Here's a link about Collab Diffusion: http://scalablegamedesign.cs.colorado.edu/wiki/Collaborative_Diff
usion

And here's Potential Fields: http://aigamedev.com/open/tutorials/potential-fields/


Also check out the idea of Influence Maps, which uses this concept to give the AI tactical awareness: http://aigamedev.com/open/tutorial/influence-map-mechanics/


@Ricky: Yup, but remember, all enemies are reusing that set of data so it's not all bad. Also, you don't really need to update it per frame. Something like, say, updating it only 10 times per second may be enough, depending on the situation. The size of the grid also affects computation speed, which is something you'd also want to tweak around.


none
 
Comment: