Understanding and Visualizing the Flood Fill Algorithm in Python

The Flood Fill algorithm is one of the most recognized and foundational algorithms in computer graphics and grid-based pathfinding. Commonly recognized as the “bucket fill” or “paint bucket” tool in image editing software like MS Paint, Adobe Photoshop, or GIMP, Flood Fill determines and alters the area connected to a given node in a multi-dimensional array.

At its core, Flood Fill is a graph traversal problem operating on a 2D grid where neighboring pixels share an edge if they have the same color or fall within a boundary threshold.

---

Problem Definition

Given:

1. A 2D grid of dimensions $M \times N$.
2. A starting coordinate $(r, c)$, often called the seed point.
3. A target color/character currently located at $(r, c)$.
4. A replacement color/character to fill.
5. Defined boundaries (either specific boundary characters/colors or any pixel whose color differs from the target color).

The goal is to replace the target color at the seed point and all 4-way (or 8-way) connected neighboring cells matching that target color with the replacement color without crossing boundary lines.

Initial State:               After Flood Fill (from center):
####################         ####################
#                  #         #@@@@@@@@@@@@@@@@@@#
#   ############   #   ==>   #@@@############@@@#
#   #          #   #         #@@@#          #@@@#
#   ############   #         #@@@############@@@#
#                  #         #@@@@@@@@@@@@@@@@@@#
####################         ####################

---

Traversal Strategy: 4-Way vs. 8-Way Connectivity

When a cell $(r, c)$ is processed, its adjacent neighbors are explored. There are two primary connectivity models:

graph TD
    subgraph 4-Connected
        C4((r, c))
        C4 --> U4["Up: (r-1, c)"]
        C4 --> D4["Down: (r+1, c)"]
        C4 --> L4["Left: (r, c-1)"]
        C4 --> R4["Right: (r, c+1)"]
    end
    
    subgraph 8-Connected
        C8((r, c))
        C8 --> U8["Up / Down / Left / Right"]
        C8 --> D1["Top-Left: (r-1, c-1)"]
        C8 --> D2["Top-Right: (r-1, c+1)"]
        C8 --> D3["Bottom-Left: (r+1, c-1)"]
        C8 --> D4b["Bottom-Right: (r+1, c+1)"]
    end

• 4-Connected Neighborhood: Only horizontal and vertical steps are allowed. This is standard for enclosed outlines, preventing color from “leaking” through diagonal corners.
• 8-Connected Neighborhood: Includes diagonals. Often used when diagonal boundaries are explicitly padded or when filling freeform clusters.

---

Recursive Flood Fill: Mechanics & Base Cases

The most intuitive implementation uses Recursion (Depth-First Search). The algorithm evaluates the current coordinate and branches into adjacent coordinates.

Essential Guard Conditions (Base Cases)

Before coloring and recurring, the function must ensure:

