Find grid cells within certain range

Question

I am working on a 2D game with a grid as underlying structure. In this grid I want to find every cell that is reachable from a given cell within a certain range. Movement is only allowed in vertical and horizontal direction but not diagonally.

This is demonstrated in the following image. The green square is the origin of the search, the red squares are "walls" that cannot be crossed and blue are all cells arround the green square with a max. distance of 10:

I already have a working implementation of an recursive algorithm, but it is extremly slow (140ms for range 10, almost a minute for range 15) so I need to either improve it or rewrite it completely. Here it is:

//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);
            }
        }
    }
}

Is there an existing algorithm for this problem, like A* for pathfinding or do you have any ideas how to improve mine? I'm open for any suggestions.

---

Edit: After MBo mentioned "breadth-first-search" I knew what was wrong with my first attempt, which wasn't even proper depth-first and visited every cell multiple times. This is my second version, which uses breath-first and is iterative. It is a lot faster (3ms for range 10, 10ms for range 15, 1sec for range 50):

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);
                        }
                    }
                }
            }
        }
    }
}

Still, if you have any suggestions on how to improve it, I'm happy to hear them.

Answer 1

Your implementation walks through the same cells again and again.

You need depth(distance)-limited BFS (breadth-first-search) at this grid. To implement it, just add array for cell marks. When you once mark cell as visited, don't go on it more.