### Flood Fill

Flood fill is a topic that commonly comes up in discussions about graphic primitives. In this context, flood fill is an algorithm which files the inside of a bounded region with a value (i.e. fill a circle with the color green).

The base flood fill algorithm has many additional uses (some of which will be discussed below). To help visualize flood fill, imagine water being poured on top of a hill (and ignore it being absorbed by the dirt). The water will flow until it reaches the lowest point. The water "floods" the lowest places.

As normal, Wikipedia is a great place to go to learn about a topic (in this case flood fill).

Typically, flood fill processes a 2-D grid (2-D array). Normally it works by looking at the 8 (or 4) cells around a given location (x,y). Flood fill can be implemented both breadth first or depth first. If doing breadth first, the process can be done via two nested loops to process the matrix (slow but simple to code). Breadth first can also be done by storing next tries in a list. Depth first just about has to be implemented using a list of additional places to go to.

Here is a very simple, recursive implementation of depth first. It uses the stack of pending calls to store all of the future places to visit. The process of filling each spot marks it as found. Future visits may then visit this spot, discover it has been filled and then bail out (dynamic programming example - recursive implementation with result caching [marking of filled spots]).

FUNCTION fill(int x, int y) BEGIN map(x,y) = FULL FOR x1,y1=neighborOf(x,y) IF (EMPTY == map(x1,y1)) THEN fill(x1,y1) END IF END FOR ENDIn this example, neighborOf is a magic function that produces a list of all of the "neighboring" spots (i.e. the four or eight or whatever points that are adjacent to a given point).

Very similar code can implement breadth first (test 4 directions only):

FUNCTION fill(int x, int y) BEGIN map(x,y) = FULL IF (EMPTY == map(x+1, y) THEN fill(x+1, y) END IF IF (EMPTY == map(x-1, y) THEN fill(x-1, y) END IF IF (EMPTY == map(x, y+1) THEN fill(x, y+1) END IF IF (EMPTY == map(x, y-1) THEN fill(x, y-1) END IF END

Flood fill can be used to solve a maze. If you wanted to know if a maze is solvable (given a starting point, can you reach the ending point?), you do something like this:

FUNCTION fill(int x, int y) BEGIN map(x,y) = FULL FOR x1,y1=neighborOf(x,y) IF (EMPTY == map(x1,y1)) THEN fill(x1,y1) END IF END FOR END MAIN BEGIN fill(startX, startY) IF (filled(map(solveX, solveY))) THEN PRINT "solvable" ELSE PRINT "unsolvable" END IF END MAIN

Pretty cool! But now, I bet you want to know the minimum number of steps to solve the maze. Here is a variant that will do that. To do so, lets make some assumptions. The matrix (map) has a zero for empty places (where you can move) ans negative values to indicate where the walls are (where you cannot move.). Lets also assume the matrix is bounded by walls on all four edges.

FUNCTION fill(int x, int y, int level) BEGIN map(x,y) = level level = level + 1 FOR x1,y1=neighborOf(x,y) IF ((0 == map(x1,y1)) OR (level < map(x1,y1)) THEN fill(x1, y1, level) END MAIN BEGIN fill(startX, startY, 1) IF (0 == map(solveX, solveY)) THEN PRINT "unsolvable" ELSE PRINT map(solveX, solveY)," steps needed to solve" END IF END MAINOne of the drawbacks of depth first, is you might have a spot that has at least two paths to it and you might have arrived there via the longer path first. In these cases you have to back track and take the shorter path. The above code does this with the if test for

*level < map(x1,y1)*. If the next location has a larger value in it than level's current value, then it acts just like the cell is empty and moves forward (essentially implementing backtracking).

To avoid the need for back tracking/possibly visiting the same cell multiple times, you need to implement a breadth first flood fill. This means all "neighbors" of the current point must be visited before going to the next level. To do this, we are going to have to make a FIFO queue to store neighbors in. Here is fill implemented breadth first:

fill(int x, int y, int level) BEGIN level = level + 1 FOR x1,y1=neighborOf(x,y) IF (0 == map(x1,y1)) THEN map(x1,y1) = level enqueue(x1, y1) END IF WHILE NOT EMPTY(queue) x1,y1 = dequeue() fill(x1, y1, map(x1, y1) END WHILE END

This approach can be extended to 3-D easily by using a 3-D array and checking for neighbors in a way that checks in x, y and z directions. Flood fill can also be used to count how may different low points exist in a grid.

To get a good idea, of the number of different uses for flood fill, visit Problem categories and go through the section on flood fill.