All-pairs shortest paths

from Red Blob Games

Quick & dirty: idea is that given a map, I want to mark how many times each location gets used in all paths from any location to any other location. This might be useful for map analysis, letting the AI find choke points, crossroads, dead ends, etc. Not sure.

Algorithm: find shortest paths from each location i to each location j. Count how many paths go through each location on the board. I have 450 nodes in this grid, so that means 4502 = 202,500 shortest paths have to be calculated, and counters incremented millions of times.

I know, this demo is slow, but I’m using the slower but easier to implement Floyd-Warshall instead of the faster Johnson’s Algorithm, and I haven’t optimized the code. Calculating all those paths on every map change is slow, but in a real game you could (1) use a faster algorithm, or (2) use a subset of points, and/or (3) precompute things ahead of time.

Also you probably don’t want to count all paths equally, but instead weight them by how likely it is that you’d want to go somewhere. So when you find the path from i to j, you increment not by 1, but by how likely something wants to take that path.

Also see[1]

Email me , or tweet @redblobgames, or comment: