I've used something like a "Robust Trace",too (for entities).

So, we will see how effective your A* will be. The Heuristic is one of the most interesting thinks in it! For Terrain-Pathfinding you need it,too. I hope I can develop a good one