每日算法 — 使用java实现泡泡龙：BFS连通检测与悬空下落算法

泡泡龙（Bubble Shooter）是一款风靡全球的益智消除游戏：玩家从屏幕底部发射彩色泡泡，当三个或更多同色泡泡相连时便会消除；消除后不再与顶部相连的泡泡会因”失去支撑”而下落。看似简单的规则背后，隐藏着六边形网格坐标映射、BFS连通检测与悬空下落判定三大核心算法问题。本文将用Java完整实现泡泡龙的核心消除引擎，从数据结构选型到算法细节逐一剖析。

一、问题建模与数据结构选型

1.1 为什么选择六边形网格

泡泡龙的泡泡呈紧密排列，每个泡泡与周围6个邻居相邻（奇偶行交错排列）。这种六边形密铺（Hexagonal Tiling）相比矩形网格更贴合圆形泡泡的物理特性：

• 六邻域连接：每个泡泡有6个邻居（上、下、左上、右上、左下、右下）
• 奇偶行偏移：奇数行与偶数行的水平位置有半格偏移
• 紧密堆积：相同空间内可以排列更多泡泡

1.2 网格坐标定义

采用偏移坐标系（Offset Coordinates），行按自然数递增，列在奇偶行采用不同的水平偏移：

/**
 * 泡泡网格坐标
 * 采用奇偶行偏移坐标系：
 * - 偶数行(0,2,4...)的列直接对应x坐标
 * - 奇数行(1,3,5...)的列向右偏移半格
 */
class BubblePos {
    // 行号，0表示最顶部
    int row;
    // 列号，每行的有效列数可能不同
    int col;

    BubblePos(int row, int col) {
        this.row = row;
        this.col = col;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof BubblePos)) return false;
        BubblePos other = (BubblePos) o;
        return this.row == other.row && this.col == other.col;
    }

    @Override
    public int hashCode() {
        return row * 1000 + col;
    }
}

1.3 泡泡节点与棋盘状态

/**
 * 泡泡节点
 * 每个节点代表棋盘上的一个泡泡，空位用 '\0' 表示
 */
class Bubble {
    // 泡泡颜色：'R'=红, 'G'=绿, 'B'=蓝, 'Y'=黄, 'P'=紫
    char color;
    // 是否已标记为悬空（待下落）
    boolean floating;

    Bubble(char color) {
        this.color = color;
        this.floating = false;
    }

    boolean isEmpty() {
        return color == '\0';
    }
}

/**
 * 泡泡龙棋盘
 * 维护一个二维网格，支持泡泡放置、消除与下落判定
 */
class BubbleBoard {
    // 棋盘最大行数
    static final int MAX_ROWS = 20;
    // 每行最大列数（偶数行）
    static final int MAX_COLS = 15;
    // 网格：bubbleGrid[row][col]
    private final Bubble[][] grid;
    // 当前实际占用的最大行数
    private int currentMaxRow;

    BubbleBoard() {
        this.grid = new Bubble[MAX_ROWS][MAX_COLS];
        this.currentMaxRow = 0;
        // 初始化所有格子为空
        for (int r = 0; r < MAX_ROWS; r++) {
            for (int c = 0; c < MAX_COLS; c++) {
                grid[r][c] = new Bubble('\0');
            }
        }
    }

    /**
     * 从字符串数组初始化棋盘
     * 每行字符串代表该行的泡泡颜色，'.'表示空位
     * 例如：["RRG..", ".BB..", "..."] 表示前两行有泡泡
     */
    void initFromStrings(String[] rows) {
        // 清空棋盘
        for (int r = 0; r < MAX_ROWS; r++) {
            for (int c = 0; c < MAX_COLS; c++) {
                grid[r][c].color = '\0';
                grid[r][c].floating = false;
            }
        }
        currentMaxRow = 0;

        for (int r = 0; r < rows.length && r < MAX_ROWS; r++) {
            String rowStr = rows[r];
            int maxCol = (r % 2 == 0) ? MAX_COLS : MAX_COLS - 1; // 奇数行列数少1
            for (int c = 0; c < rowStr.length() && c < maxCol; c++) {
                char ch = rowStr.charAt(c);
                if (ch != '.' && ch != ' ') {
                    grid[r][c].color = ch;
                    currentMaxRow = Math.max(currentMaxRow, r);
                }
            }
        }
    }

