AndreMichelle - that sounds perfect. I'll have a look through that now.
Just an initial thought though - what happens if it runs out of time for the calculation - does it completely abandon the path, or does it return the most promising path it had found so far?

Tonypa - I went through the GamaSutra link, and also found some other pathfinding articles, so that's a great help