Reputation: 313

Implementing flood fill BFS

I'm trying to find if a certain area is reachable within a set of moves using a flood fill breadth first search algorithm, but I'm having trouble implementing the algorithm. I have a grid here

        let map = [
            [0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, -1, 0, 0],
            [0, 0, -1, 1, -1, 0, 0],
            [0, 0, -1, 0, 0, 0, 0],
            [0, 0, -1, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0],
        ]

Where 1 is my starting position and -1 represents blocked or inaccessible tiles.

From what I understand of flood fill BFS is your first node is the starting position, in my case it's where my map is [y,x]==1 and push this into your que. You then iterate through each element of your que. Then find the neighbors for each element, then you check each neighbor if it's accessible or its visited. And if it's not visited, you append it to the visited list and lastly append it to your list of reachable tiles.

I'm lost on the algorithm and can't implement it properly. Here's my attempt at the algorithm

<html>

<head>

</head>

<body>
    <canvas id="canvas" width="640" height="480"></canvas>
</body>

<script>
    document.addEventListener("DOMContentLoaded", e => {
        let canvas = document.getElementById("canvas");
        let ctx = canvas.getContext("2d");
        let mapwidth = 7;
        let mapheight = 7;
        let map = [
            [0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, -1, 0, 0],
            [0, 0, -1, 1, -1, 0, 0],
            [0, 0, -1, 0, 0, 0, 0],
            [0, 0, -1, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0],
        ]
        let tw = 25;
        let th = 25;
        function drawgridlines() {
            for (var n = 0; n < mapheight; ++n) {
                for (var m = 0; m < mapwidth; ++m) {
                    ctx.strokeRect(m * th, n * tw, th, tw);
                }
            }
        }
        function fillgrid() {

            for (var n = 0; n < mapheight; ++n) {
                for (var m = 0; m < mapwidth; ++m) {
                    if (map[m][n] == 1) {
                        ctx.fillStyle = "red";
                        ctx.fillRect(m * th, n * tw, th, tw);
                    } else if (map[m][n] == -1) {
                        ctx.fillStyle = "black";
                        ctx.fillRect(m * th, n * tw, th, tw);
                    }
                }
            }
        }
        function filltile(k) {

            let m = k[0];
            let n = k[1];
            ctx.fillStyle = "blue";
            ctx.fillRect(m * th, n * tw, th, tw);
        }
        function inbounds(k) {
            let m = k[0];
            let n = k[1];
            return (m >= 0 && m < mapheight && n >= 0 && n < mapwidth);
        }
        function isblocked(k) {
            let m = k[0];
            let n = k[1];
            if (map[m][n] == -1) {
                return true;
            }
            return false;
        }
        function contains(v, k) {
            v.forEach(element => {
                if (element[0] == k[0] && element[1] == k[1]) {
                    return true;
                }
            });
            return false;
        }
        function getneighbors(start) {
            let m = start[0];
            let n = start[1];
            let neighbors = [];
            if (inbounds([m - 1, n])) {
                neighbors.push([m - 1, n]);
            }
            if (inbounds([m, n - 1])) {
                neighbors.push([m, n - 1]);
            }
            if (inbounds([m + 1, n])) {
                neighbors.push([m + 1, n]);
            }
            if (inbounds([m, n + 1])) {
                neighbors.push([m, n + 1]);
            }
            return neighbors;
        }
        function findstart() {
            for (var m = 0; m < mapheight; ++m) {
                for (var n = 0; n < mapwidth; ++n) {
                    if (map[m][n] == 1) {
                        return [m, n];
                    }
                }
            }
            return undefined;
        }


        ////HELP :(
        function floodfillreachable(start, moves) {
            let que = [];
            let visited = [];
            let flood = [];
            que.unshift(start);
            for (var k = 1; k <= moves; ++k) {
                while (que.length > 0) {
                    let current = que.pop();
                    let n = getneighbors(current);
                    n.forEach(element => {
                        if (!isblocked(element)) {
                            if (!contains(visited, element)) {
                                visited.push(element);
                                flood.push(element);
                            }
                        }
                    });
                }
            }
            return flood;
        }

        function draw(time) {
            ctx.clearRect(0, 0, canvas.clientWidth, canvas.clientHeight);
            ctx.strokeStyle = "black";
            drawgridlines();
            fillgrid();

            let start = findstart();
            let flood = floodfillreachable(start, 4);
            flood.forEach(element => {
                filltile(element);
            });
            requestAnimationFrame(draw);
        }
        requestAnimationFrame(draw);
    });
</script>

</html>

Upvotes: 0

Answers (1)

Patrick

Reputation: 11

When iterating through the neighbors, every accessible and unvisited neighbor must also be added to a new queue so that its neighbors will also be processed. Once the move is complete, the old queue is replaced by the new queue. This way, each element in the queue is visited once per move, which limits the size of the flood.

function floodfillreachable(start, moves) {
    let que = [];
    let visited = [];
    let flood = [];
    que.unshift(start);
    for (var k = 1; k <= moves; ++k) {
        // Create a new queue for the next iteration.
        let newQue = [];
        while (que.length > 0) {
            let current = que.pop();
            let n = getneighbors(current);
            n.forEach((element) => {
                if (!isblocked(element)) {
                    if (!contains(visited, element)) {
                        visited.push(element);
                        flood.push(element);

                        // Add the neighbor to the new queue.
                        newQue.push(element);
                    }
                }
            });
        }
        // Replace the queue with the new queue.
        que = newQue;
    }
    return flood;
}

In addition, the contains function will not work correctly. This is because return true; will return from the function passed to v.forEach(), and not from contains itself. This can be solved by using a for...of loop instead of forEach. The loop does not use another function.

function contains(v, k) {
    for (const element of v) {
        if (element[0] == k[0] && element[1] == k[1]) {
            return true;
        }
    }
    return false;
}

Alternatively, some can be used. This will check if the provided function returns true for any element in the array.

function contains(v, k) {
    return v.some(element => element[0] == k[0] && element[1] == k[1]);
}

Upvotes: 1

Implementing flood fill BFS

Answers (1)

Related Questions