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

    Join Date
    Feb 2004
    Location
    San Francisco Bay
    Posts
    1,939
    Rep Power
    1313
    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 02:15 PM.
  4. #3
  5. 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?
  6. #4
  7. /usr/bin/drinking
    Devshed Novice (500 - 999 posts)

    Join Date
    Jul 2004
    Posts
    719
    Rep Power
    1886
    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
  8. #5
  9. Contributing User
    Devshed Frequenter (2500 - 2999 posts)

    Join Date
    Sep 2007
    Location
    outside Washington DC
    Posts
    2,642
    Rep Power
    3700
    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
  10. #6
  11. Null Pointer Exception
    Devshed Loyal (3000 - 3499 posts)

    Join Date
    Mar 2006
    Location
    america
    Posts
    3,355
    Rep Power
    1579
    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.)
  12. #7
  13. 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.
  14. #8
  15. Null Pointer Exception
    Devshed Loyal (3000 - 3499 posts)

    Join Date
    Mar 2006
    Location
    america
    Posts
    3,355
    Rep Power
    1579
    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.
  16. #9
  17. 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?
  18. #10
  19. Null Pointer Exception
    Devshed Loyal (3000 - 3499 posts)

    Join Date
    Mar 2006
    Location
    america
    Posts
    3,355
    Rep Power
    1579
    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).
  20. #11
  21. 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
  22. #12
  23. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Feb 2004
    Location
    San Francisco Bay
    Posts
    1,939
    Rep Power
    1313
    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.
  24. #13
  25. 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.

IMN logo majestic logo threadwatch logo seochat tools logo