Even if you are working on a fantasy map, you can still use Google to navigate it. I don't know the ins and outs of that process, but I know it's been mentioned a few times.

You might also be able to do something with SVG and scripting to dynamically create vector route lines.

jb, are you using a tool that automatically does the inbetweening on an animated gif? The last time I worked with gif in PhotoPaint I had to construct every frame manually, which was just a pain. Of course, I have access to all kinds of animation tools now, so I haven't even wanted to touch PhotoPaint in ages.