我实现的Prim算法是否正确？——迷宫生成问题排查

嘿，作为同样折腾过终端迷宫的开发者，我能理解你看到那种“四通八达”迷宫的困惑😉。你的代码其实已经摸到了Prim算法的门，但几个小细节没处理好，导致迷宫变得过于“通透”，咱们一步步来修正：

先说说你的代码里的核心问题 #

1. 环形边界导致无死胡同：你用了%20和%40处理边界，这会让迷宫变成环形（上下左右首尾相连），没有真正的死胡同，自然看起来“太简单”。
2. 循环次数过多：你的迷宫是20行×40列，按标准奇偶格布局，实际需要的通路格是(20//2)*(40//2) = 200个，你循环420次，相当于重复打通了很多不必要的墙，导致通道连接过多。
3. 墙列表重复添加：每次循环都往Wall_List里加当前位置的墙，没有去重，同一个墙会被多次选中，反复打通，进一步增加了多余的连接。
4. 通路判断逻辑不准确：你找连接墙的方式可能会错误地打通多个方向的墙，而不是只打通一个连接通路的墙。

修正后的代码（带注释） #

import random

def printout(*args):
    for arg in args:
        print(*arg, sep='')

# 初始化迷宫：20行40列，全部设为墙（░）
# 注意：我们用奇偶格布局，通路格在偶数行/列，墙在奇数行/列
maze = [["░" for _ in range(40)] for _ in range(20)]

def prim_maze(maze):
    rows = len(maze)
    cols = len(maze[0])
    
    # 初始通路格：选一个偶数行、偶数列的位置（避免边界问题，选中间点）
    start_row = 0  # 或者选2,4...只要是偶数
    start_col = 20
    maze[start_row][start_col] = " "
    
    # 墙列表：存储所有与通路格相邻的墙（注意是墙的坐标，不是通路格）
    wall_list = []
    
    # 初始添加起始点周围的墙（只加合法的、在迷宫范围内的墙）
    # 上下左右的墙：通路格±1的位置（因为通路是偶数，墙是奇数）
    directions = [(-1,0), (1,0), (0,-1), (0,1)]
    for dr, dc in directions:
        wall_row = start_row + dr
        wall_col = start_col + dc
        if 0 <= wall_row < rows and 0 <= wall_col < cols:
            wall_list.append((wall_row, wall_col))
    
    # 总通路格数：(rows//2)*(cols//2)，初始已经有1个，所以需要打通的次数是总数量-1
    total_paths = (rows // 2) * (cols // 2)
    paths_created = 1
    
    while paths_created < total_paths and wall_list:
        # 随机选一个墙
        wall_idx = random.randint(0, len(wall_list)-1)
        wall_row, wall_col = wall_list.pop(wall_idx)
        
        # 找到这个墙分隔的两个通路格（墙的两边，各±1的位置）
        # 比如墙在(r,c)，两边的通路格是(r-1,c)和(r+1,c) 或者 (r,c-1)和(r,c+1)
        neighbors = []
        # 检查上下两个通路格
        if wall_row % 2 == 1:  # 墙在奇数行，分隔的是上下两个偶数行的通路格
            up_row = wall_row - 1
            down_row = wall_row + 1
            if 0 <= up_row < rows and maze[up_row][wall_col] == " ":
                neighbors.append((up_row, wall_col))
            if 0 <= down_row < rows and maze[down_row][wall_col] == " ":
                neighbors.append((down_row, wall_col))
        else:  # 墙在奇数列，分隔的是左右两个偶数列的通路格
            left_col = wall_col - 1
            right_col = wall_col + 1
            if 0 <= left_col < cols and maze[wall_row][left_col] == " ":
                neighbors.append((wall_row, left_col))
            if 0 <= right_col < cols and maze[wall_row][right_col] == " ":
                neighbors.append((wall_row, right_col))
        
        # 只有当两边恰好有一个通路格时，才打通这个墙（Prim算法的核心）
        if len(neighbors) == 1:
            # 打通墙
            maze[wall_row][wall_col] = " "
            # 找到另一个未访问的通路格
            if wall_row % 2 == 1:
                new_path_row = wall_row + 1 if neighbors[0][0] == wall_row -1 else wall_row -1
                new_path_col = wall_col
            else:
                new_path_col = wall_col +1 if neighbors[0][1] == wall_col -1 else wall_col -1
                new_path_row = wall_row
            
            # 标记新的通路格
            maze[new_path_row][new_path_col] = " "
            paths_created +=1
            
            # 添加新通路格周围的墙到列表（避免重复添加）
            for dr, dc in directions:
                new_wall_row = new_path_row + dr
                new_wall_col = new_path_col + dc
                if 0 <= new_wall_row < rows and 0 <= new_wall_col < cols:
                    if maze[new_wall_row][new_wall_col] == "░" and (new_wall_row, new_wall_col) not in wall_list:
                        wall_list.append((new_wall_row, new_wall_col))
    
    return maze

maze = prim_maze(maze)
printout(*maze)

关键改动说明 #

• 去掉环形边界：用0 <= ... < rows/cols判断边界，迷宫有真正的边缘，会产生死胡同，复杂度立刻上来了。
• 严格控制循环次数：只打通到所有通路格都连接，避免过度操作。
• 墙列表去重：添加新墙时检查是否已经在列表里，避免重复处理同一个墙。
• 遵循Prim算法核心逻辑：每次选的墙必须恰好分隔一个已访问通路和一个未访问通路，这样只会打通必要的连接，不会产生多余通道。

额外小建议 #

如果你还是觉得迷宫不够“复杂”，可以试试：

• 调整迷宫的大小，比如改成30行×60列，更大的迷宫自然更复杂。
• 生成后随机堵上一些死胡同的入口（但要保证整个迷宫还是连通的）。

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