A few years ago my friend and fellow worker Markus Prossegger and myself had the chance to contribute to an innovative computer game called waterstorm. Waterstorm was forged by a young innovative company named Rarebyte which was founded some years ago by a young team of Telematic/Network Engineering graduates.

The game belongs to the 2D multiplayer shooter genre. It is entirely written in java, They decided to use lwjgl for the game engine and FengGUI for the Graphic User Interfaces.

Our part was to implement the Bot System considering the intelligent bahavior of the bots as well as an automatic path finding, which is Markus’ hobbyhorse. To make it short – if you ever want to know how a navigation system finds the right route, ask Markus, he will explain it to you in detail 🙂

Markus will shoot me 🙂 but in the next few sentences i will try to describe what kind of algorithm we decided to use.

Little change of the master plan, Markus misplaced his gun, so he will explain it to you 🙂 ….

Markus its your turn.

First of all we had to decide, what the overall game behavior of the bots should be. We wanted them to act like a human player: (a) select a target, (b) find the best way to the target, (c) attack it or (d) flee to some power ups in case of low ammo or low health. The task of (a), (c) and (d) is simple: if the bot has enough ammo, than attack the closest enemy (could be another bot as well). If the ammo or the health is low, than select one of the power ups as the target. The task (b) is the more sophisticated part of the Bot System – the bot has to find a shortest path towards the target (the enemy or the power up). There are a lot of well-known shortest path algorithms out there, that will handle the task.

But there are some points that have to be considered: the path must not be predictable by a human player (so simple „follow-the-shortest-path“ won’t work) and the server has a limited capacity (there are a number of bots in the game, so the algorithm has to be designed very resource-conserving).

So we decided to use one of the shortest path algorithms, that uses a heuristics to search the space to efficiently reduce the time needed and to „manipulate“ the outcome of the algorithm: the path. We have picked the IDA* (IDAstar), which is a variant of the A* algorithm and allows to perform a series of independent depth-first searches, each with the cost bound increased by a minimal amount. This leads to two ways, to manipulate the resulting path between the bot and its target. First the estimation value (used in the heuristic search) can be blurred by a random value and second the number of iterations can be limited. Both together leads to an unpredictable path as well as speeding up the time needed for the path calculation.

It’s fun to play against the bots – just try it for free at www.waterstorm-game.com