[idunning]

Oh for sure, precomputation is essential. Hell, on a 100-1000 node sparse graph you can store all pairs shortest path info in a really small amount of data (like, PC game feasible for sure). For a game situation I'd be willing to burn a lot of time to crunch down pathing times, but memory pressure is real - so there is a "pareto"/nondominated set of algorithms that explore the tradeoff between memory consumption and run time, and the question is not whether you are 100x faster than another algorithm, but whether you are improving that "efficient frontier" of algorithms by using the same memory as another algorithm but running faster, or running as fast as another but using less memory.