How to code a paint bucket tool with the flood fill technique
Ever wonder how the paint bucket tool works? When you go into something like MS Paint, if you ever want to fill up a specific area, all you have to do is click a color, the paint bucket, and one specific pixel in the region you want to fill. Then, as if by magic, the area is filled. But why? Or more specifically, how exactly does the code work?
First, to simplify this problem, imagine that the area you need to fill is composed entirely of individual pixels (just like in MS Paint!). This changes the problem from filling a rough blob to an area with strict horizontal and vertical borders.
Now, this is where the flood fill technique comes in. Flood fill starts from a point and “spills” outward until it hits a wall. To illustrate this algorithm, take a look at this grid (note that it follows the definition above):
Here, gray squares denote the borders that block the spread of the flood fill, and white squares are open squares that can be filled. Now, how will the flood fill algorithm fill the space from here?
As seen here, the algorithm will first find a pixel to process and fill in (red). Then, it stores any adjacent, open pixels that have not yet been processed (light green). Once the original pixel finishes processing, it is removed from storage and marked as visited so it isn’t processed again (dark green). After, the algorithm will pick a stored pixel (light green) to process. Can you see how every pixel reachable from the start pixel will be eventually colored in?
Note: Flood fill can be implemented by adapting either Breadth-First-Search or Depth-First-Search for grids.
Here’s what the code for flood fill for the above example looks like:
grid = [[False, False, False, True, False, False],[False, True, True, False, True, False],[False, False, True, False, True, False],[False, True, True, True, True, False],[False, False, True, True, True, False],[False, False, False, False, False, False]]
starting_point = [3,2]
for row in your_grid:
str = ""
for box in row:
str += "O"
str += "X"
if not grid[current_point][current_point]:
grid[current_point][current_point] = False
directions = [[1,0],[-1,0],[0,1],[0,-1]]
for direction in directions:
adjacent_point = [current_point+direction,current_point+direction]
if adjacent_point < 0 or adjacent_point > 5 or adjacent_point < 0 or adjacent_point > 5:
print("Flood filled grid:")
Flood fill has the very obvious real-world application of filling an area in graphics applications. However, it can also help with searching a bounded area. There are plenty of other, more efficient methods to perform a flood fill; the one we’ve shown is the easiest to understand and we encourage everyone to Google flood fill algorithms for more advanced versions!
You can play with all the code we've used in this article on Replit: