Dijkstra's Algorithm vs A-star - Java-Games

This is a discussion on Dijkstra's Algorithm vs A-star - Java-Games ; Hi! Anyone here has some experience with Dijkstra's Algorithm? How does it compare to a-star? Is it worth implementing? Thanks! Eric Fortier http://www.tlnewsreader.com...

+ Reply to Thread
Results 1 to 5 of 5

Dijkstra's Algorithm vs A-star

  1. Default Dijkstra's Algorithm vs A-star

    Hi!

    Anyone here has some experience with Dijkstra's Algorithm?

    How does it compare to a-star? Is it worth implementing?

    Thanks!

    Eric Fortier
    http://www.tlnewsreader.com




  2. Default Re: Dijkstra's Algorithm vs A-star

    Eric Fortier wrote:
    > Hi!
    >
    > Anyone here has some experience with Dijkstra's Algorithm?
    >
    > How does it compare to a-star? Is it worth implementing?


    It really depends on your problem. Dijkstra can be view like a A*
    without estimated costs to your goal, so if you have implemented A*
    already, you get Dijkstra for free by changing your estimation function.
    Dijkstra will find a best solution too, but usually perform worse.
    Dijkstra is best used, where you can not (or not easily) estimate the
    costs to your search goal.

    hth
    Torsten


  3. Default Re: Dijkstra's algorithm vs a-star


    > It really depends on your problem. Dijkstra can be view like a A*
    > without estimated costs to your goal, so if you have implemented A*
    > already, you get Dijkstra for free by changing your estimation function.
    > Dijkstra will find a best solution too, but usually perform worse.
    > Dijkstra is best used, where you can not (or not easily) estimate the
    > costs to your search goal.


    Thanks for your reply, Torsten.

    Since costs are important to me, I'll stick with my A*.

    Eric Fortier
    http://www.tlnewsreader.com


  4. Default Re: Dijkstra's Algorithm vs A-star


    Hello,

    Are you working with nodes or tiles? As far as I know, one is suitable
    for one thing and the other for the other thing. A* tends to be used
    in games that use grids for their entities (tiles), Dijkstra's not used
    very much, but from the description I read some time ago, it seemed to
    be more node oriented, where you have linked nodes at various
    positions...I actually came up with my own algorithm, and I believe
    it's just an OO implementation of Dijkstra's, but I could be wrong.
    Either way, there's the URL:

    http://www.geocities.com/bpj1138/shortest_path.html

    --Bart


  5. Default Re: Dijkstra's Algorithm vs A-star

    In article <1120662598.706167.194540@g44g2000cwa.googlegroups.com>,
    bpj1138@yahoo.com says...

    > Are you working with nodes or tiles? As far as I know, one is suitable
    > for one thing and the other for the other thing. A* tends to be used
    > in games that use grids for their entities (tiles), Dijkstra's not used
    > very much, but from the description I read some time ago, it seemed to
    > be more node oriented, where you have linked nodes at various
    > positions...


    It doesn't make any difference which you have. Tiles are nothing more
    than nodes for which the links and positions are easy to calculate from
    a grid definition. The only things that matter are how many nodes
    there are and whether you have a good heuristic for distance /
    direction to the target, however that is defined.

    A* is good when there are a lot of nodes and you have a good heuristic.
    If there is no good heuristic, A* has little benefit and Dijkstra at
    least saves some overhead. And if there are only a small number of
    nodes there seems little benefit in implermenting A*.

    Strategy games with tiles do tend to have a lot of them, and they
    generally represent a map with an easily determined distance heuristic
    which might be a reason for using A* more often in such cases. But
    it's not down to the tiles per se.

    - Gerry Quinn


    > I actually came up with my own algorithm, and I believe
    > it's just an OO implementation of Dijkstra's, but I could be wrong.
    > Either way, there's the URL:
    >
    > http://www.geocities.com/bpj1138/shortest_path.html


+ Reply to Thread

Similar Threads

  1. Dijkstra's Algorithm
    By Application Development in forum basic.visual
    Replies: 1
    Last Post: 08-13-2007, 05:41 PM
  2. Fibonacci heap and Dijkstra's algorithm
    By Application Development in forum Theory
    Replies: 13
    Last Post: 05-07-2007, 04:15 PM
  3. Dijkstra's Shortest Path & Breadth-first Search
    By Application Development in forum Theory
    Replies: 9
    Last Post: 11-12-2006, 09:47 PM
  4. Replies: 0
    Last Post: 04-25-2004, 01:02 PM
  5. Dijkstra's Algorithm
    By Application Development in forum Java-Games
    Replies: 15
    Last Post: 11-11-2003, 04:22 AM