Неустранимая ошибка Python: невозможно восстановить из переполнения стека. Во время Flood Fill

Question

Я пришел в тупик, и после чрезмерного (и неудачного) Googling мне нужна помощь.

Я строю простой виджет PyQt4, где он лежит сеткой квадратов 60x80, каждая из которых инициализирована до None. Если пользователь нажимает на поле он меняет цвет в зависимости от того, сколько раз левой кнопкой мыши, определяется в этом списке:

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 

] 

Если правильных пользователь щелкает, это наводнение заполняет область, используя общий рекурсивный заливки Algo , Это отлично работает для небольших пространств, однако, если пространство достаточно велико, программа выходит из строя с ошибкой Fatal Python error: Cannot recover from stack overflow. Я понятия не имею, как это исправить, возможно, заливка заливки, которая не является рекурсивной?

Все квадраты и последующие цветовые коды хранятся в self.cells так, установив self.cells[(y,x)]=1 бы установить ячейку (y,x) в Sand цвета.

Описание программы целиком.

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() 

Может ли кто-нибудь помочь диагностировать проблему или, возможно, указать направление ее исправить? Если я не объясню что-то достаточно подробно, дайте мне знать, и я это исправлю.

Спасибо всем!

Answer 1

Вы используете алгоритм лесного пожара на основе стека, который, как известно, содержит много стека, поэтому лучше избегать его.

Мое предложение, чтобы избежать рекурсии: alternate forest fire algorithm

Я даже реализовать его с помощью объектов класса. Испытано его с некоторыми ASCII-арт, а также с фактическим кодом и он работал отлично, даже на больших зонах:

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() 

Когда вы проходите точку, он проверяет, должны быть заполнены. Если он должен быть заполнен, он вставляет его в очередь и запускает цикл.

Петля просто выталкивает элемент из очереди, меняет цвет и пытается сделать то же самое для своих соседей: если все еще находится на картинке (x, y), а не диагонали, а цвет не определен на сосед, просто вставьте координату в очередь.

Петли останавливаются, когда все предметы обработаны: через какое-то время вы достигаете краев или вы встречаете только заполненные точки, поэтому лишние очки не поставлены в очередь.

Этот подход основан только на доступной памяти, а не на стеке.

Доказательство того, что он работает: успешно заполнил огромную синюю зону без переполнения стека.