迷宫不是随机的

Question

嘿，我正在构建一个生成迷宫的程序，以便稍后将路径转换为我的图形部分。我已经大部分工作了，但是，每次你只要走东线和南线，就能到达终点。即使我将宽度设置为 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 循环中它完全没问题。然而，现在所有的方块都没有填满。

Answer 1

您使用的是迭代方法，而不是像代码所述的递归方法！

查看有关迷宫生成的一系列精彩文章（从递归回溯开始）：

http://weblog.jamisbuck.org/2010/12/27/maze- Generation-recursive-backtracking

Answer 2

您有一个迭代迷宫生成器，而不是递归回溯迷宫生成器。 Gen 目前的形式不是递归的；它是迭代的。您为每个图块调用一次；如果您检查逐步执行，问题应该很明显。