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.