& Quot; прыжки & Quot; в поиске A *

Я пытаюсь реализовать алгоритм поиска 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, но затем она внезапно скачет к (5,5).
Буду признателен за любую оказанную помощь.

1

Решение

Последовательность посещенных узлов не обязательно является вашим кратчайшим путем. Насколько я могу судить, алгоритм работает нормально. Обратите внимание, что узел -5 4 посетили в строке 12, и так -5 5 это просто сосед этого узла, который посещается в строке 15. Чтобы получить кратчайший путь, вы должны отследить parentNode конечного узла до начального узла в конце алгоритма.

1

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]