实现递归回溯器以生成迷宫

Question

我正在尝试创建一个递归创建迷宫函数，但是，我卡住了，因为我不知道如何递归调用它并放置墙壁。

有人可以告诉我如何编辑我的代码以使其工作吗？谢谢

编辑：由于我没有添加我的迷宫 class，我想我应该添加它以帮助查看整个代码。

class Maze:
    def __init__(self, Width, Height):
        assert Width>= 1 and Height>= 1

        self.Width= Width
        self.Height= Height
        self.board = np.zeros((Width, Height), dtype=WALL_TYPE)
        self.board.fill(EMPTY)

    def set_borders(self):
        self.board[0, :] = self.board[-1, :] = WALL
        self.board[:, 0] = self.board[:, -1] = WALL

    def is_wall(self, x, y):
        assert self.in_maze(x, y)
        return self.board[x][y] == WALL

    def set_wall(self, x, y):
        assert self.in_maze(x, y)
        self.board[x][y] = WALL

def create_maze(Width, Height, seed=None):
        Width = (Width // 2) * 2 + 1
        Height = (Height // 2) * 2 + 1

        if seed is not None:
            np.random.seed(seed)

        maze = Maze(Width, Height)
        maze.set_borders()

        x, y = rand(0, Width // 2) * 2, rand(0, Height // 2) * 2
        maze.set_wall(x, y)

        visited = []

        visited.append((x,y))

        while len(visited):
            start = visited[-1]

            if maze.in_maze(x - 2, y):
                visited.append((x - 2, y))

            if maze.in_maze(x + 2, y):
                visited.append((x + 2, y))

            if maze.in_maze(x, y - 2):
                visited.append((x, y - 2))

            if maze.in_maze(x, y + 2):
                visited.append((x, y + 2))

            visited.remove(start) # This goes somewhere but I don't know where

            if not maze.is_wall(x,y):
                maze.set_wall(x,y)


        create_maze() #recurse?

Answer 1

初始问题

好的，开始时您通常不会像这样设置递归函数。由于您需要一遍又一遍地调用相同的函数，因此您不希望每次调用都重新创建迷宫对象。您希望在递归函数调用之外执行所有设置和计算，并且只递归执行一项非常具体的工作。

设置

我假设你的迷宫设置 class 有点像这样:

import random

class Maze:
    def __init__(self, width, height):

        self.width = width // 2 * 2 + 1
        self.height = height // 2 * 2 + 1

        # this creates a 2d-array for your maze data (False: path, True: wall)
        self.cells = [
                      [True for x in range(self.width)] 
                      for y in range(self.height)
                     ]

    def set_path(self, x, y):
        self.cells[y][x] = False

    def set_wall(self, x, y):
        self.cells[y][x] = True

思考迷宫的方法

好的，现在我可以开始递归生成本身了。现在，我没有采用添加墙壁的方法，而是用墙壁填满了整个迷宫，"dig" 我自己就是路径。

在我们的迷宫中，即使我们将其视为一个简单的 on/off 带有墙壁和路径的二维网格，将其描绘成更像一系列节点（连接点）和 link 在那些之间。我可以看到你开始用你确保你的迷宫宽度和高度是奇数的方式来实现这个 (Width // 2) * 2 + 1 例如，你只选择了偶数单元格（尽管我无法弄清楚为什么） .

这里有一个快速图表来形象化我的意思：

每个红色圆圈都是一个节点，正如您所见，每个奇数瓦片都包含一个节点并且始终是一个路径瓦片。我们会自动假设每个奇数块都包含一条路径（因此也包含一个节点）。这意味着当生成我们的迷宫时，当我们 "dig" 穿过时，我们将同时移动两个个单元格，这样我们就在两者之间创建了一个 link节点（灰色单元格）。

算法

我将要实现的算法的本质如下：

向随机方向移动，"digging"我前进的方向，跟踪我去过的地方
重复直到到达死胡同
'Backtrack' 遍历我去过的地方，直到找到一条至少有一条可行路径的路径。转到步骤 1

下面是相同的步骤，但更详细：

随机移动，记录我去过的地方

1.1。我们环顾每个方向，看看我们的移动选项在哪里

1.2。选择一个有有效路径的随机方向

1.3。移动到新节点（记住，我们移动两个个单元格）
重复直到走到死胡同

2.1。继续重复第一步中的过程

2.2。如果在第一步中，您没有找到任何路径选项，那么您已经走到了死胡同
回溯我去过的地方

3.1。跟随您的足迹（回溯）之前访问过的节点

3.2。重复直到找到一个节点，该节点至少有一个未访问的路径可以尝试

3.3。转到第一步（例如，开始通过新路径随机方向行走）

现在用递归函数来实现这些步骤。我们对新节点采取的每一步（通过移动两个单元格）都将是一个新的函数调用，具有新的 x-y 坐标。这是相同的步骤，但递归：

随机移动以记录我去过的地方

1.1。随机选择一个方向并检查它是否还没有被访问过（例如，如果我们已经沿着它走下去，我们就已经 "dug" 通过了，所以它就是一条路径）。所以选择任何一个方向是墙（例如未访问）

1.2。现在朝那个方向移动两个单元格（但请记住将两个节点单元格和两个节点之间的 link 单元格设置为路径，否则你只是跳过了一堵墙).请记住，当 'moving' 到一个新的单元格时，我们将使用新节点的 x-y 坐标再次调用该函数
重复直到到达死胡同

2.1。如果在第一步中，您发现所有方向都包含路径（例如，您已经访问了该节点的每个方向），则需要回溯

2.2。现在回溯，我们将退出当前函数调用。这意味着我们正在向后移动到先前的函数中，该函数最初将我们移动到当前节点
原路返回直到找到路径

3.1。退出函数调用后，您现在已经返回到具有先前 x-y 坐标的前一个节点。您现在转到第一步，寻找潜在的方向，如果 none 您转到第二步并回溯更多

密码

好的，所有的理论和规划都已完成，我们现在可以将我们的设计实施到代码中。

我将创建递归函数作为迷宫的方法class，如下所示：

class Maze:
    # ...
    # constructor and other methods go here
    # ...

    def create_maze(self, x, y):
        # our recursive function goes here

这意味着要完全创建我们的迷宫，我们调用 maze.create_maze(1, 1)（将 1, 1 替换为您的起始坐标）。

所以让我们逐步完成我们之前设计的每个步骤，并将它们转化为代码。

1.1 选择一个随机可行的方向

def create_maze(self, x, y):
    # set the current cell to a path, so that we don't return here later
    self.set_path(self, x, y)

    # we create a list of directions (in a random order) we can try
    all_directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    random.shuffle(all_directions)

    # we keep trying the next direction in the list, until we have no directions left
    while len(all_directions) > 0:

        # we remove and return the last item in our directions list
        direction_to_try = all_directions.pop()

        # calculate the new node's coordinates using our random direction.
        # we *2 as we are moving two cells in each direction to the next node
        node_x = x + (direction_to_try[0] * 2)
        node_y = y + (direction_to_try[1] * 2)

        # check if the test node is a wall (eg it hasn't been visited)
        if self.is_wall(node_x, node_y):
            # success code: we have found a path
    # failure code: we find no paths

# a function to return if the current cell is a wall, and if the cell is within the maze bounds
def is_wall(self, x, y):
    # checks if the coordinates are within the maze grid
    if 0 <= x < self.width and 0 <= y < self.height:
        # if they are, then we can check if the cell is a wall
        return self.cells[y][x]
    # if the coordinates are not within the maze bounds, we don't want to go there
    else:
        return False

1.2。朝那个方向移动两个单元格，并创建 link 路径单元格

所以现在的问题是，一旦找到可行的路径选项，我们该怎么做？答案：我们将 link 单元格变成一条路径（这样我们就不会跳过墙到我们的新节点），并在我们的新方向上移动两个单元格。

这变成：

# success code: we have found a path

# set our linking cell (between the two nodes we're moving from/to) to a path
link_cell_x = x + direction_to_try[0]
link_cell_y = y + direction_to_try[1]
self.set_path(link_cell_x, link_cell_y)

# "move" to our new node. remember we are calling the function every
#  time we move, so we call it again but with the updated x and y coordinates
self.create_maze(node_x, node_y)

然后将我们的成功代码集成到我们的create_maze函数中，它变成：

def create_maze(self, x, y):
    self.set_path(x, y)
    all_directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    random.shuffle(all_directions)
    while len(all_directions) > 0:
        direction_to_try = all_directions.pop()
        node_x = x + (direction_to_try[0] * 2)
        node_y = y + (direction_to_try[1] * 2)
        if self.is_wall(node_x, node_y):
            # success code: we have found a path

            # set our linking cell (between the two nodes we're moving from/to) to a path
            link_cell_x = x + direction_to_try[0]
            link_cell_y = y + direction_to_try[1]
            self.set_path(link_cell_x, link_cell_y)

            # "move" to our new node. remember we are calling the function every
            #  time we move, so we call it again but with the updated x and y coordinates
            self.create_maze(node_x, node_y)
    # failure code: we find no paths

2.1。如果我们所有的方向都包含路径（它们都被访问过），那么我们需要回溯

2.2。为了回溯，我们退出函数调用，这将我们带到前一个节点

结束函数的一种简单方法是调用 return。这将阻止任何进一步的代码在函数中成为运行，并且 returns 到调用它的前一个函数。

# failure code: we find no paths

return

并将其添加到我们的递归函数中，它现在变为：

def create_maze(self, x, y):
    self.set_path(x, y)
    all_directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    random.shuffle(all_directions)
    while len(all_directions) > 0:
        direction_to_try = all_directions.pop()
        node_x = x + (direction_to_try[0] * 2)
        node_y = y + (direction_to_try[1] * 2)
        if self.is_wall(node_x, node_y):
            link_cell_x = x + direction_to_try[0]
            link_cell_y = y + direction_to_try[1]
            self.set_path(link_cell_x, link_cell_y)
            self.create_maze(node_x, node_y)
    # failure code: we find no paths

   return

3.1。再次尝试第一步，如果不行则进行第二步

基本上我们现在已经编写了一个功能齐全的迷宫生成程序，使用（尽我所能）一个相当好的递归方法。一旦一个函数到达死胡同，它将return，回溯到前一个函数，并继续这个过程直到那个函数到达死胡同等等。

最终代码

import random

class Maze:
    def __init__(self, width, height):

        self.width = width // 2 * 2 + 1
        self.height = height // 2 * 2 + 1

        # this creates a 2d-array for your maze data (False: path, True: wall)
        self.cells = [
                      [True for x in range(self.width)] 
                      for y in range(self.height)
                     ]

    def set_path(self, x, y):
        self.cells[y][x] = False

    def set_wall(self, x, y):
        self.cells[y][x] = True

    # a function to return if the current cell is a wall,
    #  and if the cell is within the maze bounds
    def is_wall(self, x, y):
        # checks if the coordinates are within the maze grid
        if 0 <= x < self.width and 0 <= y < self.height:
            # if they are, then we can check if the cell is a wall
            return self.cells[y][x]
        # if the coordinates are not within the maze bounds, we don't want to go there
        else:
            return False

    def create_maze(self, x, y):
        # set the current cell to a path, so that we don't return here later
        self.set_path(x, y)
        # we create a list of directions (in a random order) we can try
        all_directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        random.shuffle(all_directions)

        # we keep trying the next direction in the list, until we have no directions left
        while len(all_directions) > 0:

            # we remove and return the last item in our directions list
            direction_to_try = all_directions.pop()

            # calculate the new node's coordinates using our random direction.
            # we *2 as we are moving two cells in each direction to the next node
            node_x = x + (direction_to_try[0] * 2)
            node_y = y + (direction_to_try[1] * 2)

            # check if the test node is a wall (eg it hasn't been visited)
            if self.is_wall(node_x, node_y):
                # success code: we have found a path

                # set our linking cell (between the two nodes we're moving from/to) to a path
                link_cell_x = x + direction_to_try[0]
                link_cell_y = y + direction_to_try[1]
                self.set_path(link_cell_x, link_cell_y)

                # "move" to our new node. remember we are calling the function every
                #  time we move, so we call it again but with the updated x and y coordinates
                self.create_maze(node_x, node_y)
        return

我们开始了！生成迷宫的递归算法。抱歉，我没有使用更多你的代码，但由于我不太确定你打算用它做什么，我想我至少可以通过向你展示一些工作代码来提供帮助。

我们可以快速添加的最后一件事是打印功能，这样我们就可以将迷宫打印到屏幕上。通过使用 "double underscore method" (dundermethod) __repr__ (update: 改用方法名称 __str__，见评论）我们可以覆盖 print 功能。下面的代码生成一个代表我们新生成的迷宫的字符串：

def __repr__(self):
    string = ""
    conv = {
        True: "██",
        False: "  "
    }
    for y in range(self.height):
        for x in range(self.width):
            string += conv[self.cells[y][x]]
        string += "\n"
    return string

通过将其放入迷宫 class，我们现在可以执行以下操作，它甚至可以从偶数单元格开始！

>>> maze.create_maze(1, 1)
>>> print(maze)
██████████████████
██      ██      ██
██████  ██  ██  ██
██  ██  ██  ██  ██
██  ██  ██████  ██
██  ██          ██
██  ██████████  ██
██              ██
██████████████████
>>> maze.create_maze(4, 4)
          ██      
  ██████  ██████  
  ██              
  ██████████████  
  ██      ██      
  ██  ██████████  
  ██          ██  
  ██████████  ██  
              ██

希望对您有所帮助！

实现递归回溯器以生成迷宫

Implementing a recursive backtracker to generate a maze

python

recursive-backtracking

初始问题

设置

思考迷宫的方法

算法

密码

最终代码