    /**
     * 获取指定位置的泡泡
     */
    Bubble get(int row, int col) {
        if (row < 0 || row >= MAX_ROWS || col < 0 || col >= MAX_COLS) {
            return null;
        }
        // 奇数行的最大列数检查
        if (row % 2 == 1 && col >= MAX_COLS - 1) {
            return null;
        }
        return grid[row][col];
    }

    /**
     * 设置指定位置的颜色
     */
    void set(int row, int col, char color) {
        Bubble b = get(row, col);
        if (b != null) {
            b.color = color;
            b.floating = false;
        }
    }

    /**
     * 判断位置是否为空
     */
    boolean isEmpty(int row, int col) {
        Bubble b = get(row, col);
        return b == null || b.isEmpty();
    }

    /**
     * 打印当前棋盘状态
     */
    void printBoard() {
        for (int r = 0; r <= currentMaxRow + 2 && r < MAX_ROWS; r++) {
            // 奇数行缩进半格
            if (r % 2 == 1) System.out.print(" ");
            int maxCol = (r % 2 == 0) ? MAX_COLS : MAX_COLS - 1;
            for (int c = 0; c < maxCol; c++) {
                char ch = grid[r][c].isEmpty() ? '.' : grid[r][c].color;
                System.out.print(ch + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
}

二、核心算法一：六邻域坐标计算

2.1 邻居偏移量定义

在奇偶行偏移坐标系中，每个格子的6个邻居的相对偏移取决于当前行的奇偶性：

/**
 * 获取六邻域的相对偏移量
 * 偶数行与奇数行的邻居偏移不同
 */
static int[][] getNeighborOffsets(int row) {
    if (row % 2 == 0) {
        // 偶数行：列不偏移
        return new int[][]{
            {-1, -1}, {-1, 0},   // 左上、右上
            {0, -1}, {0, 1},     // 左、右
            {1, -1}, {1, 0}      // 左下、右下
        };
    } else {
        // 奇数行：列整体向右偏移1
        return new int[][]{
            {-1, 0}, {-1, 1},    // 左上、右上
            {0, -1}, {0, 1},     // 左、右
            {1, 0}, {1, 1}       // 左下、右下
        };
    }
}

/**
 * 获取指定位置的所有有效邻居坐标
 */
List<BubblePos> getNeighbors(int row, int col) {
    List<BubblePos> neighbors = new ArrayList<>();
    int[][] offsets = getNeighborOffsets(row);
    for (int[] off : offsets) {
        int nr = row + off[0];
        int nc = col + off[1];
        if (get(nr, nc) != null) {
            neighbors.add(new BubblePos(nr, nc));
        }
    }
    return neighbors;
}

三、核心算法二：发射落点计算

3.1 发射轨迹与网格碰撞

在实际游戏中，发射的泡泡沿直线飞行，直到碰到墙壁或已有泡泡。为简化问题，本文采用网格落点模拟：给定目标网格坐标，将新泡泡放置到该位置。

/**
 * 发射泡泡到指定网格位置
 * @param row 目标行
 * @param col 目标列
 * @param color 泡泡颜色
 * @return 是否成功发射（若位置已被占用则失败）
 */
boolean shoot(int row, int col, char color) {
    if (!isEmpty(row, col)) {
        return false; // 位置已被占用
    }
    set(row, col, color);
    currentMaxRow = Math.max(currentMaxRow, row);
    return true;
}

3.2 实际游戏中的发射角度转网格坐标

在完整游戏中，需要根据发射角度计算碰撞点。核心思路是射线步进：从发射点沿角度方向步进，检测与周围泡泡的碰撞（距离小于泡泡直径）。

/**
 * 根据发射角度计算落点网格坐标（简化版）
 * 实际游戏中使用射线碰撞检测，这里给出核心思想
 * @param startRow 发射起始行
 * @param startCol 发射起始列
 * @param angleRad 发射角度（弧度，0表示水平向右）
 * @return 落点坐标，若超出边界返回null
 */
BubblePos calculateLandingPos(int startRow, int startCol, double angleRad) {
    // 泡泡半径对应的网格步长
    double step = 0.5;
    double r = startRow;
    double c = startCol;
    double dr = Math.sin(angleRad) * step;
    double dc = Math.cos(angleRad) * step;

    // 射线步进
    while (true) {
        r += dr;
        c += dc;
        int intR = (int) Math.round(r);
        int intC = (int) Math.round(c);

        // 碰到墙壁反弹（简化处理）
        if (intC < 0 || intC >= MAX_COLS) {
            dc = -dc; // 水平反弹
            continue;
        }

        // 碰到顶部
        if (intR < 0) {
            return new BubblePos(0, Math.max(0, Math.min(intC, MAX_COLS - 1)));
        }

        // 碰到已有泡泡
        if (!isEmpty(intR, intC)) {
            // 返回碰撞点前一个有效空位
            int landR = (int) Math.round(r - dr * 2);
            int landC = (int) Math.round(c - dc * 2);
            if (landR >= 0 && landC >= 0 && isEmpty(landR, landC)) {
                return new BubblePos(landR, landC);
            }
            // 若前一个位置不合法，寻找最近的空邻居
            return findNearestEmpty(intR, intC);
        }
    }
}

/**
 * 寻找碰撞点周围的最近空位
 */
BubblePos findNearestEmpty(int row, int col) {
    List<BubblePos> neighbors = getNeighbors(row, col);
    for (BubblePos pos : neighbors) {
        if (isEmpty(pos.row, pos.col)) {
            return pos;
        }
    }
    return null;
}

四、核心算法三：同色连通检测与消除

4.1 BFS同色连通块查找

当新泡泡落位后，需要检查以该泡泡为中心的同色连通块大小。若连通块大小大于等于3，则触发消除。使用BFS遍历六邻域：

/**
 * 使用BFS查找与指定位置相连的同色泡泡连通块
 * @param startRow 起始行
 * @param startCol 起始列
 * @return 连通块中所有泡泡的坐标列表
 */
List<BubblePos> findConnectedGroup(int startRow, int startCol) {
    List<BubblePos> group = new ArrayList<>();
    Bubble start = get(startRow, startCol);
    if (start == null || start.isEmpty()) {
        return group;
    }

    char targetColor = start.color;
    boolean[][] visited = new boolean[MAX_ROWS][MAX_COLS];
    Queue<BubblePos> queue = new LinkedList<>();

    queue.offer(new BubblePos(startRow, startCol));
    visited[startRow][startCol] = true;

    while (!queue.isEmpty()) {
        BubblePos cur = queue.poll();
        group.add(cur);

        // 遍历六邻域
        List<BubblePos> neighbors = getNeighbors(cur.row, cur.col);
        for (BubblePos neighbor : neighbors) {
            if (visited[neighbor.row][neighbor.col]) continue;
            Bubble nb = get(neighbor.row, neighbor.col);
            if (nb != null && !nb.isEmpty() && nb.color == targetColor) {
                visited[neighbor.row][neighbor.col] = true;
                queue.offer(neighbor);
            }
        }
    }

    return group;
}

4.2 消除触发

/**
 * 尝试消除以指定位置为中心的同色连通块
 * @param row 目标行
 * @param col 目标列
 * @return 消除的泡泡数量（0表示未触发消除）
 */
int tryEliminate(int row, int col) {
    List<BubblePos> group = findConnectedGroup(row, col);
    if (group.size() >= 3) {
        // 执行消除
        for (BubblePos pos : group) {
            grid[pos.row][pos.col].color = '\0';
        }
        return group.size();
    }
    return 0;
}

五、核心算法四：悬空泡泡检测与下落

5.1 悬空判定原理

消除同色泡泡后，可能产生不再与顶部相连的泡泡群。这些泡泡应当下落。判定方法是：从顶部第一行的每个泡泡出发，通过BFS/DFS标记所有与顶部相连的泡泡；未被标记的泡泡即为悬空泡泡。

/**
 * 检测并移除所有悬空泡泡
 * @return 下落的泡泡数量
 */
int removeFloatingBubbles() {
    boolean[][] connected = new boolean[MAX_ROWS][MAX_COLS];

    // 第一步：从顶部第一行的所有非空泡泡开始BFS，标记所有与顶部相连的泡泡
    Queue<BubblePos> queue = new LinkedList<>();
    for (int c = 0; c < MAX_COLS; c++) {
        if (!isEmpty(0, c)) {
            connected[0][c] = true;
            queue.offer(new BubblePos(0, c));
        }
    }

    // BFS遍历所有与顶部相连的泡泡
    while (!queue.isEmpty()) {
        BubblePos cur = queue.poll();
        List<BubblePos> neighbors = getNeighbors(cur.row, cur.col);
        for (BubblePos neighbor : neighbors) {
            if (connected[neighbor.row][neighbor.col]) continue;
            Bubble nb = get(neighbor.row, neighbor.col);
            if (nb != null && !nb.isEmpty()) {
                connected[neighbor.row][neighbor.col] = true;
                queue.offer(neighbor);
            }
        }
    }

    // 第二步：将所有未被标记的非空泡泡视为悬空泡泡并移除
    int floatingCount = 0;
    for (int r = 0; r < MAX_ROWS; r++) {
        int maxCol = (r % 2 == 0) ? MAX_COLS : MAX_COLS - 1;
        for (int c = 0; c < maxCol; c++) {
            if (!isEmpty(r, c) && !connected[r][c]) {
                grid[r][c].color = '\0';
                floatingCount++;
            }
        }
    }

    // 更新currentMaxRow
    updateMaxRow();

    return floatingCount;
}

/**
 * 更新当前最大行号
 */
private void updateMaxRow() {
    currentMaxRow = 0;
    for (int r = MAX_ROWS - 1; r >= 0; r--) {
        int maxCol = (r % 2 == 0) ? MAX_COLS : MAX_COLS - 1;
        for (int c = 0; c < maxCol; c++) {
            if (!isEmpty(r, c)) {
                currentMaxRow = r;
                return;
            }
        }
    }
}

六、核心算法五：贪心发射策略

6.1 评分函数

一个简单但有效的贪心策略是：遍历所有可发射位置，评估每个落点能获得的分数（同色消除数 + 悬空下落数），选择分数最高的落点。

/**
 * 评估在指定位置发射某颜色泡泡的收益
 * @param board 棋盘副本（用于模拟）
 * @param row 落点行
 * @param col 落点列
 * @param color 泡泡颜色
 * @return 总收益（消除数 + 悬空下落数）
 */
static int evaluateMove(BubbleBoard board, int row, int col, char color) {
    // 深拷贝棋盘进行模拟
    BubbleBoard sim = board.deepCopy();
    if (!sim.shoot(row, col, color)) {
        return 0; // 位置不合法
    }

    int score = 0;
    // 同色消除收益
    int eliminated = sim.tryEliminate(row, col);
    if (eliminated >= 3) {
        score += eliminated * 10; // 消除得分
        // 悬空下落收益
        int floating = sim.removeFloatingBubbles();
        score += floating * 20; // 下落得分更高
    }
    return score;
}

/**
 * 深拷贝棋盘
 */
BubbleBoard deepCopy() {
    BubbleBoard copy = new BubbleBoard();
    for (int r = 0; r < MAX_ROWS; r++) {
        int maxCol = (r % 2 == 0) ? MAX_COLS : MAX_COLS - 1;
        for (int c = 0; c < maxCol; c++) {
            copy.grid[r][c].color = this.grid[r][c].color;
            copy.grid[r][c].floating = this.grid[r][c].floating;
        }
    }
    copy.currentMaxRow = this.currentMaxRow;
    return copy;
}

6.2 最优落点搜索

/**
 * 贪心策略：找到最佳发射落点
 * 遍历所有与现有泡泡相邻的空位，评估每种颜色组合
 * @param availableColors 当前可用颜色集合
 * @return 最佳操作 {row, col, color, score}
 */
int[] findBestMove(Set<Character> availableColors) {
    int bestRow = -1, bestCol = -1;
    char bestColor = '\0';
    int bestScore = 0;

    // 收集所有与现有泡泡相邻的空位（候选落点）
    Set<BubblePos> candidates = new HashSet<>();
    for (int r = 0; r <= currentMaxRow + 1 && r < MAX_ROWS; r++) {
        int maxCol = (r % 2 == 0) ? MAX_COLS : MAX_COLS - 1;
        for (int c = 0; c < maxCol; c++) {
            if (!isEmpty(r, c)) {
                // 该位置的邻居是候选落点
                List<BubblePos> neighbors = getNeighbors(r, c);
                for (BubblePos n : neighbors) {
                    if (isEmpty(n.row, n.col)) {
                        candidates.add(n);
                    }
                }
            }
        }
    }

    // 评估每个候选落点与每种颜色的组合
    for (BubblePos pos : candidates) {
        for (char color : availableColors) {
            int score = evaluateMove(this, pos.row, pos.col, color);
            if (score > bestScore) {
                bestScore = score;
                bestRow = pos.row;
                bestCol = pos.col;
                bestColor = color;
            }
        }
    }

    return new int[]{bestRow, bestCol, bestColor, bestScore};
}

七、完整运行示例

public class BubbleShooterGame {
    public static void main(String[] args) {
        BubbleBoard board = new BubbleBoard();

        // 初始化棋盘
        // 偶数行：R R G . .  奇数行： B B . .
        // 偶数行：. G G . .  奇数行： . R . .
        String[] initRows = {
            "RRG..",   // row 0 (偶数行，5列)
            "BB..",    // row 1 (奇数行，4列)
            ".GG..",   // row 2 (偶数行，5列)
            ".R..",    // row 3 (奇数行，4列)
            "..."      // row 4 及以后为空
        };
        board.initFromStrings(initRows);
        System.out.println("=== 初始棋盘 ===");
        board.printBoard();

        // 场景1：在row=2, col=0发射红色泡泡 'R'
        // 当前row2: . G G . .
        // 发射后:   R G G . .
        // 红色与上方row0的RR不连通，不触发消除
        System.out.println("=== 场景1：发射红色到(2,0)，不触发消除 ===");
        BubbleBoard s1 = board.deepCopy();
        s1.shoot(2, 0, 'R');
        s1.printBoard();
        int e1 = s1.tryEliminate(2, 0);
        System.out.println("消除数量: " + e1);
        s1.printBoard();

        // 场景2：构造同色消除
        // 在row=2, col=1发射绿色 'G'
        // row2: R G G . . -> R G G G . (在col=1位置发射G)
        // 等等，col=1已经是G了。我们在col=3发射G
        // row2: R G G . . -> R G G G . (col=3是空位)
        // 此时row2有 G G G 连续3个绿色，应触发消除
        System.out.println("=== 场景2：在(2,3)发射绿色，触发同色消除 ===");
        BubbleBoard s2 = board.deepCopy();
        s2.shoot(2, 3, 'G');
        System.out.println("发射后:");
        s2.printBoard();
        int e2 = s2.tryEliminate(2, 3);
        System.out.println("消除数量: " + e2);
        s2.printBoard();

        // 场景3：构造悬空下落
        // 构建一个悬空结构：
        // row0: R R G . .
        // row1:  B B . .
        // 如果在row0的某个位置消除，row1的泡泡可能悬空
        // 让我们构造更明显的例子：
        // row0: R . G . .
        // row1:  B B . .
        // row2: . . . . .
        // row1的B只与row0的R和G相连。如果消除R和G，row1的B会悬空
        String[] floatingRows = {
            "R.G..",
            "BB..",
            "....."
        };
        BubbleBoard s3 = new BubbleBoard();
        s3.initFromStrings(floatingRows);
        System.out.println("=== 场景3：悬空下落演示 ===");
        s3.printBoard();
        // 在row0, col=1发射G，与row0的G形成连通
        s3.shoot(0, 1, 'G');
        System.out.println("发射G到(0,1)后:");
        s3.printBoard();
        int e3 = s3.tryEliminate(0, 1);
        System.out.println("消除数量: " + e3);
        s3.printBoard();
        int f3 = s3.removeFloatingBubbles();
        System.out.println("悬空下落数量: " + f3);
        s3.printBoard();

        // 场景4：贪心最优决策
        System.out.println("=== 场景4：贪心最优落点搜索 ===");
        BubbleBoard s4 = board.deepCopy();
        Set<Character> colors = new HashSet<>(Arrays.asList('R', 'G', 'B'));
        int[] best = s4.findBestMove(colors);
        System.out.println("最佳操作: 行=" + best[0] + ", 列=" + best[1] +
                ", 颜色=" + (char)best[2] + ", 得分=" + best[3]);
    }
}

八、复杂度分析

九、总结与扩展

本文从泡泡龙游戏的三个核心算法问题出发，用Java实现了完整的消除引擎：

1. 六边形网格坐标映射：奇偶行偏移坐标系是处理六边形密铺的关键，正确计算六邻域为后续算法奠定基础。
2. BFS同色连通检测：落子后通过BFS快速找到同色连通块，判断是否满足消除条件。
3. 悬空下落判定：通过”从顶部反向BFS标记”的思路，优雅地识别所有失去支撑的泡泡。

可扩展方向：
– 射线碰撞检测：将发射角度转换为精确落点，处理墙壁反弹与碰撞预测。
– 高级AI策略：引入蒙特卡洛模拟，预判多步后的棋盘状态，选择长期收益最大的落点。
– 关卡生成：使用随机过程与连通性约束，自动生成有解且难度递进的初始棋盘。