在 python 中递归构建完美迷宫
build a perfect maze recursively in python
我有这个项目要使用 python 递归地构建一个完美的迷宫。我有一个 MyStack class，它创建一个堆栈来跟踪我经过的路径。还有一个 Cell class 代表迷宫中的每个方块并存储一些信息。我想我完成了代码，但 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 就像您得到的那样。
要解决此问题，您可以为迷宫 class 定义一个 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():
#...
然而，正如您最终会看到的那样，您的代码存在更多问题，但这会让您克服这一特定问题。
我有这个项目要使用 python 递归地构建一个完美的迷宫。我有一个 MyStack class，它创建一个堆栈来跟踪我经过的路径。还有一个 Cell class 代表迷宫中的每个方块并存储一些信息。我想我完成了代码，但 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 就像您得到的那样。
要解决此问题，您可以为迷宫 class 定义一个 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():
#...
然而，正如您最终会看到的那样，您的代码存在更多问题，但这会让您克服这一特定问题。