Thread: A* Pathfinding 'Tied choices'

  1. #1
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472

    Question A* Pathfinding 'Tied choices'

    i have recently been finding out about aStar and have just done some paper work prior to coding,
    i am confused because when two 'tiles' are equally valid moves i have read that it is not necessarily important which one is selected, but from my paper work i saw a much shorter path would have come from picking one than the other, and this in a simple grid.
    The example is attatched if anybody would like to comment, and i have highlighted the tied move in question in yellow. The actual path found is shown by the red circles.
    But in any case, any ideas on treatment of ties would be of interest.

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    I may be mistaken but the idea of A* should be that you continue exploring from any node that currently is the shortest estimated path. That means you'll not always continue from the node that you have currently reached, but may instead expand the nodes that you had traversed earlier.

    So, for a few steps you might explore the lower path but at some point the estimate for the upper yellow square should become better and you'll need to continue the search from there.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Yeah like anon said it dosent matter which one you start with, as at the start of the next step the lowest score will be with the node that was not chosen last time.

  4. #4
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    Yea, i see that now, i was getting tunnel vision and thinking that only the immediate surrounds of the current square were under consideration for the lowest F score, but in fact i see that it is any squares on the open list, (possibly far away from the current position and added earlier in the search), that are under consideration for next lowest square, thus the other tied square found would eventually be called back into consideration if it were really the best path.

  5. #5
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    And lol, please ignore my attatchment now, its pants!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Pathfinding question
    By h3ro in forum General AI Programming
    Replies: 13
    Last Post: 05-15-2008, 10:29 AM
  2. All-angle pathfinding algorithm?
    By TriKri in forum Game Programming
    Replies: 6
    Last Post: 06-20-2007, 07:26 PM
  3. Pathfinding AI? (Not the A* Algorithim)
    By harryP in forum C++ Programming
    Replies: 22
    Last Post: 08-01-2003, 02:32 PM
  4. AI (Pathfinding)
    By jdinger in forum Game Programming
    Replies: 7
    Last Post: 04-16-2003, 10:20 AM
  5. AI (pathfinding) tutorial
    By dirkduck in forum Game Programming
    Replies: 3
    Last Post: 02-09-2002, 12:04 PM