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: # 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.