Hey there, I am building a program that generates a maze so I can later translate the path to my graphical part. I have most of it working, however, every time you can just take the east and south routes, and you'll get to the end. Even if I set the width as high as 64, so the maze is 64*64, I'm able to choose those 2 options and get to the end every time. I really don't understand why it is doing that. The code is below, it's fairly easy to understand.
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!"
As you can see, I think the problem is at the point where I generate the maze, however, when I just have it go until the current point is at the end, it doesn't fill every maze and is usually just one straight path. Thanks for helping.
Update:
I have changed the for loop that generates the maze to a simple while loop and it seems to work much better. It seems that when the for loop ran, it didn't go recursively, however, in the while loop it's perfectly fine. However, now all the squares do not fill out.
