Привет, я создаю программу, которая генерирует лабиринт, чтобы потом я мог перевести путь к моей графической части.У меня большая часть работы работает, однако, каждый раз, когда вы можете просто взять восточный и южный маршруты, и вы доберетесь до конца.Даже если я установлю ширину 64, то есть лабиринт будет 64 * 64, я смогу выбрать эти 2 варианта и каждый раз добираться до конца.Я действительно не понимаю, почему он это делает.Код ниже, его довольно легко понять.
import random
width = 8
def check(x,y):
"""Figures out the directions that Gen can move while"""
if x-1 == -1:
maze[x][y][3] = 0
if x+1 == width + 1:
maze[x][y][1] = 0
if y+1 == width + 1:
maze[x][y][2] = 0
if y-1 == -1:
maze[x][y][0] = 0
if x + 1 in range(0,width) and visited[x+1][y] == False:
maze[x][y][1] = 2
if x - 1 in range(0,width) and visited[x-1][y] == False:
maze[x][y][3] = 2
if y + 1 in range(0,width) and visited[x][y+1] == False:
maze[x][y][2] = 2
if y - 1 in range(0,width) and visited[x][y-1] == False:
maze[x][y][0] = 2
def possibleDirs(x,y):
"""Figures out the ways that the person can move in each square"""
dirs = []
walls = maze[x][y]
if walls[0] == 1:
dirs.append('n')
if walls[1] == 1:
dirs.append('e')
if walls[2] == 1:
dirs.append('s')
if walls[3] == 1:
dirs.append('w')
return dirs
def Gen(x,y):
"""Generates the maze using a depth-first search and recursive backtracking."""
visited[x][y] = True
dirs = []
check(x,y)
if maze[x][y][0] == 2:
dirs.append(0)
if maze[x][y][1] == 2:
dirs.append(1)
if maze[x][y][2] == 2:
dirs.append(2)
if maze[x][y][3] == 2:
dirs.append(3)
print dirs
if len(dirs):
#Randonly selects a derection for the current square to move
past.append(current[:])
pos = random.choice(dirs)
maze[x][y][pos] = 1
if pos == 0:
current[1] -= 1
maze[x][y-1][2] = 1
if pos == 1:
current[0] += 1
maze[x+1][y][3] = 1
if pos == 2:
current[1] += 1
maze[x][y+1][0] = 1
if pos == 3:
current[0] -= 1
maze[x-1][y][1] = 1
else:
#If there's nowhere to go, go back one square
lastPlace = past.pop()
current[0] = lastPlace[0]
current[1] = lastPlace[1]
#Build the initial values for the maze to be replaced later
maze = []
visited = []
past = []
#Generate empty 2d list with a value for each of the xy coordinates
for i in range(0,width):
maze.append([])
for q in range(0, width):
maze[i].append([])
for n in range(0, 4):
maze[i][q].append(4)
#Makes a list of falses for all the non visited places
for x in range(0, width):
visited.append([])
for y in range(0, width):
visited[x].append(False)
dirs = []
print dirs
current = [0,0]
#Generates the maze so every single square has been filled. I'm not sure how this works, as it is possible to only go south and east to get to the final position.
while current != [width-1, width-1]:
Gen(current[0], current[1])
#Getting the ways the person can move in each square
for i in range(0,width):
dirs.append([])
for n in range(0,width):
dirs[i].append([])
dirs[i][n] = possibleDirs(i,n)
print dirs
print visited
pos = [0,0]
#The user input part of the maze
while pos != [width - 1, width - 1]:
dirs = []
print pos
if maze[pos[0]][pos[1]][0] == 1:
dirs.append('n')
if maze[pos[0]][pos[1]][1] == 1:
dirs.append('e')
if maze[pos[0]][pos[1]][2] == 1:
dirs.append('s')
if maze[pos[0]][pos[1]][3] == 1:
dirs.append('w')
print dirs
path = raw_input("What direction do you want to go: ")
if path not in dirs:
print "You can't go that way!"
continue
elif path.lower() == 'n':
pos[1] -= 1
elif path.lower() == 'e':
pos[0] += 1
elif path.lower() == 's':
pos[1] += 1
elif path.lower() == 'w':
pos[0] -= 1
print"Good job!"
Как вы видите, я думаю, что проблема в том, что я генерирую лабиринт, однако, когда я просто продолжаю его до текущеготочка находится в конце, она не заполняет каждый лабиринт и обычно представляет собой один прямой путь.Спасибо за помощь.
Обновление: я изменил цикл for, который генерирует лабиринт, на простой цикл while, и он, кажется, работает намного лучше.Кажется, что когда цикл for выполнялся, он не работал рекурсивно, однако, в цикле while он прекрасно работает.Однако теперь все квадраты не заполняются.