As luck would have it, i've been doing something very similar (tile-based shortest path finding algorythm based on the A*).

I wrote it in VB, as my C++ isn't too hot, but i'd emagine it could easily be ported.


I first created the A* algorythm as it stood (no modifications - just an implimentation). My Monsters ran the algorythm each time they wanted to move. I found this to be quite CPU intensive - mainly when there was no path).

I decided to create an array, storing a direction to move in, given a source and a destination.

This means that the monster simply looked at it's position, and it's destination, and the array would give a direction to move in (based on the best possible move).

To fill the array i used the A* algorythm over and over again.

This took several minutes on a small (25x25 grid) map. Although i could save the array to a file (and did), it was still too slow.

I then decided to refine the algorythm.

I decided to calculate all the distances from the destination (for each node). Then to get a direction from a source, it's simply the direction of a node near it (with a link to it), with the shortest distance.

At present, my AI module is a bit cluttered. (failed attempts etc), but i'll try to sort it out if you like (add more comments etc).