「跳躍」，在A *搜索

Question

我試圖實現A *搜索算法，這裏是我的嘗試：

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 
      //? 

     } 
    } 
} 

}

我認爲的函數的名稱不言自明，所以我不會進入他們。不管怎樣，在我的示例輸出我試圖從去（X：0，Y：-2）到（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

事情似乎一直很好，直到14行，但t它突然跳到（5,5）。 任何幫助，非常感謝。

Answer 1

訪問節點的序列不一定是您的最短路徑。據我所知，算法運行良好。注意到節點-5 4在第12行中被訪問過，因此-5 5只是在第15行中訪問的那個節點的一個鄰居。要獲得最短路徑，您應該將最後一個節點的父節點追溯回到最後的初始節點的算法。