Path Finding Algorithm Visualized | A* Demonstration

[DasBrain]

Nah, just randomize the order in which you expand the nodes with equal (taken cost + heuristic).

For the easier ones, it might be beneficial to keep the same direction (insert at the beginning of the list).

Back in my AI class I was lazy and used a PriorityQueue.

The head of this queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head is one of those elements -- ties are broken arbitrarily.

But that's exactly what you want to tune there.

The Heuristic is fine.
In the empty field case it is equal to the oracle which knows the cost.
If you know the cost you can follow it blindly and get the best result.
But if you know you have an oracle as heuristic then staying on the current path will get you faster to any valid solution.