Some experiments in pathfinding + AI

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