C++ A * Pathfinding вызывает бесконечный цикл

Question

Я действительно новичок в этом деле и использовал this tutorial, чтобы написать свой код.

В принципе, вызов моей функции приводит к сбою моего кода, очевидной проблемой является то, что я вызываю бесконечный цикл, но я не вижу его.

Посмотрите:

std::vector<Vector2> TileMap::pathFind(Vector2 pathStart, Vector2 pathEnd){ 
    struct Node{ 
     Vector2 pos; 
     int f; 
     inline Node operator=(Node a){ 
      pos = a.pos; 
      f = a.f; 
     } 
    }; 
    std::vector<Node> openList; 
    std::vector<Vector2> closedList; 
    closedList.push_back(pathStart); 

    Vector2 currentNode = pathStart; 
    do{ 
     if(currentNode.x - 1 >= 0){ //NORTH 
      Node node; 
      node.pos = Vector2(currentNode.x-1, currentNode.y); 
      node.f = 1 + (std::abs(pathEnd.x - node.pos.x)+std::abs(pathEnd.y - node.pos.y)); 
      openList.push_back(node); 
     } 
     if(currentNode.x + 1 <= MAP_WIDTH){ //SOUTH 
      Node node; 
      node.pos = Vector2(currentNode.x+1, currentNode.y); 
      node.f = 1 + (std::abs(pathEnd.x - node.pos.x)+std::abs(pathEnd.y - node.pos.y)); 
      openList.push_back(node); 
     } 
     if(currentNode.y - 1 >= 0){ //WEST 
      Node node; 
      node.pos = Vector2(currentNode.x, currentNode.y-1); 
      node.f = 1 + (std::abs(pathEnd.x - node.pos.x)+std::abs(pathEnd.y - node.pos.y)); 
      openList.push_back(node); 
     } 
     if(currentNode.y + 1 <= MAP_HEIGHT){ //EAST 
      Node node; 
      node.pos = Vector2(currentNode.x, currentNode.y+1); 
      node.f = 1 + (std::abs(pathEnd.x - node.pos.x)+std::abs(pathEnd.y - node.pos.y)); 
      openList.push_back(node); 
     }//step 2 now 

     if(!(openList.empty())){ 
      Node minimum = openList[0]; 
      int num = 0; 
      for(auto i : openList){ 
       num++; 
       if(minimum.f > i.f){ 
        minimum = i; 
       } 
      } 
      currentNode = minimum.pos; 
      closedList.push_back(minimum.pos); 
      openList.erase(
      std::remove_if(openList.begin(), openList.end(), [&](Node & node) { 
       return node.pos == minimum.pos; 
      }), openList.end()); 
     } 

     if(currentNode == pathEnd){ 
      openList.clear(); 
     } 
    }while(!(openList.empty())); 
    return closedList; 
} 

Я использую простой Vector2-структуру, которую я написал в заголовочном файле здесь:

#ifndef VECTOR2_H_INCLUDED 
#define VECTOR2_H_INCLUDED 

struct Vector2{ 
    int x; 
    int y; 
    Vector2(int x, int y){ 
     this->x = x; 
     this->y = y; 
    } 
    Vector2(){ 
     this->x = 0; 
     this->y = 0; 
    } 

    inline Vector2 operator=(Vector2 a){ 
     x=a.x; 
     y=a.y; 
    } 

    bool operator==(Vector2 a){ 
     return (x==a.x && y==a.y); 
    } 
}; 

#endif // VECTOR2_H_INCLUDED 

Добавление некоторых замечаний по качеству кода было бы слишком хорошо.

Answer 1

Проблема в том, что вы не правильно вычислили node.f. Ссылаясь на учебник при условии,

F = G + H 

где G- стоимость от А до текущей площади и Н представляет собой расчетная стоимость от текущей площади к B. Однако, оглядываясь назад к коду со ссылкой этой части:

node.f = 1 + (std::abs(pathEnd.x - node.pos.x)+std::abs(pathEnd.y - node.pos.y)); 

кажется, что G всегда 1, в то время как остальная часть коды для разработки H. в этом случае G должен быть шагами, она принимает от А до сиггепЬЫойи плюс 1, так как она имеет взять одну шаг для перемещения.

Итак, самая важная часть заключается в том, что для сохранения F недостаточно. G необходимо сохранить, чтобы выработать F на других квадратах.

Редактировать: причина, по которой мы не используем (std::abs(currentNode.x -pathStart.x)+std::abs(currentNode.y - pathStart.y) + 1, состоит в том, что мы не можем достичь текущей площади без обхода. например

+---+ 
| | 
| | | 
|S|E| 
+-+-+ 

предположить, что в настоящее время мы находимся в точке Е, начиная форма точки S. Используя (std::abs(currentNode.x -pathStart.x)+std::abs(currentNode.y - pathStart.y) + 1, расстояние только 1. Тем не менее, она занимает 5 шагов, чтобы перейти к Е.