1 Problem definition and terminology

Flood fill is a graph or grid traversal technique that starts from a designated seed location and processes all cells that belong to the same contiguous region under a specified rule. The rule is typically a match to a target attribute (such as a color or scalar value), and “contiguous” is defined by the chosen neighborhood relation.

1.1 Seed point and target criteria

The seed point is the starting cell from which expansion begins. A target criterion determines which neighboring cells are considered part of the region—most commonly, a cell is eligible if its value equals a target value (e.g., the original color at the seed) or satisfies a predicate relative to that target.

In recoloring use cases, the algorithm usually replaces the values of all eligible cells with a new output value. In region-detection use cases, it may instead produce a label map or a set of visited coordinates.

1.2 Connectedness (4-way, 8-way, and custom neighborhoods)

Connectedness specifies how neighbors are defined. In 2D grids, common options include:

  • 4-way connectivity: neighbors are up, down, left, right.
  • 8-way connectivity: also includes diagonals.
  • Custom neighborhoods: may include offsets shaped to a specific domain, such as knight moves in grid games, hex-like adjacency on skewed lattices, or neighborhood masks used in image processing.

The choice of connectivity affects which cells are included and therefore changes the resulting region.

1.3 Region labeling vs. recoloring

Flood fill is used in two closely related modes:

  • Recoloring: each visited cell is assigned a new value, often to simulate painting.
  • Region labeling: each visited cell is assigned an identifier so the algorithm can distinguish multiple regions in the same input.

Labeling is typically done with multiple flood-fill runs (one per unassigned region), while recoloring is usually a single run per operation.

2 Core algorithm approaches

Several traversal strategies implement flood fill. They differ primarily in the order in which frontier cells are explored and in the memory structure used to hold pending work.

2.1 Breadth-first flood fill (BFS)

BFS explores the region in layers: all cells at distance *d* from the seed (with distance measured in number of neighbor steps) are processed before those at distance *d+1*.

2.1.1 Queue-based exploration

In grid settings, BFS maintains a queue of eligible cells discovered but not yet processed. The algorithm repeatedly dequeues a cell, checks whether it still satisfies the eligibility criterion (to avoid stale entries if values can change), then marks it and enqueues its eligible neighbors.

Queueing naturally matches BFS semantics and avoids deep call stacks, making it a common choice for robust implementations.

2.1.1.1 Complexity and memory considerations

Time complexity is generally linear in the number of visited cells under typical constant-time neighbor checks, denoted *O(V)* for *V* visited cells (or *O(N)* for *N* total cells in the grid). Space complexity depends on frontier width; in worst cases it can be large, roughly proportional to the maximum number of cells in a BFS layer.

2.2 Depth-first flood fill (DFS)

DFS explores along a path as far as possible before backtracking. This can be implemented recursively or iteratively with an explicit stack.

2.2.1 Stack/recursion-based exploration

Recursive DFS uses the call stack: when a neighbor is eligible, DFS calls itself on that neighbor. Iterative DFS uses an explicit stack data structure, pushing neighbors onto it and popping to continue exploration.

DFS often has better memory behavior when the region is narrow or when the stack depth stays moderate, but it can be sensitive to worst-case depth in large, snake-like regions.

2.2.1.1 Recursion depth limits and iterative DFS

Many programming environments impose limits on recursion depth, and a large region can trigger stack overflow if recursion is used naively. Iterative DFS with an explicit stack avoids this limitation and is a common remedy in production code.

2.3 Scanline flood fill

Scanline flood fill fills contiguous horizontal (or vertical) spans rather than cell-by-cell expansion in a strict frontier ordering. The method identifies a maximal run (span) of eligible cells from a starting point, fills it, and then examines neighboring rows to find additional spans that should be processed.

2.3.1 Span filling and boundary tracking

A typical scanline approach:

  1. From a seed coordinate, extend left and right to find the full eligible span on that scanline.
  2. Fill the span.
  3. For the row above and below, scan only at positions adjacent to the filled span boundaries to locate new eligible spans.
  4. Push discovered spans onto a stack/queue of intervals rather than pushing every individual cell.

Boundary tracking is key: by restricting where scanning happens on neighboring lines, the algorithm reduces redundant neighbor checks.

2.3.1.1 Performance characteristics vs. BFS/DFS

Scanline flood fill can be faster and use less memory for certain shapes, particularly large regions with long straight boundaries. Where BFS/DFS processes each cell with explicit neighbor checks, scanline methods can amortize work by handling runs as units, sometimes leading to fewer operations overall.

