The flood fill algorithm is a method of determining connected regions in an array (e.g. for filling an area of pixels with a colour).

Implementations

Pseudocode

One implicitly stack-based recursion flood-fill implementation (for a two-dimensional array) goes as follows:

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.

ActionScript (Flash)

      fill_map = new Array();
      fill_map[0] = [1, 1, 1, 1, 1, 1, 1, 1, 1];
      fill_map[1] = [1, 0, 0, 0, 1, 0, 0, 0, 1];
      fill_map[2] = [1, 0, 0, 0, 1, 0, 0, 0, 1];
      fill_map[3] = [1, 0, 0, 1, 0, 0, 0, 0, 1];
      fill_map[4] = [1, 1, 1, 0, 0, 0, 1, 1, 1];
      fill_map[5] = [1, 0, 0, 0, 0, 1, 0, 0, 1];
      fill_map[6] = [1, 0, 0, 0, 1, 0, 0, 0, 1];
      fill_map[7] = [1, 0, 0, 0, 1, 0, 0, 0, 1];
      fill_map[8] = [1, 1, 1, 1, 1, 1, 1, 1, 1];
      for (y=0; y<9; y++) {
          for (x=0; x<9; x++) {
              tile = _root.attachMovie("tile", "tile_"+(y+x*9), _root.getNextHighestDepth(), {_x:y*50, _y:x*50});
              tile.gotoAndStop(1+fill_map[x][y]);
          }
      }
      _root.attachMovie("cursor", "cursor", _root.getNextHighestDepth());
      cursor.onEnterFrame = function() {
          this._x = 50*Math.floor(_root._xmouse/50);
          this._y = 50*Math.floor(_root._ymouse/50);
      };
      _root.onMouseDown = function() {
          pos_x = Math.floor(_root._xmouse/50);
          pos_y = Math.floor(_root._ymouse/50);
          flood_fill(pos_x, pos_y);
      };
      function flood_fill(x, y) {
          pos = x+y*9;
          if (fill_map[y][x] == 0) {
              fill_map[y][x] = 2;
              _root["tile_"+(x+y*9)].gotoAndStop(3);
              flood_fill(x+1,y);
              flood_fill(x-1,y);
              flood_fill(x,y+1);
              flood_fill(x,y-1);
          }
      }

C

 #define BOARD_WIDTH  10
 #define BOARD_HEIGHT 20
 
 typedef struct MAP
 {
   unsigned char b[BOARD_HEIGHT][BOARD_WIDTH];
 } MAP;
 static void flood_loop(MAP *map, int x, int y,
                        unsigned int dst_c, unsigned  int src_c)
 {
   int fillL, fillR, i;
   int in_line = 1;
   //unsigned char c = src_c, fillC = dst_c;
 
   /* find left side, filling along the way */
   fillL = fillR = x;
   while( in_line )
   {
     map->b[y][fillL] = dst_c;
     fillL--;
     in_line = (fillL < 0) ? 0 : (map->b[y][fillL] == src_c);
   }
   fillL++;
   /* find right side, filling along the way */
   in_line = 1;
   while( in_line )
   {
     map->b[y][fillR] = dst_c;
     fillR++;
     in_line = (fillR > BOARD_WIDTH-1) ? 0 : (map->b[y][fillR] == src_c);
   }
   fillR--;
   /* search top and bottom */
   for(i = fillL; i <= fillR; i++)
   {
     if( y > 0 && map->b[y - 1][i] == src_c )
         flood_loop(map, i, y - 1, dst_c, src_c);
     if( y < BOARD_HEIGHT-1 && map->b[y + 1][i] == src_c )
         flood_loop(map, i, y + 1, dst_c, src_c);
   }
 }
 void flood_fill(MAP *map, int x, int y, unsigned int c)
 {
   flood_loop(map, x, y, c, map->b[y][x]);
   map->b[y][x] = c;  /* some buggy optimizers needed this line */
 }

Micromouse

