Jump to content
  • Advertisement
Sign in to follow this  
lucky6969b

AStar Tie Breaker Problem

This topic is 491 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I generally would give an id to the nodes that are opened to the opened list....

when there is a tie, I compare the ids....

Is it the normal approach to favor nodes that are opened earlier than later nodes.... (nodes with smaller ids)

When should I favor later nodes than earlier nodes? (favor nodes with bigger ids)?

Thanks

Jack

 

Share this post


Link to post
Share on other sites
Advertisement
Why would it matter? Pick one and be done.

If you are growing your open nodes then you'll still be testing the lowest cost first. It doesn't matter which one because most likely both will result in open nodes rather than completing the path. Just test one arbitrarily, whatever happens to be first on the list. If it results in more nodes then add those, otherwise finish the node and go to the next.

For the destination you found multiple routes with an identical lowest cost. Most games don't bother, the moment you've got a path you can be finished, no need to check for a tie.

If equal costs happen frequently in your game and it bothers you, consider adding additional costs to various nodes, perhaps an extra cost for heavily-traveled spaces or something. But otherwise it shouldn't really matter. You will find a path with a low cost based on your heuristic. Path found, move along.

Share this post


Link to post
Share on other sites

I have seen approaches where the node closest to the destination is favored, ie lowest estimate. It attempts to avoid computing equivalent paths that haven't been explored so much. There was a video demonstrating the difference, and that was quite dramatic. However, much depends on the details of movement costs and estimation.

Of course, the path-length is still the same optimum length, you may just get a different random path, assuming you abort on the finding the first match.

Share this post


Link to post
Share on other sites

I have seen approaches where the node closest to the destination is favored, ie lowest estimate.

That should always happen in the A* algorithm.  In fact, that is the defining feature of A*, the thing that makes it different from Dijkstra's pairwise shortest path algorithm.

A* should always work first from the one with the lowest heuristic value, meaning the one with the lowest cost that is nearest the destination.

The typical implementation of Dijkstra's algorithm -- of which A* is a specialization -- uses a priority queue with the lowest cost nodes evaluated first.  A* speeds up the algorithm by adding the shortest distance to the priority queue's preference, favoring the shortest path that is also nearest the destination.  A heuristic function that doesn't include the distance is just the plain original Dijkstra's shortest pairwise path algorithm.

Share this post


Link to post
Share on other sites

A* should always work first from the one with the lowest heuristic value, meaning the one with the lowest cost that is nearest the destination.
total cost in A* is real traveled cost + estimate cost for remaining path.

I was saying to use estimate cost as tie-breaker between paths with equal total costs (ie favor lower estimates in case of equal total cost, so you generally pick paths that are closer to the destination).

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!