c++ - 查找一定范围内的网格单元

Question

我正在开发一款以网格为基础结构的 2D 游戏。在这个网格中，我想找到从给定单元格在一定范围内可到达的每个单元格。只允许垂直和水平方向移动，不允许斜向移动。

下图对此进行了演示。绿色方 block 是搜索的原点，红色方 block 是无法跨越的“墙”，蓝色是绿色方 block 周围的所有单元格，其最大值为。距离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 提到“广度优先搜索”之后，我知道我的第一次尝试出了什么问题，它甚至不是正确的深度优先，并且多次访问了每个单元格。这是我的第二个版本，它使用呼吸优先并且是迭代的。它要快得多(范围 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 )。要实现它，只需添加单元格标记数组即可。一旦您将单元格标记为已访问，就不要再继续下去了。