The path found by findPath can vary from run to run, probably due to nodesAdjacent returning a Set rather than a NSOrderedSet.

[jackpal]

I used A-Star to write a "Hitman Go" level solver:

https://jackpal.github.io/2022/04/29/A_Solver_for_Hitman_Go_Levels.html

A-Star worked well for me. Thanks for providing it!

However, I ran into an issue when writing unit tests: For many game levels, the path returned by findPath varies from run to run of the test. For example a diagonal path on a 2D grid might return North, East on one run, and East, North on the next run.

After thinking about it, I think the reason for this variation is that the GraphNode nodesAdjacent func returns a Set rather than a NSOrderedSet. Set doesn't guarantee an iteration order for its elements. So I think even though my app always inserts nodes into the set the same order, when A-Star iterates over the set of elements, it will iterate over them in random order.

It would be better (in terms of being able to reproduce results) if GraphNode nodesAdjacent either returned a NSOrderedSet, or even just a plain Array.

(I think I can work around the issue by slightly biasing my edge weights in a checkerboard pattern, but it seems like the problem will hit other users too, so you might want to fix it.)