迷宫不随机

Question

你好，我正在制作一个程序，用来生成迷宫，这样我就可以把路径转化为图形部分。我大部分功能都已经实现了，不过每次我都只能选择向东和向南的路线，这样就能到达终点。即使我把宽度设置得很大，比如64，这样迷宫就是64*64的，我还是只能选择这两条路线到达终点。我真的不明白为什么会这样。下面是我的代码，比较容易理解。

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循环中就没问题了。不过现在所有的方块都没有填满。

数据结构递归算法优化图形处理 while循环迷宫生成路径算法迷宫填充

迷宫不随机

2 个回答

撰写回答