Board game pathfinding - finding multiple optimal paths

Question

I have a very simple pathfinding task- a board game played on an 8x8 grid, with each square either being passable or not. What I'm looking for is an algorithm which will give me the best n paths to get from some square A to square B (assuming there are any).

I've been looking at A*, but as far as I can see, there's no clear way to extend it to find more than one path.

So, what's critical is that the paths it gives are actually the shortest n paths, that it doesn't miss any. Efficiency is also very important. Could anybody suggest an algorithm that would be appropriate, or point me in the right direction?

Answer 1

Dijkstra's is a good algorithm for most situations like these, but since you're on an 8x8 grid, I'm going to assume that all the distances between each cell are both equal and static. In this case, a BFS (Breadth First Search) should suit you well.

Answer 2

Given the small size of the board a breadth-first exhaustive search is something you should be considering. 8 x 8 means only 64 squares, x8 moves (or 4 if you don't permit diagonals) and the total search is pretty small.

Answer 3

Dijkstra's works well to find the single shortest path. To find the second, third ... nth shortest paths, you'd need to use an extension to Dijksta's algorithm. Once a shortest path from N1, N2, N3 ... Nx is found, clone all of the intermediate nodes on that path to create nodes N2' through Nx-1'. Clone all of the entering edges on the shortest path as well except for (N1,N2') and remove edge (Nx-1,Nx). Relax all the edges into nodes on the cloned path which now represents the second fastest way of getting to the nodes on the shortest path from the previous iteration.

Answer 4

Check out k-shortest paths, an open-source implementation that also includes some references.