# AStar Tie Breaker Problem

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

## 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 on other sites
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 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 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 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).

1. 1
2. 2
3. 3
Rutin
22
4. 4
5. 5
khawk
14

• 9
• 11
• 11
• 23
• 10
• ### Forum Statistics

• Total Topics
633652
• Total Posts
3013137
×