You might want to look in the classical networking domain. This isn't the exact answer, but should give you a starting point for "better than brute force" algorithms.
jcsf
2010-06-01 05:55:37
A:
+1
A:
Dijkstra's shortest path algorithm is the classic, but is only designed for static graphs.
You can try searching the web for dynamic shortest past algorithms.
Here is one paper which seems relevant: http://www.utdallas.edu/~edsha/papers/bin/Globecom04_SPT.pdf (and might give you other leads).
This paper describes a network of routers, where each router maintains it's own Shortest Path Table. Perhaps you can do something similar.
I suggest you also look at routing algorithms in general as taking the shortest path always might cause congestion etc (I am thinking 16 team Halo!). You might also want to incorporate load balancing etc.
Hope it helps.
Moron
2010-06-02 01:50:14
In the context of the network, traffic levels/etc are not relevant, as it is only a simple high-level simulation. The game is coded in a language compiled to bytecode and then interpreted, so the functions need to be relatively lightweight (And the code that moves pathables from one network to another is about as efficient as it'll get without removing functionality). As long as I can quickly build *any* valid path or quickly determine no such path exists (Or some compromise of the two), I'm happy.
Sukasa
2010-06-02 22:25:04
@Sukasa: You might find splitting your graph into bi-connected components useful, then.
Moron
2010-06-02 23:28:20
@Moron could you perhaps give a bit more info? The wikipedia article on them leaves me a little unsure
Sukasa
2010-06-03 03:01:52
@Sukasa: A bi-connected (or 2-connected) component is a graph where there are at least two disjoint paths between each pair of vertices. So if you split your graph into 2-connected components, and then find the 'edge' networks/routers it might speed up things a little. For instance to get from component A to C, you might have to go through component B, if you know the edge connectors, then you might quickly be able to find a path. It will take at least 2 edge deletions before you (possibly) need to do some remapping. It was just an idea which I thought you might find useful.
Moron
2010-06-03 03:23:24
@Sukasa: Also, you might find the Other Algorithms section of en.wikipedia.org/wiki/Biconnected_component useful, which talks about a dynamic bi-connected components algorithm (by Westbrook and Tarjan).
Moron
2010-06-03 03:27:28