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

Question

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

Lor*_*XII 1 python recursive-backtracking

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

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

编辑：由于我没有添加我的迷宫类，我想我会添加它来帮助查看整个代码。

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?

Run Code Online (Sandbox Code Playgroud)

Answer 1

dan*_*guy 6

初始问题

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

设置

我假设你的迷宫类设置有点像这样：

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

Run Code Online (Sandbox Code Playgroud)

思考迷宫的方式

好的，现在我可以开始递归生成本身了。现在我没有采取添加墙壁的方法，而是用墙壁填充整个迷宫并“挖掘”自己的路径。

在我们的迷宫中，即使我们将其视为带有墙壁和路径的简单开/关 2d 网格，将其描绘成更像是一系列节点（连接点）和它们之间的链接是有帮助的。我可以看到你开始通过确保你的迷宫宽度和高度是奇数的方式来实现这一点，(Width // 2) * 2 + 1例如，你只选择了偶数单元格（尽管我不知道为什么）。

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

每个红色圆圈都是一个节点，正如您所看到的，每个奇数图块都包含一个节点，并且始终是路径图块。我们将自动假设每个奇数图块都包含一条路径（因此也包含一个节点）。这意味着在生成我们的迷宫时，当我们“挖掘”我们的方式时，我们将一次移动两个单元格，以便我们在节点（灰色单元格）之间创建链接。

算法

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

向随机方向移动，“挖掘”我的前进方向，跟踪我去过的地方
重复直到我走到死胡同
“回溯”我去过的地方，直到我找到一条至少有一条可行路径的路径。转到步骤 1

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

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

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

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

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

2.1. 继续重复第一步的过程

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

3.1. 通过之前访问过的节点跟随您的脚步（回溯）

3.2. 重复，直到找到至少有一个未访问路径的节点来尝试

3.3. 转到第一步（例如，开始在新路径中随机方向行走）

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

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

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

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

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

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

3.1. 退出函数调用后，您现在已移回前一个节点，使用前一个 xy 坐标。您现在转到第一步，在那里寻找潜在的方向，如果没有，则转到第二步并进一步回溯

编码

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

我将创建递归函数作为我们 Maze 类的方法，如下所示：

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

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

Run Code Online (Sandbox Code Playgroud)

这意味着完全创建我们的迷宫，我们称之为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

Run Code Online (Sandbox Code Playgroud)

1.2. 沿该方向移动两个单元格，并创建链接路径单元格

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

这变成：

# 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)

Run Code Online (Sandbox Code Playgroud)

然后将我们的成功代码集成到我们的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

Run Code Online (Sandbox Code Playgroud)

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

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

结束函数的一种简单方法是调用return. 这将停止在函数中运行任何进一步的代码，并返回到调用它的前一个函数。

# failure code: we find no paths

return

Run Code Online (Sandbox Code Playgroud)

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

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

Run Code Online (Sandbox Code Playgroud)

3.1. 再试第一步，如果不行就跳第二步

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

最终代码

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

Run Code Online (Sandbox Code Playgroud)

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

我们可以快速添加的最后一件事是打印功能，以便我们可以将迷宫打印到屏幕上。通过使用“双下划线方法”（dundermethod）__repr__（更新：改用方法名称__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

Run Code Online (Sandbox Code Playgroud)

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

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

Run Code Online (Sandbox Code Playgroud)

希望有帮助！

归档时间：	5 年，9 月前
查看次数：	1393 次
最近记录：	5 年，9 月前