1. Index Out of Bounds: The row $r$ or column $c$ is beyond the grid limits ($r < 0$, $r \ge M$, $c < 0$, or $c \ge N$).
2. Boundary Hit: The current cell is an impermeable boundary character (e.g., #).
3. Already Visited / Filled: The current cell already contains the replacement character (prevents infinite recursive loops).
4. Target Mismatch: The current cell is not of the target replacement type.

Recursive Flow Diagram

flowchart TD
    Start([flood_fill(r, c)]) --> CheckBounds{In Grid Bounds?}
    CheckBounds -- No --> Return([Return])
    CheckBounds -- Yes --> CheckTarget{Cell == Target Char?}
    CheckTarget -- No --> Return
    CheckTarget -- Yes --> Fill[Grid[r][c] = Replacement Char]
    Fill --> Render[Render & Sleep for Visualization]
    Render --> RecurseUp[flood_fill(r - 1, c)]
    RecurseUp --> RecurseDown[flood_fill(r + 1, c)]
    RecurseDown --> RecurseLeft[flood_fill(r, c - 1)]
    RecurseLeft --> RecurseRight[flood_fill(r, c + 1)]
    RecurseRight --> Return

---

Python Implementation with Terminal Visualization

Below is a complete, working script that transforms an ASCII canvas into a mutable 2D matrix, animates the recursive fill using standard terminal escape codes or screen clears, and visualizes how Depth-First Search expands through the bounded region.

import os
import time

# Sample ASCII canvas with enclosed boundaries
CANVAS_TEMPLATE = """
########################################
#                                      #
#      ##########################      #
#      #                        #      #
#      #    ################    #      #
#      #    #              #    #      #
#      #    #              #    #      #
#      #    ################    #      #
#      #                        #      #
#      ##########################      #
#                                      #
########################################
""".strip("\n")

def clear_screen():
    """Clears terminal screen across platforms."""
    os.system("cls" if os.name == "nt" else "clear")

def print_grid(grid):
    """Renders the 2D grid onto the console."""
    clear_screen()
    for row in grid:
        print("".join(row))

def flood_fill(
    grid,
    r,
    c,
    target_char=" ",
    fill_char="@",
    boundary_char="#",
    delay=0.01,
):
    rows = len(grid)
    cols = len(grid[0])

    # 1. Bounds check
    if r < 0 or r >= rows or c < 0 or c >= cols:
        return

    # 2. Boundary or already filled check
    if grid[r][c] == boundary_char or grid[r][c] == fill_char:
        return

    # 3. Target character check
    if grid[r][c] != target_char:
        return

    # 4. Fill current cell
    grid[r][c] = fill_char

    # 5. Visual output
    print_grid(grid)
    time.sleep(delay)

    # 6. Recurse in 4 orthogonal directions
    flood_fill(grid, r - 1, c, target_char, fill_char, boundary_char, delay)  # Up
    flood_fill(grid, r + 1, c, target_char, fill_char, boundary_char, delay)  # Down
    flood_fill(grid, r, c - 1, target_char, fill_char, boundary_char, delay)  # Left
    flood_fill(grid, r, c + 1, target_char, fill_char, boundary_char, delay)  # Right


def main():
    # Convert string canvas into a mutable list of character lists
    grid = [list(line) for line in CANVAS_TEMPLATE.split("\n")]

    # Choose a seed coordinate inside the outer corridor
    seed_row, seed_col = 1, 1

    print("Initial Canvas:")
    print_grid(grid)
    time.sleep(1)

    flood_fill(grid, seed_row, seed_col, target_char=" ", fill_char="*")

    print("\nFlood fill complete!")


if __name__ == "__main__":
    main()

---

Complexity Analysis

Dimension	Recursive DFS	Iterative BFS / DFS	Scanline Fill
Time Complexity	$O(M \times N)$	$O(M \times N)$	$O(M \times N)$
Space Complexity	$O(M \times N)$ call stack	$O(M \times N)$ queue/stack	$O(\text{Height})$
Cache Locality	Poor (non-contiguous jumps)	Moderate	High (scans rows contiguously)

• Time: In the worst-case scenario (an empty canvas), every cell is evaluated a constant number of times (at most 4 checks per cell). Hence, the time complexity is strictly linear with respect to the number of cells: $O(V) = O(M \times N)$.
• Space: The recursive call stack can grow up to the total number of cells in the bounded area. In an open $1000 \times 1000$ canvas, recursion depth reaches up to $10^6$ calls, which easily exceeds Python’s default recursion limit (sys.getrecursionlimit() = 1000) and causes a RecursionError: maximum recursion depth exceeded.

---

Production Trade-Offs & Advanced Optimizations

While the basic recursive flood fill is pedagogically clean, real-world graphics pipelines and production software avoid direct naive recursion for two main reasons:

1. Stack Overflow Vulnerability

Because standard recursion consumes system call-stack frames, modern engines implement Iterative Flood Fill using an explicit heap-allocated stack or queue:

def flood_fill_iterative(grid, start_r, start_c, target_char, fill_char):
    if grid[start_r][start_c] != target_char or target_char == fill_char:
        return

    stack = [(start_r, start_c)]
    rows, cols = len(grid), len(grid[0])

    while stack:
        r, c = stack.pop()

        if r < 0 or r >= rows or c < 0 or c >= cols:
            continue
        if grid[r][c] != target_char:
            continue

        grid[r][c] = fill_char

        # Add neighbors
        stack.append((r + 1, c))
        stack.append((r - 1, c))
        stack.append((r, c + 1))
        stack.append((r, c - 1))

2. Scanline Flood Fill

In computer graphics literature (e.g., standard algorithms described by Foley & Van Dam, and research papers on raster graphics optimization), Scanline Flood Fill is the preferred high-performance approach:

• Instead of visiting pixel-by-pixel in individual recursion steps, the algorithm finds contiguous horizontal runs of target pixels along a scanline (a row).
• It fills the entire horizontal segment in a tight CPU memory loop (leveraging CPU cache locality).
• It then inspects the scanlines directly above and below that segment to identify and push only the seed points of adjacent runs onto the stack.
• This dramatically bounds memory consumption and reduces stack depth from $O(M \times N)$ to $O(M)$.

---

Key Takeaways

1. Core Problem Model: Flood Fill is an unweighted graph traversal (DFS/BFS) operating on a 2D spatial grid.
2. Critical Edge Conditions: Boundary checks and immediate marking of visited nodes are essential to prevent infinite cycles.
3. Production Readiness: Naive recursion is great for understanding and small grids, but practical systems use explicit stack allocations or Scanline algorithms to ensure predictable memory usage and prevent call-stack exhaustion.