August 16th, 2009, 06:57 AM
Help required in path finding algorithm
Following is my problem:
Given is a matrix with a label for each vertex saying it is a "danger spot" or a "safe spot".
Also the starting and destination vertex are provided at run time.
I need to figure out the quickest route possible with this given input.
Any suggestions as to which algorithm I should use?
August 16th, 2009, 06:54 PM
Dijkstra's algorithm would do it. (It's a general-purpose algorithm for finding the shortest paths between a source node and any number of other nodes.) Edit: Not. Use A* instead.
Last edited by Lux Perpetua; August 19th, 2009 at 01:15 PM.
August 17th, 2009, 12:07 AM
I know Dijkstra's would do it. But is it the fastest as well?
August 17th, 2009, 10:18 PM
Nice little discussion about it here
Three Fastest Shortest Path Algorithms on Real Road Networks: Data Structures and Procedures
August 17th, 2009, 10:29 PM
Dijkstra's algorithm is proven to have a minimal O() value. You can't get faster than that. But any big-OH calculation has some constants, and they dominate for small values of "n"
Originally Posted by eknathiyer
Or in this case, any shortest path algorithm's performance is controlled by the number of nodes (n) and edges (e) connecting the nodes.
In practical purposes, dijkstra's algorithm is fine, just use it. If you find you have huge differences in numbers n,e, then you can look. But in nearly all real world implementations, other parts of the application are the slow part. i.e. shadder mapping, AI, etc
August 17th, 2009, 10:35 PM
A good article I might recommend: http://theory.stanford.edu/~amitp/GameProgramming/
Talks about Best-first search, Dijsktra's algorithm, and a* (which is basically a combination of BFS and Dijsktra's algorithm, ideal for video games as it allows you to balance speed and accuracy of your pathfinding.)
August 18th, 2009, 02:31 AM
I am really sorry. The problem at hand has been gravely misunderstood by me. I will restate to make it clearer.
There is a 5x5 matrix where the 0,0 position is the starting point.
The end point can be anywhere within the matrix
Each vertex on the matrix can be either of the following types:
(1) Safe Spot: this point MUST be included in the traversal
(2) Danger Spot: the point MUST NOT be included in the traversal
(3) Neutral Spot: the point MAY or MAY NOT be included in the traversal.
Now with the problem statement very explicit, can you people please help me.
August 18th, 2009, 09:41 PM
Read the article I have posted. The entire article mostly talks about 2D grids with tiles of different "costs".
The most basic pathfinding would be a "brute force" method. In which you have a very inefficient loop (or possibly recursive function) that tests every possible valid path to get from node A to node B on your 2D grid. After trying enough different valid sequences the brute force method WILL find a path if one exists. Think of it like rearranging the word such as mississippi to be a different word (using the same letters), using brute force and simply putting the letters in every possible unique combination, you may be able to create a different word (find a path) using the letters (nodes) given to you, or you may not be able to create a different word. If efficiency is not a concern, then go ahead and do a brute force loop that tries rerranging the nodes into every pattern possible.
After brute force would become what is called "Best First Search". Rather than testing every combination of nodes and checking whether it is a valid path or not. BFS uses something called a "heuristic function" (which would be a different algorithm in every application). A node's heuristic is an ESTIMATE of how close the node is to the goal. Higher the heuristic value, the closer to the goal the node is. BFS is usually more effecient (as in how many cycles it takes to generate the path), however the path itself may involve taking the "scenic route" to get to the goal, because the heuristic only provides an ESTIMATE.
Dijkstra's algorithm is the opposite, it potentially requires more resources to find the path (but still more effecient than brute forcing), This function will ALWAYS finds the shortest path to the goal.
A* combines the best BFS and Dijkstra's algorithm. Most games use A* (a star). The jist of A* is that it uses Dijkstra's algorithm when the game is running fine. This allows for the best paths. However if you have 1,000 zombies on the screen that all need to find paths. Then the resource cost of Dikstra's algorithm could cause the game to come to a stand still. Using A* the game could shift to a pathfinding method that is more along the lines of BFS (more efficient searches, but doesn't always provide the best paths).
There are other advantages to using A* which you might find in the link I've posted.
Comments on this post
August 19th, 2009, 12:52 AM
@MisterDanny, thanks a lot. I think I can safely narrow down on A star. But the issue is that I am unable to find C/C++ implementation of the A*. Would it be possible for you to post a link for that or am I asking for too much?
August 19th, 2009, 09:01 AM
I don't think there are any "pathfinding" libraries you can just implement into your game. Pathfinding is different for every game. That article will give you enough information to make your own pathfinding code (I think it even has compilable examples).
August 19th, 2009, 10:07 AM
Alright. Thank you very much MisterDanny
August 19th, 2009, 01:14 PM
After further reflection, I think misterdanny is right to recommend A* over Dijkstra's algorithm in this case, since the Manhattan distance gives you a natural heuristic you can use to your advantage. I withdraw my earlier recommendation. However:
I think this changes the problem completely. I don't think any of the algorithms mentioned in this thread will do the job if you are required to visit a certain set of nodes, not simply end up at a particular node. If the number of safe spots is large, finding the absolutely shortest path might actually be a pretty hard problem. You can simplify it by finding, for each safe spot, the shortest route to every other safe spot, and recording the lengths of all these paths. (You can find those paths, say, by A* search.) Having compiled that information, now you're looking at an instance of the travelling salesman problem, which is a hard but well-studied problem. You can decide whether you want to solve it exactly or find an "acceptable" short path that may not be optimal.
Originally Posted by eknathiyer
August 19th, 2009, 02:21 PM
oh god. I was pounding my head over it. That was really helpful.
I was wondering how I am going to satisfy the requirement of traversing through each safe spot.
Thank you very much indeed Lux Perpetua.
I don't suppose I would face any other obstacle regarding this problem.