Błąd krytycznego Pythona: nie można odzyskać danych po przepełnieniu stosu. Podczas Flood Fill

Question

Doszedłem do ślepego zaułka, a po nadmiernych (i nieudanych) Googlingach potrzebuję pomocy.

Buduję prosty widżet PyQt4, w którym znajduje się siatka o wymiarach 60x80 kwadratów, z których każdy jest zainicjowany na None. Jeżeli użytkownik kliknie na tym polu zmienia kolor na podstawie tego, ile razy lewej kliknięciu zdefiniowane przez tę 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 

] 

Jeśli użytkownik kątem kliknięć, to powódź wypełnia powierzchnię, korzystając ze wspólnego rekurencyjną wypełnienia powódź algo . Działa to doskonale dla małych przestrzeni, jednak jeśli przestrzeń jest wystarczająco duża, program kończy się niepowodzeniem z błędem Fatal Python error: Cannot recover from stack overflow. Nie mam pojęcia, jak to naprawić, być może wypełnienie powodziowe, które nie jest rekurencyjne?

Wszystkie kwadraty i kolejne kody kolorów są przechowywane w self.cells tak ustawiając self.cells[(y,x)]=1 by ustawić komórkę (y,x) do koloru Sand.

Oto program w całości.

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

Czy ktoś może pomóc zdiagnozować problem lub wskazać kierunek jego naprawy? Jeśli nie wyjaśniłem czegoś wystarczająco szczegółowo, daj mi znać, a ja to naprawię.

Dzięki!

Answer 1

Używasz algorytmu pożaru opartego na stosie, o którym wiadomo, że je dużo, więc lepiej go unikać.

Moja propozycja, aby uniknąć rekurencji: alternate forest fire algorithm

I nawet to realizowane przy użyciu obiektów klasy. Testowałem go z jakimś ASCII-art, a także z rzeczywistym kodzie i to działało dobrze nawet na dużych obszarach:

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

Po przejechaniu punkt, sprawdza, czy muszą być wypełnione. Jeśli trzeba go wypełnić, wstawia go do kolejki i uruchamia pętlę.

Pętla właśnie wyskakuje z kolejki, zmienia jej kolor i próbuje zrobić to samo dla jej sąsiadów: jeśli wciąż na zdjęciu (sprawdzanie granicy x, y), a nie przekątnych, i bez koloru zdefiniowanego na sąsiad, po prostu wstaw koordynację w kolejce.

Pętle zostają zatrzymane po przetworzeniu wszystkich przedmiotów: po pewnym czasie albo dojdziesz do krawędzi, albo napotkasz tylko wypełnione punkty, więc żadne dodatkowe punkty nie są w kolejce.

Podejście to opiera się tylko na dostępnej pamięci, a nie na stosie.

Dowód, że to działa: pomyślnie wypełniono ogromną niebieską strefę bez przepełnienia stosu.