深度优先搜索迷宫生成递归函数报错：NoneType不可下标访问

我正在实现迷宫生成的深度优先搜索（DFS）算法，用二进制标记表示相邻节点的连接关系：0无方向，1=左，2=右，4=上，8=下，数值相加表示多方向（如3=左右、12=上下）。核心递归函数DepthFirstSearch理论支持任意大小二维列表，但运行时抛出TypeError: 'NoneType' object is not subscriptable，错误出在调用CheckPriorPositions后取[0]和[1]的位置。怀疑问题在CheckPriorPositions函数，附上相关代码、错误栈和测试用例，请分析原因并给出修复建议。

核心函数代码 #

def DepthFirstSearch(map,inX,inY,priorPoses,iteration,seed,mapSize):
    if len(priorPoses) == mapSize:
        print(F"Finished in {iteration} iterations")
        print(map)
        return map
    x = inX
    y = inY
    mapHold = map
    history = priorPoses
    random.seed(seed + iteration)
    if CheckNeighbors(map, x, y) == []:
        CheckPriorPositions(map,priorPoses)
        print(F"Check prior positions, {CheckNeighbors(map,x,y)}")
        return DepthFirstSearch(mapHold,CheckPriorPositions(map,priorPoses)[0],CheckPriorPositions(map,priorPoses)[1],
                         priorPoses,iteration+1,seed,mapSize)
    else:
        move = CheckNeighbors(map, x, y)
        move = random.choice(move)
        if move == 1:
            mapHold[inY][inX] += move
            x -= 1
            mapHold[y][x] += 2
        else:
            if move == 2:
                mapHold[inY][inX] += move
                x += 1
                mapHold[y][x] += 1
            else:
                if move == 4:
                    mapHold[inY][inX] += move
                    y += 1
                    mapHold[y][x] += 8
                else:
                    if move == 8:
                        mapHold[inY][inX] += move
                        y -= 1
                        mapHold[y][x] += 4
        history.append([x,y])
        return DepthFirstSearch(mapHold,x,y,priorPoses,iteration+1,seed,mapSize)

CheckPriorPositions函数代码 #

def CheckPriorPositions(map,priorPoses):
    posesToSearch = priorPoses
    posesToSearch.reverse()
    for poses in range(0,len(posesToSearch)):
        if CheckNeighbors(map,posesToSearch[poses][0],posesToSearch[poses][1]) != []:
            return posesToSearch[poses]

错误栈 #

Traceback (most recent call last):
  File "C:\Users\Wyatt\Desktop\python prjects\DepthFirstSearchMazeGenProject\DepthFirstSearch.py", line 87, in <module>
    DepthFirstSearch(testMapD,0,0,testHistoryD,0,5,4)
  File "C:\Users\Wyatt\Desktop\python prjects\DepthFirstSearchMazeGenProject\DepthFirstSearch.py", line 71, in DepthFirstSearch
    return DepthFirstSearch(mapHold,x,y,priorPoses,iteration+1,seed,mapSize)
  File "C:\Users\Wyatt\Desktop\python prjects\DepthFirstSearchMazeGenProject\DepthFirstSearch.py", line 71, in DepthFirstSearch
    return DepthFirstSearch(mapHold,x,y,priorPoses,iteration+1,seed,mapSize)
  File "C:\Users\Wyatt\Desktop\python prjects\DepthFirstSearchMazeGenProject\DepthFirstSearch.py", line 71, in DepthFirstSearch
    return DepthFirstSearch(mapHold,x,y,priorPoses,iteration+1,seed,mapSize)
  File "C:\Users\Wyatt\Desktop\python prjects\DepthFirstSearchMazeGenProject\DepthFirstSearch.py", line 46, in DepthFirstSearch
    return DepthFirstSearch(mapHold,CheckPriorPositions(map,priorPoses)[0],CheckPriorPositions(map,priorPoses)[1],
TypeError: 'NoneType' object is not subscriptable

测试用例 #

testMapA = [[0,0],[0,0],[0,0]]
testHistoryA = []
DepthFirstSearch(testMapA,0,0,testHistoryA,0,5,6)

testMapB = [[4,0],[10,5],[2,9]]
testHistoryB = [[0,0],[0,1],[1,1],[1,2],[0,2]]
DepthFirstSearch(testMapB,0,2,testHistoryB,5,5,6)

testMapC = [[4,0],[14,5],[8,8]]
testHistoryC = [[0,0],[0,1],[0,2],[1,1],[1,2]]
DepthFirstSearch(testMapC,1,2,testHistoryC,5,5,6)

testMapD = [[0,0],[0,0]]
testHistoryD = []
DepthFirstSearch(testMapD,0,0,testHistoryD,0,5,4)

testMapE = [[0,0]]
testHistoryE = []
DepthFirstSearch(testMapE,0,0,testHistoryE,0,5,2)

错误原因分析 #

1. CheckPriorPositions返回None：函数仅在找到可扩展的历史位置时返回坐标，若遍历完所有位置都无有效邻居，函数默认返回None，此时取[0]/[1]会触发TypeError。
2. 破坏原历史列表：posesToSearch = priorPoses是引用赋值，调用reverse()会直接修改原priorPoses列表；加上递归中多次调用该函数，历史列表会被反复反转，遍历逻辑完全混乱，最终导致找不到有效位置返回None。
3. 重复调用引发副作用：回溯逻辑中连续三次调用CheckPriorPositions，每次调用都会反转列表，既浪费性能，又进一步破坏历史记录顺序。

修复建议 #

1. 修复CheckPriorPositions的返回逻辑 #

添加默认返回处理，同时避免修改原历史列表：

def CheckPriorPositions(map,priorPoses):
    # 创建列表副本，防止修改原历史记录
    posesToSearch = priorPoses.copy()
    posesToSearch.reverse()
    for pos in posesToSearch:
        if CheckNeighbors(map, pos[0], pos[1]) != []:
            return pos
    # 所有位置无法扩展时返回None，后续递归中处理终止逻辑
    return None

2. 优化递归回溯逻辑 #

将CheckPriorPositions结果存入变量，避免重复调用，并处理返回None的情况：

if CheckNeighbors(map, x, y) == []:
    next_pos = CheckPriorPositions(map,priorPoses)
    # 处理无有效位置的情况（迷宫已完成或异常）
    if next_pos is None:
        if len(priorPoses) == mapSize:
            print(F"Finished in {iteration} iterations")
            print(map)
            return map
        raise Exception("No valid prior position found, maze generation failed")
    print(F"Check prior positions, moving to {next_pos}")
    return DepthFirstSearch(mapHold, next_pos[0], next_pos[1], priorPoses, iteration+1, seed, mapSize)

3. 简化方向判断（可选） #

用字典映射替代多层嵌套if-else，提升代码可读性：

move_map = {
    1: (-1, 0, 2),   # 左：x减1，目标节点加2（右方向标记）
    2: (1, 0, 1),    # 右：x加1，目标节点加1（左方向标记）
    4: (0, 1, 8),    # 上：y加1，目标节点加8（下方向标记）
    8: (0, -1, 4)    # 下：y减1，目标节点加4（上方向标记）
}
dx, dy, opposite = move_map[move]
mapHold[inY][inX] += move
x += dx
y += dy
mapHold[y][x] += opposite

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