Flood Fill

This is a game, but it's also a gentle introduction to the idea of recursion. Flood fill is a good way to start learning about recursion because it's a more familiar concept than factorials or prime factorisation and uses a recursive procedure rather than a function - there are no return values to worry about.

The object of the game is to fill the board so that it's a single colour. You have a limited number of moves to do so, based on the number of squares in the grid. Click one of the coloured circles below the grid to flood fill from the top-left square. As the purpose of the game is also to demonstrate the flood-fill process you can use the Speed: slider to slow it down so that you can more easily see what it's doing.


Click one of the coloured circles to flood-fill from the top-left.

How Does It Work?

A flood fill is a common feature of painting applications (such as Microsoft Paint) - colour is applied from a selected point and "floods" all of the pixels until a different colour is reached. The tricky part is filling irregular spaces and going around "islands" of other colours. There are lots of different methods for performing a flood fill, but this page uses the recursive one.

In general terms, the recursive steps (adapted from Wikipedia) are as follows:

  1. if pixel is outside the fill area then return
  2. set the colour of the current pixel
  3. perform flood fill one step to the south of the current pixel
  4. perform flood fill one step to the north of current pixel
  5. perform flood fill one step to the west of current pixel
  6. perform flood fill one step to the east of current pixel
  7. return

For each pixel the algorithm either completes step 1 (when an edge is met and there is nothing to fill) or completes steps 2 to 7, re-colouring the current pixel and then checking the pixels around it. As with all recursive algorithms, step 1 is important because it's the stopping condition - without it the algorithm would go on forever.

This algorithm is recursive because the function calls itself. It's a procedure because there is no return value. The reason that recursion is necessary is for the fill to got around obstacles and possibly round corners and back on itself - you can't always only go down and right. You can see the order in which the pixels are filled (i.e. how the "flood" negotiates obstacles) in the game above by reducing the speed.

In this particular application, the flood() function takes four arguments - the colour being replaced, the new colour, and the x- and y- co-ordinates of the pixel being filled. The steps are as follows:

  1. if pixel co-ordinates are off the top, bottom, left or right of the grid OR the colour of the pixel isn't the colour being replaced then return
  2. set the colour of the current pixel to the new colour (the colours are stored in a list/array, but the web version also updates the display at this point)
  3. add one to the y-co-ordinate and call flood() again to fill the next pixel down
  4. subtract one from the y-co-ordinate and call flood() again to fill the next pixel up
  5. subtract one from the x-co-ordinate and call flood() again to fill the pixel to the left
  6. add one to the x-co-ordinate and call flood() again to fill the pixel to the right
  7. return

Although it always starts at the top-left, steps 4 and 5 are still necessary when filling around a pixel of a different colour, e.g. when going underneath a pixel and up the other side, or going down the right-hand side of a pixel and then round to the left.

You can see the flood() function by viewing the source of this page, but as it contains additional code required to slow it down, you might prefer to look at the Python version of Flood Fill that I created as a prototype.