How do I make sprites do straight line pathfinding or reuse?

Take the situation of a dynamically generated map that is static once rendered:

How can I make construct sprite move in a step engine fashion? (think games like FF1-6 where there is no diagnal movement on the grid)

Is there anyway to store and reuse the path inform so the sprite can return to it's original position w/o recalculating?

This is assuming not creating a waypoint system, but even with straight lines sprites will sometimes do this curvey thing while getting there.

Sorry, I have to bump this incase there's a better solution than what I'm going to do.

Just a small static map with maybe 50 or so non solid tiles, but I'd like them to walk in a straight line.

If no ideas are given, I'm going to implement a waypoint system instead.