Pathfinding Algorithm

Flood Fill

“The Completionist”

Time: O(V + E)

Space: O(V)

Shortest Path: Guaranteed

History

Flood Fill is a staple of computer graphics, famous for powering the "Paint Bucket" tool in MS Paint and Photoshop. While usually associated with image manipulation, in a graph context, it is simply a Breadth-First Search that has no brakes.

It doesn't stop when it sees the goal. It keeps going until it has visited every single reachable node. It is the cartographer of algorithms.

How It Works

Flood Fill performs a complete traversal of the connected component.

The Algorithm Step-by-Step

Start: Pick a seed node.
Spread: Visit all valid neighbors.
Recurse/Loop: Repeat for those neighbors.
Stop: Only stop when there are no unvisited neighbors left.

In Yield, we use this to generate a "Heatmap" or "Dijkstra Map." Instead of finding a path, we assign every tile a number representing its distance from the start. This creates a flow field that can guide hundreds of agents simultaneously.

Time ComplexityO(V + E)

It touches every pixel or node exactly once. It is linear relative to the size of the reachable area.

Space ComplexityO(V)

Recursion stack or queue size depends on the shape of the area to be filled.

Data StructureQueue or Stack

The core data structure powering Flood Fill.

Visual PatternA tidal wave filling every nook and cranny

How this algorithm appears during visualization.

Code Walkthrough

Real implementations in multiple programming languages. Select a language to view idiomatic code.

1from collections import deque
2
3def flood_fill(grid: list[list[int]], start: tuple[int, int]) -> dict[tuple[int, int], int]:
4    """Flood fill from start, returning distances to all reachable cells."""
5    rows, cols = len(grid), len(grid[0])
6    distances = {start: 0}
7    queue = deque([start])
8    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
9
10    while queue:
11        row, col = queue.popleft()
12        current_dist = distances[(row, col)]
13
14        for dr, dc in directions:
15            new_row, new_col = row + dr, col + dc
16            neighbor = (new_row, new_col)
17
18            if (0 <= new_row < rows and 0 <= new_col < cols
19                    and grid[new_row][new_col] == 0
20                    and neighbor not in distances):
21                distances[neighbor] = current_dist + 1
22                queue.append(neighbor)
23
24    return distances