在python中递归建立一个完美的迷宫 [英] build a perfect maze recursively in python
本文介绍了在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.west
Here 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 range
I'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中递归建立一个完美的迷宫的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
