"Jumping" in A* search

Question

I'm trying to implement A* search algorithm and here is my attempt:

void Map::findPath(Robot robot, Model target, vector<Node> nodeList, vector<Node> &closedList) {
Node targetNode = target.getCurrentNode();
Node startNode = robot.getCurrentNode();

vector<Node> openList;

openList.push_back(startNode);
startNode.setG(0);startNode.setH(0);startNode.setF(0);
int i = 0;
while (!openList.empty()) {
    Node currentNode = nodeWithLowestFScore(openList);//always returns the most recent one
    /*for ( int i = 0; i < openList.size(); i++){
        cout << "X: " << openList[i].getX() << " Y: " << openList[i].getY() <<
                " G: " << openList[i].getG() << " M: " << openList[i].getH() << endl;
    }*/

    cout << i++ << ". " << currentNode.getX() << " " << currentNode.getY() << " G: " <<
            currentNode.getG() << " M: " << currentNode.getH() << endl;

    closedList.push_back(currentNode);
    removeFromVector(openList, currentNode);
    if (inVector(closedList, targetNode))
        break;
    vector<Node> adjacentNodes;
    currentNode.getWalkableAdjacentNodes(nodeList, adjacentNodes);
    for ( int i = 0; i < adjacentNodes.size(); i++){
        if (inVector(closedList, adjacentNodes[i]))
            continue;
        if (!inVector(openList, adjacentNodes[i])){
            adjacentNodes[i].setParent(&currentNode);
            adjacentNodes[i].setG(currentNode.getG() +1);//distance is always 1 between adjacent nodes
            adjacentNodes[i].setH(adjacentNodes[i].getDistance(targetNode, 'm'));//heuristic as manhattan
            adjacentNodes[i].setF(adjacentNodes[i].getG() + adjacentNodes[i].getH());
            openList.push_back(adjacentNodes[i]);
        }
        if (inVector(openList, adjacentNodes[i])){//update if it's in the list already
            //?

        }
    }
}

}

I think the names of the functions are self explanatory so I'll not go into them. Anyway, in my sample output I'm trying to go from (x:0, y:-2) to (x:-7, y:6)

1. 0 -2
2. -1 -2
3. -2 -2
4. -3 -2
5. -3 -1
6. -3 0
7. -4 0
8. -5 0
9. -5 1
10. -5 2
11. -5 3
12. -5 4
13. -6 4
14. -7 4
15. -5 5
16. -5 6
17. -3 1
18. -3 2
19. -3 3
20. -3 4
21. -2 4
22. -2 2
23. -4 6
24. -5 7
25. -8 4
26. -4 4
27. -5 -1
28. -1 -3
29. 1 -2
30. 2 -2
31. -1 -4
32. -2 -4
33. -3 -4
34. -5 -2
35. -9 4
36. -9 5
37. -9 6
38. -8 6
39. -7 6

Things seems to be going fine until line 14 but then it suddenly jumps to (5,5). Any help is much appreciated.

Answer 1

The sequence of visited nodes is not necessarily your shortest path. The algorithm is running fine as far as I can tell. Observe that the node -5 4 was visited in line 12, and so -5 5 is just a neighbor of that node that is visited in line 15. To get the shortest path you should trace the parentNode of the final node back to the initial node at the end of the algorithm.