Dawn of the Geeks

A-Star (A*) Implementation in C# is an excellent implementation of A* in C#. It plugged neatly into Bunnies 3.0 which will soon have a sequal “Zombies.” The AI in Bunnies consists of stupid bunnies that just bounce around and multiply and slightly more intelligent enemies that will come at you and shoot at you if they see you. In “Zombies” you can run but you can’t hide. The game will be slow moving but difficult to kill hordes of enemies with limited ammo and various weapons. The A* algorithm is being used by the zombies to always keep them moving towards you no matter where you go.

This isn’t my first use of the A* algorithm and the flaws with it are still there. My first use of A* was for a simulator that had tanks and flying vehicals moving around complex 3D terrain that was created using DEM data (geological survey data of real life locations). One of the test paths took a helicopter over Mount Saint Helens. The helicopter would fly up the side of the mountain at the maximum pitch, fly down into the mountain, fly up out of the mountain and then fly down the side of the mountain to the destination.

The reason it did this is because A* always wants to be close to the final destination which was at the base of the other side of the mountain. So if it got a chance to lower the altitude to be close to the base it did. But that’s obviously not the optimum path. The fix for flying vehicals is to find the farthest point in the list of destinations which can be seen with a simple line of sight check. So from the base of the mountain the helicopter can see the top of the mountain so it heads straight there. From there it can see the other side of the rim so it flies straight there. And from there it can see it’s destination so it flies straight there. A path that was dozens of points is reduced to less than 10.

The technique is basically just doing intelligent post processing on the A* path to cut out unnecessary steps. Land vehicals had limits on the angle of the terrain they were going over. Sometimes A* would come up with tangled paths that didn’t go anywhere. So to fix that I found the farthest point along the A* path that the vehical could see and travel to without violating the steepness rule. That easily cut out knots that A* had created and simplified paths significantly.

Because the Bunnies Engine deals with flat terrain the line of sight algorithm can be used on the zombies to simplify their movement. Once I start putting together an actual tutorial on A* I’ll give visual examples of how post processing helps clean up A*.