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