在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(): 
#... 

还有更多的问题与您的代码，但是，因为你最终会看到，但是这将让你过去的这个特定的一个。