Context
Old Lucas Arts (ScummVM era) point and click graphic adventure games used precomputed pathfinding. Here's a rough outline of the technique.
Step 1
The floor in each room was divided into what they called "walk boxes", which were pretty much equivalent to nodes in a navigation mesh, but limited to trapezoid shapes. E.g:
______ _____ _________ _____
\ A | B | C | D \
\_____| | |_______\
|_____| |
|_________|
Step 2
An offline algorithm (e.g. Dijkstra or A*) would calculate the shortest path between each and every pair of nodes, and store the first step of the path in a 2D matrix, indexed in each dimension by the starting and ending node used. E.g. using the walk boxes above:
___ ___ ___ ___
| A | B | C | D | <- Start Node
___|___|___|___|___|
| A | A | A | B | C | ---
|___|___|___|___|___| |
| B | B | B | B | C | |
|___|___|___|___|___| |-- Next node in shortest path
| C | B | C | C | C | | from Start to End
|___|___|___|___|___| |
| D | B | C | D | D | ---
|___|___|___|___|___|
^
|
End Node
As you may guess, the memory requirements increase quickly as the number of nodes increase (N^2). Since a short would usually be large enough to store each entry in the matrix, with a complex map of 300 nodes that would result in storing an extra:
300^2 * sizeof(short) = 176 kilobytes
Step 3
On the other hand, calculating the shortest path between two nodes was extremely fast and trivial, just a series of lookups into the matrix. Something like:
// Find shortest path from Start to End
Path = {Start}
Current = Start
WHILE Current != End
Current = LookUp[Current, End]
Path.Add(Current)
ENDWHILE
Applying this simple algorithm to find the shortest path from C to A returns:
1) Path = { C }, Current = C
2) Path = { C, B }, Current = B
3) Path = { C, B, A }, Current = A, Exit
Question
I'm suspecting that with today's powerful hardware, coupled with the memory requirements of doing this for every level, any benefits this technique once had are now outweighted by simply performing an A* at runtime.
I've also heard that nowadays memory lookups might even be slower than general computation, which is why creating sine and cosine look up tables is not as popular anymore.
But I must admit I'm not yet too knowledgeable on these matters of low-level hardware efficiency though, so I'm taking this chance to ask the opinion of those more familiar with the subject.
On my engine I also needed the ability to dynamically add and remove nodes to the graph at runtime (see this) so the precomputed route only made things more complicated, so I scrapped it (not to mention my runtime A* solution was already running perfectly). Still, I was left wondering...
Bottom line, is this technique still relevant nowadays in any scenario?
