The Python Book

floodfill stack
20151010

# Flood fill

• Turn lines of text into a grid[row][column] (taking care to pad the lines to get a proper rectangle)
• Central data structure for the flood-fill is a stack
• If the randomly chosen point is blank, then fill it, and push the coordinates of its 4 neighbours onto the stack
• Handle the neighbouring points the same way

Src:

``````#!/usr/bin/python

import random

lines='''
+++++++        ++++++++++                ++++++++++++++++++++    +++++
+     +        +        +                +                  +    +   +
+     +        +        +                +                  +    +++++
+     +        +     ++++                +                  +
+++++++        +                         +                  +
+     ++++                +                  +
+        +                +                  +
+        +                +                  +
+        +                +                  +
++++++++++                +                  +
+                  +
+                  +
++++++++++++                        +                  +
+          +                        +                  +
+          +                         +                +
+          +                          +              +
++++++++++++                           ++++++++++++++
'''.split("\n")

# maximum number of columns and rows
colmax= max( [ len(line) for line in lines ] )
rowmax=len(lines)

grid= [ list(lines[row]+padding)[0:colmax]  for row in range(0,rowmax) ]

for l in grid: print( ''.join(l) )   # print the grid
print '-' * colmax                   # print a separating line

# creat a stack, and put a random coordinate on it
pointstack=[]
pointstack.append( ( random.randint(0,colmax),      # col
random.randint(0,rowmax) ) )   # row

# floodfill
while len(pointstack)>0:
(col,row)=pointstack.pop()
if col>=0 and col<colmax and row>=0 and row<rowmax:
if grid[row][col]==' ':
grid[row][col]='O'
if col<(colmax-1): pointstack.append( (col+1,row))
if col>0:          pointstack.append( (col-1,row))
if row<(rowmax-1): pointstack.append( (col,row+1) )
if row>0:          pointstack.append( (col,row-1) )

for l in grid: print( ''.join(l) ) # print the grid``````

Output of a few runs:

``````+++++++        ++++++++++                ++++++++++++++++++++    +++++
+     +        +        +                +OOOOOOOOOOOOOOOOOO+    +   +
+     +        +        +                +OOOOOOOOOOOOOOOOOO+    +++++
+     +        +     ++++                +OOOOOOOOOOOOOOOOOO+
+++++++        +                         +OOOOOOOOOOOOOOOOOO+
+     ++++                +OOOOOOOOOOOOOOOOOO+
+        +                +OOOOOOOOOOOOOOOOOO+
+        +                +OOOOOOOOOOOOOOOOOO+
+        +                +OOOOOOOOOOOOOOOOOO+
++++++++++                +OOOOOOOOOOOOOOOOOO+
+OOOOOOOOOOOOOOOOOO+
+OOOOOOOOOOOOOOOOOO+
++++++++++++                        +OOOOOOOOOOOOOOOOOO+
+          +                        +OOOOOOOOOOOOOOOOOO+
+          +                         +OOOOOOOOOOOOOOOO+
+          +                          +OOOOOOOOOOOOOO+
++++++++++++                           ++++++++++++++               ``````

Completely flooded:

``````OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
+++++++OOOOOOOO++++++++++OOOOOOOOOOOOOOOO++++++++++++++++++++OOOO+++++OOO
+     +OOOOOOOO+OOOOOOOO+OOOOOOOOOOOOOOOO+                  +OOOO+   +OOO
+     +OOOOOOOO+OOOOOOOO+OOOOOOOOOOOOOOOO+                  +OOOO+++++OOO
+     +OOOOOOOO+OOOOO++++OOOOOOOOOOOOOOOO+                  +OOOOOOOOOOOO
+++++++OOOOOOOO+OOOOOOOOOOOOOOOOOOOOOOOOO+                  +OOOOOOOOOOOO
OOOOOOOOOOOOOOO+OOOOO++++OOOOOOOOOOOOOOOO+                  +OOOOOOOOOOOO
OOOOOOOOOOOOOOO+OOOOOOOO+OOOOOOOOOOOOOOOO+                  +OOOOOOOOOOOO
OOOOOOOOOOOOOOO+OOOOOOOO+OOOOOOOOOOOOOOOO+                  +OOOOOOOOOOOO
OOOOOOOOOOOOOOO+OOOOOOOO+OOOOOOOOOOOOOOOO+                  +OOOOOOOOOOOO
OOOOOOOOOOOOOOO++++++++++OOOOOOOOOOOOOOOO+                  +OOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO+                  +OOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO+                  +OOOOOOOOOOOO
OOOOO++++++++++++OOOOOOOOOOOOOOOOOOOOOOOO+                  +OOOOOOOOOOOO
OOOOO+          +OOOOOOOOOOOOOOOOOOOOOOOO+                  +OOOOOOOOOOOO
OOOOO+          +OOOOOOOOOOOOOOOOOOOOOOOOO+                +OOOOOOOOOOOOO
OOOOO+          +OOOOOOOOOOOOOOOOOOOOOOOOOO+              +OOOOOOOOOOOOOO
OOOOO++++++++++++OOOOOOOOOOOOOOOOOOOOOOOOOOO++++++++++++++OOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO``````

Notes by Willem Moors. Generated on momo:/home/willem/sync/20151223_datamungingninja/pythonbook at 2019-07-31 19:22