However, the implementation is more complex and can depend on the grid orientation and the cost of interval bookkeeping.

2.4 Union-find style region merging (conceptual alternative)

Union-find (disjoint-set union) offers a different perspective: instead of expanding from a seed, preprocessing can group cells into connected sets by unioning eligible adjacent pairs. After construction, a seed’s region can be obtained by finding its representative set.

2.4.1 When preprocessing helps

Union-find is most advantageous when multiple queries on the same static grid are needed, or when the application already builds connectivity structures for other purposes. For a single flood fill on a mutable grid, traversal-based methods are often simpler and more direct.

3 Data structures and implementation details

Efficient flood fill implementations rely on careful representation of the grid and disciplined bookkeeping to avoid revisiting cells.

3.1 Grid representation

Flood fill is usually defined on a discretized domain such as a pixel grid, tilemap, or occupancy grid.

3.1.1 2D arrays and index mapping

A common representation is a 2D array indexed by (row, column). In languages that store arrays in row-major order, it is common to map 2D coordinates to a single linear index using an expression like idx = row * width + col, improving cache locality and simplifying storage of auxiliary arrays.

Neighbors can then be computed by adding or subtracting offsets corresponding to the chosen connectivity.

3.1.2 Sparse grids and memory-efficient storage

In applications where only a small subset of cells are present or relevant (e.g., large maps with mostly empty space), sparse representations can be used. Approaches include:

  • Hash maps keyed by coordinates.
  • Compressed row structures.
  • Hierarchical spatial indices.

Flood fill on sparse domains must carefully define what “absent” means (blocked, empty, or unknown) because neighbor eligibility depends on cell values.

3.2 Visited tracking strategies

To prevent repeated processing, implementations mark cells as visited or otherwise ensure that each eligible cell is processed at most once.

3.2.1 Marking with sentinel values

A typical technique overwrites the cell value with a special marker (or the new recolor value) to indicate it has been handled. This avoids a separate visited structure and can reduce memory usage.

This method is safe when overwriting does not affect the eligibility test for yet-unprocessed cells. If the eligibility criterion depends on the original value, the algorithm may need to store the target value separately or use a visited bitmap.

3.2.2 Separate visited bitmaps

A visited bitmap stores a boolean flag per cell. This is often clearer when the eligibility predicate depends on stable input values. It can also be used when recoloring should not change the original grid or when the original data must be preserved for later steps.

3.3 Handling the color/value match test

The eligibility check is central to flood fill correctness. It determines which neighbors are included and how robust the method is to variations in numeric data.

3.3.1 Exact matches vs. tolerance for numeric data

For images with discrete color indices, exact matching is common. For numeric fields (e.g., grayscale floats or sensor measurements), tolerance-based comparisons are often used, such as accepting neighbors whose values differ from the target by at most a threshold.

Tolerance can introduce sensitivity to noise; choosing it typically balances under-segmentation (region breaks too easily) against over-segmentation (unwanted merging).

3.3.2 Avoiding redundant neighbor checks

Flood fill can spend time re-checking neighbors that are already processed or known to be ineligible. Common optimizations include:

  • Checking bounds and eligibility before inserting into the queue/stack.
  • Marking as soon as a cell is enqueued to avoid multiple insertions.
  • Using visited flags to short-circuit neighbor exploration.

These reduce overhead without changing the set of visited cells.

4 Edge cases and robustness

Flood fill implementations must handle situations where naive code may fail or degrade dramatically.

4.1 Boundaries and out-of-range neighbors

When exploring neighbors, the algorithm must ensure neighbor coordinates remain within the grid bounds. Off-by-one errors are a frequent source of bugs, especially when using linear indexing or custom neighbor lists.

4.2 Large regions and stack/queue growth

In worst cases—such as a fully eligible large grid—BFS and DFS can both approach linear memory usage. BFS may require a large frontier queue, while recursive DFS risks stack overflow. Iterative DFS with an explicit stack and cautious memory allocation are typical mitigation strategies.

4.3 Non-rectangular or masked domains

Some domains use masks to mark valid cells (e.g., irregular shapes in a grid or image alpha regions). In such settings, the eligibility criterion should incorporate the mask, and connectivity should be computed only among valid cells. Otherwise, flood fill might leak into invalid or sentinel regions.

4.4 Cycles and repeated processing prevention

