astar.go will not always choose the optimal path#1

The "Found a path to the goal" condition is checked when expanding neighbours. But to be optimal, this condition should be checked for a node freshly popped from the priority queue instead. Its taking me longer than Id like to produce a failing testcase, but I can show a simple thought experiment that illustrates the problem. It's not as easy to illustrate in the grid world (and Im not even certain I could illustrate it in that world, because it does not use Edge weights), but your algorithm appears to be designed to be more general that just solving the grids. Consider a world with Nodes and Edges, Edges each having a cost ``` E / | / | S---- M ``` S=Start E=End M=Middle Edges: S-E is a giant chasm, cost: 10000 S-M and M-E are paved roads. cost: 1 Currently, astar.go would do this. -Push S onto the Queue -Pop S -Expand neighbors of S using Edges -Neighbor E found. END. Resulting solution would be S-E cost 10000. But optimal solution is S-M-E, cost 2.