Aldous-Broder迷宫算法实现出现不可达区域问题排查

我在Godot项目中使用Aldous-Broder算法生成随机迷宫，选择它的原因是算法简单且能生成完全随机的迷宫（即使耗时较长）。多数情况下生成的迷宫正常，但偶尔会出现部分单元格与迷宫主体隔离的情况，示例如下：

以下是我编写的算法代码：

func aldous_broder() -> void:
    # Start at a random cell
    var current_position: Vector2 = Vector2(randi() % MAZE_WIDTH, randi() % MAZE_HEIGHT)
    var previous_position: Vector2
    first_cell = current_position
    maze[current_position.x][current_position.y].visited = true
    unvisited_cells -= 1
    
    # The main loop. Repeat until every cell in the area has been visited
    while (unvisited_cells > 0):
        print("Unvisited cells: ", unvisited_cells)
        print("Currently at: ", current_position)
        previous_position = current_position
        
        # Move in a random direction
        var loop = true
        while (loop):
                match (randi() % 4):
                0:
                    current_position += NORTH 
                1:
                    current_position += SOUTH 
                2:
                    current_position += EAST 
                3:
                    current_position += WEST 
                        # The new position is within the bounds of the grid, exit loop
            if ((current_position.x >= 0 && current_position.x < MAZE_WIDTH) && (current_position.y >= 0 && current_position.y < MAZE_HEIGHT)):
                loop = false
            else:
                current_position = previous_position
        
        # Check if this current cell has been visited. If not, 'connect' it to previous cell
        if (!maze[current_position.x][current_position.y].visited):
            maze[current_position.x][current_position.y].visited = true
            unvisited_cells -=1
            maze[current_position.x][current_position.y].connects_to = previous_position
            
    final_cell = current_position

说明：first_cell和final_cell用于后续迷宫可视化，maze是二维数组，包含自定义的Cell对象，该对象拥有grid_position、visited和connects_to属性。

排查方向： #

• 检查unvisited_cells初始值：确认初始化时unvisited_cells是否被正确设置为MAZE_WIDTH * MAZE_HEIGHT。当前代码仅执行了unvisited_cells -= 1，如果初始值错误，主循环会提前终止，导致部分单元格从未被处理。
• 修复代码缩进错误：代码中内部移动循环的缩进存在问题——match块的代码缩进层级错误，边界检测的if语句也未正确嵌套在内部while循环的逻辑流中。这可能导致方向移动后，边界判断或位置回退的逻辑执行顺序错误，进而出现路径连接断裂。
• 补充双向连接逻辑：Aldous-Broder算法需要在相邻单元格间建立双向连接。当前代码仅设置了新访问单元格的connects_to为前一个位置，但未更新前一个单元格的connects_to来包含当前位置。如果可视化依赖connects_to绘制路径，单向连接会被误认为是单元格隔离。
• 验证Cell对象初始化：确认所有Cell的visited属性初始化为false，connects_to初始化为无效值（如Vector2(-1,-1)）。若初始状态下存在错误的visited=true标记，会导致对应单元格被跳过，形成孤立区域。
• 检查随机数生成逻辑：虽然概率较低，但如果randi()的使用存在种子问题（如未正确初始化随机种子），可能导致极端路径重复出现。可以尝试固定随机种子，看是否能复现隔离问题，以此定位是否为随机数导致的异常。

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