webgeek - I was thinking your pre-calculated path idea last night (couldn't sleep...), how do you store the path data?
I've been using a string with absolute directions in (ie. NNNENWS for go north 3 times, then go to the east once etc.) - and there's bound to be a better way!