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.