Fatal Python error: Cannot recover from stack overflow. During Flood Fill

Question

I've come to a dead end, and after excessive (and unsuccessful) Googling, I need help.

I'm building a simple PyQt4 Widget where it lies out a grid of 60x80 squares, each initialized to None. If the user clicks on that box it changes color based on how many times left-clicked, defined by this list:

self.COLORS=[
        (0, 0, 255),        #WATER
        (255, 210, 128),    #SAND
        (0, 128, 0),       #GREEN
        (255, 255, 0),    #YELLOW
        (255, 165, 0),    #ORANGE
        (255, 0, 0)          #RED

]

If the user right clicks, it flood fills an area, using the common recursive flood fill algo. This works perfectly for small spaces, however if the space is large enough the program fails with the error Fatal Python error: Cannot recover from stack overflow. I have no idea how to fix this, perhaps a flood fill that isn't recursive?

All squares and subsequent color codes are stored in self.cells so by setting self.cells[(y,x)]=1 would set cell (y,x) to the Sand color.

Here is the program in whole.

import sys
from PyQt4 import QtGui, QtCore

class Example(QtGui.QWidget):

    def __init__(self, cell_size=10, swidth=800, sheight=600):
        QtGui.QWidget.__init__(self)
        self.resize(swidth,sheight)

        self.cell_size = cell_size
        self.height = sheight
        self.width = swidth
        self.columns = self.width // self.cell_size
        self.rows = self.height // self.cell_size

        self.COLORS=[
                (0, 0, 255),        #WATER
                (255, 210, 128),    #SAND
                (0, 128, 0),       #GREEN
                (255, 255, 0),    #YELLOW
                (255, 165, 0),    #ORANGE
                (255, 0, 0)          #RED

        ]

        self.cells = {(x,y):None for x in range(1,self.columns+1) for y in range(1,self.rows+1)}        

    def translate(self,pixel_x, pixel_y):
        "Translate pixel coordinates (pixel_x,pixel_y), into grid coordinates"
        x = pixel_x * self.columns // self.width + 1
        y = pixel_y * self.rows // self.height  + 1
        return x,y

    def check_cell(self,x,y):
        if self.cells[(x,y)] <= 0:
            self.cells[(x,y)]=0
        elif self.cells[(x,y)] >= len(self.COLORS)-1:
            self.cells[(x,y)]=len(self.COLORS)-1
        else:
            pass

    def draw_cell(self, qp, col, row):
        x1,y1 = (col-1) * self.cell_size, (row-1) * self.cell_size
        x2,y2 = (col-1) * self.cell_size + self.cell_size, (row-1) * self.cell_size + self.cell_size 
        qp.drawRect(x1, y1, x2-x1, y2-y1)

    def color_cell(self, qp, col, row):
        qp.setBrush(QtGui.QColor(*self.COLORS[self.cells[(col,row)]]))
        self.draw_cell(qp, col, row)

    def draw_grid(self, qp):
        qp.setPen(QtGui.QColor(128,128,128)) # gray
        # Horizontal lines
        for i in range(self.rows):
            qp.drawLine(0, i * self.cell_size, self.width, i * self.cell_size)
        # Vertical lines
        for j in range(self.columns):
            qp.drawLine(j * self.cell_size, 0, j * self.cell_size, self.height)

    def set_all(self, type):
        self.cells = {(x,y):type for x in range(1,self.columns+1) for y in range(1,self.rows+1)}  
        self.repaint()

    def fill(self, x, y, type):
        print(x,y)
        if x < 1 or x >= self.columns+1 or y < 1 or y >= self.rows+1:
            return
        if self.cells[(x,y)] != None:
            return
        self.cells[(x,y)] = type
        self.repaint()
        self.fill(x+1, y, type)
        self.fill(x-1, y, type)
        self.fill(x, y+1, type)
        self.fill(x, y-1, type)


    def paintEvent(self, e):
        qp = QtGui.QPainter()
        qp.begin(self)
        self.draw_grid(qp)
        for row in range(1, self.rows+1):
            for col in range(1, self.columns+1):
                if self.cells[(col,row)] != None:
                    self.color_cell(qp, col, row)
        qp.end()

    def drawPoints(self, qp):
        size = self.size()

        for i in range(1000):
            x = random.randint(1, size.width()-1)
            y = random.randint(1, size.height()-1)
            qp.drawPoint(x, y)  

    def mousePressEvent(self, e):
        x,y = self.translate(e.pos().x(),e.pos().y())

        if e.button() == QtCore.Qt.LeftButton:
            if self.cells[(x,y)] == None:
                self.cells[(x,y)]=0
            else:
                self.cells[(x,y)]+=1
                self.check_cell(x,y)

        elif e.button() == QtCore.Qt.RightButton:
            self.fill(x,y,0)
            '''
            if self.cells[(x,y)] == None:
                self.cells[(x,y)]=0
            else:  
                self.cells[(x,y)]-=1
                self.check_cell(x,y)
            '''            
        else: pass

        self.repaint()

    def save(self):
        return self.cells

    def open(self, new_cells):
        self.cells=new_cells
        self.repaint()


def main():
    app = QtGui.QApplication(sys.argv)
    ex = Example()
    ex.show()
    sys.exit(app.exec_())


if __name__ == '__main__':
    main()

Can anyone help diagnose the problem or perhaps point in a direction to fix it?

Answer 1

You are using a stack-based forest fire algorithm, known to eat a lot of stack, so it's better to avoid it.

My proposal to avoid recursion: alternate forest fire algorithm

I even implemented it using your class objects. Tested it with some ASCII-art and also with your actual code and it worked fine even on big zones:

def fill(self, x, y, t):
    if self.cells[(x,y)] == None:  # cannot use not: there are 0 values
        to_fill = [(x,y)]
        while to_fill:
            # pick a point from the queue
            x,y = to_fill.pop()
            # change color if possible
            self.cells[(x,y)] = t

            # now the neighbours x,y +- 1
            for delta_x in range(-1,2):
                xdx = x+delta_x
                if xdx > 0 and xdx < self.columns+1:
                    for delta_y in range(-1,2):
                        ydy = y+delta_y
                        # avoid diagonals
                        if (delta_x == 0) ^ (delta_y == 0):
                            if ydy > 0 and ydy < self.rows+1:
                                # valid x+delta_x,y+delta_y
                                # push in queue if no color
                                if self.cells[(xdx,ydy)] == None:
                                    to_fill.append((xdx,ydy))
    self.repaint()

When you pass a point, it checks if must be filled. If must be filled, it inserts it in the queue and runs a loop.

The loop just pops an item from the queue, changes its color, and attempts to do the same for its neighbors: if still in the picture (x,y boundary checking) and not the diagonals, and no color defined on the neighbour, just insert the coord in the queue.

The loops stops when all items have been processed: after a while, either you reach the edges or you encounter only filled points, so no extra points are queued.

This approach only relies on available memory, not stack.

Proof that it works: successfully filled a huge blue zone without stack overflow.