A* implementation is not running efficiently but gets correct result

I'm not entirely sure what code other people will need to see, if I miss something off that is important please leave me a comment and I will update it as soon as I possibly can.

I have coded an A* algorithm following the pseudo code from Wikipedia. The problem is, from a relatively short route I am getting about 180 loops through the while loop where as from other people I've heard that they only get about 30

```
@Override
public RouteInfoInterface GetRoute(String[] start, String[] end, int routetype) {
int pos = vertex.GetItem(start[0], start[1]);
if (pos == -1) {
return null;
}
Vertex pStart = vertex.data[pos];
pos = vertex.GetItem(end[0], end[1]);
if (pos == -1) {
return null;
}
Vertex pEnd = vertex.data[pos];
Heap openSet = new Heap(); //known nodes
openSet.Push(pStart); //only start initially
openSet.heap[1].gScore = 0;
openSet.heap[1].fScore = heuristicFormula(pStart, pEnd); //complete heuristic guess

while (openSet.GetLastItem() != 0) { //THIS IS THE LOOP GETTING EXCESSIVE INVOCATIONS
Vertex current = openSet.Pop(); //get node in openSet with lowest fScore and remove it from the openSet
if (current == pEnd) {
eVector route = new eVector();
while (current.whereFrom != null) {
route.AddItem(current.whereFrom);
current = current.whereFrom.from;
}
RouteInfoInterface rI = new RouteInfo(route);
resetData();
return rI;
}

current.closed = true; //add openSet item to closedSet

for (int i = 0; i = current.edges[i].to.gScore) {
continue;
}
if (current.edges[i].to.closed) { //if neighbour in closed set skip
continue;
}
if (!checkOpenSet(openSet, current.edges[i].to)) { //discovered new node?
openSet.Push(current.edges[i].to); //add it to open

Oh, I see your problem all right.

The ^ operator does not do what you think it does.

So your heuristic is wrong. It is possible that for some cases it is inadmissible -- remember, a heuristic is required to under-estimate path length, and yours might sometimes over-estimate due to the error. What's more likely though is that it is massively under-estimating, and your algorithm is little better than Dijkstra's Algorithm at finding the shortest path quickly.

Most of the time, your heuristic will give the square root of the Manhattan distance, which is going to be pretty small compared to the Euclidean distance.

The moral of the story is test your subsystems. If you'd written a test that verifies that the heuristic gives the right answer, you'd have found the bug yourself.

(Also, there's no need to do an abs on the sum of two squares. It's already positive!)

(Also, make a constant -- it pains me to type this, but you are a Java programmer so you get the joy of SHOUTY_SNAKE_CASE -- called METERS_PER_MILE and set it to 1609. Don't litter your program with unexplained magical numbers. Give them names.)

StackExchange Code Review Q#126128, answer score: 3