Java A* Implementation Issues

Question

I have written an implementation of the A* algorithm, taken mainly from This wiki page, however I have a major problem; in that I believe I am visiting way too many nodes while calculating a route therefore ruining my performance. I've been trying to figure out the issue for a few days and I can't see what's wrong. Please note, all my data structures are self implemented however I've tested them and believe they're not the issue. I've included my Priority Queue implementation just in case.

closedVertices is a Hash map of Vertices.

private Vertex routeCalculation(Vertex startLocation, Vertex endLocation, int routetype) 
{  
    Vertex vertexNeighbour;            

    pqOpen.AddItem(startLocation);

    while (!(pqOpen.IsEmpty())) 
    {       
        tempVertex = pqOpen.GetNextItem();


            for (int i = 0; i < tempVertex.neighbors.GetNoOfItems(); i++) //for each neighbor of tempVertex
            {
                currentRoad = tempVertex.neighbors.GetItem(i);
                currentRoad.visited = true;

                vertexNeighbour = allVertices.GetNewValue(currentRoad.toid);

                //if the neighbor is in closed set, move to next neighbor   
                checkClosed();              
                nodesVisited++;
                setG_Score();
                //checks if neighbor is in open set
                findNeighbour();
                //if neighbour is not in open set 
                if (!foundNeighbor || temp_g_score < vertexNeighbour.getTentativeDistance()) 
                {
                    vertexNeighbour.setTentativeDistance(temp_g_score);
                    //calculate H once, store it and then do an if statement to see if it's been used before - if true, grab from memory, else calculate.
                    if (vertexNeighbour.visited == false)
                        vertexNeighbour.setH(heuristic(endLocation, vertexNeighbour)); 


                        vertexNeighbour.setF(vertexNeighbour.getH() + vertexNeighbour.getTentativeDistance());                    

                    // if neighbor isn't in open set, add it to open set
                    if (!(foundNeighbor)) 
                    {    
                        pqOpen.AddItem(vertexNeighbour); 
                    }
                    else
                    {
                        pqOpen.siftUp(foundNeighbourIndex);
                    } 
                }

            }
        }
    }
    return null;
}

Can anyone see where I may be exploring too many nodes?

Also, I've attempted to implement a way to calculate the quickest (timed) route, by modifying F by the speed of the road. Am I right in saying this the correct way to do it? (I divided the speed of the road by 100 because it was taking a long time to execute otherwise).

Answer 1

I found my own error; I had implemented the way in which I calculate the heuristic for each node wrong - I had an IF statement to see if the H had already been calculated however I had done this wrong and therefore it never actually calculated the H for some nodes; resulting in excessive node exploration. I simply removed the line: if (vertexNeighbour.visited == false) and now I have perfect calculations.

However I am still trying to figure out how to calculate the fastest route in terms of time.