Python fatal error: cannot be recovered from. During the flood

Question

I am at a standstill, and after an excessive (and unsuccessful) Google search, I need help.

I am creating a simple PyQt4 widget in which it consists of a grid of 60x80 squares, each of which has a value of None . If the user clicks on this field, it changes color depending 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, he fills the area using the usual recursive filling algorithm. This works great for small spaces, however, if the space is large enough, the program exits with a Fatal Python error: Cannot recover from stack overflow. I have no idea how to fix this, perhaps a fill that is not recursive?

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

Here is the program as a 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 someone help diagnose the problem, or perhaps indicate a direction to solve it?

Answer 1

You are using a stack-based forest fire algorithm, which is known to consume a lot of stack, so it is best avoided.

My suggestion is to avoid recursion: an alternative forest fire algorithm

I even implemented this using your class objects. I tested it with some ASCII art, as well as with your real code, and it worked perfectly even in large areas:

 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 it should be filled. If it needs to be filled, it inserts it into the queue and starts the loop.

The loop simply extracts the element from the queue, changes its color and tries to do the same for its neighbors: if everything is still in the picture (checking the x, y borders) and not the diagonals, and the color is not defined for the neighbor, just insert the coordinates into the queue.

The cycles stop when all the elements are processed: after a while, either you reach the edges or you meet only filled points, so additional points will not be queued.

This approach relies only on available memory, not on the stack.

Proof that this works: successfully filled a huge blue zone without.