In this article you will learn about the floodfill algorithm.
You will learn the intuitive explanation of the algorithm, how it can be used to colour regions in images, and how to implement it in Python.
You will also see three example applications of the floodfill algorithm, with interactive demos and code.
By the time you are finished reading this article, you will be able to apply the floodfill algorithm in your own projects and modify it or tweak it according to your needs and preferences.
What is the floodfill algorithm?
Click the image below to randomly colour the region you click.
Go ahead, try it!
IMG_WIDTH = 160
IMG_HEIGHT = 160
PIXEL_SIZE = 2
import asyncio
import collections
import itertools
from pyscript import display
from pyodide.ffi import create_proxy
import js
from js import fetch
canvas = js.document.getElementById("bitmap")
ctx = canvas.getContext("2d")
_BITMAP_COLOURS = itertools.cycle([AC_COLOUR, AC2_COLOUR, RE_COLOUR, BL_COLOUR, YE_COLOUR, GR_COLOUR, OR_COLOUR])
_ints = [0, 0, 0, 0, 0, 0, 0, 9903520019135137019840167936, 316912650047833978337321025536, 5069364463233662545642129457152, 40406362882311561545666757918720, 159723975628759174402796798607360, 628754697713202062365541686837248, 1216944576219100292990829487718400, 2433889152438200467762168756961280, 4543259751217974183408433589387264, 9086519502435948354150493226795008, 18173039004871896701827061989244928, 15586952552243794457451031487840256, 36366340612306816504545604379082752, 31189423920820070440268979792510976, 31224838909463946599208478310400000, 31214663042341020773348807509278720, 31295792680755627454903859026067456, 31295772873714998888819460640079872, 31295772873714998888819460640079872, 31214663042341020773208070020923392, 31214658090580863631686970424426496, 31224838909463946599067740822044672, 31191949318500212615924220889661440, 31174023946731360309543681570897920, 31158772525447364424556924360458240, 31153781151208965771288531091587072, 31153781151208965771288531091587072, 31153781151208965771288531091587072, 31153781151208965771288531091587072, 31153781151208965771288531091587072, 31153781151208965771288531091587072, 41538374867674158118542209162674176, 41538374867674158118542209162674176, 41538374867674158118542209162674176, 1813388729527496878325760, 1813388729531894857728000, 5444517870735014810951084025942904930304, 87112285931760246042160989809567281971200, 347088014259357233337105009500967893204992, 1372018503425223884684326417278139134115840, 2613368577952807399398716985189229563609088, 5226737155905614798797433970265209426542592, 9756576024357147624421876744396907856986112, 19513152048714295248843753488680566015623168, 39026304097428590497687506977247882333241344, 78052608194857180995375013954382514968641536, 78052608194857180995375013954382514968649728, 156105216389714361990750027908651780239548416, 133804471191183738849214309636003418733572096, 312210432779428723981500055817190310781399040, 267608942382367477698428619271893587769440256, 624420865558857447963000111634267371865126912, 535217884764734955396857238543673925841197056, 535217884764734955396857238543673925841198080, 1248841731117714895926000223268421494032571392, 1070435769529469910793714477087375339473079296, 1070435769529469910793714477087375339473079296, 1070435769529469910793714477087339055589363200, 2497683462235429791852000446537115666948820480, 2497683462235429791852000446537045298204642816, 2140871539058939821587428954175243260155397632, 2140871539058939821587428954176226223550629376, 2140871539058939821587428954176243815736673792, 2140871539058939821587428954182717740201018880, 2140871539058939821587428954191192775827916288, 4995366924470859583704000893143091548121990912, 4995366924470859583704000893352579299538896640, 4995366924470859583704000897667150887862142720, 4995366924470900148523208196270458264975574784, 4995366924471184102257659318649205691078674176, 4995366924472147516713832774153879352074307328, 4995366924475889621285706507409303589789632256, 4995366924480596407964353923103877354846422784, 4995366924489042763913674615590287289608046336, 4995366924507286632895834264625967053561399040, 4995366924543708928397916780318445517146162944, 4995366924533795900704132026398741298080122624, 2140871539205541078202623227998533436869445120, 2140871539185988835344703017709848286629725696, 2140871539354576223970255702273697839319090688, 2140871539312713330548318654518670712664753664, 2140871539649563589245765596919586662022907392, 2140871539648265515031131890012454037940604416, 2497683462752063329276215795575400873427209728, 2497683462749467180846948381761135625262599168, 1070435770708121297681120348763544019020024832, 1070435770728890485115259659277666004336905216, 1248841732317135470247545405458852896384752640, 1248841732311943173389010577830322400055531520, 535217885958963232859867593105574831864158208, 535217885958963232859867593105574831864166400, 624420866753085725426010466196168277888086016, 267608943576595755161438973833794493792415744, 312210433973657001444510410379091216804372480, 133804472385412016312224664197904324756561920, 156105217583942639453760382470552686262534144, 66902236789820146887617509379959240238678016, 78052609389085458458385368516283420991782912, 39026305291656867960697861539148788356546560, 19513153242942572711854108050581472039272448, 20906949817850736658200090442621994634313728, 10453475506039507060605222502318075184414720, 5226738350133892261807788532166115481092096, 1306685483204681162709713054552146185289728, 691454963811624423185783403544767058935808, 174224436863802173805581096441418979737600, 21777936483221741569526362504672367869952, 31153781153022354500604921737379840, 31153781153626817410377051952644096, 31153781153626817410377051952644096, 31153781153626817410377051952644096, 31153781151208965771288531091587072, 31153781151208965771288531091587072, 31153781151208965771288531091587072, 31153781151208965771288531091587072, 31153781151208965771288531091587072, 31153781151208965771288531091587072, 31153781151208974706430191794651136, 31153781151209002592719084472762368, 31153781151209035487010762786865152, 31153781151209095024597836624822272, 31153781151209076577853762915270656, 31153781151209224079748758553755648, 31153781151209187195267810389393408, 31153781151209187195267810389393408, 31153781151209224088755957808496640, 36346078009744051708279254882975744, 36346078009743922653128332954042368, 15576890575604621488479174058311680, 18173039004871970415021728557170688, 9086519502435985099512434151915520, 9086519502435951809185463605919744, 4543259751217974175949346706554880, 2433889152438200452843994991296512, 1216944576219100229377484751110144, 628754697713201800030863392505856, 157188674428300515591385421709312, 39930993907189793600699199651840, 10061976639316146531601490116608, 2534063261007325117889137082368, 158456325026222832177874206720, 4951760083354544804758290432, 0, 0, 0, 0, 0, 0, 0, 0, 0]
def parse_bitmap():
return [[1] * 160] + [
[1] + [int(c) for c in bin(i).removeprefix("0b").zfill(158)] + [1]
for i in _ints
] + [[1] * 160]
'''
async def load_bitmap(url: str) -> list[list[int]]:
# Fetch the text file from the URL
response = await fetch(url)
text = await response.text()
bitmap: list[list[int]] = []
for line in text.splitlines():
line = line.strip()
if not line:
continue
row = [int(ch) for ch in line if ch in "01"]
if row:
bitmap.append(row)
return bitmap
'''
def draw_bitmap(bitmap):
rows = len(bitmap)
cols = len(bitmap[0]) if rows > 0 else 0
if rows == 0 or cols == 0:
return
for y, row in enumerate(bitmap):
for x, value in enumerate(row):
if value == 1:
ctx.fillStyle = FG_COLOUR
else:
ctx.fillStyle = BG_COLOUR
ctx.fillRect(x * PIXEL_SIZE, y * PIXEL_SIZE, PIXEL_SIZE, PIXEL_SIZE)
async def fill_bitmap(bitmap, x, y):
if bitmap[y][x] == 1:
return
_neighbours = ((1, 0), (-1, 0), (0, 1), (0, -1))
ctx = canvas.getContext("2d")
ctx.fillStyle = next(_BITMAP_COLOURS)
def draw_pixel(x, y):
ctx.fillRect(x * PIXEL_SIZE, y * PIXEL_SIZE, PIXEL_SIZE, PIXEL_SIZE)
pixels = collections.deque([(x, y)])
seen = set((x, y))
while pixels:
nx, ny = pixels.pop()
draw_pixel(nx, ny)
for dx, dy in _neighbours:
x_, y_ = nx + dx, ny + dy
if x_ < 0 or x_ >= IMG_WIDTH or y_ < 0 or y_ >= IMG_HEIGHT or (x_, y_) in seen:
continue
if bitmap[y_][x_] == 0:
seen.add((x_, y_))
pixels.appendleft((x_, y_))
await asyncio.sleep(0.0001)
is_running = False
def get_event_coords(event):
"""Return (clientX, clientY) for mouse/pointer/touch events."""
# PointerEvent / MouseEvent: clientX/clientY directly available
if hasattr(event, "clientX") and hasattr(event, "clientY") and event.clientX is not None:
return event.clientX, event.clientY
# TouchEvent: use the first touch point
if hasattr(event, "touches") and event.touches.length > 0:
touch = event.touches.item(0)
return touch.clientX, touch.clientY
# Fallback: try changedTouches
if hasattr(event, "changedTouches") and event.changedTouches.length > 0:
touch = event.changedTouches.item(0)
return touch.clientX, touch.clientY
return None, None
async def on_canvas_press(event):
global is_running
if is_running:
return
is_running = True
try:
# Avoid scrolling / zooming taking over on touch
if hasattr(event, "preventDefault"):
event.preventDefault()
clientX, clientY = get_event_coords(event)
if clientX is None:
# Could not read coordinates; bail out gracefully
return
rect = canvas.getBoundingClientRect()
# Account for CSS scaling: map from displayed size to canvas units
scale_x = canvas.width / rect.width
scale_y = canvas.height / rect.height
x_canvas = (clientX - rect.left) * scale_x
y_canvas = (clientY - rect.top) * scale_y
x_idx = int(x_canvas // PIXEL_SIZE)
y_idx = int(y_canvas // PIXEL_SIZE)
# Bounds check just to be safe
if 0 <= x_idx < IMG_WIDTH and 0 <= y_idx < IMG_HEIGHT:
await fill_bitmap(bitmap, x_idx, y_idx)
finally:
# Ensure the flag is always reset, even if something raises
is_running = False
bitmap = parse_bitmap()
draw_bitmap(bitmap)
proxied_on_canvas_press = create_proxy(on_canvas_press)
# Attach event listener
canvas.addEventListener("pointerdown", proxied_on_canvas_press)
canvas.addEventListener("touchstart", proxied_on_canvas_press)
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 and how to implement it.
The algorithm will be implemented as a function floodfill with three arguments:
a grid representing the locations of the walls; and
the x and y coordinates of the starting point (the place you clicked).
def floodfill(walls, x, y):
pass
Ok, 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]:
return
In 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:
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:
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:
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:
Neighbours of a pixel.
To represent this, I usually create a tuple 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?
):
continue
If 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:
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.
Below, you can find an interactive demo of this algorithm in action, which is trying to fill the centre region with pink.
Play the algorithm step by step until you're comfortable with its behaviour and then click “auto-play” to see the pink region fill up completely...
█painted;
█to_paint:
Starting the floodfill algorithm from the centre square. Press “Next”.
import asyncio
import js
from pyodide.ffi import create_proxy # you'll likely use this later
# --- configuration ----------------------------------------------------
CELL_SIZE = 60
GRID_LINE_WIDTH = 3
GRID = [
[0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0],
[0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0],
[1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0],
[1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
]
START = (5, 3)
ROWS = len(GRID)
COLS = len(GRID[0])
CANVAS_WIDTH = COLS * CELL_SIZE + (COLS + 1) * GRID_LINE_WIDTH
CANVAS_HEIGHT = ROWS * CELL_SIZE + (ROWS + 1) * GRID_LINE_WIDTH
# --- drawing helpers --------------------------------------------------
def draw_cells(ctx):
for row in range(ROWS):
for col in range(COLS):
value = GRID[row][col]
color = BG_COLOUR if value == 0 else FG_COLOUR
ctx.fillStyle = color
ctx.fillRect(
col * CELL_SIZE + (col + 1) * GRID_LINE_WIDTH,
row * CELL_SIZE + (row + 1) * GRID_LINE_WIDTH,
CELL_SIZE,
CELL_SIZE,
)
def draw_gridlines(ctx):
ctx.lineWidth = 3
ctx.fillStyle = UI_COLOUR
# I'm drawing the lines as rectangles because it's easier to control
# the position of the corners of the “thick lines” this way.
for c in range(COLS + 2):
x = c * (CELL_SIZE + GRID_LINE_WIDTH)
ctx.fillRect(
x,
0,
GRID_LINE_WIDTH,
CANVAS_HEIGHT,
)
for r in range(ROWS + 2):
y = r * (CELL_SIZE + GRID_LINE_WIDTH)
ctx.fillRect(
0,
y,
CANVAS_WIDTH,
GRID_LINE_WIDTH,
)
def draw_grid1():
canvas = js.document.getElementById("slow-ff-grid")
ctx = canvas.getContext("2d")
# Ensure canvas has the correct internal size
canvas.width = CANVAS_WIDTH
canvas.height = CANVAS_HEIGHT
draw_cells(ctx)
draw_gridlines(ctx)
class Animation:
def __init__(self, ctx, status_p):
self.ctx = ctx
self.status_p = status_p
self.painted = set()
self.to_paint = []
self.animation_ff = None
self.autoplaying = False
self.stop_autoplaying = asyncio.Event()
def current_cell_colour(self, x, y):
if GRID[y][x]:
return FG_COLOUR
elif (x, y) in self.to_paint:
return AC2_COLOUR
elif (x, y) in self.painted:
return AC_COLOUR
else:
return BG_COLOUR
def mark_cell(self, x, y):
cell_colour = self.current_cell_colour(x, y)
self.ctx.strokeStyle = CONTRAST[cell_colour]
cx = x * CELL_SIZE + (x + 1) * GRID_LINE_WIDTH + CELL_SIZE // 2
cy = y * CELL_SIZE + (y + 1) * GRID_LINE_WIDTH + CELL_SIZE // 2
self.ctx.beginPath()
self.ctx.arc(cx, cy, 3 * CELL_SIZE // 10, 0, 2 * js.Math.PI)
self.ctx.stroke()
def mark_cell_x(self, x, y):
"""Draw an X on top of this cell."""
self.ctx.beginPath()
self.ctx.strokeStyle = CONTRAST[self.current_cell_colour(x, y)]
xl = x * CELL_SIZE + (x + 1) * GRID_LINE_WIDTH + CELL_SIZE // 4
xr = x * CELL_SIZE + (x + 1) * GRID_LINE_WIDTH + CELL_SIZE // 4 * 3
yt = y * CELL_SIZE + (y + 1) * GRID_LINE_WIDTH + CELL_SIZE // 4
yb = y * CELL_SIZE + (y + 1) * GRID_LINE_WIDTH + CELL_SIZE // 4 * 3
self.ctx.moveTo(xl, yt)
self.ctx.lineTo(xr, yb)
self.ctx.stroke()
self.ctx.moveTo(xl, yb)
self.ctx.lineTo(xr, yt)
self.ctx.stroke()
def clear_cell(self, x, y):
self.draw_cell(x, y, self.current_cell_colour(x, y))
def draw_cell(self, x, y, colour):
self.ctx.fillStyle = colour
self.ctx.fillRect(
x * CELL_SIZE + (x + 1) * GRID_LINE_WIDTH,
y * CELL_SIZE + (y + 1) * GRID_LINE_WIDTH,
CELL_SIZE,
CELL_SIZE,
)
async def start(self, _evt):
if self.autoplaying:
self.stop_autoplaying.set()
await asyncio.sleep(0) # Give the loop a chance to cancell the running autoplay
self._start()
def _start(self):
draw_grid1()
self.status_p.innerHTML = "Starting the floodfill algorithm from the centre square. Press “Next”."
self.painted = set()
self.to_paint = [START]
self.draw_cell(*START, AC2_COLOUR)
self.sync_painted()
self.sync_to_paint()
self.animation_ff = self.floodfill()
def sync_to_paint(self):
for x, y in self.to_paint:
self.draw_cell(x, y, AC2_COLOUR)
elem = js.document.getElementById("slow-ff-grid-to_paint-values")
elem.innerHTML = ", ".join(map(str, self.to_paint))
def sync_painted(self):
elem = js.document.getElementById("slow-ff-grid-painted-values")
elem.innerHTML = ", ".join(map(str, self.painted))
def animation_step(self):
if self.autoplaying:
return
if self.animation_ff is None:
self.start()
try:
msg = next(self.animation_ff)
except StopIteration:
msg = "Done"
self.status_p.innerHTML = msg
print(msg)
async def autoplay(self, _evt):
self.autoplaying = True
await self._autoplay()
async def _autoplay(self):
if self.animation_ff is None:
self.start()
for msg in self.animation_ff:
self.status_p.innerHTML = msg
print(msg)
await asyncio.wait(
[
asyncio.create_task(asyncio.sleep(.25)),
asyncio.create_task(self.stop_autoplaying.wait()),
],
return_when=asyncio.FIRST_COMPLETED,
)
if self.stop_autoplaying.is_set():
self.stop_autoplaying.clear()
self.autoplaying = False
break
def floodfill(self):
print("starting ff")
_NEIGHBOUR_OFFSETS = ((+1, 0), (0, +1), (-1, 0), (0, -1))
neighbour_msgs = {
(1, 0): "Checking the cell on the right...",
(-1, 0): "Checking the cell on the left...",
(0, 1): "Checking the cell below...",
(0, -1): "Checking the cell above...",
}
while self.to_paint:
this_pixel = self.to_paint.pop()
self.painted.add(this_pixel)
self.sync_painted()
self.sync_to_paint()
tx, ty = this_pixel
self.mark_cell(tx, ty)
yield f"Will now process {this_pixel}."
self.draw_cell(tx, ty, AC_COLOUR)
self.mark_cell_x(tx, ty)
yield f"The cell {this_pixel} has now been coloured. Now, we check its neighbours."
for dx, dy in _NEIGHBOUR_OFFSETS:
nx, ny = tx + dx, ty + dy
# Produce nice message about neighbour to process.
if not (nx < 0 or nx >= COLS or ny < 0 or ny >= ROWS):
self.mark_cell(nx, ny)
yield neighbour_msgs[(dx, dy)]
if nx < 0 or nx >= COLS or ny < 0 or ny >= ROWS:
yield f"... oh wait, there's no cell there because the grid ends here."
continue
elif GRID[ny][nx]:
yield f"Will skip this neighbour because it's a wall!"
self.clear_cell(nx, ny)
continue
if (nx, ny) not in self.painted:
self.to_paint.append((nx, ny))
self.sync_to_paint()
self.draw_cell(nx, ny, AC2_COLOUR)
yield f"Tracked and set neighbour to paint later."
else:
self.clear_cell(nx, ny)
yield f"Skipped because it was painted already!"
self.clear_cell(tx, ty)
yield f"We're done because there are no more cells to paint!"
animator1 = Animation(
js.document.getElementById("slow-ff-grid").getContext("2d"),
js.document.getElementById("slow-ff-grid-status"),
)
proxied_start = create_proxy(animator1.start)
js.document.getElementById("slow-reset").addEventListener("click", proxied_start)
proxied_animation_step = create_proxy(lambda evt: animator1.animation_step())
js.document.getElementById("slow-next").addEventListener("click", proxied_animation_step)
proxied_autoplay = create_proxy(animator1.autoplay)
js.document.getElementById("slow-autoplay").addEventListener("click", proxied_autoplay)
# Initial reset
animator1._start()
Wait, did you see that?
Did you notice how, at the end, some of the pink cells turned purple again and you had to paint them more than once?!
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 that doesn't prevent the same pixel to be added to the list to_paint twice!
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:
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 = {(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 demo below lets you step through the floodfill algorithm as it tries to paint the middle region in pink.
The cells shown in purple are cells that have been added to the list to_paint, but haven't been painted yet.
██tracked;
█to_paint:
Starting the floodfill algorithm from the centre square. Press “Next”.
import asyncio
import js
from pyodide.ffi import create_proxy # you'll likely use this later
# --- configuration ----------------------------------------------------
CELL_SIZE = 60
GRID_LINE_WIDTH = 3
GRID = [
[0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0],
[0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0],
[1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0],
[1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
]
START = (5, 3)
ROWS = len(GRID)
COLS = len(GRID[0])
CANVAS_WIDTH = COLS * CELL_SIZE + (COLS + 1) * GRID_LINE_WIDTH
CANVAS_HEIGHT = ROWS * CELL_SIZE + (ROWS + 1) * GRID_LINE_WIDTH
# --- drawing helpers --------------------------------------------------
def draw_cells(ctx):
for row in range(ROWS):
for col in range(COLS):
value = GRID[row][col]
color = BG_COLOUR if value == 0 else FG_COLOUR
ctx.fillStyle = color
ctx.fillRect(
col * CELL_SIZE + (col + 1) * GRID_LINE_WIDTH,
row * CELL_SIZE + (row + 1) * GRID_LINE_WIDTH,
CELL_SIZE,
CELL_SIZE,
)
def draw_gridlines(ctx):
ctx.lineWidth = 3
ctx.fillStyle = UI_COLOUR
# I'm drawing the lines as rectangles because it's easier to control
# the position of the corners of the “thick lines” this way.
for c in range(COLS + 2):
x = c * (CELL_SIZE + GRID_LINE_WIDTH)
ctx.fillRect(
x,
0,
GRID_LINE_WIDTH,
CANVAS_HEIGHT,
)
for r in range(ROWS + 2):
y = r * (CELL_SIZE + GRID_LINE_WIDTH)
ctx.fillRect(
0,
y,
CANVAS_WIDTH,
GRID_LINE_WIDTH,
)
def draw_grid():
canvas = js.document.getElementById("ff-grid")
ctx = canvas.getContext("2d")
# Ensure canvas has the correct internal size
canvas.width = CANVAS_WIDTH
canvas.height = CANVAS_HEIGHT
draw_cells(ctx)
draw_gridlines(ctx)
class Animation:
def __init__(self, ctx, status_p):
self.ctx = ctx
self.status_p = status_p
self.tracked = set()
self.to_paint = []
self.animation_ff = None
self.autoplaying = False
self.stop_autoplaying = asyncio.Event()
def current_cell_colour(self, x, y):
if GRID[y][x]:
return FG_COLOUR
elif (x, y) in self.to_paint:
return AC2_COLOUR
elif (x, y) in self.tracked:
return AC_COLOUR
else:
return BG_COLOUR
def mark_cell(self, x, y):
cell_colour = self.current_cell_colour(x, y)
self.ctx.strokeStyle = CONTRAST[cell_colour]
cx = x * CELL_SIZE + (x + 1) * GRID_LINE_WIDTH + CELL_SIZE // 2
cy = y * CELL_SIZE + (y + 1) * GRID_LINE_WIDTH + CELL_SIZE // 2
self.ctx.beginPath()
self.ctx.arc(cx, cy, 3 * CELL_SIZE // 10, 0, 2 * js.Math.PI)
self.ctx.stroke()
def mark_cell_x(self, x, y):
"""Draw an X on top of this cell."""
self.ctx.beginPath()
self.ctx.strokeStyle = CONTRAST[self.current_cell_colour(x, y)]
xl = x * CELL_SIZE + (x + 1) * GRID_LINE_WIDTH + CELL_SIZE // 4
xr = x * CELL_SIZE + (x + 1) * GRID_LINE_WIDTH + CELL_SIZE // 4 * 3
yt = y * CELL_SIZE + (y + 1) * GRID_LINE_WIDTH + CELL_SIZE // 4
yb = y * CELL_SIZE + (y + 1) * GRID_LINE_WIDTH + CELL_SIZE // 4 * 3
self.ctx.moveTo(xl, yt)
self.ctx.lineTo(xr, yb)
self.ctx.stroke()
self.ctx.moveTo(xl, yb)
self.ctx.lineTo(xr, yt)
self.ctx.stroke()
def clear_cell(self, x, y):
self.draw_cell(x, y, self.current_cell_colour(x, y))
def draw_cell(self, x, y, colour):
self.ctx.fillStyle = colour
self.ctx.fillRect(
x * CELL_SIZE + (x + 1) * GRID_LINE_WIDTH,
y * CELL_SIZE + (y + 1) * GRID_LINE_WIDTH,
CELL_SIZE,
CELL_SIZE,
)
async def start(self, _evt):
if self.autoplaying:
self.stop_autoplaying.set()
await asyncio.sleep(0) # Give the loop a chance to cancell the running autoplay
self._start()
def _start(self):
draw_grid()
self.status_p.innerHTML = "Starting the floodfill algorithm from the centre square. Press “Next”."
self.tracked = {START}
self.to_paint = [START]
self.draw_cell(*START, AC2_COLOUR)
self.sync_tracked()
self.sync_to_paint()
self.animation_ff = self.floodfill()
def sync_to_paint(self):
elem = js.document.getElementById("ff-grid-to_paint-values")
elem.innerHTML = ", ".join(map(str, self.to_paint))
def sync_tracked(self):
elem = js.document.getElementById("ff-grid-tracked-values")
elem.innerHTML = ", ".join(map(str, self.tracked))
def animation_step(self):
if self.autoplaying:
return
if self.animation_ff is None:
self.start()
try:
msg = next(self.animation_ff)
except StopIteration:
msg = "Done"
self.status_p.innerHTML = msg
print(msg)
async def autoplay(self, _evt):
self.autoplaying = True
await self._autoplay()
async def _autoplay(self):
if self.animation_ff is None:
self.start()
for msg in self.animation_ff:
self.status_p.innerHTML = msg
print(msg)
await asyncio.wait(
[
asyncio.create_task(asyncio.sleep(1)),
asyncio.create_task(self.stop_autoplaying.wait()),
],
return_when=asyncio.FIRST_COMPLETED,
)
if self.stop_autoplaying.is_set():
self.stop_autoplaying.clear()
self.autoplaying = False
break
def floodfill(self):
print("starting ff")
_NEIGHBOUR_OFFSETS = ((+1, 0), (0, +1), (-1, 0), (0, -1))
neighbour_msgs = {
(1, 0): "Checking the cell on the right...",
(-1, 0): "Checking the cell on the left...",
(0, 1): "Checking the cell below...",
(0, -1): "Checking the cell above...",
}
while self.to_paint:
this_pixel = self.to_paint.pop()
self.sync_to_paint()
tx, ty = this_pixel
self.mark_cell(tx, ty)
yield f"Will now process {this_pixel}."
self.draw_cell(tx, ty, AC_COLOUR)
self.mark_cell_x(tx, ty)
yield f"The cell {this_pixel} has now been coloured. Now, we check its neighbours."
for dx, dy in _NEIGHBOUR_OFFSETS:
nx, ny = tx + dx, ty + dy
# Produce nice message about neighbour to process.
if not (nx < 0 or nx >= COLS or ny < 0 or ny >= ROWS):
self.mark_cell(nx, ny)
yield neighbour_msgs[(dx, dy)]
if nx < 0 or nx >= COLS or ny < 0 or ny >= ROWS:
yield f"... oh wait, there's no cell there because the grid ends here."
continue
elif GRID[ny][nx]:
yield f"Will skip this neighbour because it's a wall!"
self.clear_cell(nx, ny)
continue
if (nx, ny) not in self.tracked:
self.tracked.add((nx, ny))
self.to_paint.append((nx, ny))
self.sync_to_paint()
self.sync_tracked()
self.draw_cell(nx, ny, AC2_COLOUR)
yield f"Tracked and set neighbour to paint later."
else:
self.clear_cell(nx, ny)
yield f"Skipped because it was tracked already!"
self.clear_cell(tx, ty)
yield f"We're done because there are no more cells to paint!"
animator = Animation(
js.document.getElementById("ff-grid").getContext("2d"),
js.document.getElementById("ff-grid-status"),
)
proxied_start = create_proxy(animator.start)
js.document.getElementById("reset").addEventListener("click", proxied_start)
proxied_animation_step = create_proxy(lambda evt: animator.animation_step())
js.document.getElementById("next").addEventListener("click", proxied_animation_step)
proxied_autoplay = create_proxy(animator.autoplay)
js.document.getElementById("autoplay").addEventListener("click", proxied_autoplay)
# Initial reset
animator._start()
Example applications of the floodfill algorithm
This section shows a couple of practical applications of the floodfill algorithm.
Is a maze solvable?
If you have a maze, you can use the floodfill algorithm to check where the maze exit could go based on your starting point.
All you have to do is start the floodfill algorithm at your maze entrance and then you can place an exit in any point reached by the floodfill algorithm;
if the floodfill algorithm doesn't reach a certain point, the exit can't go there.
Click any empty cell of the maze below and see what portion of the maze you can fill.
For example, if you start in the bottom left of the maze, can you go all the way up to the top right corner of the maze?
█ processed;
█ queued
Click an empty cell to start the floodfill.
import asyncio
import js
from pyodide.ffi import create_proxy
# --- configuration ----------------------------------------------------
FF2_CELL_SIZE = 20
FF2_GRID_LINE_WIDTH = 2
FF2_GRID = [
[1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0],
[1,1,1,1,1,1,0,0,1,0,1,1,1,1,1,1,0,0,1,0,1,1,1,1,1,1,0,1,0],
[0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,1,0,0,0],
[1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1],
[0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0],
[0,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1],
[0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0],
[1,0,1,1,1,0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1],
[0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0],
[0,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1],
[0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0],
[1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1],
[0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0],
[0,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1],
]
FF2_ROWS = len(FF2_GRID)
FF2_COLS = len(FF2_GRID[0])
FF2_CANVAS_WIDTH = FF2_COLS * FF2_CELL_SIZE + (FF2_COLS + 1) * FF2_GRID_LINE_WIDTH
FF2_CANVAS_HEIGHT = FF2_ROWS * FF2_CELL_SIZE + (FF2_ROWS + 1) * FF2_GRID_LINE_WIDTH
# --- drawing helpers --------------------------------------------------
def ff2_draw_cells(ctx):
for row in range(FF2_ROWS):
for col in range(FF2_COLS):
value = FF2_GRID[row][col]
color = BG_COLOUR if value == 0 else FG_COLOUR
ctx.fillStyle = color
ctx.fillRect(
col * FF2_CELL_SIZE + (col + 1) * FF2_GRID_LINE_WIDTH,
row * FF2_CELL_SIZE + (row + 1) * FF2_GRID_LINE_WIDTH,
FF2_CELL_SIZE,
FF2_CELL_SIZE,
)
def ff2_draw_gridlines(ctx):
ctx.lineWidth = FF2_GRID_LINE_WIDTH
ctx.fillStyle = UI_COLOUR
for c in range(FF2_COLS + 2):
x = c * (FF2_CELL_SIZE + FF2_GRID_LINE_WIDTH)
ctx.fillRect(
x,
0,
FF2_GRID_LINE_WIDTH,
FF2_CANVAS_HEIGHT,
)
for r in range(FF2_ROWS + 2):
y = r * (FF2_CELL_SIZE + FF2_GRID_LINE_WIDTH)
ctx.fillRect(
0,
y,
FF2_CANVAS_WIDTH,
FF2_GRID_LINE_WIDTH,
)
def ff2_draw_grid():
canvas = js.document.getElementById("ff2-grid-canvas")
ctx = canvas.getContext("2d")
canvas.width = FF2_CANVAS_WIDTH
canvas.height = FF2_CANVAS_HEIGHT
ff2_draw_cells(ctx)
ff2_draw_gridlines(ctx)
# --- animation --------------------------------------------------------
class FF2Animation:
def __init__(self, ctx, status_p):
self.ctx = ctx
self.status_p = status_p
self.running = False
self.current_task = None
def current_cell_colour(self, x, y):
if FF2_GRID[y][x]:
return FG_COLOUR
else:
return BG_COLOUR
def draw_cell(self, x, y, colour):
self.ctx.fillStyle = colour
self.ctx.fillRect(
x * FF2_CELL_SIZE + (x + 1) * FF2_GRID_LINE_WIDTH,
y * FF2_CELL_SIZE + (y + 1) * FF2_GRID_LINE_WIDTH,
FF2_CELL_SIZE,
FF2_CELL_SIZE,
)
def reset(self):
if self.current_task is not None:
self.current_task.cancel()
self.current_task = None
self.running = False
ff2_draw_grid()
self.status_p.innerHTML = "Click an empty cell to start the floodfill."
async def floodfill_from(self, start):
self.running = True
try:
_NEIGHBOUR_OFFSETS = ((+1, 0), (0, +1), (-1, 0), (0, -1))
stack = [start]
tracked = {start}
sx, sy = start
# start cell as queued
self.draw_cell(sx, sy, AC2_COLOUR)
while stack:
x, y = stack.pop()
# mark as being processed
self.draw_cell(x, y, AC_COLOUR)
await asyncio.sleep(0.05)
for dx, dy in _NEIGHBOUR_OFFSETS:
nx, ny = x + dx, y + dy
if nx < 0 or nx >= FF2_COLS or ny < 0 or ny >= FF2_ROWS:
continue
if FF2_GRID[ny][nx]:
continue
if (nx, ny) in tracked:
continue
tracked.add((nx, ny))
stack.append((nx, ny))
# queued cell
self.draw_cell(nx, ny, AC2_COLOUR)
await asyncio.sleep(0.02)
except asyncio.CancelledError:
pass
finally:
self.running = False
self.current_task = None
self.status_p.innerHTML = "Floodfill finished. Click any cell or Reset."
def start_from_cell(self, x, y):
if self.running:
# do not interrupt an ongoing floodfill
return
if FF2_GRID[y][x]:
# clicked on a wall; ignore
return
# reset grid and start from the clicked cell
ff2_draw_grid()
self.status_p.innerHTML = f"Floodfilling from ({x}, {y})."
self.current_task = asyncio.create_task(self.floodfill_from((x, y)))
# --- helpers ----------------------------------------------------------
def ff2_canvas_coords_to_cell(x, y):
# convert canvas pixel coordinates to grid indices or return None
# subtract initial grid line
x_local = x - FF2_GRID_LINE_WIDTH
y_local = y - FF2_GRID_LINE_WIDTH
if x_local < 0 or y_local < 0:
return None
cell_span = FF2_CELL_SIZE + FF2_GRID_LINE_WIDTH
col, x_off = divmod(x_local, cell_span)
row, y_off = divmod(y_local, cell_span)
if col < 0 or col >= FF2_COLS or row < 0 or row >= FF2_ROWS:
return None
# ignore clicks on grid lines
if x_off >= FF2_CELL_SIZE or y_off >= FF2_CELL_SIZE:
return None
return int(col), int(row)
# --- setup ------------------------------------------------------------
ff2_canvas = js.document.getElementById("ff2-grid-canvas")
animator2 = FF2Animation(ff2_canvas.getContext("2d"), js.document.getElementById("ff2-grid-status"))
def ff2_handle_canvas_click(evt):
if animator2.running:
# ignore clicks while floodfill is running
return
rect = evt.target.getBoundingClientRect()
x = (evt.clientX - rect.left) * (ff2_canvas.width / rect.width)
y = (evt.clientY - rect.top) * (ff2_canvas.height / rect.height)
cell = ff2_canvas_coords_to_cell(x, y)
if cell is None:
return
cx, cy = cell
animator2.start_from_cell(cx, cy)
def handle_reset_click(evt):
animator2.reset()
# attach event listeners
ff2_canvas_click_proxy = create_proxy(ff2_handle_canvas_click)
ff2_canvas.addEventListener("click", ff2_canvas_click_proxy)
ff2_reset_proxy = create_proxy(handle_reset_click)
js.document.getElementById("ff2-reset-button").addEventListener("click", ff2_reset_proxy)
# initial draw
ff2_draw_grid()
I love mazes, but checking if a maze is solvable isn't your typical programmer task.
But the maze is just a simple way of understanding this application of the floodfill algorithm.
Instead of checking if a maze is solvable, you can apply this algorithm in the same way to check if you can go from one place to another in your city by bus:
your “cells” are bus stops and the “neighbours” of a bus stop are all the stops you can get to by taking a bus there.
Counting disconnected regions
The maze above isn't fully connected.
Starting from the bottom left corner of the maze, there are some corridors you can't get to...
But how many such regions are there?
With a bit of effort, you may conclude that there are 5 independent regions.
Regions that are disconnected from each other.
But how can you use the floodfill algorithm to figure that out?
What if instead of a small maze, you had a huge grid and you didn't want to count the regions by hand?
In order to achieve this, you can apply the floodfill algorithm successively:
start by looking for a cell that hasn't been covered yet;
apply the floodfill algorithm from the cell found in 1 until it finishes;
mark all cells that were filled as “covered”; and
go back to 1 until you cover all cells.
You can see this in action in the demo below:
█ processed;
█ queued;
█████ regions
Click “Count regions” to start the demo.
import asyncio
import itertools
import js
from pyodide.ffi import create_proxy
# --- configuration ----------------------------------------------------
FF3_CELL_SIZE = 20
FF3_GRID_LINE_WIDTH = 2
FF3_GRID = [
[1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0],
[1,1,1,1,1,1,0,0,1,0,1,1,1,1,1,1,0,0,1,0,1,1,1,1,1,1,0,1,0],
[0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,1,0,0,0],
[1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1],
[0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0],
[0,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1],
[0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0],
[1,0,1,1,1,0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1],
[0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0],
[0,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1],
[0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0],
[1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1],
[0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0],
[0,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1],
]
FF3_ROWS = len(FF3_GRID)
FF3_COLS = len(FF3_GRID[0])
FF3_CANVAS_WIDTH = FF3_COLS * FF3_CELL_SIZE + (FF3_COLS + 1) * FF3_GRID_LINE_WIDTH
FF3_CANVAS_HEIGHT = FF3_ROWS * FF3_CELL_SIZE + (FF3_ROWS + 1) * FF3_GRID_LINE_WIDTH
REGION_COLOURS = itertools.cycle([RE_COLOUR, BL_COLOUR, GR_COLOUR, YE_COLOUR, OR_COLOUR])
# --- drawing helpers --------------------------------------------------
def ff3_draw_cells(ctx):
for row in range(FF3_ROWS):
for col in range(FF3_COLS):
value = FF3_GRID[row][col]
color = FG_COLOUR if value else BG_COLOUR
ctx.fillStyle = color
ctx.fillRect(
col * FF3_CELL_SIZE + (col + 1) * FF3_GRID_LINE_WIDTH,
row * FF3_CELL_SIZE + (row + 1) * FF3_GRID_LINE_WIDTH,
FF3_CELL_SIZE,
FF3_CELL_SIZE,
)
def ff3_draw_gridlines(ctx):
ctx.lineWidth = FF3_GRID_LINE_WIDTH
ctx.fillStyle = UI_COLOUR
for c in range(FF3_COLS + 2):
x = c * (FF3_CELL_SIZE + FF3_GRID_LINE_WIDTH)
ctx.fillRect(
x,
0,
FF3_GRID_LINE_WIDTH,
FF3_CANVAS_HEIGHT,
)
for r in range(FF3_ROWS + 2):
y = r * (FF3_CELL_SIZE + FF3_GRID_LINE_WIDTH)
ctx.fillRect(
0,
y,
FF3_CANVAS_WIDTH,
FF3_GRID_LINE_WIDTH,
)
def ff3_draw_grid():
canvas = js.document.getElementById("ff3-grid-canvas")
ctx = canvas.getContext("2d")
canvas.width = FF3_CANVAS_WIDTH
canvas.height = FF3_CANVAS_HEIGHT
ff3_draw_cells(ctx)
ff3_draw_gridlines(ctx)
# --- animation --------------------------------------------------------
class FF3Animation:
def __init__(self, ctx, status_p):
self.ctx = ctx
self.status_p = status_p
self.running = False
self.current_task = None
self.painted = set() # cells already assigned to a region
self.region_count = 0
def draw_cell(self, x, y, colour):
self.ctx.fillStyle = colour
self.ctx.fillRect(
x * FF3_CELL_SIZE + (x + 1) * FF3_GRID_LINE_WIDTH,
y * FF3_CELL_SIZE + (y + 1) * FF3_GRID_LINE_WIDTH,
FF3_CELL_SIZE,
FF3_CELL_SIZE,
)
def reset(self):
if self.current_task is not None:
self.current_task.cancel()
self.current_task = None
self.running = False
self.painted.clear()
self.region_count = 0
ff3_draw_grid()
self.status_p.innerHTML = "Click “Count regions” to start the demo."
async def floodfill_region(self, start, region_colour):
_NEIGHBOUR_OFFSETS = ((+1, 0), (0, +1), (-1, 0), (0, -1))
stack = [start]
tracked = {start}
sx, sy = start
self.draw_cell(sx, sy, AC2_COLOUR)
while stack:
x, y = stack.pop()
# mark as being processed
self.draw_cell(x, y, AC_COLOUR)
await asyncio.sleep(0.05)
for dx, dy in _NEIGHBOUR_OFFSETS:
nx, ny = x + dx, y + dy
if nx < 0 or nx >= FF3_COLS or ny < 0 or ny >= FF3_ROWS:
continue
if (nx, ny) in tracked:
continue
if FF3_GRID[ny][nx]:
continue
tracked.add((nx, ny))
stack.append((nx, ny))
# queued cell
self.draw_cell(nx, ny, AC2_COLOUR)
await asyncio.sleep(0.02)
# repaint region cells with region colour, except the starting cell
for (x, y) in tracked:
if (x, y) == start:
continue
self.draw_cell(x, y, region_colour)
# mark all cells as painted (including the start cell)
print("Updating ")
self.painted.update(tracked)
async def run_all_regions(self):
self.running = True
self.painted.clear()
self.region_count = 0
ff3_draw_grid()
try:
for y in range(FF3_ROWS):
for x in range(FF3_COLS):
print("@@@")
print(x, y)
print(self.painted)
print((x, y) in self.painted)
print("@@@")
if (x, y) in self.painted or FF3_GRID[y][x]:
continue
next_start = (x, y)
self.region_count += 1
region_colour = next(REGION_COLOURS)
self.status_p.innerHTML = (
f"Region {self.region_count}: starting at {next_start}."
)
await self.floodfill_region(next_start, region_colour)
await asyncio.sleep(0.1)
self.status_p.innerHTML = f"Finished. Found {self.region_count} disconnected regions."
except asyncio.CancelledError:
self.status_p.innerHTML = "Cancelled."
finally:
self.running = False
self.current_task = None
def start_count(self):
if self.running:
return
self.status_p.innerHTML = "Running region floodfills..."
self.current_task = asyncio.create_task(self.run_all_regions())
# --- setup ------------------------------------------------------------
ff3_canvas = js.document.getElementById("ff3-grid-canvas")
ff3_draw_grid()
animator3 = FF3Animation(ff3_canvas.getContext("2d"), js.document.getElementById("ff3-grid-status"))
def ff3_handle_count_click(evt):
animator3.start_count()
def ff3_handle_reset_click(evt):
animator3.reset()
# attach event listeners
ff3_count_proxy = create_proxy(ff3_handle_count_click)
js.document.getElementById("ff3-count-button").addEventListener("click", ff3_count_proxy)
ff3_reset_proxy = create_proxy(ff3_handle_reset_click)
js.document.getElementById("ff3-reset-button").addEventListener("click", ff3_reset_proxy)
The code below represents this algorithm:
_NEIGHBOUR_OFFSETS = ((+1, 0), (0, +1), (-1, 0), (0, -1))
def count_regions(walls):
HEIGHT = len(walls)
WIDTH = len(walls[0])
covered = set()
regions = 0
for x in range(WIDTH):
for y in range(HEIGHT):
if walls[y][x]: # We don't care about walls.
continue
if (x, y) in covered: # This was covered already, skip.
continue
regions += 1
region_cells = floodfill(walls, x, y)
covered.update(region_cells)
... # (1) Process this region.
return regions
def floodfill(walls, x, y):
# Everything else is the same...
# ... but you add this line:
return tracked # <-- VERY IMPORTANT :D
The code above represents the main mechanic of the algorithm.
Depending on what you want to do with the regions, you may want to keep a list of all different regions or, for the demo above, I would paint each new region in a new colour in the line of code marked with (1).
Simulating a fluid spreading on a surface
You can also use the floodfill algorithm to create a basic simulation of a fluid spreading on a surface.
It won't be physically accurate, but it will look pretty cool given the amount of effort you have to put in...
And trust me, I did numerical simulations for 2D and 3D flows and it's not easy.
To apply the floodfill algorithm in this context, all you do is change the way in which cells are added to the list to_paint and the order in which they are processed.
Instead of working one cell at a time, you are going to keep a set that represents the “fringe” of the fluid.
(This starts off as a single cell.)
Then, all the cells that are neighbours of any cell in the fringe are added to the list to_paint and they become the fringe for the next iteration.
In the beginning, you have a single point in the fringe:
█ processed:
█ fringe: (1, 0)
FF4_CELL_SIZE = 60
FF4_GRID_LINE_WIDTH = 3
FF4_GRID = [
[0,0,0,0,0,0],
[0,0,0,1,1,0],
[0,0,0,1,1,0],
[0,0,0,0,0,0],
]
FF4_ROWS = len(FF4_GRID)
FF4_COLS = len(FF4_GRID[0])
FF4_CANVAS_WIDTH = FF4_COLS * FF4_CELL_SIZE + (FF4_COLS + 1) * FF4_GRID_LINE_WIDTH
FF4_CANVAS_HEIGHT = FF4_ROWS * FF4_CELL_SIZE + (FF4_ROWS + 1) * FF4_GRID_LINE_WIDTH
def ff4_draw_cells(ctx):
for row in range(FF4_ROWS):
for col in range(FF4_COLS):
value = FF4_GRID[row][col]
color = BG_COLOUR if value == 0 else FG_COLOUR
ctx.fillStyle = color
ctx.fillRect(
col * FF4_CELL_SIZE + (col + 1) * FF4_GRID_LINE_WIDTH,
row * FF4_CELL_SIZE + (row + 1) * FF4_GRID_LINE_WIDTH,
FF4_CELL_SIZE,
FF4_CELL_SIZE,
)
def ff4_draw_gridlines(ctx):
ctx.lineWidth = FF4_GRID_LINE_WIDTH
ctx.fillStyle = UI_COLOUR
for c in range(FF4_COLS + 2):
x = c * (FF4_CELL_SIZE + FF4_GRID_LINE_WIDTH)
ctx.fillRect(
x,
0,
FF4_GRID_LINE_WIDTH,
FF4_CANVAS_HEIGHT,
)
for r in range(FF4_ROWS + 2):
y = r * (FF4_CELL_SIZE + FF4_GRID_LINE_WIDTH)
ctx.fillRect(
0,
y,
FF4_CANVAS_WIDTH,
FF4_GRID_LINE_WIDTH,
)
def ff4_draw_cell(ctx, x, y, colour):
ctx.fillStyle = colour
ctx.fillRect(
x * FF4_CELL_SIZE + (x + 1) * FF4_GRID_LINE_WIDTH,
y * FF4_CELL_SIZE + (y + 1) * FF4_GRID_LINE_WIDTH,
CELL_SIZE,
CELL_SIZE,
)
def ff4_draw_grid():
canvas = js.document.getElementById("ff4-grid-canvas")
ctx = canvas.getContext("2d")
canvas.width = FF4_CANVAS_WIDTH
canvas.height = FF4_CANVAS_HEIGHT
ff4_draw_cells(ctx)
ff4_draw_gridlines(ctx)
ff4_draw_cell(ctx, 1, 0, AC2_COLOUR)
ff4_draw_grid()
Then, you expand the fringe to include all points that are the neighbours of the previous point:
At the next step, you expand the fringe again.
But this time, you have to include the neighbours of all the cells that were in the fringe in the previous step.
At this iteration, the fringe is starting to hug an obstacle, and subsequent iterations will just floodfill around it!
The next iteration looks like this:
By repeating this process until the grid is fully covered, you get a nice spreading effect.
Here's the same logic, but applied to an interactive demo with a larger grid:
█ processed;
█ fringe
Click any empty cell to start spreading the fluid.
FF7_CELL_SIZE = 20
FF7_GRID_LINE_WIDTH = 2
FF7_GRID = [
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0],
[0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,1,1,1,1,0,0,0,0],
[0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,1,0,0,1,0,0,1,1,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0],
[0,0,0,0,0,1,0,0,1,0,0,1,1,0,0,0,0,0,1,0,0,0,0,1,1,0,0,0,0],
[0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0],
[0,1,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0],
[0,0,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,0,0,0,0,0,1,0,0,0,0,0,0],
[0,0,1,0,0,0,0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0],
[0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0],
[0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1],
]
FF7_ROWS = len(FF3_GRID)
FF7_COLS = len(FF3_GRID[0])
FF7_CANVAS_WIDTH = FF7_COLS * FF7_CELL_SIZE + (FF7_COLS + 1) * FF7_GRID_LINE_WIDTH
FF7_CANVAS_HEIGHT = FF7_ROWS * FF7_CELL_SIZE + (FF7_ROWS + 1) * FF7_GRID_LINE_WIDTH
# --- drawing helpers --------------------------------------------------
def ff7_draw_cells(ctx):
for row in range(FF7_ROWS):
for col in range(FF7_COLS):
value = FF7_GRID[row][col]
color = FG_COLOUR if value else BG_COLOUR
ctx.fillStyle = color
ctx.fillRect(
col * FF7_CELL_SIZE + (col + 1) * FF7_GRID_LINE_WIDTH,
row * FF7_CELL_SIZE + (row + 1) * FF7_GRID_LINE_WIDTH,
FF7_CELL_SIZE,
FF7_CELL_SIZE,
)
def ff7_draw_gridlines(ctx):
ctx.lineWidth = FF7_GRID_LINE_WIDTH
ctx.fillStyle = UI_COLOUR
for c in range(FF7_COLS + 2):
x = c * (FF7_CELL_SIZE + FF7_GRID_LINE_WIDTH)
ctx.fillRect(
x,
0,
FF7_GRID_LINE_WIDTH,
FF7_CANVAS_HEIGHT,
)
for r in range(FF7_ROWS + 2):
y = r * (FF7_CELL_SIZE + FF7_GRID_LINE_WIDTH)
ctx.fillRect(
0,
y,
FF7_CANVAS_WIDTH,
FF7_GRID_LINE_WIDTH,
)
def ff7_draw_grid():
canvas = js.document.getElementById("ff7-grid-canvas")
ctx = canvas.getContext("2d")
canvas.width = FF7_CANVAS_WIDTH
canvas.height = FF7_CANVAS_HEIGHT
ff7_draw_cells(ctx)
ff7_draw_gridlines(ctx)
# --- animation --------------------------------------------------------
class FF7Animation:
def __init__(self, ctx, status_p):
self.ctx = ctx
self.status_p = status_p
self.running = False
self.current_task = None
def draw_cell(self, x, y, colour):
self.ctx.fillStyle = colour
self.ctx.fillRect(
x * FF7_CELL_SIZE + (x + 1) * FF7_GRID_LINE_WIDTH,
y * FF7_CELL_SIZE + (y + 1) * FF7_GRID_LINE_WIDTH,
FF7_CELL_SIZE,
FF7_CELL_SIZE,
)
def reset(self):
if self.current_task is not None:
self.current_task.cancel()
self.current_task = None
self.running = False
ff7_draw_grid()
self.status_p.innerHTML = "Click any empty cell to start spreading the fluid."
async def floodfill_with_fringe(self, start):
_NEIGHBOUR_OFFSETS = ((+1, 0), (0, +1), (-1, 0), (0, -1))
fringe = {start}
tracked = {start}
self.draw_cell(*start, AC2_COLOUR)
while fringe:
next_fringe = set()
for x, y in fringe:
self.draw_cell(x, y, AC_COLOUR)
for dx, dy in _NEIGHBOUR_OFFSETS:
nx, ny = x + dx, y + dy
if nx < 0 or nx >= FF7_COLS or ny < 0 or ny >= FF7_ROWS:
continue
if (nx, ny) in tracked:
continue
if FF7_GRID[ny][nx]:
continue
next_fringe.add((nx, ny))
tracked.update(next_fringe)
for cell in next_fringe:
self.draw_cell(*cell, AC2_COLOUR)
fringe = next_fringe
await asyncio.sleep(.75)
async def run(self, starting_cell):
self.running = True
ff7_draw_grid()
try:
await self.floodfill_with_fringe(starting_cell)
self.status_p.innerHTML = f"Finished."
except asyncio.CancelledError:
self.status_p.innerHTML = "Cancelled."
finally:
self.running = False
self.current_task = None
def start(self, starting_cell):
if self.running:
return
self.status_p.innerHTML = "Running the demo..."
self.current_task = asyncio.create_task(self.run(starting_cell))
# --- setup ------------------------------------------------------------
def ff7_canvas_coords_to_cell(x, y):
x_local = x - FF7_GRID_LINE_WIDTH
y_local = y - FF7_GRID_LINE_WIDTH
if x_local < 0 or y_local < 0:
return None
cell_span = FF7_CELL_SIZE + FF7_GRID_LINE_WIDTH
col, x_off = divmod(x_local, cell_span)
row, y_off = divmod(y_local, cell_span)
if col < 0 or col >= FF7_COLS or row < 0 or row >= FF7_ROWS:
return None
# ignore clicks on grid lines
if x_off >= FF7_CELL_SIZE or y_off >= FF7_CELL_SIZE:
return None
return int(col), int(row)
def ff7_handle_canvas_click(evt):
if animator7.running:
# ignore clicks while floodfill is running
return
rect = evt.target.getBoundingClientRect()
x = (evt.clientX - rect.left) * (ff7_canvas.width / rect.width)
y = (evt.clientY - rect.top) * (ff7_canvas.height / rect.height)
cell = ff7_canvas_coords_to_cell(x, y)
if cell is None:
return
animator7.start(cell)
ff7_canvas = js.document.getElementById("ff7-grid-canvas")
ff7_draw_grid()
animator7 = FF7Animation(ff7_canvas.getContext("2d"), js.document.getElementById("ff7-grid-status"))
def ff7_handle_reset_click(evt):
animator7.reset()
ff7_click_proxy = create_proxy(ff7_handle_canvas_click)
ff7_canvas.addEventListener("click", ff7_click_proxy)
ff7_reset_proxy = create_proxy(ff7_handle_reset_click)
js.document.getElementById("ff7-reset-button").addEventListener("click", ff7_reset_proxy)
The code for this modified version of the floodfill algorithm is very similar to the original one, but this time you are processing multiple cells in one go.
_NEIGHBOUR_OFFSETS = ((+1, 0), (0, +1), (-1, 0), (0, -1))
async def floodfill_with_fringe(walls, start):
HEIGHT = len(walls)
WIDTH = len(walls[0])
fringe = {start}
tracked = {start}
while fringe:
next_fringe = set()
for x, y in fringe:
... # (1) Mark the cell (x, y) as having been processed.
for dx, dy in _NEIGHBOUR_OFFSETS:
nx, ny = x + dx, y + dy
if (
nx < 0 or nx >= WIDTH
or ny < 0 or ny >= HEIGHT
or walls[ny][nx]
):
continue
if (nx, ny) in tracked:
continue
next_fringe.add((nx, ny))
tracked.update(next_fringe)
for x, y in next_fringe:
... # (2) Mark the cell (x, y) as being in the fringe.
fringe = next_fringe
Depending on what you will do with the cells, you can add code to process the cells as they are added to the fringe for the first time or as they are moved from the fringe to the set of cells that has been completely processed.
In the simulation above, I use the line (1) to change the colour of purple cells to pink (to mark they are no longer in the fringe) and I use the line (2) to paint the cells that were just added to the fringe in purple.
Conclusion
This article showed you the main visual interpretation of the floodfill algorithm, as you used it to colour the Python logo in random colours.
You saw what the algorithm looks like in code, you stepped through it, and you learned about a minor tweak you can make to the algorithm to make it much more efficient.
In this article you also saw how you can use the floodfill algorithm to perform real-life tasks like
checking whether a grid is connected or not (when you checked where you could get to inside the maze);
segmenting an image (counting the number of disconnected regions in the maze); and
simulating a flow spreading on a surface.
This is a very important stepping stone in understanding some classical and fundamental Computer Science algorithms, and I can't wait to see you apply this algorithm in your code and experiments!
Improve your Python 🐍 fluency and algorithm knowledge 🎯
