This page: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#S1 provides an example of breaking ties with an A* algorithm. Unfortunately, I don't fully understand it. I'm just learning pathfinding so forgive me if this is obvious, but anyway, the page explains: The tie breaker needs to be deterministic with respect to the vertex (i.e., it can't just be a random number), and it needs to make the f values differ. Since A* sorts by f value, making them different means only one of the "equivalent" f values will be explored. One way to break ties is to nudge the scale of h slightly. If we scale it downwards, then f will increase as we move towards the goal. Unfortunately, this means that A* will prefer to expand vertices close to the starting point instead of vertices close to the goal. We can instead scale h upwards slightly (even by 0.1%). A* will prefer to expand vertices close to the goal. heuristic *= (1.0 + p) The factor p should be chosen so that p < (minimum cost of taking one step) / (expected maximum path length). Assuming that you don't expect the paths to be more than 1000 steps long, you can choose p = 1/1000. The result of this tie-breaking nudge is that A* explores far less of the map than previously. So this is what I don't understand: if you have a tie, and then multiply it by 1.0 + p where p = some predetermined value, won't you just end up with a new value for each h(n) but still have a tie? Is p supposed to be dynamic or does it stay the same? Does anyone have a different example for the usage of this? Any help is appreciated. My algorithm is actually working but I'd like to make it more efficient with methods such as tie-breaking.

I think a good tie-breaker would be to count the number of times your path deviates. I would think units should be more inclined to take straighter paths.

Quote:

Original post by Tom I think a good tie-breaker would be to count the number of times your path deviates. I would think units should be more inclined to take straighter paths.

Ok I will give this a shot as well, but can you shed any light on their example just in case I want to try that?

That tie breaker is equivalent to sorting the nodes first by f value (g+h) and then by h value. Nodes closer to the goal have a lower h value, so multiplying h by a small amount increases the cost of nodes close to the goal by less than it would a node further from the goal, but that would otherwise have the same estimated total path cost (f value).

I don't think tie breaking has to be deterministic as long as you choose one of the nodes with the lowest f value, but if it is chosen non-deterministically (maybe by picking one of the nodes at random) then the paths found may differ between runs when there is more than one optimal path.

Tie breaking in favor of lower h value is a slight heuristic in itself, in that under some circumstances it will slightly increase the speed of the pathfinding. If the optimal path ends with a series of nodes that have a perfect heuristic, then tie breaking in favor of lower h values will cause the search to expand these nodes one after another. In any other circumstance, either all of the tied nodes would need to eventually be expanded anyway, or the heuristic was inadmissible so the tie breaking strategy finds a non-optimal path. With an inadmissible heuristic the tie breaking can affect the length of the path found.

In the example on that page, the tie breaking strategy makes a huge difference because the search space is a grid with many optimal paths and a perfect heuristic on every space. In more complicated situations, this might not happen so much, or at all. For example, if diagonal moves were allowed, there would be fewer optimal paths than in the case where they are not allowed (mainly because the optimal path would have fewer edges in it).

Quote:

Original post by Tom I think a good tie-breaker would be to count the number of times your path deviates. I would think units should be more inclined to take straighter paths.

On a grid the straighter path has more turns:



But there is a problem: all paths bending the same number of times have the same cost:



The penalty should be proportional to the distance from the ideal line between the endpoints, so that paths that cross it as often and as near the middle as possible are preferred.

What I've done is to make sure that h(n) returns an estimate 1 less than the cost, and then I add 0.01 times the straight line distance from the current node from the direct route. (This is a hex-based system.)

Thanks to everyone who replied. These responses are very helpful.

Quote:

Original post by Vorpyif it is chosen non-deterministically (maybe by picking one of the nodes at random) then the paths found may differ between runs when there is more than one optimal path.

Is that a bad thing though? If the AI randomly chooses from several paths that are nearly the same length it might make the AI seem more realistic and less predictable? Rather than always taking the exact path from A to B every time.

Quote:

Original post by FippyDarkpaw Quote: Original post by Vorpyif it is chosen non-deterministically (maybe by picking one of the nodes at random) then the paths found may differ between runs when there is more than one optimal path. Is that a bad thing though? If the AI randomly chooses from several paths that are nearly the same length it might make the AI seem more realistic and less predictable? Rather than always taking the exact path from A to B every time.

Usually there aren't that many paths that have the optimal cost, and often there is only one such path. The only time there are likely to be several varied paths is in open spaces on grid worlds, and in that case breaking ties using the h value can speed things up slightly.

Quote:

Original post by FippyDarkpaw Quote: Original post by Vorpyif it is chosen non-deterministically (maybe by picking one of the nodes at random) then the paths found may differ between runs when there is more than one optimal path. Is that a bad thing though? If the AI randomly chooses from several paths that are nearly the same length it might make the AI seem more realistic and less predictable? Rather than always taking the exact path from A to B every time.

A pseudorandom choice between steps with an identical or very close estimated distance could significantly randomize enemy behaviour, making AI less predictable and sometimes (with multiple agents) more natural-looking and maybe more effective.
For example, an infantry formation that spreads randomly in open terrain is less vulnerable than one that remains in line and much less likely to jam.