Zombie Path Finding: Part 3

Last time I talked about some of the methods I tried that didn’t quite work out. This time I’m going to talk about what I did that finally worked.

Often a problem that is very difficult to solve, can become much easier to solve it you limit the scope of the problem. The more limited the scope, the easier it is to solve. For example, a self aware AI is a very hard problem, an AI that plays games well is an easier problem, an AI that plays a single game well is even easier. The trick is to limit the scope, without making the realm in which the solution operates uninteresting.


So, I decided that it would greatly simplify things, but still keep them interesting, if I changed the rules of how a map is put together. If you look at screen shots I’ve posted in the past, most of them feature a mix of open areas, and tighter areas, but the two mix together freely. So I set it up so that maps can only have two types of areas, open areas, and passageways connecting those open areas. The passageways are only one tile wide. Here’s a good image of a new map.


This breaks the tiles into two types of groups. One group I call edges, the other is called nodes. The edges are bright green in this other image. Barriers are only allowed on tiles in the edge group, which means that if a barricade is put up, the only way around it is through another edge, which means that I don’t have to look at each individual tile and calculate the best path, I can look at the larger groups of tiles instead.

Each node knows how to get a zombie from any tile in the group to any other tile in the group, and knows how to get a zombie to any adjacent tile groups. So there are two levels of path finding going on, the micro level, getting the zombies between individual tiles, can be done once when the level is loaded, or even when the level is built, because it will never change. The macro level, getting the zombies between the nodes and to the goal, needs to be calculated in real time, but because there is a relatively small number of nodes it goes pretty quickly. I only have to process around 22 nodes, rather than around 300 tiles.

Tuesday night I got the zombies to capture buildings again, and the zombies win pretty quickly. So I'll have to tweak them to make them weaker, or the humans tougher, or a little of both. But I'm glad that they are presenting a good challenge now.

Looking at it now the solution seems pretty obvious, but it was kind of a rough journey to get here. It reminds me of something one of my math professors once said. He had shown us how to do a proof, and a student said “Well I can understand it when I see you do it, but I can’t come up with it myself.” The professor replied “Yeah, it’s really easy to watch a strong guy lift weights in the gym, but it’s much harder when you’re the one lifting the weights.” Hopefully next time my mind will be a bit stronger, and I’ll be able to more quickly find these types of solutions. In any case it was a fun problem to solve.

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.

Zombie Path Finding: Part 1

If you’ve been following my blog at all, you’ve probably noticed that it’s been over a month since I posted anything, but there’s been a good reason for that. Remember how I said that I’ve discovered that in game development gameplay balancing is the hard part, and implementation is the easy part? Well, I was wrong; they are both the hard part, probably along with some other hard parts I haven’t discovered yet.

I’ve been working on the path finding for my game, and it’s been a real beast, but I’m happy to say that I believe I’ve come up with a really good solution. I’d like to take you through how it works, and the process I went through to get there.

I realized I needed to do something very different with the path finding when I tried creating a big map. It took so long for the zombies to find the target building that I didn’t even have to do anything to win, just wait, it was pretty boring. So I sat down and came up with several requirements that I needed my path finding algorithms to satisfy:

• The zombies had to be able to find the target building from any spot on the map
• The route had to be able to be recalculated very quickly to route around barricades
• I wanted the route to be non-deterministic, so that all hundred or so zombies wouldn’t follow the exact same route through the maze
• Route calculations for each zombie had to be very quick, since I was going to be routing possibly hundreds of zombies around the map at once

Individually these requirements wouldn’t be too bad, but together they presented a real challenge for me. I spent a lot of time looking at graphs, and trying to figure out clever ways of handling things. Eventually I realized that in most of the maps there were a lot of wide open spaces that narrowed down to choke points, and that if I were to route the zombies between the choke points, then I could save myself a lot of calculations. So I started coming up with different ideas on how to mark those choke points.

As a human, it’s pretty easy to quickly pick out potential choke points, but that’s because we tend to look at the whole map at once, and do parallel processing to figure out which points are important. A computer can only look at one point at a time, so I had to come up with some heuristics, or rules of thumb, that would allow the computer to quickly determine which points would serve as good waypoints on the map.

Next time I’ll talk about some of the methods that I tried that didn’t quite work out, and some of the difficulties of the problem.