i was working on something like this once when i was tinkering with a 2d rpg. It was going to be like ultima - monsters on map. I had a second array with terrain movement plotted out ahead of time. If i can find my old work, i'll tell you more. I just seem to remember that it was 4x the size of the terrain grid. And i was able to do this by breaking the large area into manageable smaller ones. It did screen switching like the first zelda. However that can be applied to huge maps as well because you most likely won't have the entire map in memory at once. I mainly plotted it all out ahead of time so monsters could chase me based on my destination square and possibly intercept me. There was only one path calculation this way instead of one for each creature on the screen.