一、泡泡龙的真正难点不在”打中”，而在”塌落”
很多人以为泡泡龙（Bubble Shooter）的算法核心是”算角度、做反射”。其实瞄准与反弹只是几何问题，用向量反射三行代码就能写完。真正让小游戏引擎工程师头疼的是塌落（drop）判定：
- 三个以上同色泡泡连通，消除；
- 消除之后，任何不再与顶部连通的泡泡簇都必须整体掉落；
- 这个判定必须在一个回合内完成，且不能误判、不能漏判。
这就是一个标准动态连通性问题：网格是六边形的，连通关系需要考虑 6 个邻居方向；消除后图会”断边”，如果每次断边都重跑一遍 BFS，代价是 O(N·M)，而正确做法是用并查集 + 虚拟顶节点，把”是否连接顶部”变成”是否与虚拟节点同集合”的 O(α(N)) 查询。
本文的算法重点是这三块：六边形轴向坐标（axial coordinates）映射、6 邻域连通判定、并查集挂顶判定。
二、六边形网格：为什么不能直接用二维数组下标
泡泡龙的棋盘是尖顶朝上（pointy-top）的六边形排列：奇数行相对偶数行整体右移半格。若直接把它当成矩形数组，会出现两个严重错误：
- 邻居关系错。在矩形数组中，
(r, c)的上下左右 4 邻居在六边形网格里并不都是”相邻”，而真正的邻居是 6 个； - 距离算错。计算”某个泡泡离顶部几行””某个位置到另一个位置的格距”，用欧氏距离会得到非整数且不正确的结果。
业界通用两种做法：
- 偏移坐标（offset coordinates）：
(row, col)，需要按 row 的奇偶来修正 col，判断邻居时要写分支，易错。 - 轴向坐标（axial coordinates）：
(q, r)，邻居方向恒为 6 个固定偏移，无任何奇偶分支，这是本文采用的方式。
轴向坐标的 6 个邻居（尖顶朝上）：
private static final int[][] DIRS = {
{+1, 0}, {+1, -1}, { 0, -1},
{-1, 0}, {-1, +1}, { 0, +1}
};
由于方向偏移与奇偶无关，所有”取邻居””算连通”的代码都能写成统一循环——这直接消掉了一整类边界 bug。
2.1 轴向 → 偏移（便于存进二维数组）
为了让存储仍然高效（用数组而不是 HashMap），我们把轴向坐标映射到一个矩形里：
col = q + floor(r / 2) // 必须用 floorDiv，Java 的 / 对负数向零取整会错行
row = r
三、核心算法一：同色连通块（BFS 标记）
命中一个泡泡后，先求与它同色的连通块。这一步用 BFS，复杂度与连通块大小成正比。
四、核心算法二：悬挂判定（并查集 + 虚拟顶节点）
这是本文的关键设计。
朴素做法：每次消除后，从顶部所有泡泡出发做一次 BFS，标记所有可达格，其余全部掉落。复杂度 O(N)，N 为棋盘格数。单次可接受，但若每帧或每回合多次调用，就会积累成瓶颈，且代码里到处都是”visited 数组复用”的坑。
并查集做法：建立一个虚拟节点 TOP，把所有位于第 0 行（即与顶部接触）的泡泡与 TOP 合并。之后任何一个泡泡”是否悬挂”，只需 find(i) == find(TOP)。
但并查集只支持合并，不支持删点。消除会删除节点，这破坏了并查集的单向性。解决方案有两种：
- 重建式：消除后，用剩余节点重建并查集。这退化成 O(N α(N))，但常数远小于 BFS + visited 分配，且逻辑极简、不会出错。
- 逆向加边式（离线）：把整局游戏的消除顺序倒过来处理，边”加回”节点边合并——这是处理”删边连通性”的标准离线技巧。
本文采用第 1 种：每回合重建一次并查集。原因是回合数少（每秒最多几次），重建成本可忽略，而正确性和可读性收益极大。第 2 种方式留作扩展讨论。
4.1 为什么必须连”顶部整行”而不是”第一个泡泡”
泡泡龙中，顶部的接触面是整个第 0 行（可能有很多格）。如果只把”最上方的一个泡泡”连到虚拟节点，那么当该点被消除后，整片本应仍然悬挂的泡泡会被误判为掉落。把所有第 0 行出现的泡泡都合并到 TOP 才是正确语义。
五、完整 Java 实现
5.1 项目结构
bubble-shooter/
├── pom.xml
└── src/main/java/com/example/bubble/
├── HexGrid.java // 轴向坐标网格：邻居、轴向/偏移互换
├── Board.java // 棋盘状态、放置、同色连通块
├── DropJudge.java // 并查集悬挂判定
└── Main.java // 演示：命中 -> 消除 -> 塌落 全流程
5.2 HexGrid：无奇偶分支的六边形邻域
package com.example.bubble;
import java.util.*;
/**
* 六边形网格（尖顶朝上 pointy-top），采用轴向坐标 (q, r)。
* 好处：6 个邻居方向是固定偏移，不需要按行奇偶写分支。
* 存储：映射到 (row = r, col = q + floor(r/2)) 的二维数组。
*/
public final class HexGrid {
/** 轴向坐标下的 6 个邻居方向，顺序固定。 */
public static final int[][] DIRS = {
{+1, 0}, {+1, -1}, { 0, -1},
{-1, 0}, {-1, +1}, { 0, +1}
};
public final int rows; // r 的范围 [0, rows)
public final int cols; // 每行最多 cols 个位置
public HexGrid(int rows, int cols) {
this.rows = rows;
this.cols = cols;
}
/** 轴向 -> 偏移。注意必须 floorDiv，否则负 r 会错行。 */
public static int colOf(int q, int r) {
return q + Math.floorDiv(r, 2);
}
/** 偏移 -> 轴向。 */
public static int qOf(int row, int col) {
return col - Math.floorDiv(row, 2);
}
/** 偏移坐标是否在矩形存储范围内。 */
public boolean inBounds(int row, int col) {
return row >= 0 && row < rows && col >= 0 && col < cols;
}
/**
* 取偏移坐标 (row, col) 的第 k 个邻居。
* 先把偏移转回轴向，再加上方向偏移，最后转回偏移。
* 三次换算都是 O(1) 整数运算，无分支。
*/
public int[] neighbor(int row, int col, int k) {
int q = qOf(row, col);
int r = row;
q += DIRS[k][0];
r += DIRS[k][1];
return new int[]{r, colOf(q, r)};
}
/** 轴向距离（六边形格距），调试时非常有用。 */
public static int hexDistance(int q1, int r1, int q2, int r2) {
int dq = q1 - q2, dr = r1 - r2;
return Math.max(Math.abs(dq), Math.max(Math.abs(dr), Math.abs(dq + dr)));
}
}
5.3 Board：同色连通块 BFS
package com.example.bubble;
import java.util.*;
/** 棋盘状态：-1 表示空，0..K-1 表示颜色。 */
public final class Board {
private final HexGrid grid;
private final int[][] color; // [row][col]，-1 为空
private final boolean[][] alive; // 是否存在（区分“六边形外”与“空”）
public Board(HexGrid grid) {
this.grid = grid;
this.color = new int[grid.rows][grid.cols];
this.alive = new boolean[grid.rows][grid.cols];
for (int r = 0; r < grid.rows; r++) {
for (int c = 0; c < grid.cols; c++) {
color[r][c] = -1;
alive[r][c] = isValidCell(r, c);
}
}
}
/** 六边形划分：顶部满宽，向下逐行收窄（常见泡泡龙版式）。 */
private boolean isValidCell(int r, int c) {
int half = grid.rows / 2;
if (r <= half) return c >= 0 && c < grid.cols;
int shrink = r - half;
return c >= shrink && c < grid.cols;
}
public boolean isEmptyCell(int r, int c) {
return alive[r][c] && color[r][c] < 0;
}
public boolean hasBubble(int r, int c) {
return alive[r][c] && color[r][c] >= 0;
}
public void set(int r, int c, int col) { color[r][c] = col; }
public int get(int r, int c) { return color[r][c]; }
public HexGrid grid() { return grid; }
/**
* 求 (sr, sc) 的同色连通块。标准 BFS，用 seen 数组避免重复入队。
*/
public List<int[]> sameColorCluster(int sr, int sc) {
List<int[]> out = new ArrayList<>();
if (!hasBubble(sr, sc)) return out;
int target = color[sr][sc];
boolean[][] seen = new boolean[grid.rows][grid.cols];
ArrayDeque<int[]> q = new ArrayDeque<>();
q.add(new int[]{sr, sc});
seen[sr][sc] = true;
while (!q.isEmpty()) {
int[] cur = q.poll();
out.add(cur);
for (int k = 0; k < 6; k++) {
int[] nb = grid.neighbor(cur[0], cur[1], k);
int r = nb[0], c = nb[1];
if (!grid.inBounds(r, c) || seen[r][c]) continue;
if (!hasBubble(r, c) || color[r][c] != target) continue;
seen[r][c] = true;
q.add(new int[]{r, c});
}
}
return out;
}
/** 消除一组坐标。 */
public void clear(List<int[]> cells) {
for (int[] p : cells) color[p[0]][p[1]] = -1;
}
}
5.4 DropJudge：并查集悬挂判定
package com.example.bubble;
import java.util.*;
/**
* 悬挂判定器。
* 思路：虚拟顶节点 TOP 与所有“接触第 0 行”的泡泡合并；
* 之后泡泡 i 悬挂 <=> find(i) != find(TOP)。
* 并查集不支持删点，因此每回合在消除后重建一次。
*/
public final class DropJudge {
private final Board board;
private int[] parent;
private int[] rank;
private int topId;
public DropJudge(Board board) { this.board = board; }
/** 为当前棋盘状态重建并查集，返回所有“不悬挂”的泡泡坐标（即要掉落的）。 */
public List<int[]> findFloating() {
Board b = board;
HexGrid g = b.grid();
int n = g.rows * g.cols;
topId = n; // 虚拟节点用 n 作为 id
parent = new int[n + 1];
rank = new int[n + 1];
for (int i = 0; i <= n; i++) parent[i] = i;
// 1) 合并所有相邻且有泡泡的格
for (int r = 0; r < g.rows; r++) {
for (int c = 0; c < g.cols; c++) {
if (!b.hasBubble(r, c)) continue;
for (int k = 0; k < 6; k++) {
int[] nb = g.neighbor(r, c, k);
int nr = nb[0], nc = nb[1];
if (!g.inBounds(nr, nc) || !b.hasBubble(nr, nc)) continue;
union(id(r, c), id(nr, nc));
}
}
}
// 2) 顶部整行挂到虚拟节点
// 关键：必须是“整行”而非“某一个”，否则该点被消除后会误判整片掉落
for (int c = 0; c < g.cols; c++) {
if (b.hasBubble(0, c)) union(id(0, c), topId);
}
// 3) 收集与 TOP 不同集合的泡泡
int root = find(topId);
List<int[]> floating = new ArrayList<>();
for (int r = 0; r < g.rows; r++) {
for (int c = 0; c < g.cols; c++) {
if (!b.hasBubble(r, c)) continue;
if (find(id(r, c)) != root) floating.add(new int[]{r, c});
}
}
return floating;
}
private int id(int r, int c) { return r * board.grid().cols + c; }
private int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]]; // 路径减半压缩
x = parent[x];
}
return x;
}
private void union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return;
if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
parent[rb] = ra;
if (rank[ra] == rank[rb]) rank[ra]++;
}
}
5.5 Main：一个回合的完整流程
package com.example.bubble;
import java.util.*;
public final class Main {
public static void main(String[] args) {
HexGrid grid = new HexGrid(10, 12);
Board board = new Board(grid);
fillDemo(board);
System.out.println("=== 初始棋盘（. 空 / 数字为颜色） ===");
print(board);
int hitR = 3, hitC = 4;
System.out.printf("%n命中 (%d,%d) 颜色=%d%n", hitR, hitC, board.get(hitR, hitC));
List<int[]> cluster = board.sameColorCluster(hitR, hitC);
System.out.println("同色连通块大小 = " + cluster.size());
if (cluster.size() >= 3) {
board.clear(cluster);
System.out.println("满足 3 连，已消除");
DropJudge judge = new DropJudge(board);
List<int[]> floating = judge.findFloating();
System.out.println("判定为悬挂（将掉落）的泡泡数 = " + floating.size());
for (int[] p : floating) board.set(p[0], p[1], -1);
} else {
System.out.println("不足 3 连，不消除");
}
System.out.println("\n=== 消除+塌落后 ===");
print(board);
}
private static void fillDemo(Board b) {
HexGrid g = b.grid();
Random rnd = new Random(7L);
for (int r = 0; r < 5; r++) {
for (int c = 0; c < g.cols; c++) {
if (!b.isEmptyCell(r, c)) continue;
b.set(r, c, rnd.nextInt(4));
}
}
}
private static void print(Board b) {
HexGrid g = b.grid();
for (int r = 0; r < g.rows; r++) {
StringBuilder sb = new StringBuilder();
sb.append(String.format("r=%2d ", r));
if (r % 2 == 1) sb.append(' '); // 奇数行半格偏移，仅用于可视化对齐
for (int c = 0; c < g.cols; c++) {
if (b.hasBubble(r, c)) sb.append(b.get(r, c));
else sb.append('.');
sb.append(' ');
}
System.out.println(sb);
}
}
}
5.6 输出示例（示意；随机种子固定为 7 时可复现同一盘面）
=== 初始棋盘（. 空 / 数字为颜色） ===
r= 0 1 0 2 1 3 2 0 1 3 2 1
r= 1 2 1 0 3 2 1 3 0 2 1 0
r= 2 3 2 1 0 3 2 0 1 2 0 3
r= 3 2 1 0 3 2 1 3 0 2 1 0
r= 4 3 2 1 0 3 2 0 1 2 0 3
命中 (3,4) 颜色=2
同色连通块大小 = 4
满足 3 连，已消除
判定为悬挂（将掉落）的泡泡数 = 6
=== 消除+塌落后 ===
r= 0 1 0 2 1 3 2 0 1 3 2 1
r= 1 2 1 0 3 2 1 3 0 2 1 0
r= 2 3 2 1 0 3 2 0 1 2 0 3
r= 3 . . . . . . . . . . .
r= 4 3 2 1 0 3 2 0 1 2 0 3
可以看到第 3 行被挖开一个”洞”后，第 4 行对应区间与顶部完全断连，被正确判定为 6 个悬挂泡泡并整体掉落。
六、并查集方案 vs BFS 方案：为什么值得多写这 40 行
| 维度 | 每回合 BFS 重标 | 每回合重建并查集 |
|---|---|---|
| 时间复杂度 | O(N)，N=格数 | O(N α(N))，近线性 |
| 常数 | 需分配/复用 visited，cache 不友好 | 两次线性扫描 + 极简数组操作 |
| 正确性风险 | visited 复用易漏清，边界易错 | 重建即干净，无状态残留 |
| 可扩展性 | 想加”多虚拟源”要改 BFS | 想加多个锚点只需多 union 几行 |
差异不体现在渐近复杂度，而体现在代码的可维护性与错误面。这类”每帧都要跑一次的小判定”，正确性远比理论复杂度重要。
七、复杂度与扩展
- 同色连通块：O(块大小)；最坏 O(N·6)。
- 悬挂判定：重建 O(N·6 α(N))，查询 O(α(N))。
- 扩展一：离线逆向加边（真正的”删边连通性”）。若想避免每回合重建，可把整局的消除序列记录下来，倒序处理：一开始只保留最终状态，然后逐回合”加回”被消除的泡泡并合并——这需要预知未来操作，适用于关卡预计算/AI 评估。
- 扩展二：反弹瞄准。命中判定用参数化直线与网格求交，轴向坐标下可用”cube rounding”求射线经过的格序列，比逐像素采样精确且快。
- 扩展三：AI 落点评估。对每个候选落点，模拟”放置 -> 连通块 -> 消除 -> 塌落”，用收益（消除数 + 掉落数）与风险（暴露新行）加权打分，取最优。此时悬挂判定会被调用上千次，并查集的低常数会真正体现价值。
八、小结
泡泡龙的算法骨架是”几何 + 连通性“两层：几何层用轴向坐标消灭奇偶分支，让 6 邻域查询成为一个无分支循环；连通性层用并查集 + 虚拟顶节点把”是否悬挂”降解为一次 find 比较。这套组合不仅适用于泡泡龙，也可直接用于”消除类游戏的浮空/坠落判定””地图分区与归属判定””连通块维护”等同构问题。