Implemented in C

    #define NORTH      1
    #define EAST       2
    #define SOUTH      4
    #define WEST       8           
    #define VISITED      16
    #define ONROUTE      32

    #define NOTNORTH  (255-NORTH)
    #define NOTEAST   (255-EAST)
    #define NOTSOUTH  (255-SOUTH)
    #define NOTWEST   (255-WEST)
    #define ALLWALLS  (NORTH|EAST|SOUTH|WEST)     

    // maze storage
    #define NUMCELLS 256
    extern CELL maze[NUMCELLS] ;
    extern CELL map[NUMCELLS];

    /*
      floodMaze solves the maze using wall data found in the array maze
      and places the flooding data - effectively the routemap - into
      the array map. The destination cell is passed in to the function
      to allow solving for any location.
      The state of map on entry is not important and it is not important
      whether all the walls have been found. The algorithm simply performs
      the flood based on what it knows at the time it is called.
      At worst, up to 255 passes are made through the maze date in generating
      the map. If that many passes are made, there has been an error and
      the maze should be considered to be seriously in error.
      Passes of the algorithm are made until either the limit has been reached
      or the change flag indicates that none of the map data has changed in
      that pass. At that point the maze can be considered to have been solved.
      Clearly, unless all the walls have been observed, the map will contain
      invalid paths. The mouse will discover new walls and call the solver again
      as needed.
      The function returns the number of passes required to solve the maze.
      A returned value of 255 indicates an error.
      Note that the array is allowed to wrap around in a most dangerous
      manner by relying on the 8 bit pointer.
      This should not be a real problem in as much as the existence of the outer
      walls means we never have to make use of the value
    */

    UCHAR floodMaze(UCHAR goal)
    {
      UCHAR i,j;
      UCHAR now,next;
      UCHAR passes;
      UCHAR cellwalls;    // the wall data for a given cell
      UCHAR changed;

      i = 0;
      do{
        map[i--] = 255;
      } while (i);

      map[goal]=0;
      passes = 0;
      now = 0;
      next = now+1;
      do
      {
        changed = 0;
        i = 0;
        do
        {
          if (map[i]==now)
          {
            cellwalls=maze[i];
            if ((cellwalls & NORTH) == 0)
            {
              j = i+1;
              if (map[j] == 255){ map[j] = next; changed=1;}
            }
            if ((cellwalls & EAST) == 0)
            {
              j = i + 16;
              if (map[j] == 255){ map[j] = next; changed=1;}
            }
            if ((cellwalls & SOUTH) == 0)
            {
              j = i + 255;
              if (map[j] == 255){ map[j] = next; changed=1;}
            }
            if ((cellwalls & WEST) == 0)
            {
              j = i + 240;
              if (map[j] == 255){ map[j] = next; changed=1;}
            }
          }
          i--;
        } while(i);
        now  = now+1;
        next = now+1;
        passes++;
      } while(changed);
      return passes;
    }

Java

This is next algorithm adapted by Claudio Santana and Damian Johnson for Java:

  /**
   * Fills the selected pixel and all surrounding pixels of the same color with the fill color.
   * @param img image on which operation is applied
   * @param fillColor color to be filled in
   * @param loc location at which to start fill
   * @throws IllegalArgumentException if loc is out of bounds of the image
   */
  public static void floodFill(BufferedImage img, Color fillColor, Point loc) {
    if (loc.x < 0 || loc.x >= img.getWidth() || loc.y < 0 || loc.y >= img.getHeight()) throw new IllegalArgumentException();
    
    WritableRaster raster = img.getRaster();
    int[] fill =
        new int[] {fillColor.getRed(), fillColor.getGreen(), fillColor.getBlue(),
            fillColor.getAlpha()};
    int[] old = raster.getPixel(loc.x, loc.y, new int[4]);
    
    // Checks trivial case where loc is of the fill color
    if (isEqualRgba(fill, old)) return;
    
    floodLoop(raster, loc.x, loc.y, fill, old);
  }
  
  // Recursively fills surrounding pixels of the old color
  private static void floodLoop(WritableRaster raster, int x, int y, int[] fill, int[] old) {
    Rectangle bounds = raster.getBounds();
    int[] aux = {255, 255, 255, 255};
    
    // finds the left side, filling along the way
    int fillL = x;
    do {
      raster.setPixel(fillL, y, fill);
      fillL--;
    } while (fillL >= 0 && isEqualRgba(raster.getPixel(fillL, y, aux), old));
    fillL++;
    
    // find the right right side, filling along the way
    int fillR = x;
    do {
      raster.setPixel(fillR, y, fill);
      fillR++;
    } while (fillR < bounds.width - 1 && isEqualRgba(raster.getPixel(fillR, y, aux), old));
    fillR--;
    
    // checks if applicable up or down
    for (int i = fillL; i <= fillR; i++) {
      if (y > 0 && isEqualRgba(raster.getPixel(i, y - 1, aux), old)) floodLoop(raster, i, y - 1,
          fill, old);
      if (y < bounds.height - 1 && isEqualRgba(raster.getPixel(i, y + 1, aux), old)) floodLoop(
          raster, i, y + 1, fill, old);
    }
  }
  
  // Returns true if RGBA arrays are equivalent, false otherwise
  // Could use Arrays.equals(int[], int[]), but this is probably a little faster...
  private static boolean isEqualRgba(int[] pix1, int[] pix2) {
    return pix1[0] == pix2[0] && pix1[1] == pix2[1] && pix1[2] == pix2[2] && pix1[3] == pix2[3];
  }

