A* implementation is not running efficiently but gets correct result

Question

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.length; i++) { //for each neighbour
 double d = current.gScore + (current.edges[i].distance); //calc tenative distance
 if (d >= 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 openSet
 }
 current.edges[i].to.whereFrom = current.edges[i];
 current.edges[i].to.gScore = d;
 current.edges[i].to.fScore = current.edges[i].to.gScore + heuristicFormula(current.edges[i].to, pEnd);
 }
 openSet.BuildMinHeap();
 }
}

A note on the Heuristic, the distance data given is in meters, I divide by 1609.34 to put it into miles as I use miles for other sections of the program that are not shown here

private double heuristicFormula(Vertex from, Vertex to) {
 double result = (Math.sqrt(Math.abs((from.x - to.x) ^ 2 + (from.y - to.y) ^ 2)) / 1609.34);
 return result;
}

My algorithm does get the right route however I am trying to make the algorithm as fast as possible. Again if theres anything else people need then please let me know.

• user103510: I think it would be helpful to see the rest of your code

Answer 1

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.)

• Terramet: Thank you, its running great now, I had been staring at this work for ages wondering why it was preforming at Dijkstra's efficiency