Grids can contain cycles under neighbor adjacency (for example, moving around a rectangle returns to earlier cells). Proper visited tracking prevents infinite loops and ensures termination. Correctness depends on marking cells at the right time (either upon enqueue or upon dequeue, depending on the design).

5 Performance analysis

Flood fill performance depends on how many cells are visited and on the cost of each eligibility and neighbor operation.

5.1 Time complexity by traversal model

For standard BFS/DFS on a grid, time is typically *O(V)*, where *V* is the number of visited eligible cells, assuming constant-time operations per cell. If every cell qualifies, then *V* equals the grid size *N*, yielding *O(N)* time.

Eligibility checks and neighbor iteration contribute constant factors that differ among implementations and connectivity patterns.

5.2 Space complexity by frontier/stack size

Space complexity is dominated by the frontier/stack/queue plus any auxiliary arrays (visited markers, labels). BFS frontier size can be large when the region grows in a wave-like manner. DFS stack depth depends on traversal order and the region’s shape; it can be small for branching regions but large for long corridors.

5.3 Worst-case behavior in dense grids

Dense grids with many eligible cells tend to maximize both visited count and frontier size. In such cases, all flood fill variants require memory proportional to a significant fraction of the grid. Scanline fill can be more efficient in practice when eligibility forms large contiguous spans, but its worst-case behavior can also approach linear scaling with the number of cells.

6 Applications in software engineering

Flood fill appears across domains where one needs to process connected regions under a rule.

6.1 Image editing and “paint bucket” tools

“Paint bucket” tools fill an area connected to a clicked pixel, constrained by a similarity rule. This enables interactive recoloring of shapes in raster images. The technique underlies many user-facing features in drawing applications, often with additional safeguards for performance on large images.

6.2 Tilemap and level generation in games

In game development, flood fill can identify reachable areas, determine which tiles belong to a region (such as rooms connected by corridors), or assist procedural generation by marking contiguous spaces for further processing.

Connectivity selection matters: for example, whether diagonal touching counts as connected can change how rooms are classified.

6.3 Maze and puzzle region detection

Flood fill can solve puzzles by finding connected regions of walls, passages, or colored zones. It is commonly used to validate level constraints, detect enclosed areas, or compute connectivity in grid-based mazes.

6.4 Computational geometry over discretized spaces

When geometry is represented on a grid (e.g., occupancy maps or rasterized shapes), flood fill can approximate concepts like area filling, region extraction, or topological properties such as connectedness. It is also used as a stepping stone in more complex pipelines that refine boundaries after discrete processing.

Flood fill relates to broader ideas in graph theory and image analysis.

7.1 Connected components labeling

Connected components labeling extends flood fill to label all maximal connected regions in an entire grid. Typically, the algorithm scans cells and starts a flood fill from each unvisited cell, assigning a new component label each time.

This produces a complete partition of the grid under the chosen connectivity and eligibility criteria.

7.2 Segmentation by thresholding + flood fill

In image segmentation workflows, flood fill often follows thresholding: a pixel classification step (e.g., based on intensity) defines a preliminary mask, and then flood fill extracts connected segments. This combination is used to isolate objects or regions that share a similar value range while maintaining spatial coherence.

7.3 Flood fill on graphs vs. grids

Although often described for 2D grids, flood fill generalizes to graphs: the neighborhood of a node is the set of adjacent vertices. Eligibility then determines which vertices are traversable from the seed. BFS, DFS, and queue-based wavefront methods apply directly.

7.4 Multiseed flood fill and wavefront propagation

Multiseed flood fill begins from several seeds simultaneously. This is closely related to wavefront propagation, where each cell may be assigned the nearest seed (or a distance) under uniform step costs. The approach is useful for influence maps, distance transforms on discrete spaces, and certain game AI techniques.

8 Pseudocode and reference implementations

The following pseudocode outlines common flood fill patterns. It assumes functions exist to test bounds and eligibility, and uses a fixed neighbor set consistent with the chosen connectivity.

8.1 BFS flood fill pseudocode

function floodFillBFS(grid, seed, targetValue, newValue):
    if grid[seed] != targetValue:
        return grid

    create an empty queue Q
    enqueue seed onto Q
    mark grid[seed] as newValue

    while Q is not empty:
        cell = dequeue Q
        for each neighbor n of cell:
            if inBounds(n) and grid[n] == targetValue:
                mark grid[n] as newValue
                enqueue n onto Q

    return grid

8.2 DFS flood fill pseudocode

