检测棋盘是否连通的简洁高效算法（适配贪吃蛇AI场景）

针对贪吃蛇每帧蛇身动态变化的场景，最高效的连通性检测方案是基于BFS的洪水填充（Flood Fill），2020左右的常规棋盘单次检测耗时不到1ms，完全满足实时运行要求，可以和你现有的A寻路逻辑无缝配合。

核心检测逻辑 #

连通性检测不需要用复杂的高级数据结构，核心思路非常直接：

1. 以当前（或模拟移动后的）蛇头位置为起点，只向合法的空格（非蛇身的格子）做四方向BFS/DFS遍历
2. 统计所有可达的空格总数，和当前棋盘总空格数（棋盘总格子数 - 当前蛇身长度）做对比：如果两个数值相等，说明全棋盘连通；如果可达数小于总空格数，说明存在被蛇身围死的封闭区域
3. 遍历过程中额外加一个标记位，判断是否能到达当前蛇尾位置——这个判断比全连通判断实用性更强：只要始终能摸到蛇尾，AI就永远不会把自己困死，因为蛇尾会持续移动让出空间，哪怕暂时存在封闭区域，跟着蛇尾走也能等到区域解封。

适配A*寻路的优化点 #

把连通性检测嵌入你现有的A*决策流程，按下面的逻辑做方向筛选，可以直接解决蛇把自己困死的问题：

• 每次A*算出到食物的候选路径后，先模拟走完这条路径后的蛇身状态（蛇头到食物位置，蛇身按路径顺延，吃食物时蛇尾不收缩，没吃食物时蛇尾收缩一格）
• 对模拟后的状态跑连通性检测，优先选择同时满足「能到达食物」「能到达蛇尾」的路径
• 如果到食物的路径会导致走完后摸不到蛇尾，就放弃追食物，临时切换成追蛇尾的策略，直到重新出现安全的吃食物路径
• BFS遍历加剪枝：只要统计到的可达格子数已经等于当前总空格数，直接终止遍历返回结果，不需要把所有节点走完，能减少至少一半的计算量

极简实现参考 #

from collections import deque

def check_connectivity(board, head_pos, tail_pos, total_empty_cell, board_size):
    """
    返回值：(is_all_connected: 全棋盘是否连通, can_reach_tail: 是否能到达蛇尾)
    board: 二维数组，1表示蛇身/障碍，0表示空格
    """
    visited = set()
    q = deque()
    q.append(head_pos)
    visited.add(head_pos)
    reach_count = 0
    can_reach_tail = False
    # 四方向偏移
    dirs = [(-1,0), (1,0), (0,-1), (0,1)]

    while q:
        x, y = q.popleft()
        reach_count += 1
        if (x, y) == tail_pos:
            can_reach_tail = True
        # 提前剪枝：已经覆盖所有空格，不用继续遍历
        if reach_count >= total_empty_cell:
            break
        for dx, dy in dirs:
            nx = x + dx
            ny = y + dy
            # 判断坐标合法、不是蛇身、没访问过
            if 0 <= nx < board_size and 0 <= ny < board_size \
                and board[nx][ny] != 1 \
                and (nx, ny) not in visited:
                visited.add((nx, ny))
                q.append((nx, ny))
    
    return reach_count == total_empty_cell, can_reach_tail

避坑提示 #

• 不要用并查集做这个场景的连通检测：蛇每移动一格最多改变2个格子的状态（蛇头新增、蛇尾移除），并查集不支持高效的动态删点，小棋盘下性能远不如BFS洪水填充
• 不要只对当前蛇的状态做检测就决策，一定要模拟走完候选路径后的最终状态再跑检测，否则很容易出现「当前看着连通，走两步就把自己堵死」的问题
• 吃食物的回合蛇不会收缩蛇尾，计算总空格数的时候要记得把蛇身增长占的格子扣掉，不要按普通移动的空格数计算

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