Flood fill

Flood fill, also called seed fill, is a recursive algorithm that determines connected regions in an array. It's used in the "bucket" fill tool of [paint programs]? to determine which part of a bitmap to fill with color, in Tetris implementations for determing what falls and what doesn't, and in [Puyo Puyo]? and [Magical Drop]? implementations for determining what pieces are cleared.

Flood fill takes three parameters: seed point, source symbol, and destination symbol. Normally, a helper function wraps around flood fill and initializes the source symbol from the symbol under the provided point.

1. Look to the left of the current element for more elements that match the source symbol. Stop when you find the edge of the array or an element not of the source color.
2. Look to the right of the current element for more elements that match the source symbol.
3. Fill this horizontal line with the destination symbol.
4. For each element above or below (or in 3D, in front of or behind) an element in the horizontal line that matches the source symbol, run flood fill on that element.

Adapting the algorithm to use an additional array to store the shape of the region allows generalization to cover "fuzzy" flood filling, where an element can differ by up to a specified threshold from the source symbol, and the edges of the filled region blend somewhat smoothly with the not-filled region.