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.
