在Python中遞歸地構建一個完美的迷宮

Question

我有這個項目通過使用python遞歸地構建一個完美的迷宮。我有一個MyStack類，創建一個堆棧來跟蹤我經歷的路徑。還有一個Cell類，代表迷宮中的每個方塊並存儲一些信息。我認爲我完成了代碼，但IDLE給了我一些我無法弄清楚的錯誤。這是代碼。

from random import * 
from graphics import * 

class MyStack: 

    def __init__(self): 
     self.S = [] 

    def push(self, item): 
     self.S.insert(0, item) 

    def pop(self): 
     return self.S.pop(0) 

    def isEmpty(self): 
     return True if len(self.S) == 0 else False 

    def size(self): 
     return len(self.S) 

class Maze: 
    def __init__(self, N): 

     self.size = N 
     self.maze = [[i for i in range(N + 2)] for i in range(N + 2)] 

     for r in range(self.size + 2): 
      for c in range(self.size + 2): 
       self.maze[r][c] = Cell() 

    def walk(self, s, x, y): 

     neighboor = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)] 

     if s.size() == self.size**2: return 

     else: 
      new = choice(neighboor) 

      while self.maze[new[0]][new[1]].getVisit(): 

       while new[0] < 1 or new[1] > self.size: 

        new = choice(neighboor) 

       if neighboor != []: new = choice(neighboor.remove(new)) 
       else: 
        temp = s.pop(s) 
        x, y = temp[0], temp[1] 
        self.walk(s, x, y) 

      if new == neighboor[0]: 
       self.maze[x][y].changeNorth() 
       self.maze[new[0]][new[1]].changeSouth() 
      elif new == neighboor[1]: 
       self.maze[x][y].changeSouth() 
       self.maze[new[0]][new[1]].changeNorth() 
      elif new == neighboor[2]: 
       self.maze[x][y].changeEast() 
       self.maze[new[0]][new[1]].changeWest() 
      elif new == neighboor[3]: 
       self.maze[x][y].changeWest() 
       self.maze[new[0]][new[1]].changeEast() 


      s.push(new) 

      self.walk(s, new[0], new[1]) 

    def search(self): 
     startX, startY = randint(1, self.size), randint(1, self.size) 

     s = MyStack() 

     temp = (startX, startY) 

     s.push(temp) 

     self.maze[startX][startY].changeVisit() 

     self.walk(s, startX, startY) 

    def draw(self): 

     win = GraphWin() 

     startXY = Point(27, 27) 
     start = Circle(startXY, 5) 
     start.setOutline('orange') 
     start.setFill('orange') 
     start.draw(win) 

     x, y = 20, 20 


     for r in range(1, self.size + 1): 
      for c in range(1, self.size + 1): 
       if self.maze[r][c].getNorth(): 
        unit = Line(Point(x, y), Point(x + 15, y)) 
        unit.draw(win) 

       x, y = x + 15, y 

      x, y = 20, y + 15 

     x, y = 20, 20 
     for c in range(1, self.size + 1): 
      for r in range(1, self.size + 1): 
       if self.maze[r][c].getWest(): 
        #print(self.maze[r][c].getWest()) 
        unit = Line(Point(x, y), Point(x, y + 15)) 
        unit.draw(win) 

       x, y = x, y + 15 

      x, y = x + 15, 20 

     x, y = 20, self.size * 15 + 20 
     for c in range(1, self.size + 1): 
      if self.maze[self.size][c].getSouth(): 
       unit = Line(Point(x, y), Point(x + 15, y)) 
       unit.draw(win) 
      x, y = x + 15, y 

     x, y = self.size * 15 + 20, 20 
     for r in range(1, self.size + 1): 
      if self.maze[self.size][c].getEast(): 
       unit = Line(Point(x, y), Point(x, y + 15)) 
       unit.draw(win) 
      x, y = x, y + 15 

class Cell: 
    def __init__(self): 
     #self.x = x 
     #self.y = y 
     self.north = True 
     self.south = True 
     self.east = True 
     self.west = True 
     self.visit = False 

    def changeVisit(self): 
     self.visit = True 

    def changeNorth(self): 
     self.north = False 

    def changeSouth(self): 
     self.south = False 

    def changeEast(self): 
     self.east = False 

    def changeWest(self): 
     self.west = False 

    def getVisit(self): 
     return self.visit 

    def getNorth(self): 
     return self.north 

    def getSouth(self): 
     return self.south 

    def getEast(self): 
     return self.east 

    def getWest(self): 
     return self.west 

