C++ A * Pathfinding verursacht Endlosschleife

Question

Ich bin wirklich neu in dieser Art von Sache und this tutorial verwendet, um meinen Code zu schreiben.

Grundsätzlich ruft der Aufruf meiner Funktion meinen Code zum Absturz, das offensichtliche Problem wäre, dass ich eine Endlosschleife verursache, aber ich kann es nicht sehen.

Werfen Sie einen Blick:

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; 
} 

ich eine einfache Vector2 struct verwende ich hier in einer Header-Datei geschrieben:

#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 

einige Anmerkungen zu Codequalität Hinzufügen wäre schön.

Answer 1

Das Problem ist, dass Sie node.f nicht korrekt berechnet haben. zum Tutorial Bezug versehen

F = G + H 

wobei G die Kosten von A auf den aktuellen Platz ist und H die geschätzten Kosten von der Stromquadrat jedoch B., Bezug auf den Code dieses Teil im Rückblick:

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

es scheint, dass die G 1 ist immer, während der Rest des Codes ist für H. In diesem Fall ausarbeitet, sollte G die Schritte sei es von A bis currentNode plus 1 nimmt, da es eine nehmen hat Schritt zum Bewegen.

Der wichtigste Teil ist, dass nur das Speichern von F nicht ausreicht. G muss gespeichert werden, um F in anderen Quadraten auszuarbeiten.

Bearbeiten: Der Grund, warum wir (std::abs(currentNode.x -pathStart.x)+std::abs(currentNode.y - pathStart.y) + 1 nicht verwenden, ist, weil wir das aktuelle Quadrat ohne einen Umweg nicht erreichen könnten. z.B.

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

Vermeintliche, dass wir jetzt an einem Punkt E Ausgang Form Punkt S sind (std::abs(currentNode.x -pathStart.x)+std::abs(currentNode.y - pathStart.y) + 1 Mit dem Abstand 1 jedoch nur, dauert es 5 Schritte, um E.