Matlab

function flood_fill(xc,yc,x,y,new,old,width,height)
% flood fills area of matrix
% (xc,yc) = start point of flood fill
% (x,y) = current test location
% new = new value to be filled
% old = old value to replace
%
% example use:
% global fill
% width = 20;
% height = 20;
% fill = zeros(width,height);
% new = 1;
% old = 0;
% xc = 10;
% yc = 10;
% flood_fill(xc,yc,xc,yc,new,old,width,height);
%
% Results:
% The flood fill will alter all values of 0 to one flood filling from a
% start point (xc,yc)
% If the flood fill starts in an enclosed space it will fill up to the
% boundary
%
% Author: James Goodwin, June 2003
% email: JamesRichardGoodwin@lyocs.com


global fill;
global call;

call = call + 1;

if (x<2 || x>=width)
    x = xc;
end

if (y<2 || y>=height)
    y = yc;
end

if (fill(y,x) == old) 
    fill(y,x) = new;
    flood_fill(xc,yc,x+1,y,new,old,width,height);
    flood_fill(xc,yc,x,y+1,new,old,width,height);
    flood_fill(xc,yc,x-1,y,new,old,width,height);
    flood_fill(xc,yc,x,y-1,new,old,width,height);
end

OCaml

Naive non-tail-recursive implementation (this is more than adequate in practice because OCaml only allocates tiny stack frames, allowing deep recursion):

# let rec flood img targ repl (x, y) =
    match try Some img.(x).(y) with _ -> None with
    | Some color when color = targ ->
        img.(x).(y) <- repl;
        let f = flood img targ repl in
        f(x-1, y); f(x+1, y); f(x, y-1); f(x, y+1)
    | _ -> ();;
val flood : 'a array array -> 'a -> 'a -> int * int -> unit = <fun>

For example:

# let test =
    Array.init 10 (fun y -> Array.init 10 (fun x -> if (x+1)/(y+1)<2 then 1 else 0));;
val test : int array array =
  [|[|1; 0; 0; 0; 0; 0; 0; 0; 0; 0|];
    [|1; 1; 1; 0; 0; 0; 0; 0; 0; 0|];
    [|1; 1; 1; 1; 1; 0; 0; 0; 0; 0|];
    [|1; 1; 1; 1; 1; 1; 1; 0; 0; 0|];
    [|1; 1; 1; 1; 1; 1; 1; 1; 1; 0|];
    [|1; 1; 1; 1; 1; 1; 1; 1; 1; 1|];
    [|1; 1; 1; 1; 1; 1; 1; 1; 1; 1|];
    [|1; 1; 1; 1; 1; 1; 1; 1; 1; 1|];
    [|1; 1; 1; 1; 1; 1; 1; 1; 1; 1|];
    [|1; 1; 1; 1; 1; 1; 1; 1; 1; 1|]|]
