Sign in to follow this  
  • entries
    50
  • comments
    27
  • views
    46140

Quick pathfinding

Sign in to follow this  

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

Sign in to follow this  


4 Comments


Recommended Comments

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.

Share this comment


Link to comment
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 :)

Share this comment


Link to comment
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.

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now