优化寻路功能中的矢量使用

Question

所以，我在网格上运行了一个基本的 A* 函数，最终需要被调用很多次。可以肯定地说，正在寻找减少调用的方法，但仍然希望简化功能本身。

毫不奇怪，最大的减慢速度是搜索开/闭向量的副本，并对开列表进行排序。有没有更快的方法来做到这一点，或者有更好的容器用于此目的？预先感谢！

有问题的代码：

if ((iterMapSearch = std::find(vecOpenList.begin(), vecOpenList.end(), pCurrentTile)) != vecOpenList.end()) //We find it in the open list.
                if ((*iterMapSearch)->fTotalWeight <= fTotalWight) //value is worse then something already used, so skip.
                    continue;

if ((iterMapSearch = std::find(vecClosedList.begin(), vecClosedList.end(), pCurrentTile)) != vecClosedList.end()) //We find it in the closed list.
                if ((*iterMapSearch)->fTotalWeight <= fTotalWight) //value is worse then something already used, so skip.
                    continue;

还有

vecOpenList.push_back(pCurrentTile);
std::sort(vecOpenList.begin(), vecOpenList.end(), compareWeightVal);

Answer 1

使用哈希映射（std::unordered_map）来跟踪打开和关闭列表中的节点。这将允许插入和查找的平均时间复杂度。以下是如何使用优先级队列和 unordered_map 作为打开列表的示例：

#include <queue>
#include <unordered_map>

struct CompareWeight {
    bool operator()(const Tile* lhs, const Tile* rhs) const {
        return lhs->fTotalWeight > rhs->fTotalWeight;
    }
};

std::priority_queue<Tile*, std::vector<Tile*>, CompareWeight> pqOpenList;
std::unordered_map<Tile*, Tile*> mapOpenList;
std::unordered_map<Tile*, Tile*> mapClosedList;

// When adding to the open list
if (mapClosedList.find(pCurrentTile) != mapClosedList.end() && 
    mapClosedList[pCurrentTile]->fTotalWeight <= fTotalWeight) {
    continue;
}

if (mapOpenList.find(pCurrentTile) != mapOpenList.end() && 
    mapOpenList[pCurrentTile]->fTotalWeight <= fTotalWeight) {
    continue;
}

pqOpenList.push(pCurrentTile);
mapOpenList[pCurrentTile] = pCurrentTile;