C++ A *パスファインディングは無限ループを引き起こします

Question

私はこの種のことに本当に新しく、this tutorialを使用してコードを記述しました。

基本的には、私の関数を呼び出すとコードがクラッシュすることがありますが、明らかな問題は無限ループの原因になりますが、私はそれを見ることができません。

は見てみましょう：あまりにもいいだろうコードの品質上のいくつかのコメントを追加

#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 

：

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

は私がここにヘッダファイルに書いた簡単なベクトル2の構造体を使用します。

Answer 1

問題は、正しくnode.fを計算しなかったことです。提供されるチュートリアルを参照 、

F = G + H 

Gは、現在の正方形からコストであり、Hは、この部分を参照してコードに戻って見て、しかしBに電流二乗からの推定コストで

：

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

Gは常に1であると思われますが、残りのコードはHを実行するためのものです。この場合、GはAからcurrentNodeに1を加えた値をとるステップでなければなりません移動するステップ。

したがって、最も重要な部分は、Fを保存するだけでは不十分であるということです。他の四角でFを動かすためには、Gを保存する必要があります。

編集：(std::abs(currentNode.x -pathStart.x)+std::abs(currentNode.y - pathStart.y) + 1を使用しない理由は、迂回することなく現在の広場に到達できない可能性があるためです。例えば私はちょうど1を交換することができませんでした今、私たちは(std::abs(currentNode.x -pathStart.x)+std::abs(currentNode.y - pathStart.y) + 1を使用したS. フォームの開始点を点Eであり、距離はしかし、それはE.