neoSprockets .. the next generation of engineers and tech professionals ..

To Build A Better Zombie

Sometimes I worry about zombies. Thankfully, I know a little C++.

A while back, some of my weekend code tinkering turned toward a zombie simulation. Written entirely within MATLAB, ZombieSim was mostly based around an old orbital mechanics project — zombies would gravitate toward humans, while humans would gravitate away from zombies and toward other humans. Once a human was “bitten” by a zombie, the human died momentarily and subsequently turned into a zombie himself. As with any great sim, the simplest of rules can sometimes produce the most entertaining results. In ZombieSim, humans would huddle together in corners and scatter as zombies bum-rushed the herd.

Now the purpose of a simulation is to gather cheap analysis of a system without actually building the system. After the initial entertainment value was gone, there really was no valuable analysis to gather from ZombieSim. The models used were simply too immature.

So the classic modeling and simulation question is raised: how do you build a better zombie?

Hunting

The answer requires a brief look at predator-prey relationships. Consider a wolf and a mouse. The wolf, throughout its life, learns to catch the mouse. It develops a gauge for the mouse’s speed, its maneuverability, and its size. And using this gauge, it can adjust its own hunting parameters. It has essentially adapted its hunting ability to catching a mouse.

Now if all the mice were suddenly replaced by a different animal, like a rabbit, with a faster speed, a swifter maneuverability, and a larger size, the wolf would have some initial difficulty catching its prey. Over time though, the wolf would adjust its own hunting parameters from mice-hunting to rabbit-hunting, and the predator-prey battle would continue.

So perhaps to build a better zombie, we need a better human.

Upgrades

For this new and improved ZombieSim, I’m using a neural network (braaaaaainsssss…) optimized by a genetic algorithm. To summarize the concept for those only half-interested, the neural network decides what to do, and the genetic algorithm decides how to do the “what” well. For an easy refresher on GAs, check out my Genetic Algorithms in 400 Words or Less post.

The brunt of the ZombieSim code comes courtesy of Mat Buckland over at A.I. Junkie which is a priceless resource for any newbies interested in neural networks and genetic algorithms. I’m building upon the Mat’s “Smart Sweeper” project, which evolves mine-seeking agents using a NN/GA combo.

ZombieSim 2.0 has two neural networks and two genetic algorithms evolving independently within the same environment. This is known as coevolution. As the zombies figure out how to catch the humans, the humans must figure out how to avoid the zombies. As each party gets better at its respective job, the opposite party must quickly adapt to its competitor’s improvements. This system puts increasing pressure on each agent to improve itself in an increasingly hostile environment. This coevolution concept, popularized by Hillis in his network sorting algorithm, can be a very powerful tool in improving GA effectiveness.

The fitness of a zombie is defined simply as the number of humans eaten within a time frame. The fitness of a human is a scaled summation of the distance to the closest zombie per time step; at each moment, a human gets more points for being farther away from a zombie.

The input into each respective neural network is a normalize vector to the nearest enemy, and a normalized vector of its current heading. The outputs are two thrust parameters that determine the speed and direction of the agent. Both humans and zombies have about the same maximum run speed (I like the modern “fast” zombie over the classic lumbering undead).

Data of the Dead

The evolution of both the humans and zombies is very interesting. Both parties figure out fairly quickly that they need to either run from or chase the other. Humans seem to pick a direction and move as a herd. As zombies attack, humans swerve and momentarily change course before returning to their standard heading. Some species of human learn to stall, spinning in place while zombies aren’t around.

Zombies sometimes learn to run with the human herd and make quick swooping attacks. Some savvy species of zombie run in herds at a conflicting angle to the human herd, easily grabbing humans in the overlapping zone.

In many cases, the results are a see-saw fitness curve, evidence that coevolution is indeed occurring — zombies start out ahead, humans adapt and gain the lead, zombies adapt and gain the lead, and so forth. In other cases, one party quickly jumps ahead and establishes a dominant position in the environment.

Try it out!

The original A.I. Junkie code is free to use, as long as appropriate props are given to Mat. So feel free to play around with my modifications. I’ve included the precompiled executable for those who just want to watch the bloodbath. Hit “F” to switch to a fitness graph, and “R” to reset the sim. You can download ZombieSim 2.0 below:

ZombieSim2.0
[Note: The project file is for Visual C++ Express 2008, which you can get for free.]

Finally, for those truly concerned about a zombie apocalypse, I highly recommend the following books.

Happy breeding!