page_title: Flood fill
section_title: The algorithm
hierarchical_section_title: Flood fill / The algorithm
caption_attribution_description: English: This image shows the running recursive flood fill algorithm with eight directions. This animation has been generated using the Perl script below. Deutsch: Dieses Bild zeigt den Ablauf des Floodfill-Algorithmus mit acht Richtungen. Die Animation wurde mit untenstehender Perl-Funktion erzeugt. Français&#160;: Cette image illustre l'exécution récursive de l'algorithme de remplissage par diffusion dans sa variante 8-connexe. Cette animation a été générée à l'aide du script Perl ci-dessous. ... sub FloodFill8 { my ($x, $y) = @_; if ($im-&gt;getPixel ($x, $y) == $colfill) { $im-&gt;setPixel ($x, $y, $colpen); WriteImage (); FloodFill8 ($x, $y+1); FloodFill8 ($x, $y-1); FloodFill8 ($x+1, $y); FloodFill8 ($x-1, $y); FloodFill8 ($x+1, $y+1); FloodFill8 ($x+1, $y-1); FloodFill8 ($x-1, $y+1); FloodFill8 ($x-1, $y-1); } } ...
context_page_description: Flood fill, also called seed fill, is an algorithm that determines the area connected to a given node in a multi-dimensional array. It is used in the "bucket" fill tool of paint programs to fill connected, similarly-colored areas with a different color, and in games such as Go and Minesweeper for determining which pieces are cleared.
context_section_description: 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 that 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.
  Depending on whether we consider nodes touching at the corners connected or not, we have two variations: eight-way and four-way respectively.
caption: Recursive flood fill with 8 directions