Flood Fill Algorithm Python

Question

So I'm trying to create a flood fill algorithm and I keep getting a recursion error with this. The algorithm seems to have infinite recursion and I cannot pinpoint why. I have looked all over the internet and I cannot find a solution as it seems like my program is correct according to most sources. There seems to be something wrong however. This is the edited version of the code. The error message is still maximum recursions.

Can I get some help?

    from Tkinter import *
    from PIL import Image, ImageTk
    from random import *


    w= 75
    h= w

    flood = Image.new("RGB", (w,h), (0,0,0))

    x = 0
    y = 0
    count = 0

    colorlist = []
    i = 0

    while x < w -1:
        y = 0
        while y < h-1:
            r = random()
            if r < .25:
                flood.putpixel((x,y), (0,0,0))
            else:
                flood.putpixel((x,y), (255,255,255))
            y += 1
        x += 1
    x = 0
    y = 0
    while x < w-1:
        y = 0
        while y < h-1:
            r = random()
            if x == 0 or y == 0 or x == w-1 or y ==h-1:
                flood.putpixel((x,y), (0,0,0))
            y += 1
        x += 1


    def floodfill(x,y, d,e,f, g,h,i, image, count):
            count+=1
            (a,b,c) = image.getpixel((x,y))
            if (a,b,c) == (255,255,255):
                (j,k,l) = image.getpixel((x-1,y))
                (m,n,o) = image.getpixel((x+1, y))
                (p,q,r) = image.getpixel((x,y-1))
                (s,t,u) = image.getpixel((x,y+1))
            if count > 990:
                return
            if (a,b,c) == (255,255,255):
                image.putpixel((x,y), (g,h,i))
                floodfill(x-1, y, d,e,f, g,h,i, image, count)
                floodfill(x+1, y, d,e,f, g,h,i, image, count)
                floodfill(x, y-1, d,e,f, g,h,i, image, count)
                floodfill(x, y+1, d,e,f, g,h,i, image,count)



    floodfill(2,2, 0,0,0,255,0,0,flood, 0)

    flood.save("flood.png")
    print "done"

Answer 1

This has not been tested but is based mostly off the code you provided. It should work and provides an alternative method of implementing the floodfill algorithm. The function could be more efficient.

import PIL
import random
import collections

WHITE = 255, 255, 255
BLACK = 0, 0, 0
RED = 255, 0, 0

def main(width, height):
    flood = PIL.Image.new('RGB', (width, height), BLACK)
    # Create randomly generated walls
    for x in range(width):
        for y in range(height):
            flood.putpixel((x, y), BLACK if random.random() < 0.15 else WHITE)
    # Create borders
    for x in range(width):
        for y in range(height):
            if x in {0, width - 1} or y in {0, height - 1}:
                flood.putpixel((x, y), BLACK)
    floodfill(50, 25, RED, image)
    # Save image
    image.save('flood.png')

def floodfill(x, y, color, image):
    # if starting color is different from desired color
    #     create a queue of pixels that need to be changed
    #     while there are pixels that need their color changed
    #         change the color of the pixel to what is desired
    #         for each pixel surrounding the curren pixel
    #             if the new pixel has the same color as the starting pixel
    #                 record that its color needs to be changed
    source = image.getpixel((x, y))
    if source != color:
        pixels = collections.deque[(x, y)]
        while pixels:
            x, y = place = pixels.popleft()
            image.putpixel(place, color)
            for x_offset in -1, 1:
                x_offset += x
                for y_offset in -1, 1:
                    y_offset += y
                    new_place = x_offset, y_offset
                    if image.getpixel(new_place) == source:
                        pixels.append(new_place)

if __name__ == '__main__':
    main(100, 50)

Answer 2

Instead of recursion, why not flood-fill in a depth-first manner? Recursion uses an implicit stack anyway so you've nothing to lose.

And yes, as pointed out in the comments, you should be checking for x and y being out of bounds.

Answer 3

Python has a tendency to throw a maximum recursion depth exceeded error, even if the algorithm doesn't recurse infinitely and would eventually halt on its own. There are two solutions to this: increase the recursion limit, or switch to an iterative algorithm.

You can raise your recursion limit with sys.setrecursionlimit. Choose a number higher than the worst-case recursion depth of your algorithm. In your case, that would be the number of pixels in your image, length * height.

Changing your algorithm into an iterative one is fairly simple, since it doesn't really matter in what order you paint the pixels, as long as you get them all at least once. A set is very well suited to holding unique non-ordered data, so let's use that to store the pixels we need to paint.

def floodFill(x,y, d,e,f, g,h,i, image):
    toFill = set()
    toFill.add((x,y))
    while not toFill.empty():
        (x,y) = toFill.pop()
        (a,b,c) == image.getpixel((x,y))
        if not (a,b,c) == (255, 255, 255):
            continue
        image.putpixel((x,y), (g,h,i))
        toFill.add((x-1,y))
        toFill.add((x+1,y))
        toFill.add((x,y-1))
        toFill.add((x,y+1))
    image.save("flood.png")

If you do use the iterative method, be sure to put bound checking in it. Otherwise, it might run forever! Or at least until your hard drive is filled by one gigantic toFill set.