I understand that in the A* algorithm when taking the next step the step with the next lowest predicted cost should be chosen from the openlist or frontier, but when there is multiple lowest steps all with the same predicted cost is there any preference for which one should be chosen?
I think last on first off could work better, but I'm not sure if there is a better way to select the next move when there are multiple matching costs.
According to A*, all the steps with equal estimated cost (cost from start plus heuristic) are equally worth investigating.
The thing is that, without further heuristic, i's difficult to make the choice; or, rather, it depends on what you want.
In the standard f(x) = g(x) + h(x) case, if you have no other heuristic or information, there are 2 main strategies:
x, hoping that it corresponds to a good track (and it might help for memory locality issues): if it's recent, it means that it only got a relatively minor cost update with respect to the others; x with the smallest h, that is, for which the relative contribution of the know cost is highest with respect to unknown cost (that's what weighted A* aims for).For this second strategy, beside inflating the heuristic, you just need to order your steps/nodes by the pair (f, h) instead of just f. It will however not guarantee that you don't have ties:
*
/ \
| |
\ /
+
In the end, you'll need to choose one, for example the most recent (or just the one that your implementation of priority queue yields).
Note that if you choose x with the most h, you'll get closer to the breadth behavior Amit was referring to.