Precomputing pathfinding: Which algorithm?

What is very complex? What number of nodes and edges?

Is the resulting mesh gridlike? Then you should take a look at: http://www.avglab.com/andrew/pub/msr-tr-2004-24.ps, it describes a pathfinding algorithm which is very fast on gridlike graphs (20 times faster than A*). Maybe fast enough for pathfinding without precomputation of all paths.

Floyd-Warshall is O(n^3), A* for all pairs is O(n^3) too if implemented without heaps. So which one is faster is implementation dependend.
How are you going to store your precomputed paths?

Very complex as in large and complex scenes, not many almost straight line paths.

As for storage, I will keep it in an hierarchical set of tables, to have a compromise between memory consuptiom and time to resolve the path.

As for the gridlike approach, I'm afraid that I can't use it, as my navigation meshes won't be gridlike at all.

I do not have much detailed information about the mesh itself, though, as the collision meshes from where I construct the navigation meshes are still being done, and I won't have access to that data for a while.

From what I've been seeing it seems like the best option is to go for A* using priority queues, but I still have to do some more research...

Personally, last time I was working with this stuff I based things on Dijkstra's algorithm. Because it's a labelling algorithm, you can use it to generate shortest-path data from a given start node to all other nodes in the network in a single pass (instead of searching for node/node pairs).

However, I've never learnt about things like Floyd-Warshall or Johnson's sparse graphs so it's very likely that I'm just ignorant of better solutions [grin]

Bidirectional dijkstra/A* is another option. There is also a basic description of it in the .ps i linked above...

Straight lines aren't important for the landmark based search, it works on roadmaps too.