這是我得到的錯誤：

>>> a = Maze(5) 
>>> a.search() 
Traceback (most recent call last): 
    File "<pyshell#1>", line 1, in <module> 
    a.search() 
    File "C:\Users\Serena\Desktop\XAproject\Stack.py", line 91, in search 
    self.walk(s, startX, startY) 
    File "C:\Users\Serena\Desktop\XAproject\Stack.py", line 76, in walk 
    self.walk(s, new[0], new[1]) 
    File "C:\Users\Serena\Desktop\XAproject\Stack.py", line 76, in walk 
    self.walk(s, new[0], new[1]) 
    File "C:\Users\Serena\Desktop\XAproject\Stack.py", line 76, in walk 
    self.walk(s, new[0], new[1]) 
    File "C:\Users\Serena\Desktop\XAproject\Stack.py", line 76, in walk 
    self.walk(s, new[0], new[1]) 
    File "C:\Users\Serena\Desktop\XAproject\Stack.py", line 76, in walk 
    self.walk(s, new[0], new[1]) 
    File "C:\Users\Serena\Desktop\XAproject\Stack.py", line 76, in walk 
    self.walk(s, new[0], new[1]) 
    File "C:\Users\Serena\Desktop\XAproject\Stack.py", line 76, in walk 
    self.walk(s, new[0], new[1]) 
    File "C:\Users\Serena\Desktop\XAproject\Stack.py", line 76, in walk 
    self.walk(s, new[0], new[1]) 
    File "C:\Users\Serena\Desktop\XAproject\Stack.py", line 76, in walk 
    self.walk(s, new[0], new[1]) 
    File "C:\Users\Serena\Desktop\XAproject\Stack.py", line 48, in walk 
    while self.maze[new[0]][new[1]].getVisit(): 
IndexError: list index out of range 

我新的節目，任何幫助將升值。謝謝〜

修復一前一後，我得到了行錯誤

if len(neighboor) != 0: new = choice(neighboor.remove(new)) 

的錯誤消息是

Traceback (most recent call last): 


File "<pyshell#11>", line 1, in <module> 
    a.search() 
    File "C:\Users\Serena\Desktop\XAproject\Stack.py", line 88, in search 
    self.walk(s, startX, startY) 
    File "C:\Users\Serena\Desktop\XAproject\Stack.py", line 73, in walk 
    self.walk(s, new[0], new[1]) 
    File "C:\Users\Serena\Desktop\XAproject\Stack.py", line 52, in walk 
    if len(neighboor) != 0: new = choice(neighboor.remove(new)) 
    File "C:\Python34\lib\random.py", line 253, in choice 
    i = self._randbelow(len(seq)) 
TypeError: object of type 'NoneType' has no len() 

但我定義「neighboor」作爲一個列表，它應該有一個len（）

非常感謝你的幫助！ plzplz〜

Answer 1

問題是，你不能確保你的步行步驟是有效的。

您目前的方式，walk可能會選擇一個neighboor超出了迷宮的界限。例如，如果迷宮是5x5，則試圖訪問maze[5][?]或maze[?][5]將導致您獲得IndexError。

爲了解決這個問題，你可以定義一個is_valid方法爲您的迷宮類，如：

def is_valid(self, x, y): 
    return (0 <= x < self.size) and (0 <= y < self.size) 

然後，當你選擇一個neighboor，可以確保它是有效的：

#... 
else: 
    new = choice(neighboor) 
    while self.is_valid(new[0], new[1]) == False: 
     new = choice(neighboor) 

    while self.maze[new[0]][new[1]].getVisit(): 
#... 

這代碼片段選取neighboor，然後，如果它無效，則重新生成new，直到找到有效的片段。

但這個循環將被更好地寫成：

#... 
else: 
    while True: 
     new = choice(neighboor) 
     if self.is_valid(new[0], new[1]): break 

    while self.maze[new[0]][new[1]].getVisit(): 
#... 

還有更多的問題與您的代碼，但是，因爲你最終會看到，但是這將讓你過去的這個特定的一個。