Python递归回溯生成迷宫遇递归深度超限及程序异常退出问题

问题描述 #

我编写了一个程序，可根据用户输入的尺寸，使用递归回溯算法生成n²大小的完美迷宫。最初遇到递归深度超限错误时，我用sys.setrecursionlimit(8000)解决了问题，但当增大迷宫尺寸后，程序直接退出且无任何提示。比如输入尺寸100时，程序直接返回命令行，没有报错信息。

程序在5、20、50等小尺寸下运行正常，但大尺寸就会出现问题。我认为应该能生成更大的迷宫，怀疑是递归回溯实现存在问题，但不认同老师提出的“停止条件失效导致重复访问单元格”的结论。

方向定义字典 #

_dic = {
    "N": (-1, 0),
    "S": (1, 0),
    "E": (0, 1),
    "W": (0, -1),
}

迷宫存储优化 #

我将迷宫存储在字符串类型的numpy数组中，仅保存需要修改的中间部分，转换为字符串显示时再补充其余内容，以此实现小幅优化。

比如3×3的迷宫显示效果：

.######
..#.#.#
#######
#.#.#.#
#######
#.#.#..
######.

而数组中仅存储中间部分：

.#.#.
#####
.#.#.
#####
.#.#.

核心代码 #

回溯函数_backtrack #

# 递归回溯函数，参数posx和posy是当前要访问的单元格坐标
def _backtrack(self, posx, posy):
    self._map[posx][posy] = 'V' # 标记单元格为已访问
    while True:
        # hasNeighbors如果没找到有效邻居返回空列表
        # 找到的话返回对应方向的列表，比如["N", "E"]表示右侧和下方有有效邻居
        dir = self._hasNeighbors(posx, posy) 
        lenght = len(dir)

        # 没有有效邻居，说明是死路，返回回溯
        if lenght == 0:
            return
        
        # 随机选一个方向，并从列表中移除
        toBreak = dir.pop(dir.index(random.choice(dir)))

        # 把墙替换为通路
        self._map[posx + self._dic[toBreak][0]][posy + self._dic[toBreak][1]] = '.'

        # 如果只有一个有效邻居，打通墙后更新坐标，用while循环继续访问，避免递归
        if lenght == 1:
            posx += self._dic[toBreak][0] * 2
            posy += self._dic[toBreak][1] * 2
            self._map[posx][posy] = 'V'

        # 否则递归调用回溯函数，访问目标单元格
        else:
            self._backtrack(posx + self._dic[toBreak][0] * 2, posy + self._dic[toBreak][1] * 2)

邻居检查函数_hasNeighbors #

def _hasNeighbors(self, posx, posy):
    result = []

    # 检查每个方向的邻居
    for dir in self._dic.keys():

        # 确保索引不超出迷宫范围
        if 0 <= posx + self._dic[dir][0] < self._size * 2 - 1 and 0 <= posy + self._dic[dir][1] < self._size * 2 - 1:

            # 如果邻居未被访问
            if self._map[posx + self._dic[dir][0] * 2][posy + self._dic[dir][1] * 2] == '.':

                # 将该方向加入有效邻居列表
                result.append(dir)
    return result

错误复现示例 #

输入尺寸100时，程序直接退出无提示：

PS C:\Users\pierr\Travail\Code\Amazing-Maze> python -m amazingmaze
Please entre the size of the maze : 100
PS C:\Users\pierr\Travail\Code\Amazing-Maze>

内容的提问来源于stack exchange，提问作者Ulquileon