Zombox

Here’s a video which shows the results of the pathfinding system I’ve implemented. Below I roughly outline the process involved:

I haven’t posted any new developments for Zombox in a couple of weeks because I’ve mainly been doing code re-writes, optimizations and other things to get the game running faster on iOS.

One of the main hiccups in development has been the zombie AI. Until this week, zombies “saw” their environment with raycasts. While I was pooling raycasts and not doing 1 per frame per zombie, raycast performance with 30-40 zombies and many colliders on the iOS was slow. Also, while zombies don’t require an overly complex AI system, the previous I-won’t-chase-it-unless-I-see-it method left them unnecessarily dumb. Not to mention, the AI system couldn’t really be scaled up to include NPCs that need to be able to find targets.

So, I implemented an A* pathfinding system for all AI instead. The main hurdles I encountered while working on this system were:

• getting/setting realtime nav data for a large environment that includes many dynamic objects, in realtime on the iPhone
• quickly calculating paths for many zombies in realtime on the iPhone
• having the calculated paths for zombies/NPCs realistically curve around other zombies/NPCs to avoid collisions

Overall, simply getting things to run quickly on the iPhone was the main challenge. My first prototype of the A* system was actually many times slower than the original raycast method I was using, which made me think many hours of work had been wasted.

Eventually, I got things working quite a bit faster, though (the A* method now works 4-5x faster than the raycast method). Here’s what I did:

• There is no actual navmesh generated for the environment, instead I created a spatial grid that subdivides the environment into manageable nodes and store that in an array. If I need to find which node an object is closest to, I just take the object’s position and calculate its relative grid coordinates. Each grid node is a standard size and the grid size itself is equal to the size of the map, so this is very easy to do.
• To keep the number of path calculations per frame down to a minimum, each zombie/NPC only requests a new path when they’ve reached the first target node in the last path they requested. The upside is that this creates a natural pool of path requests, meaning only a couple of path requests will occur per frame which is quite manageable on the iPhone.
• Within the navgrid generation system, each zombie’s position is also set to be a dynamic “hole”. This means that when zombies move around, they’ll update the nav grid accordingly and new paths requested by other zombies will naturally curve around the existing zombies. This makes some really nice flocking motion practically free, in terms of extra computations. For added safety, zombies who see other zombies in front of them (up to a certain distance) will stop, to ensure nobody walks into anybody else. Instead of using a raycast to do this, I implement a fast distance calculation and an angle of deviance calculation to find which zombies are about to be bumped into. A close zombie within 100 degrees of another zombie’s forward vector is considered too close.

Overall, I’m getting close to finishing this backend-optimization iteration of Zombox, and am getting closer to the adding-new-features-and-gameplay-elements side of things. It’s been a challenging ride so far nonetheless!