function floodFillDFS(grid, seed, targetValue, newValue):
    if grid[seed] != targetValue:
        return grid

    create an empty stack S
    push seed onto S

    while S is not empty:
        cell = pop S
        if grid[cell] != targetValue:
            continue

        mark grid[cell] as newValue

        for each neighbor n of cell:
            if inBounds(n) and grid[n] == targetValue:
                push n onto S

    return grid

8.3 Scanline flood fill pseudocode

function floodFillScanline(grid, seed, targetValue, newValue):
    if grid[seed] != targetValue:
        return grid

    create an empty stack of intervals I
    push interval (seed.row, seed.col, seed.col) onto I

    while I is not empty:
        (row, left, right) = pop I

        // Extend to the left
        l = left
        while l - 1 is inBounds and grid[row][l - 1] == targetValue:
            l = l - 1

        // Extend to the right
        r = right
        while r + 1 is inBounds and grid[row][r + 1] == targetValue:
            r = r + 1

        // Fill the span
        for col from l to r:
            if grid[row][col] == targetValue:
                grid[row][col] = newValue

        // Check the row above for new spans
        for col from l to r:
            if row - 1 is inBounds and grid[row - 1][col] == targetValue:
                // Find contiguous span in the row above
                colStart = col
                while col is inBounds and grid[row - 1][col] == targetValue:
                    col = col + 1
                colEnd = col - 1
                push interval (row - 1, colStart, colEnd) onto I

        // Check the row below similarly
        for col from l to r:
            if row + 1 is inBounds and grid[row + 1][col] == targetValue:
                colStart = col
                while col is inBounds and grid[row + 1][col] == targetValue:
                    col = col + 1
                colEnd = col - 1
                push interval (row + 1, colStart, colEnd) onto I

    return grid

(Real implementations typically optimize the “scan for contiguous spans” loops to avoid repeated work.)

9 Testing and verification

Flood fill is straightforward but easy to get wrong due to boundary conditions, connectivity choices, and matching criteria.

9.1 Test cases (small grids, narrow corridors, enclosed regions)

Useful test scenarios include:

  • Single-cell region: seed matches but all neighbors do not.
  • Full grid match: all cells satisfy the criteria.
  • Narrow corridor: long, thin eligible paths to stress stack/queue behavior.
  • Enclosed pockets: eligibility that forms cavities separated by ineligible cells.
  • Connectivity-sensitive cases: regions connected diagonally but not orthogonally (tests 4-way vs 8-way behavior).
  • Value mismatch: seed does not match the target criterion.

9.2 Property-based testing ideas

Property-based tests can validate invariants without enumerating all outcomes. Examples include:

  • Termination: the algorithm finishes on finite grids.
  • Containment: every modified cell belongs to the seed’s eligible connected region.
  • Maximality: no eligible cell in the region is left unmodified.
  • Idempotence under fixed criteria: if rerun with targetValue equal to the already-painted value, no further changes occur (depending on recoloring logic).

9.3 Visual regression testing approaches

In graphics-related applications, visual regression helps ensure flood fill behaves as expected. A common workflow:

  1. Run flood fill on a set of input images or tilemaps.
  2. Store expected outputs.
  3. Compare new results using pixel-diff thresholds or region-based similarity metrics.

This is particularly helpful when performance optimizations or tolerance changes are introduced.

10 Practical tips and common pitfalls

Many flood fill failures stem from small implementation decisions.

10.1 Choosing neighbor connectivity correctly

Before coding, determine whether diagonal adjacency should connect regions. The wrong connectivity choice can make results look “leaky” or artificially split. For tilemaps, designers often expect game-specific connectivity rules that may not align with standard 4-way or 8-way settings.

10.2 Preventing infinite loops on unchanged seeds

If recoloring is performed by setting the new value, a standard pitfall is failing to update cells in a way that prevents them from continuing to satisfy the eligibility test. For example, if the algorithm marks visited cells too late or compares against the wrong target value, it can re-enqueue the same locations repeatedly. Ensuring cells stop matching after processing (or using a visited structure) prevents this.

10.3 Balancing speed vs. memory in real systems

Trade-offs depend on constraints:

  • BFS tends to be predictable but can require substantial queue memory.
  • DFS can be memory-efficient for certain shapes but needs care to avoid deep recursion.
  • Scanline fill can reduce operations for span-like regions but requires more complex logic.
  • Union-find can speed up repeated queries after preprocessing but costs time and memory up front.

Selecting an approach typically depends on typical region sizes, frequency of operations, and whether the grid is static or dynamic.