### Thread: Help required in path finding algorithm

1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Aug 2009
Posts
6
Rep Power
0

#### Help required in path finding algorithm

Hi,

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?
2. No Profile Picture
Contributing User
Devshed Intermediate (1500 - 1999 posts)

Join Date
Feb 2004
Location
San Francisco Bay
Posts
1,939
Rep Power
1317
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.
3. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Aug 2009
Posts
6
Rep Power
0
@Lux,
I know Dijkstra's would do it. But is it the fastest as well?
4. Nice little discussion about it here

Three Fastest Shortest Path Algorithms on Real Road Networks: Data Structures and Procedures
http://publish.uwo.ca/~jmalczew/gida_1/Zhan/Zhan.htm
5. Originally Posted by eknathiyer
I know Dijkstra's would do it. But is it the fastest as well?
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"

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
6. 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.)
7. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Aug 2009
Posts
6
Rep Power
0
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.
8. 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

• Lux Perpetua agrees : I think you're right to recommend A*, but your explanation of it is a bit odd.
9. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Aug 2009
Posts
6
Rep Power
0
@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?
10. 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).
11. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Aug 2009
Posts
6
Rep Power
0
Alright. Thank you very much MisterDanny
12. No Profile Picture
Contributing User
Devshed Intermediate (1500 - 1999 posts)

Join Date
Feb 2004
Location
San Francisco Bay
Posts
1,939
Rep Power
1317
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:
Originally Posted by eknathiyer
(1) Safe Spot: this point MUST be included in the traversal
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.
13. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Aug 2009
Posts
6
Rep Power
0
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.