Flood Fill

The flood-fill algorithm determines the area connected to a given node in a multidimensional array. Using connection rules to establish if an adjacent node is connected or blocked you can "fill" all surrounding nodes to any desired depth.

The algorithm takes three parameters: a start node, a target fill function, a target block detection function and optionally a maximum range or depth.

Flood Fill Usage

Flood-fill is the same algorithm used in paint bucket functions of image editors. I have put it to use as a character's available travel cells in 2D games. It is recursive in nature and can be expanded for any number of "adjacent" direction checks, though most applications are for 4 direction space.

In this example we are rendering available movement positions for a player's turn. A flood fill takes the players speed as the range and sweeps all non-blocking structures to display places the player can travel to.

void LevelClient::renderMoveMarkers()
{
    unsigned int i=0;
    LevelClient* lc = this;
    bit::FloodFill::compute(playerTile->schema.x / tileWidth, playerTile->schema.y / tileHeight,
        // Lambda function to take a cell's coordinate, find it in our map, and create a movement marker over it
        [lc, &i] (int x, int y, int depth) {
            TileClient* tile = lc->getTileAtIndices(x, y);
            // This check was to not duplicate markers because floodfill will inspect the same one more than once
            if(tile && tile->metadata_floodfillId != bit::FloodFill::floodfillId)
            {
                tile->metadata_floodfillId = bit::FloodFill::floodfillId;

                sf::Color w(255, 255, 255);
                lc->moveMarkers[i].renderAt(x * lc->tileWidth, y * lc->tileHeight, w);
                i++;
            }
        },
        // This is our optional block check routine, which looks for the tile being checked and sees if it has an obstacle on it
        [lc] (int x, int y, int depth) -> bool {
            TileClient* tile = lc->getTileAtIndices(x, y);
            return !tile || depth > lc->playerCharacter->schema.speed || (tile->hasBody && tile->bodyClient != lc->playerCharacter);
        }
    );
}

Implementation in C++

The algorithm was implemented for 4 directional use cases. In addition the multi-dimensional array has been abstracted away and replaced with simple x and y coordinate math and lambda functions to map the coordinates back to implementation data.

FloodFill.hpp

#pragma once
#ifndef BIT_FLOODFILL_H
#define BIT_FLOODFILL_H

#include <functional>
#include <vector>

namespace bit
{
    class FloodFill
    {
    public:

        static unsigned int floodfillId;

        static void compute(int x, int y, std::function<void(int, int, int)> inspect, std::function<bool(int, int, int)> isBlocked);

    private:
        static void compute(int x, int y, std::function<void(int, int, int)> inspect, std::function<bool(int, int, int)> isBlocked, int depth);

    };
}
#endif

FloodFill.cpp

#include "FloodFill.hpp"

unsigned int bit::FloodFill::floodfillId = 0;

void bit::FloodFill::compute(int x, int y, std::function<void(int, int, int)> inspect, std::function<bool(int, int, int)> isBlocked)
{
    floodfillId++;
    compute(x, y, inspect, isBlocked, 0);
}

void bit::FloodFill::compute(int x, int y, std::function<void(int, int, int)> inspect, std::function<bool(int, int, int)> isBlocked, int depth)
{
    if(isBlocked(x, y, depth))
        return;

    inspect(x, y, depth);

    depth++;

    compute(x + 1, y, inspect, isBlocked, depth);
    compute(x - 1, y, inspect, isBlocked, depth);
    compute(x, y + 1, inspect, isBlocked, depth);
    compute(x, y - 1, inspect, isBlocked, depth);
}