c++ - A* 寻路 - 巨大的开放 map 速度慢

Question

我已经实现了 A* 寻路，它可以完美地用于较小的网格。然而，本地图变大并且不再是迷宫结构时，如下图所示，算法会变得越来越慢。

根据 A* 的定义，我使用的是开放列表和封闭列表。开放列表是使用 std::set 实现的。关闭列表是使用 Qt 的 QSet 实现的。 QSet 是 Qt 对 std::unordered_list 的实现。

在分析我的应用程序之后，我注意到 std::set 的树的重新平衡是最昂贵的操作。当在两个不同的 map 中运行该算法时，这一点很明显，下面显示的 map 具有较大的开放列表大小，而另一个类似迷宫的 map 具有低得多的开放列表大小。

在迷宫般的 map 中，我的开放列表的大小会在 20 到 120 个节点之间波动。打开的 map 慢慢增长到 2000 多个节点。

所以我的问题是有没有什么办法可以减少打开列表的大小？

我尝试了以下方法:

• 将打开列表更改为 std::priority_queue:我无法实现此操作，因为我需要检查打开列表以查看它是否已包含该元素。如果我错了，请纠正我，但是 priority_queue 不会遇到同样的重新平衡问题吗？

• 使用更高的启发式权重:这并没有解决问题，打开列表中节点的数量级仍然相同。

• 剪裁开放列表中的节点:这样可以加快运行速度，但通常会导致找不到路径。最初我认为这会起作用，因为我只会用更高的 F(启发式 + 移动)成本来修剪值，这将变得无关紧要。这个假设被证明是错误的。

提前致谢。

编辑 1: 添加了一些代码以进行说明。

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。在将节点添加到队列之前，无需检查节点是否已经在开放集中。如果它已经存在，则不将其插入封闭集中会更便宜。