• entries
50
27
• views
46670

# Quick pathfinding

453 views

So the following is probably obvious, but I spent a good while coding it, so I'll share it.

Given a graph of nodes that identify possible paths around a map, how could you find the shortest path from node A to B? A* is nice, but a bit slow to be using often, especially if there are a lot of nodes and a lot of entities using them. So, I propose we pre-calculate all the shortest paths through a graph, and store it in a table:

Feel free to poke a hole in my logic. I'm not completely sure it's sound.

- issue: n squared storage. But assume 100 or 150 nodes is enough for my map, that's just 10,20,30 kilobytes.

In case you were unaware of the wheel you were re-inventing [smile]

While I am at risk of re-inventing a wheel, I don't think I re-invented dijkstra's since Dijkstra's algorithm finds the shortest path from one node to all others, where as mine constructs a table from all nodes to all others.

Feel free to debate that though.

Not really re-inventing the wheel as far as pathing algorithms go, but this is one of those old-school optimization tricks that today's programmers don't use but were very common back in the day. Anyways Ysaneya is using this for pathfinding inside space stations in his space game, because it's a MMO and speed is more important than size. Also the number of nodes is pretty low. It's a neat system you've got there :)

Quote:
 Original post by matt_j While I am at risk of re-inventing a wheel, I don't think I re-invented dijkstra's since Dijkstra's algorithm finds the shortest path from one node to all others, where as mine constructs a table from all nodes to all others. Feel free to debate that though.

Well you are trying to find the shortest path between two nodes using your own algorithm, that's why I suggest looking at Dijkstra's algorithm. And, really, that is the only intersting part of the problem. Tabulating the results for all pairs is not really challenging and is likely to present fewer problems.

## Create an account

Register a new account