Search code examples
theorypath-finding

Fast path cache generation for a connected node graph

I'm trying to get a faster pathfinding mechanism in place in a game I'm working on for a connected node graph. The nodes are classed into two types, "Networks" and "Routers."


In this picture, the blue circles represent routers and the grey rectangles networks.

Each network keeps a list of which routers it is connected to, and vice-versa. Routers cannot connect directly to other routers, and networks cannot connect directly to other networks.


Networks list which routers they're connected to



Routers do the same

I need to get an algorithm that will map out a path, measured in the number of networks crossed, for each possible source and destination network excluding paths where the source and destination are the same network. I have one right now, however it is unusably slow, taking about two seconds to map the paths, which becomes incredibly noticeable for all connected players.

The current algorithm is a depth-first brute-force search (It was thrown together in about an hour to just get the path caching working) which returns an array of networks in the order they are traversed, which explains why it's so slow. Are there any algorithms that are more efficient?

As a side note, while these example graphs have four networks, the in-practice graphs have 55 networks and about 20 routers in use. Paths which are not possible also can occur, and as well at any time the network/router graph topography can change, requiring the path cache to be rebuilt.

What approach/algorithm would likely provide the best results for this type of a graph?

Solution

  • 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.