Flood fill
|
|
Flood fill, also called seed fill, is a recursive algorithm that determines connected regions in a multi-dimensional array. It is used in the "bucket" fill tool of paint programs to determine which part of a bitmap to fill with color, in Tetris implementations for determining 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: start element, source symbol, and destination symbol. It changes every element in the array that is connected to the start element and that contains the source symbol to the destination symbol. Normally, a helper function wraps around flood fill and initializes the source symbol from the symbol under the provided point.
- If the start element does not contain the source symbol, or if the source symbol equals the destination symbol, stop.
- Look to the left of the start element for more elements that match the source symbol. Stop when you find the edge of the array or an element not containing the source symbol.
- Look to the right of the current element for more elements that match the source symbol.
- Fill this horizontal line with the destination symbol.
- For each element above or below (or in 3D, in front of or behind) an element in the horizontal line just filled, run flood fill on that element, keeping source and destination symbol the same.
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.