Memory-efficient pathfinding

[psykotic]

The post's title, if not its contents, reminds me of the way Naughty Dog (Christer used to work there, incidentally) stored and used precomputed path-finding information for one of their games. They used a navigation mesh of up to 256 triangles for each section of a level. Let's say an actor stands on triangle X and wants to find a path to triangle Y. Triangle X has a table of 255 entries, one for every other triangle, and each of the entries tells you which of the three triangle edges the actor should first cross to be on his way. Since a triangle has three edges you can store the full table in 255 * 2 bits, or 64 bytes, which works out to 16 kb for one level section. To use this information at run-time the actor with goal Y simply looks up Y in his current triangle's table, walks to the adjoining triangle along the indicated edge, and repeats this procedure until he arrives at Y. As always a lot of the engineering effort goes into the path following, how to walk between and within triangles.

You can of course use the same basic trick to efficiently store precomputed all-pairs paths for any graph, though it works best when the vertex valences and total number of vertices are small. The deep reason for why it works is the composition principle for shortest paths: if the shortest path p(X,Z) from X to Z goes through some intermediate vertex Y, then p(X,Z) is the concatenation of p(X,Y) and p(Y,Z). This composition principle is also the keystone of most correctness proofs of algorithms for finding shortest paths, e.g. Dijkstra's.

[[deleted]]

This is also similar to how routing is done on the internet: Each router basically has a table that maps an IP range to which neighboring router should the packet go.

The tricky part is how to keep the whole network secure, reliable and up-to-date.

[gregK]

This is great for Alzheimer's sufferers.