本文介绍了在python中递归建立一个完美的迷宫的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我有这个项目，可以使用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〜
解决方案问题是您不能确保步行的步骤有效.
您目前所拥有的方式，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(): #...但是，如您最终看到的那样，您的代码还有更多问题，但这将使您摆脱这一特定的难题.
I have this project to build a perfect maze recursively by using python. I have a MyStack class which creates a stack to track the path that I go through. And a Cell class which represent each square within the maze and store some information. I think I complete the code but IDLE gives me some error that I couldn't figure out. Here is the code.
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.westHere is the Error I got:
>>> 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 rangeI'm new to programming, any help would be appreciate. Thank you~
After fix the previous one, I got an error for the line
if len(neighboor) != 0: new = choice(neighboor.remove(new))The error message is
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()But I define 'neighboor' as a list, it should has a len()
Thank you so much for help! plzplz~
解决方案The problem is that you're not ensuring that the steps in your walk are valid.
The way you have it currently, walk could pick a neighboor that is out of the bounds of the maze. For example, if a maze is 5x5, attempting to access maze[5][?] or maze[?][5] will result in an IndexError like you get.
To fix this, you could define an is_valid method for your maze class, e.g.:
def is_valid(self, x, y): return (0 <= x < self.size) and (0 <= y < self.size)Then, you when you pick a neighboor, you ensure it's valid:
#... else: new = choice(neighboor) while self.is_valid(new[0], new[1]) == False: new = choice(neighboor) while self.maze[new[0]][new[1]].getVisit(): #...This snippet picks a neighboor, then, if it's not valid, regenerates new until it finds a valid one.
But this loop would be better written as:
#... else: while True: new = choice(neighboor) if self.is_valid(new[0], new[1]): break while self.maze[new[0]][new[1]].getVisit(): #...There are more problems with your code, however, as you'll eventually see, but this will get you past this specific one.
更多推荐
在python中递归建立一个完美的迷宫
发布评论