(continues from page 1)

ARTIFICIAL INTELLIGENCE

In DickDynamite we have basically two different algorithms for the AI of the bad guys: one is "step-based" and the other is "path-based". Let me explain this a little bit better.

In order to make the enemies search Dick through the labirinth it is possible to calculate the next move of the sprite by just comparing it's position to the one of the hero and then taking the appropriate move (if the way is free).
This was our first approach to the problem and it is the type of AI that drives the most dumb of the enemy: The Blob.

Although this algorithm is not very complex and doesn't need too many cpu resources, it has some side-effects:
since the next move is calculated upon some "suppositions" based on the target position, this doesn't guarantee that you are really going in towards the hero. Maybe after 5 or 6 steps you'll come across a dead end.

Pic 2: the Blob uses a simple
algortithm to track Dick.

This can happen because just one step towards the target is calculated at every game cycle.

A better solution is to calculate the whole path to the target, and possibly the shortest one !
This is done using more complex algorithms (A* seems to be the most popular) that analyzes the entire map and constructs the right path between the enemy and the hero. (A series of articles will be published on this argument, stay tuned)

This kind of approach is the one we used to create the AI of the "Bouncer" and the "Hunter".
This part of the developement took us more time than what we expected: at first I wrote a simplified version of the A* (pronounced "A star") pathfind algorithm as a separate movieClip, just as a prototype.
Everything seemed to be ok, but once we implemented this in the game it was simply unusable !

The matter was that all these extra calculations slowed everything down to the point that all the game animations
had some sort of "hiccup" everytime the enemy calculated a new path.

So I went back to the prototype and started doing a series of benchmarks and ARRRRRRGHHHHH !!
I found that the average time for calculating a path was between 290 to 600 milliseconds, way toooo slooooow !

After some weeks of researches and experiments, I came up with a better solution, still based the A* algorithm
but much lighter, which allowed us to search a path in about 40-70 milliseconds !
To improve performance and save cpu time we also added a "path caching" system in the game: this optimizes the calculations
by reusing some of the information computed in the previous game cycles.

(continues on page 3)