# 10.16: The Flood Fill Algorithm

- Page ID
- 14677

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. # For more info on the Flood Fill algorithm, see: # 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 [522] and 11 [523] 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.