c++ - 如何使我的洪水填充算法更有效？

Question

我的代码中有一个泛洪填充函数，它只在填充的单元格上返回一个数字。但它非常慢，我的 A* 寻路算法比它快成指数级。这是片段:

   bool withinBoundaries(_2D::Point p) {
//cerr << "Checking if x: " << p.x << " y: " << p.y << " is within boundaries" << endl;
if (p.x <= 29 && p.y <= 19 && p.x >= 0 && p.y >= 0) {
    return true;
}
return false;
}


bool canMove(_2D::Point point, _2D::Point offset, map<pair<int, int>, bool> gameGrid) {
if (!gameGrid[(point + offset).toPair()] && withinBoundaries(point + offset)) return true;
else return false;
}

int floodFillGetArea(_2D::Point point, map<pair<int, int>, bool> gameGrid) {
    map<pair<int, int>, bool> checked;
    map<pair<int, int>, bool> gameGridCopy = gameGrid;
    deque<_2D::Point> openPoints;
    openPoints.push_back(point);
    int count = 0;

    while (!openPoints.empty()) {
    _2D::Point curPoint = openPoints.back();
    openPoints.pop_back();
    if(checked[curPoint.toPair()]) break;
    gameGridCopy[curPoint.toPair()] = true;
    count++;
    if (canMove(curPoint, _2D::Point::UP(), gameGridCopy)) {

        openPoints.push_back(curPoint + _2D::Point::UP());
    }
    if (canMove(curPoint, _2D::Point::RIGHT(), gameGridCopy)) {
        openPoints.push_back(curPoint + _2D::Point::RIGHT());
    }
    if (canMove(curPoint, _2D::Point::DOWN(), gameGridCopy)) {
        openPoints.push_back(curPoint + _2D::Point::DOWN());
    }
    if (canMove(curPoint, _2D::Point::LEFT(), gameGridCopy)) {
        openPoints.push_back(curPoint + _2D::Point::LEFT());
    }
    checked[curPoint.toPair()] = true;
}
return count;
}

这每秒检查一个节点，为什么这么慢？ _2D::Point 只是一个具有 int x 和 int y 的对象。当它们已经被标记为正在检查时，它还会创建开放式点头，为什么？

Answer 1

首先，您将一个 std::map 对象复制了 6 次，但没有任何结果。

尝试将 map 对象作为常量引用传递，而不是按值传递(=复制)