A *経路探索 - 巨大なオープンマップで遅い

Question

私は小規模なグリッドで完璧に動作するA *経路探索を実装しました。しかし、マップが大きくなり、下に描かれているマップのようにもはや迷路構造になっていないとき、アルゴリズムはますます遅くなります。 * 'sの定義に従って

、私はオープンリストと、閉じたリストを使用しています。オープンリストは、std::setを使用して実装されています。閉じられたリストは、QtのQSetを使用して実装されます。 QSetはQtの実装でstd::unordered_listです。

私のアプリケーションをプロファイリングした後、std::setのツリーの再平衡が最も高価な操作であることに気付きました。これは、大きく開いたリストのサイズを持つ以下のマップと、オープンリストのサイズがはるかに小さい別の迷路のようなマップの2つの異なるマップでアルゴリズムを実行する場合に顕著です。

迷路のようなマップでは、オープンリストのサイズは20〜120ノードの間で変動します。開かれた地図はゆっくりと2000以上のノードまで成長しました。

オープンリストのサイズを減らす方法があれば、私の質問になりますか？

は、私は、次の方法を試してみました：

• 変更オープンリストをstd::priority_queueに：私は、私はそれがすでに要素が含まれているかどうかを確認するために開いているリストを確認する必要があるため、これを実装することができませんでした。私が間違っていれば私を修正してください。しかし、priority_queueは同じ問題を再調整しないでしょうか？

• これは、問題を解決しなかったため、オープンリストのノードの大きさの順番は同じです。

• 開いているリストのノードをクリッピングする：これにより、実行のスループットは向上しましたが、パスが見つからないことがよくありました。最初は、これは無関係になっていたより高いF（ヒューリスティック+ムーブメント）コストで値をトリミングするだけなので、これはうまくいくと思いました。この仮定は間違っていることが判明した。

ありがとうございます。

EDIT1： 説明のためにいくつかのコードを追加しました。

std::shared_ptr<Node> Pathfinding::findPath(float heuristicWeight) { 
    int i = 0; 
    while (!m_sOpen.empty()) { 
     ++i; 
     std::shared_ptr<Node> current = *m_sOpen.begin(); 
     m_sOpen.erase(current); 
     m_sClosed.insert(*current); 
     if (updateNeighbours(current, heuristicWeight)) { 
      return std::make_shared<Node>(*m_sClosed.find(*m_nEnd)); 
     } 
     if (i % 100 == 0) { 
      qInfo() << "Sizes: " << i << " open_size= " << m_sOpen.size() << " & closed_size= " << m_sClosed.size(); 
     } 
    } 
    return NULL; 
} 

bool Pathfinding::updateNeighbours(std::shared_ptr<Node> current, float heuristicWeight) { 
    int maxRows = wm.getRows(); // Rows in map 
    int maxCols = wm.getCols(); // Cols in map 
    for (int x = clamp((current->getX()-1),0,maxCols-1); x <= clamp((current->getX()+1),0,maxCols-1); ++x) { 
     for (int y = clamp((current->getY()-1),0,maxRows-1); y <= clamp((current->getY()+1),0,maxRows-1); ++y) { 
      bool exists = false; 
      Node n = Node(x,y); // Node to compare against and insert if nessecary. 
      // Tile contains information about the location in the grid. 
      Tile * t = wm.m_tTiles[(x)+(maxCols * y)].get(); 
      if (t->getValue() != INFINITY) { // Tile is not a wall. 
       for (std::set<std::shared_ptr<Node>>::iterator it = m_sOpen.begin(); it != m_sOpen.end(); ++it) { 
        if (**it == n) { 
         exists = true; 
         if ((*it)->getF() > (current->getG() + moveCost(*it,current)) + (*it)->getH()) { 
          (*it)->setG(current->getG() + moveCost(*it,current)); 
          (*it)->setParent(current); 
         } 
         break; 
        } 
       } 
       bool exists_closed = (m_sClosed.find(n) != m_sClosed.end()); 
       if (!exists && !exists_closed) { 
        std::shared_ptr<Node> sN = std::make_shared<Node>(n); 
        sN->setParent(current); 
        sN->setG(current->getG() + moveCost(sN,current)); 
        sN->setH(manhattenCost(sN,m_nEnd)*heuristicWeight); 
        if (sN->getH() == 0) { m_sClosed.insert(*sN); return true; } 
        else m_sOpen.insert(sN); 
       } 

      } 
     } 
    } 
    return false; 
} 

Answer 1

スイッチをstd::setからstd::priority_queueに切り替えます。キューにキューを追加する前にノードがすでにオープンセットに入っているかどうかを確認する必要はありません。すでに閉じられている場合は、閉じたセットに挿入しないほうが安いです。