Any search algorithm that returns perfect paths (as in the guaranteed shortest path) from point a to point b could be used. I just happened to have an implementation of Dijkstra's algorithm from Brandon Hall's book so I used it.

Lots of people have asked about the array so I will try and make it more clear. The basic idea is that you find the path from node a to all other nodes on the map. Then you store the first step of each of those nodes in the array. Then you do the same for node b and so on through all nodes in the map. All of this occurs during the pre-computation step. This is the ONLY place that the "real" searching algorithm is used.

Lets do a real example. If I have a map that is 1x4 tiles and looks like this:

Code:
_________________
|   |   |   |   |
| 1 | 2 | 3 | 4 |
|   |   |   |   |
-----------------

Then the to break down the paths, I could say that:

starting --> destination = next step
1 --> 1 = 1
1 --> 2 = 2
1 --> 3 = 2
1 --> 4 = 2
2 --> 1 = 1
2 --> 2 = 2
2 --> 3 = 3
2 --> 4 = 3
3 --> 1 = 2
3 --> 2 = 2
3 --> 2 = 3
3 --> 4 = 4
4 --> 1 = 3
4 --> 2 = 3
4 --> 3 = 3
4 --> 4 = 4

Now, if you think about it, you could store that in an array in just that format. In fact, thats exactly what you do...

pathArray[start][destination] = nextStep

Then, when you want to do your actual search at runtime, you need only loop over that array and find the next step. You keep repeating that process by replacing the starting point as the next step. Each loop gets you one node closer to your goal until starting and destination are equal. All that make sense? It's really not that complicated, but it's a different way to think about it. Like I said in my first post; I dont get credit for coming up with it I just implemented it in Flash to see how it would do. Thanks!

P.S. The really clever of you out there might have noticed that the engine DOES support one way paths. So from 1 --> 4 = 2, 3, 4 but 4 --> 1 might involve a completely different path.