Zombie Path Finding: Part 2

Last time I talked about the requirements I had for my path finding algorithm. Today I’m going to talk about some of the false starts I had, and some of the considerations that makes path finding difficult.

Initially I tried a straight implementation of Dijkstra’s algorithm. Basically how Dijkstra’s works, is that you pick a target point on the map, then move out from that point recording the distance to every point along the way. After you’re done you know how long the shortest path from any point to the target point is. You can use this information to get to the target from any point on the map. From any point, you pick the neighbor that has the smallest distance, and move there, then repeat the process until you reach the target.

It did everything really well, except for the quick recalculations. With a map that is only ten by ten (pretty small) there are a hundred squares, and each time I wanted to recalculate the paths I would have to visit each square and check its distance. This was pretty time consuming. Every time I placed a barricade, or the zombies tore one down, the game would pause for a half second while it recalculated. This was completely unacceptable, especially since I wanted to have maps that were at least twenty by twenty or larger. So I started investigating other path finding methods.

One algorithm that is very popular for path finding is A*, it’s a great algorithm, but not well suited to this situation. Mostly because A* works best to find a path between two points. If I wanted hundreds of zombies running around on the screen I couldn’t afford to run A* for each one, and it’s actually quicker to use Dijkstra’s rather than A* to find the quickest path from every point on the map. So I didn’t bother giving A* a try.

The first alternative I did try was the Ant Colony algorithm. Using this method the zombies would wander the map randomly until they found the target, then they would mark the path they followed, and when other zombies stumbled across the path they would use it. As more zombies followed the path, it got stronger, and even more zombies would follow it. There were two big problems with this though. First, it would take forever on a big map for the zombies to find the target point, once they did you would have every zombie on the map running at you as fast as they could come. But until then they wandered around aimlessly, and it was pretty boring. The other problem was that if they did manage to find a path, and you cut it off with a barricade, they would have a hard time routing around the barricade. It all became very noticeable on larger maps.

I tried another idea where I had the zombies do a breadth first search. Basically I marked the tiles that hadn’t been explored yet as the most interesting. The zombies would move in the direction that was most interesting to them. Tiles that were farther away from explored tiles would be less interesting, so the zombies would naturally spread out and explore. The most interesting tile was the target tile, so when the zombies found that one they would tend to move towards it above all the others. This did a good job of getting the zombies to spread out and search, but similar to the ant colony method, they took a long time to find the target tile.

I decided to give Dijkstra’s another try, but decided to see if I could find ways to reduce the number of calculations that had to be done. I figured it might be a good idea to break the map up into groups of tiles, then navigate between the groups of tiles rather than between the tiles themselves. That’s where I got into trying to calculate choke points, because a choke point would make a logical place to end one group of tiles, and start a new one.

So I started looking at ways to find chokepoints. I wrote some routines to go over the map and mark the tiles different colors based on how good it thought they were as candidates for chokepoints. The brighter the green, the more likely that the tile would make a good chokepoint.


None of them really gave very good results, although they were kind of interesting. This image shows the rankings based on which tiles have neighbors that are farther away from the target point. The idea was that if a tile has a lot of neighbors that are farther away, then more zombies will go through that tile on their way to the target.

This image shows the tiles that have a small number of neighbors. I thought that if a tile had a lot of neighbors, then it wasn’t as important because zombies would have more options when moving through the area, and could use one of the tile’s neighbors.


This image shows the tiles that have more options of where to go than their neighbors. This one seemed to have promise, since most of the tiles I would pick as chokepoints were also highlighted by this method. But it also highlighted a lot of extra tiles that weren’t important.


The last method I tried was to see how removing a given tile affected the distance of all of the other tiles. For each tile on the map I would remove the tile, then recalculate all of the distances, and check the new average distance against the old average distance. The greater the difference, the brighter the green. I figured that if a tile increased the average distance by a lot, then a lot of paths must pass through it, which would make it a good chokepoint. Unfortunately, while almost all of the tiles it picked out could be considered important, there were a lot of others that were important that didn’t get picked out.

I tried several other methods besides these to figure out which tiles were the important ones, but I finally decided that I needed a better approach, I needed to narrow the scope of the problem. So I found a way to greatly simplify the problem that I was trying to solve, but still keep things interesting. I’ll talk about that next time.