# flood test 1 2 (0,0); test;;
- : int array array =
[|[|2; 0; 0; 0; 0; 0; 0; 0; 0; 0|];
  [|2; 2; 2; 0; 0; 0; 0; 0; 0; 0|];
  [|2; 2; 2; 2; 2; 0; 0; 0; 0; 0|];
  [|2; 2; 2; 2; 2; 2; 2; 0; 0; 0|];
  [|2; 2; 2; 2; 2; 2; 2; 2; 2; 0|];
  [|2; 2; 2; 2; 2; 2; 2; 2; 2; 2|];
  [|2; 2; 2; 2; 2; 2; 2; 2; 2; 2|];
  [|2; 2; 2; 2; 2; 2; 2; 2; 2; 2|];
  [|2; 2; 2; 2; 2; 2; 2; 2; 2; 2|];
  [|2; 2; 2; 2; 2; 2; 2; 2; 2; 2|]|]

Queue-based version:

# let rec flood img targ repl = function
    | [] -> ()
    | (x, y) :: t ->
        match try Some img.(x).(y) with _ -> None with
        | Some color when color = targ ->
            img.(x).(y) <- repl;
            flood img targ repl
              ((x-1, y) :: (x+1, y) :: (x, y-1) :: (x, y+1) :: t)
        | _ -> flood img targ repl t;;
val flood : 'a array array -> 'a -> 'a -> (int * int) list -> unit = <fun>

Continuation passing style (CPS) uses a stack of closures which is shorter but slower than the explicit queue:

# let rec flood img targ repl (x, y) k () =
    match try Some img.(x).(y) with _ -> None with
    | Some color when color = targ ->
        img.(x).(y) <- repl;
        let f = flood img targ repl in
        f(x-1, y) (f(x+1, y) (f(x, y-1) (f(x, y+1) k))) ()
    | _ -> k();;
val flood : 'a array array -> 'a -> 'a -> int * int -> unit = <fun>

Perl

Assuming floodfill_*, col and the four directions are methods on some object whose instance is passed as first argument as per standard method call syntax.

sub col;    # implementation
sub west;   # left
sub east;   # as exercise
sub north;  # for
sub south;  # the reader

sub floodfill_stack {
    my $self    = shift;
    my $target  = shift;
    my $repl    = shift;

    return unless $target eq $self->col;    # get
=pod
One might either overload the eq resp. == operator
here if a colour cannot be expressed in primitive
types, or write an encapsulating method for
comparison instead:   $target->equals($self->col)
=cut

    $self->col($repl);      # set
    $self->$_->floodfill_stack($target, $repl)
        for qw(west east north south);
    return;
};

sub floodfill_queue {
    my $self    = shift;
    my $target  = shift;
    my $repl    = shift;

    my @q;
# thanks to Perl arrays, queue management is totally painless

    return unless $target eq $self->col;    # get
    push @q, $self;
    while (my $n = shift @q) {
=pod
Be careful that the assignment to $n evaluates true in
boolean context, else the loop ends prematurely. Since
$n is supposed to be an object instance and not just a
primitive number, that accident will not happen. $n is
only ever undef when the @q is actually emptied.
=cut
        $n->col($repl);     # set
        for (qw(west east north south)) {
            push @q, $n->$_ if $target eq $n->$_->col;
        };
    };
};

Python

Assuming floodfill_*, and the four directions are methods in some class, and color is an instance variable.

class ?:
                             # implementation
    def west(self): pass     # left
    def east(self): pass     # as exercise
    def north(self): pass    # for
    def south(self): pass    # the reader

    def floodfill_stack(self, target, repl):
        if target != self.color:
            return

        self.color = repl
        for x in [self.west(), self.east(), self.north(), self.south()]:
            x.floodfill_stack(target, repl)
        return

    def floodfill_queue(self, target, repl):
        if target != self.color:
            return

        q = [self]
        while q:
            n = q.pop(0)
            n.color = repl
            for x in [n.west(), n.east(), n.north(), n.south()]:
                if x.color == target:
                    x.color = repl
                    q.append(x)