What is the floodfill algorithm?
Click the image below to randomly colour the region you click.
Go ahead, try it!
If you click the image, you will see colour spread out from the place you clicked, filling in the region you clicked on. If you click one of the eyes of the snakes, the eye fills pretty quickly and you can barely see it... If you click one of the snakes, you can see the colour spread to fill the entire snake... And if you click the outside area, you see the colour spread in weird ways, going around the snakes and into the tight corners between the two snakes.
But regardless of where you click, you see that the colour spreading will always stay inside the region you clicked. And the floodfill algorithm is the algorithm that allows you to implement this behaviour:
- spread out from the starting point; but
- remain constrained inside a region.
Understanding the floodfill algorithm
The floodfill algorithm does not have a lot of moving parts and, because it can be visualised as paint filling up a region of a drawing, it is a great stepping stone for someone looking to learn more about graph algorithms. Now, you'll understand how it works in the context of painting the Python logo.
The algorithm will be implemented as a function floodfill with two arguments:
- a grid representing the locations of the walls; and
- the
xandycoordinates of the starting point (the place you clicked).
def floodfill(walls, x, y):
passOk, I lied. The function has three arguments, really.
If the position you click is a wall, you don't want to do anything and you return from the function right away:
def floodfill(walls, x, y):
if walls[y][x]:
returnIn here, you can assume that walls is a list of lists, where each list represents a row of the image.
So, the first piece of code checks if you clicked a wall, because you don't want to change the colour of walls.
Next, you need a way to represent the growing region of colour, and that's represented by a growing collection of all of the pixels you already painted. To make it very efficient, you can use a set instead of a list, and this set starts empty because you haven't painted anything yet:
def floodfill(walls, x, y):
if walls[y][x]:
return
painted = set() # <--You also need another collection to keep track of all the points you still need to paint. In the beginning, you already know you have to paint your starting point:
def floodfill(walls, x, y):
if walls[y][x]:
return
painted = set()
to_paint = [(x, y)] # <--Now comes the fun part, which is the while loop that ensures your painted region keeps growing to fill in every empty spot!
You want to write a loop that runs while there are pixels to be painted:
def floodfill(walls, x, y):
if walls[y][x]:
return
painted = set()
to_paint = [(x, y)]
while to_paint: # <--
... # <--Inside this loop you need to do four things:
- get a new pixel to process from the list of pixels to process;
- paint the pixel you're processing now;
- mark this pixel as having been painted; and
- find if the neighbours of the current pixel must be painted also.
To do the first thing, you can just pop from the list to_paint:
def floodfill(walls, x, y):
if walls[y][x]:
return
painted = set()
to_paint = [(x, y)]
while to_paint:
this = to_paint.pop() # <--To paint this pixel, you can assume you have an auxiliary function that does that:
def draw_pixel(p): pass # Do-nothing; just so the code works.
def floodfill(walls, x, y):
if walls[y][x]:
return
painted = set()
to_paint = [(x, y)]
while to_paint:
this_pixel = to_paint.pop()
draw_pixel(this_pixel) # <--And now that your pixel has been painted, you can mark it as having been painted:
def draw_pixel(p): pass # Do-nothing; just so the code works.
def floodfill(walls, x, y):
if walls[y][x]:
return
painted = set()
to_paint = [(x, y)]
while to_paint:
this_pixel = to_paint.pop()
draw_pixel(this_pixel)
painted.add(this_pixel) # <--The fourth and final step is the most important one, though: “find if the neighbours of the current pixel must be painted also”.
One of my favourite ways of looking at the neighbours of a pixel is realising that the neighbours of a pixel have coordinates that are very similar to the original pixel; all I have to do is add or subtract 1 from either coordinate, as the diagram below shows:
To represent this, I usually create a list with the small offsets and then use a loop to go through the offsets and modify the coordinates of the base pixel:
neighbour_offsets = [(+1, 0), (0, +1), (-1, 0), (0, -1)] # <--
def draw_pixel(p): pass # Do-nothing; just so the code works.
def floodfill(walls, x, y):
if walls[y][x]:
return
painted = set()
to_paint = [(x, y)]
while to_paint:
this_pixel = to_paint.pop()
draw_pixel(this_pixel)
painted.add(this_pixel)
tx, ty = this_pixel # <--
for dx, dy in neighbour_offsets: # <--
nx, ny = tx + dx, ty + dy # <--The coordinates tx, ty represent the pixel you just painted; the offsets dx, dy represent the small jump you need to take from the base pixel to a neighbouring pixel; and the coordinates nx, ny represent the coordinates of the neighbour pixel.
For each of the neighbours, you need to check if that's still inside the grid and, if it is, if it's a wall or an empty space. If the neighbour is outside of the grid or a wall, you don't want to do anything with that neighbour and you skip to the next one:
neighbour_offsets = [(+1, 0), (0, +1), (-1, 0), (0, -1)]
def draw_pixel(p): pass # Do-nothing; just so the code works.
def floodfill(walls, x, y):
if walls[y][x]:
return
HEIGHT = len(walls)
WIDTH = len(walls[0])
painted = set()
to_paint = [(x, y)]
while to_paint:
this_pixel = to_paint.pop()
draw_pixel(this_pixel)
painted.add(this_pixel)
tx, ty = this_pixel
for dx, dy in neighbour_offsets:
nx, ny = tx + dx, ty + dy
if (
nx < 0 or nx >= WIDTH # Is nx too big/small?
or ny < 0 or ny >= HEIGHT # Is ny too big/small?
or walls[ny][nx] # Is this a wall?
):
continueIf the neighbour pixel is a valid pixel that is not a wall, then you can add it to the list of pixels to paint next! As long as this pixel hasn't been painted yet, of course:
neighbour_offsets = [(+1, 0), (0, +1), (-1, 0), (0, -1)]
def draw_pixel(p): pass # Do-nothing; just so the code works.
def floodfill(walls, x, y):
if walls[y][x]:
return
HEIGHT = len(walls)
WIDTH = len(walls[0])
painted = set()
to_paint = [(x, y)]
while to_paint:
print(to_paint)
this_pixel = to_paint.pop()
draw_pixel(this_pixel)
painted.add(this_pixel)
tx, ty = this_pixel
for dx, dy in neighbour_offsets:
nx, ny = tx + dx, ty + dy
if (
nx < 0 or nx >= WIDTH
or ny < 0 or ny >= HEIGHT
or walls[ny][nx]
):
continue
if (nx, ny) not in painted: # <--
to_paint.append((nx, ny)) # <--That's it! This is enough to use the floodfill algorithm and this is very close to what I actually used to paint the Python logo above.
Optimising the floodfill algorithm to avoid duplicated work
There is a key difference between the algorithm I'm using to paint the Python logo and the algorithm you just used, and it has to do with the role that the set painted has.
The main objective of the set painted is to avoid wasting time painting the same pixel more than once, but what you really want is to not waste any time whatsoever.
If you modify the function floodfill to add a couple of calls to print and if you call it with a small grid, you will find that you can end up with duplicated points in the list to_paint:
neighbour_offsets = [(+1, 0), (0, +1), (-1, 0), (0, -1)]
def draw_pixel(p): pass # Do-nothing; just so the code works.
def floodfill(walls, x, y):
# ...
painted = set()
to_paint = [(x, y)]
while to_paint:
print(to_paint) # <--
# ...
grid = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
floodfill(grid, 1, 1)[(1, 1)]
[(2, 1), (1, 2), (0, 1), (1, 0)]
[(2, 1), (1, 2), (0, 1), (2, 0), (0, 0)]
[(2, 1), (1, 2), (0, 1), (2, 0), (0, 1)]
# ...The first four lines of output are shown above and the fourth line of output has the pixel (0, 1) repeated in the third and fifth positions.
This means we'll process this pixel twice.
For this small 3 x 3 grid, this isn't a big problem...
But for big grids, these overlaps will be costly and waste a lot of your time.
Instead of keeping track of the pixels that have been painted already, you can keep track of the pixels that you already queued up for painting. This means you add a new pixel to the set at the same time as you add it to the list of pixels to paint:
neighbour_offsets = [(+1, 0), (0, +1), (-1, 0), (0, -1)]
def draw_pixel(p): pass # Do-nothing; just so the code works.
def floodfill(walls, x, y):
if walls[y][x]:
return
HEIGHT = len(walls)
WIDTH = len(walls[0])
tracked = set((x, y)) # <-- The starting point starts in the set.
to_paint = [(x, y)]
while to_paint:
this_pixel = to_paint.pop()
draw_pixel(this_pixel)
tx, ty = this_pixel
for dx, dy in neighbour_offsets:
nx, ny = tx + dx, ty + dy
if (
nx < 0 or nx >= WIDTH
or ny < 0 or ny >= HEIGHT
or walls[ny][nx]
):
continue
if (nx, ny) not in tracked: # <--
tracked.add((nx, ny)) # <-- Add it to the set right away.
to_paint.append((nx, ny))Visualising the floodfill algorithm step by step
Hopefull you understood the prose that explains the algorithm... But there's nothing like seeing it in action. The widget below lets you step through the floodfill algorithm as it fills the middle region of the grid that's seen below:
Become a better Python 🐍 developer, drop by drop 💧
Get a daily drop of Python knowledge. A short, effective tip to start writing better Python code: more idiomatic, more effective, more efficient, with fewer bugs. Subscribe here.
