Jump to content
  • Advertisement
Sign in to follow this  

Pathfinding Algorithms

This topic is 4522 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm trying to understand the fundamental differences between various pathfinding techniques. Ive studied in college Dijkstra's algorithm and Prim-Jarnik and Kruskal's algorithms for minimum spanning trees which can be used to find intelligent paths. Recently I found the A* algorithm which uses heuristics. Can someone explain to me in terms of performance and memory usage what how these methods differ, and what strengths each one brings ?

Share this post


Link to post
Share on other sites
Advertisement
The first three you mentioned compute the optimal values for the entire system, and require a lot of time for dense graphs. A* is greedy and may not find optimal values quickly.

All three (Dijkstra's Algorithm, Prim-Jarnik Algorithm and Kruskal's Algorithm) require a lot of time since they are interested in finding the minimal (optimal) solution. They don't require much space, although optimized impementations do need a little bit more. Since they find the optimal solution, they can't be pruned very well and have a very bad worst case. Sparse connectivity graphs can be optimized ... but if you know a map has sparse connectivity, you might consider precomputing it for all nodes.

A* requires a lot of space for large graphs. There are many variants and improvements that have been researched for A*. Due to the greedy nature, you can often discard many answers, requiring less space. Constrained versions don't always find the optimal solution, and (in contrived situations) can select a horrible path. If you don't constrain it or prune it, it can eventually come up with the optimal path. For many games with dense connectivity graphs, it can come up with the optimal or near-optimal path very quickly.

Games generally want 'good enough' and not necessarily optimal. A* will let you do that. Since it is greedy-first, A* can find good paths pretty fast. Another benefit is that if you have a lot of processor time left you can keep looking for better paths after finding a good greedy path.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Prim's and Kruskal's algorithms for finding the minimal spanning tree don't even find the optimal paths.

Share this post


Link to post
Share on other sites
Heuristics are the real win. With good heuristics you can get a huge performance boost. The best case is a "heuristic" that knows the exact distance between all pairs, in this case you only need to visit the vertices on the shortest path once (to get the actual path).

Dijkstra examines every vertex that is closer to the start than the target vertex. That can easily be a factor of 1000 or more in terms of visited vertices on reasonably sized graphs (which results in similar factors in performance and memory usage).

A good paper on this topic is: Computing the Shortest Path: A* Search Meets Graph Theory (the paper uses preprocessing on the graph to obtain a heuristic that is way better than euclidean distances)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!