# Is precomputed pathfinding still relevant?

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]
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?

-
I think it is still relevant if you're on a tight CPU budget. But once you want dynamic paths it's just no longer useful. Btw I looked at where you got your A* algorithm from and you can optimize it even further using a minheap and some other tricks. I've done a few iterations of improving A* in C# which you can see here: roy-t.nl/index.php/2011/09/24/… might be useful. – Roy T. Dec 16 '11 at 23:17
Thanks, I've bookmarked it and will look into it when I start optimizing my application. I pretty much used Eric Lippert's solution with a few minor modifications because it was so clean and easy to follow... And for all of my test cases it ran pretty much "instantly" so I didn't even bother with optimizing it. – David Gouveia Dec 16 '11 at 23:27
BTW if you decide to pursue precomputation, you might want to look at the Floyd-Warshall algorithm. It builds the “next step” matrix more efficiently than repeatedly using Dijkstra/A*. – amitp Dec 20 '11 at 16:51
@amitp Thanks for the tip, it's always good to know about these alternatives! Although, since in most cases precomputation would be done offline, there wouldn't be much to gain from making it more efficient. Unless you're really impatient. :-) – David Gouveia Dec 20 '11 at 17:00
Agreed, although Floyd-Warshall is also much simpler to implement than Dijkstra's algorithm, so if you don't already have Dijkstra's implemented, it's worth a look :) – amitp Feb 8 '12 at 20:25

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?

I can see no benefit from using such a technique.

I lacks the flexibility of a Graph (you can have different LODs, they don't have to be any specific shape, ect...). Also any user of your engine is going to know what a graph is and how to use one. So if they want to add extra functionality their going to have to learn how to implement their extension using a situation completely novel to them.

As you mentioned it looks like it would scale horribly. Also its worth noting that if a graph fits on the cash and you run all of your path findings back to back it really cuts down on the IO time. It looks like you implementation would soon grow too large to fit on any cache.

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.

Unless you can fit all of your program and its need memory in the cache you are going to bottle neck at pulling things in and out of memory way before you bottle neck the processor.

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

Also realize that many games have separate loops for updating the AI. I believe he way my project is set up is that there is an update loop for user input at 60hz, the AI is only 20hz, and the games draws as quickly as possible.

Also as a side note I did some GBA programming just for fun and nothing at all transfers over to using a modern device. For the GBA everything was about minimizing the workload of the processor (because it was pathetic). You also have to realize that most high level languages C# and Java (not so much C++ or C) do tons of optimizations for you. As for optimizing you code their isn't much to do other than access memory as little as possible and when you do run as many computations on it as possible before bringing in new memory that will bump it out of the cache and making sure you are only doing things once.

Edit: Also to answer your title yes it is. Precomputing frequently used paths is an excellent idea and can be done with A* anywhere outside of your game loop. For example from you base to a resource in a RTS so that the gathers don't have to recalculate every time they want leave or return.

-
About your edit, I wasn't really talking about precomputing frequently used paths, but strictly about the technique outlined of precomputing every single possible path. I'm also a bit confused about how most of your answer was against using precomputed pathfinding, but then at the end you said it would be an excelent idea. So, would it be useful on a CPU restricted environment such as the GBA? – David Gouveia Dec 17 '11 at 0:06
My bad I was trying to point out that the answer to your title taken out of context is yes. While the answer relating to the specific algorithm described in your question is no. So in short precomputing all possible path is a bad idea but precomputing a few very frequently used paths can a good idea. – ClassicThunder Dec 17 '11 at 0:38
@ClassicThunder: This technique of pre-computing all paths from a few landmarks is often referred to as ALT: A-star with Landmarks & Triangle-inequality: cs.princeton.edu/courses/archive/spr06/cos423/Handouts/GW05.pdf – Pieter Geerkens Nov 23 '13 at 19:04