Flood Fill (Extra)

In this note we provide the source code for a basic flood fill algorithm. Suppose you have a rectangular grid of cells representing, say, the floor of a dungeon in a video game. Some of the cells are empty, and some of the cells are walls (meaning nothing can go over or on them).

We assume that for each cell it has, at most, four possible neighbors: the cells above and below it, and to the left and right of it. We won’t won’t count diagonal neighbors. However, they are not hard to add if that’s what you want, e.g. add a four extra if-statements in the main loop of the flood fill code below.

The flood fill problem is this: given a starting cell, “mark” all cells that can be reached from the start by a series of single-step up, down, left, or right moves. One way to think about this is that we start pouring water at the starting cell, and want to figure all the other cells the water flows to (assuming it can’t go through walls).

Many interesting problems can be solved by flood fill, or variations of it. For example, in a painting program, you usually get a “flood fill” tool that will make all the pixels of an enclosed region the same color. Or, suppose you want to know if there is a path from some starting point to some ending point in a maze. You could answer this by doing a flood fill at the beginning point, and then, after its done, check to see if the ending point has been marked.

The source code below implements basic flood fill that will mark all reachable cells in the maze. It has no intelligence at all: it keeps going until all reachable cells are marked.

Here are a few examples of related problems that can be solved with variations of flood fill, or ideas related to it:

• Find any path from a start cell to an end cell.
• Find all paths from a start cell to an end cell.
• Find the shortest path from a start cell to an end cell. One algorithm that does this is Dijkstrta’a algorithm.
• Efficiently find the shortest path from a given start cell to a given end cell. This turns out to be quite a challenging problem in general, and can depend on many details, such as the size of the maze, the percentage of walls, whether or not you have a way to estimate the direction you should go, and so on. An important algorithm that does this is A* search.
• Given a starting cell, generate a list of all cells that are “visible” from it, e.g. all that cells that you could draw a straight line to without going over a wall (or through the corners of two walls).
• Given a starting cell, and a list of “target” cells, determine which cell can be reached by the shortest path.
• There are many algorithms for drawing interesting-looking mazes. Search the web for “maze drawing algorithms” and you will find lots of information.

Flood Fill Source Code

#include "error.h"
#include <iostream>
#include <vector>
#include <cstdlib>
#include <time.h>

using namespace std;

enum class Cell : char {
    Empty = '.',
    Wall = 'M',
    Blob = '^'
}; // enum class Cell

char to_char(Cell t) { return static_cast<char>(t); }

class Map {
private:
    int rows;
    int cols;
    vector<vector<Cell>> map;

public:
    Map(int r, int c, Cell init_val = Cell::Empty)
    : rows(r), cols(c)
    {
        map = vector<vector<Cell>>(rows);
        for(int i = 0; i < rows; ++i) {
            map[i] = vector<Cell>(cols, init_val);
        }

        // add some random walls
        for(int i = 0; i < rows; ++i) {
            for(int j = 0; j < cols; ++j) {
                if (rand() % 3 == 0) {
                    map[i][j] = Cell::Wall;
                }
            }
        }

        // ensure upper-left corner is empty
        map[0][0] = Cell::Empty;
    }

    int num_rows() const { return rows; }
    int num_cols() const { return cols; }

    Cell get_cell(int r, int c) const {
        if (!is_valid(r, c)) error("invalid cell coordinates");
        return map[r][c];
    }

    void set_path(int r, int c) {
        if (!is_valid(r, c)) error("invalid cell coordinates");
        if (map[r][c] == Cell::Empty) {
            map[r][c] = Cell::Blob;
        }
    }

    bool is_valid(int r, int c) const {
        return r >= 0 && r < num_rows() && c >= 0 && c < num_cols();
    }

    void print() const {
        for(const vector<Cell>& row : map) {
            for(const Cell& c : row) {
                cout << to_char(c) << " ";
            }
            cout << "\n";
        }
    }

}; // class Map

struct Location {
    int row;
    int col;
};

// flood fill
int flood_fill(Map& map, int row = 0, int col = 0) {
    vector<Location> stack;

    // assumes start (col, row) is empty; (0, 0) by default
    stack.push_back(Location{row, col});
    int count = 0;

    while (!stack.empty()) {
        Location loc = stack.back();
        stack.pop_back();

        int r = loc.row;
        int c = loc.col;
        map.set_path(r, c);
        count++;

        // add empty cells to the stack
        //
        // note that the only difference in these if-statements are the cell
        // coordinates
        if (map.is_valid(r - 1, c) && map.get_cell(r - 1, c) == Cell::Empty) {
            stack.push_back(Location{r - 1, c});
        }
        if (map.is_valid(r + 1, c) && map.get_cell(r + 1, c) == Cell::Empty) {
            stack.push_back(Location{r + 1, c});
        }
        if (map.is_valid(r, c - 1) && map.get_cell(r, c - 1) == Cell::Empty) {
            stack.push_back(Location{r, c - 1});
        }
        if (map.is_valid(r, c + 1) && map.get_cell(r, c + 1) == Cell::Empty) {
            stack.push_back(Location{r, c + 1});
        }
    }
    return count;
}

int main() {
    srand(time(NULL));

    Map map(10, 10);
    map.print();
    cout << "\n";

    int count = flood_fill(map);
    map.print();
    cout << "# of blobs = " << count << "\n";
}