查找特定范围内的网格单元

Question

我正在开发一款以网格作为底层结构的 2D 游戏。在这个网格中，我想找到从特定范围内的给定单元格可到达的每个单元格。只能在垂直和水平方向上移动，但不能沿对角线移动。

如下图所示。绿色方块是搜索的原点，红色方块是"walls"不能越过的，蓝色是绿色方块周围的所有单元格，最大值为。 10 的距离：

我已经有一个递归算法的工作实现，但它非常慢（范围 10 为 140 毫秒，范围 15 将近一分钟）所以我需要改进它或完全重写它。这是：

//accessible is a vector of points
//blocked is a 2D array of bools

void updateAccessible(Point currentPoint, int restRange) {
    bool existing = false;
    for (int i = 0; i < accessible.size(); i++) {
        Point p = accessible[i];
        if (p.x == currentPoint.x && p.y == currentPoint.y) {
            existing = true;
            break;
        }
    }
    if (!existing) {
        accessible.push_back(currentPoint);
    }

    if (restRange == 0) 
        return;

    int dx[] = { -1, 1, 0, 0 };
    int dy[] = { 0, 0, -1, 1 };

    for (int i = 0; i < 4; i++) {
        Point nextPoint{ currentPoint.x + dx[i], currentPoint.y + dy[i] };
        if (nextPoint.x > 0 && nextPoint.y < gridWidth && nextPoint.y > 0 && nextPoint.y < gridHeight) {
            if (!blocked[nextPoint.x][nextPoint.y]) {
                updateAccessible(nextPoint, restRange - 1);
            }
        }
    }
}

是否有解决此问题的现有算法，例如用于寻路的 A*，或者您有任何改进方法的想法吗？我愿意接受任何建议。

编辑：在 MBo 提到 "breadth-first-search" 之后，我知道我的第一次尝试出了什么问题，它甚至不是正确的深度优先并且多次访问每个单元格。这是我的第二个版本，它使用呼吸优先并且是迭代的。它要快得多（范围 10 为 3 毫秒，范围 15 为 10 毫秒，范围 50 为 1 秒）：

void updateAccessible(Point start, int range) {
    struct Node {
        int x, y, r;
    };
    std::vector<Node> nodes = std::vector<Node>();
    accessible = std::vector<Point>();
    nodes.push_back(Node{ start.x,start.y,range });
    while (nodes.size() > 0) {
        Node currentNode = nodes[0];
        accessible.push_back(Point{ currentNode.x, currentNode.y });
        nodes.erase(nodes.begin());

        if (currentNode.r > 0) {
            int dx[] = { -1, 1, 0, 0 };
            int dy[] = { 0, 0, -1, 1 };

            for (int i = 0; i < 4; i++) {
                Node nextNode{ currentNode.x + dx[i],currentNode.y + dy[i], currentNode.r - 1 };
                if (nextNode.x > 0 && nextNode.x < gridWidth && nextNode.y > 0 && nextNode.y < gridHeight) {
                    if (!blocked[nextNode.x][nextNode.y]) {
                        bool existing = false;
                        for (int ii = 0; ii < nodes.size(); ii++) {
                            Node n = nodes[ii];
                            if (n.x == nextNode.x && n.y == nextNode.y) {
                                existing = true;
                                break;
                            }
                        }
                        for (int ii = 0; ii < accessible.size(); ii++) {
                            Point p = accessible[ii];
                            if (p.x == nextNode.x && p.y == nextNode.y) {
                                existing = true;
                                break;
                            }
                        }
                        if (!existing) {
                            nodes.push_back(nextNode);
                        }
                    }
                }
            }
        }
    }
}

不过，如果您有任何改进建议，我很乐意听取。

Answer 1

您的实现一次又一次遍历相同的单元格。

你需要在这个网格上有深度（距离）限制的 BFS (breadth-first-search)。要实现它，只需为单元格标记添加数组。一旦您将单元格标记为已访问，就不要再继续了。

查找特定范围内的网格单元

Find grid cells within certain range

c++

algorithm

grid

2d

game-engine