最短経路を見つけても正しく計算しない星アルゴリズム

Question

パスの精度を比較する方法として次のA星の視覚化を使用すると、私の実装と今回のものとの間に大きな変化が見られました。

私のテストパス：私はと比較してる

https://qiao.github.io/PathFinding.js/visual/

パス

アルゴリズムがあまりにもチェックしているようにそれはそう時があります

いくつかのノード（すなわち、テスト＃6）。これが期待されるのか、それとも正しくないのでしょうか？アルゴリズムで

重要な変数：オープンリストをソートするための

TileMap* m_tileMap; 
vector<Tile*> m_openList; 
vector<Tile*> m_path; 

// Direct mapping of 2D tile map. 
// Stores the list type for the same-indexed tile 
vector<vector<int>> m_listMap; 

コンパレータ：

struct CompareNodes 
{ 
    // sorts lowest F cost to end of vector 
    bool operator() (Tile* lhs, Tile* rhs) 
    { 
     return lhs->getFCost() > rhs->getFCost(); 
    } 
}; 

ハイレベルの実装：

vector<Tile*> PathGenerator::generatePath(Tile* startNode, Tile* endNode) 
{ 
    setUpListMap(); 

    startNode->setGCost(0); 
    startNode->setHCost(calculateHCost(startNode, endNode)); // Manhattan (no diagonal). { abs(y2 - y1) + abs(x2 - x1) } 
    startNode->calculateFCost(); // calculates G+H internally 

    m_openList.push_back(startNode); 
    Vector2D startNodePos = startNode->getMapPos(); 
    m_listMap[startNodePos.x][startNodePos.y] = LIST_TYPES::OPEN; 

    Tile* currentNode; 


    while (m_openList.empty() == false) 
    { 
     currNode = m_openList[m_openList.size() - 1]; 
     m_openList.pop_back(); 

     Vector2D currNodePos = currNode->getMapPos(); 
     m_listMap[currNodePos.x][currNodePos.y] = LIST_TYPES::CLOSED; 

     if (currNode != endNode) 
     { 
      vector<Tile*> neighbours = findNeighbours(currNode); 
      removeUnnecessaryNodes(&neighbours); // remove walls and closed nodes 
      computeCosts(&neighbours, currNode, endNode); 
      addUniqueNodesToOpenList(&neighbours); // ignores duplicates and then sorts open list 
     } 
     else 
     { 
      m_path = getPath(currNode); 
      resetLists(); // erases all vectors 
     } 
    } 

    return m_path; 
} 

void PathGenerator::computeCosts(vector<Tile*>* nodes, Tile* current, Tile* end) 
{ 
    int newGCost = current->getGCost() + 1; 

    for (int i = 0; i < nodes->size(); i++) 
    { 
     Tile* node = nodes->at(i); 
     unsigned int nodeGCost = node->getGCost(); // G cost defaults to max int limit 

     if (newG < nodeGCost) 
     { 
      // set up node costs like above 
      node->setParentNode(current); 
     } 
    } 
} 

私が最も重要なコードを追加しました。上位レベルの関数が問題の原因を見つけるのに役立たない場合は、私に知らせてください。私はそれらの実装も追加します。

ヘルプありがとうございます。

Answer 1

並べ替えの部分は正しいようですが、ベクトルなので確認するのは非常に簡単です。

代わりに、あなたは本当に最低のF-コストのノードを取得していることを確認するためのテストケースとして、forループ使用してみてください：それはそれを修正する場合

Tile* currnode = m_openlist[0]; 
for (int i = 0; i < m_openList.size() i++) 
{ 
    if (m_openList[i]->getFCost() < currnode->getFCost()) 
     currnode = m_openList[i]; 
} 

を参照してください。もしそうなら、あなたの問題には問題がありますが、私はその問題がどうなるか分かりません。

また、あなたのcomputeCosts機能では、あなたが実行します。

for (int i = 0; i < nodes->size(); i++) 
    { 
     Tile* node = nodes->at(i); 
     //.. other code 
    } 

あなたはなぜその機能を利用すること、およびイテレータを使用するか、範囲ベースのループではない、のstd ::ベクトルを使用しているので：

// Iterators 
for (auto it = nodes->begin(); it != nodes->end(); it++) 
{ 
    Tile* node = *it; 
    //.. other code 
} 

// Range based loop 
for (auto node : *nodes) 
{ 
    //.. other code 
}