# 10.16: The Flood Fill Algorithm

• • Al Sweigart
$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

The flood fill algorithm is used in Star Pusher to change all of the floor tiles inside the walls of the level to use the "inside floor" tile image instead of the "outside floor" tile (which all the tiles on the map are by default). The original floodFill() call is on line 295. It will convert any tiles represented with the ' ' string (which represents an outdoor floor) to a 'o' string (which represents an indoor floor).

def floodFill(mapObj, x, y, oldCharacter, newCharacter):
"""Changes any values matching oldCharacter on the map object to
newCharacter at the (x, y) position, and does the same for the
positions to the left, right, down, and up of (x, y), recursively."""

# In this game, the flood fill algorithm creates the inside/outside
# floor distinction. This is a "recursive" function.
#   http://en.Wikipedia.org/wiki/Flood_fill
if mapObj[x][y] == oldCharacter:
mapObj[x][y] = newCharacter

if x < len(mapObj) - 1 and mapObj[x+1][y] == oldCharacter:
floodFill(mapObj, x+1, y, oldCharacter, newCharacter) # call right
if x > 0 and mapObj[x-1][y] == oldCharacter:
floodFill(mapObj, x-1, y, oldCharacter, newCharacter) # call left
if y < len(mapObj[x]) - 1 and mapObj[x][y+1] == oldCharacter:
floodFill(mapObj, x, y+1, oldCharacter, newCharacter) # call down
if y > 0 and mapObj[x][y-1] == oldCharacter:
floodFill(mapObj, x, y-1, oldCharacter, newCharacter) # call up


Line 10  and 11  converts the tile at the XY coordinate passed to floodFill() to the newCharacter string if it originally was the same as the oldCharacter string.

These four if statements check if the tile to the right, left, down, and up of the XY coordinate are the same as oldCharacter, and if so, a recursive call is made to floodFill() with those coordinates.

To better understand how the floodFill() function works, here is a version that does not use recursive calls, but instead uses a list of XY coordinates to keep track of which spaces on the map should be checked and possibly changed to newCharacter.

def floodFill(mapObj, x, y, oldCharacter, newCharacter):
spacesToCheck = []
if mapObj[x][y] == oldCharacter:
spacesToCheck.append((x, y))
while spacesToCheck != []:
x, y = spacesToCheck.pop()
mapObj[x][y] = newCharacter

if x < len(mapObj) - 1 and mapObj[x+1][y] == oldCharacter:
spacesToCheck.append((x+1, y)) # check right
if x > 0 and mapObj[x-1][y] == oldCharacter:
spacesToCheck.append((x-1, y)) # check left
if y < len(mapObj[x]) - 1 and mapObj[x][y+1] == oldCharacter:
spacesToCheck.append((x, y+1)) # check down
if y > 0 and mapObj[x][y-1] == oldCharacter:
spacesToCheck.append((x, y-1)) # check up


If you would like to read a more detailed tutorial on recursion that uses cats and zombies for an example, go to http://invpy.com/recursivezombies.

This page titled 10.16: The Flood Fill Algorithm is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Al Sweigart via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.