Astar2D Inconsistent with tie-breaking decision in path traversal

Godot version: 3.2.stable

OS/device including version: Ubuntu 18.04.4 LTS x86_64

Astar2D path finding is not consistent due to the use of OAHashMap. The tie breaker for choosing points that are equivalent in distance from any current point is decided by which was first iterated in the OAHashMap as seen here

I can understand the want for speed with the lookups, but having inconsistent results in pathfinding is not worth the cost in my opinion; I think we should consider adding the option for Astar to use an ordered set, such as the ordered_hash_map if not outright changing the graph to use it.

Quick minimal setup to see the inconsistency.

    var astar = AStar2D.new()
    astar.add_point(1, Vector2(0,0))
    astar.add_point(2, Vector2(0,1))
    astar.add_point(3, Vector2(0,2))
    astar.add_point(4, Vector2(1,0))
    astar.add_point(5, Vector2(1,1))
    astar.add_point(6, Vector2(1,2))
    astar.add_point(7, Vector2(2,0))
    astar.add_point(8, Vector2(2,1))
    astar.add_point(9, Vector2(2,2))

    astar.connect_points(1,2)
    astar.connect_points(2,3)
    astar.connect_points(4,5)
    astar.connect_points(5,6)
    astar.connect_points(7,8)
    astar.connect_points(8,9)
    astar.connect_points(1,4)
    astar.connect_points(4,7)
    astar.connect_points(2,5)
    astar.connect_points(5,8)
    astar.connect_points(3,6)
    astar.connect_points(6,9)

    print(astar.get_point_path(1, 9))
    print(astar.get_point_path(9,1))
    print(astar.get_id_path(1,9))
    print(astar.get_id_path(9,1))

    print(1, astar.get_point_connections(1))
    print(2, astar.get_point_connections(2))
    print(3, astar.get_point_connections(3))
    print(4, astar.get_point_connections(4))
    print(5, astar.get_point_connections(5))
    print(6, astar.get_point_connections(6))
    print(7, astar.get_point_connections(7))
    print(8, astar.get_point_connections(8))
    print(9, astar.get_point_connections(9))

//Printout on my machine is as follows

[(0, 0), (1, 0), (1, 1), (2, 1), (2, 2)]
[(2, 2), (2, 1), (1, 1), (0, 1), (0, 0)]
[1, 4, 5, 8, 9]
[9, 8, 5, 2, 1]
1[4, 2]
2[1, 5, 3]
3[2, 6]
4[5, 1, 7]
5[8, 2, 4, 6]
6[5, 9, 3]
7[8, 4]
8[9, 5, 7]
9[8, 6]

Visualizing this as a number pad, 1 on bottom left, 9 on the top right, 3 on the bottom right.. We get the first big standout result with the path from 9 to 1 breaking the ties at nodes 9 and 5 differently. On 9, it goes to 8 (left node), and on 5 it goes to 2 (bottom node), whereas on the path from 1 to 9, the ties broken are consistent. On 1 to 9, the ties are at 1 (going up to 4), and at 5 (again going up 8).

I'm not sure how much of a reproduction effect this has on say multiplayer games where 2 different clients need to recalculate the same path and ties are being handled on each machine, but this does have an affect on 2d grid games where the pathing just looks odd when it isn't consistent across diagonals.

godotengine / godot

Astar2D Inconsistent with tie-breaking decision in path traversal #43452