| rdfs:comment | - Flood fill, also called seed fill, is an algorithm that determines the area that are connected to a given node in a multi-dimensional array. It is used in the "bucket" fill tool of paint programs to determine which parts of a bitmap to fill with color, and in puzzle games such as Puyo Puyo, Lumines, Magical Drop, and some implementations of Tetris (but not Columns) for determining which pieces are cleared. An explicitly queue-based implementation might resemble the following:
|
| abstract | - Flood fill, also called seed fill, is an algorithm that determines the area that are connected to a given node in a multi-dimensional array. It is used in the "bucket" fill tool of paint programs to determine which parts of a bitmap to fill with color, and in puzzle games such as Puyo Puyo, Lumines, Magical Drop, and some implementations of Tetris (but not Columns) for determining which pieces are cleared. The flood fill algorithm takes three parameters: a start node, a target color, and a replacement color. The algorithm looks for all nodes in the array which are connected to the start node by a path of the target color, and changes them to the replacement color. There are many ways in which the flood-fill algorithm can be structured, but they all make use of a queue or stack data structure, explicitly or implicitly. One implicitly stack-based (recursive) flood-fill implementation (for a two-dimensional array) goes as follows: Image:Recursive Flood Fill 4 (aka).gif Image:Recursive Flood Fill 8 (aka).gif Flood-fill (node, target-color, replacement-color): 1. If the color of node is not equal to target-color, return. 2. Set the color of node to replacement-color. 3. Perform Flood-fill (one step to the west of node, target-color, replacement-color). Perform Flood-fill (one step to the east of node, target-color, replacement-color). Perform Flood-fill (one step to the north of node, target-color, replacement-color). Perform Flood-fill (one step to the south of node, target-color, replacement-color). 4. Return. An explicitly queue-based implementation might resemble the following: Flood-fill (node, target-color, replacement-color): 1. Set Q to the empty queue. 2. If the color of node is not equal to target-color, return. 3. Add node to the end of Q. 4. For each element n of Q: 5. Set the color of n to replacement-color. 6. If the color of the node to the west of n is target-color, add that node to the end of Q. If the color of the node to the east of n is target-color, add that node to the end of Q. If the color of the node to the north of n is target-color, add that node to the end of Q. If the color of the node to the south of n is target-color, add that node to the end of Q. 7. Continue looping until Q is exhausted. 8. Return. Most practical implementations use a loop for the west and east directions as an optimization to avoid the overhead of queue management: Flood-fill (node, target-color, replacement-color): 1. Set Q to the empty queue. 2. If the color of node is not equal to target-color, return. 3. Add node to the end of Q. 4. For each element n of Q: 5. Set w and e equal to n. 6. Move w to the west until the color of the node to the west of w no longer matches target-color. 7. Move e to the east until the color of the node to the east of e no longer matches target-color. 8. Set the color of nodes between w and e to replacement-color. 9. For each node n between w and e: 10. If the color of the node to the north of n is target-color, add that node to the end of Q. If the color of the node to the south of n is target-color, add that node to the end of Q. 11. Continue looping until Q is exhausted. 12. Return. 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. Using this additional array as an alpha channel allows the edges of the filled region to blend somewhat smoothly with the not-filled region.
|
