引言
魔法气泡（Puyo Puyo）是 Compile 于1991年推出的经典连锁消除游戏，以其深度的策略性和华丽的连锁系统闻名。游戏中，玩家控制成对下落的气泡（Puyo），将四个及以上同颜色气泡连在一起即可消除。消除后上方气泡下落，可能触发连锁反应（Chain），产生巨大的攻击压力。本文用 Java 实现魔法气泡的 AI 核心算法，重点讲解BFS连通块检测与连击深度评估。
游戏规则建模
游戏场景为一个 6 列 × 12 行的垂直场地（Field）：
– 气泡（Puyo）：红、绿、蓝、黄、紫五色，每次下落一对（可以旋转）
– 消除规则：4 个及以上同色气泡在上下左右四连通时消除
– 连锁（Chain）：消除后气泡下落，若形成新的 4 连则继续消除，连锁数 +1
– 攻击（Attack）：连锁数越高，向对手发送的干扰气泡（Ojama）越多
AI 的目标：选择最优下落位置和旋转角度，最大化连锁深度或即时消除威胁。
核心算法设计
BFS 连通块检测
连通块检测是魔法气泡最基础的算法。对于场地上每个有气泡的格子，使用 BFS 或 Flood Fill 找到其所属的连通区域，统计区域大小（气泡数量）。当区域大小 ≥ 4 时，该区域标记为待消除。
关键细节：
– 四连通：上下左右，不包含对角线
– 颜色严格匹配：只有完全相同颜色的气泡才能连通
– 消除后重力处理：被消除的气泡变为空，上方气泡逐个下落
连击深度评估
连击深度评估是 AI 的核心难点。与简单的单次消除不同，优秀的魔法气泡玩家追求的是”先搭后消”——先在场地上构建多层潜在消除结构，然后一次性触发深层连锁。
我们的评估策略：
1. 即时消除分：当前动作直接消除的气泡数 × 10
2. 一步连锁预测：模拟放置后消除 → 下落 → 再次检测，计算连锁深度
3. 结构潜力分：评估场地上已存在的、差 1-2 个气泡就能形成 4 连的”准连通块”数量
4. 高度风险分：最高气泡列的高度越接近顶部，风险越大
5. 颜色集中度：同色气泡越集中，越容易形成大连锁
Java 实现
import java.util.*;
/**
* 魔法气泡 AI：BFS连通检测与连击深度评估
*/
public class PuyoPuyoAI {
static final int ROWS = 12;
static final int COLS = 6;
static final int EMPTY = 0;
static final int RED = 1, GREEN = 2, BLUE = 3, YELLOW = 4, PURPLE = 5;
static final int OJAMA = 9; // 干扰气泡（灰色）
// 四连通方向
static final int[] DX = {0, 0, -1, 1};
static final int[] DY = {-1, 1, 0, 0};
int[][] field;
public PuyoPuyoAI() {
this.field = new int[ROWS][COLS];
}
public PuyoPuyoAI(int[][] field) {
this.field = new int[ROWS][COLS];
for (int i = 0; i < ROWS; i++) {
System.arraycopy(field[i], 0, this.field[i], 0, COLS);
}
}
/**
* 气泡对：主气泡 + 副气泡，可旋转
*/
static class PuyoPair {
int c1, c2; // 两个气泡颜色
int x; // 主气泡列（0-5）
int y; // 主气泡行（下落中）
int rotation; // 0=副在上, 1=副在右, 2=副在下, 3=副在左
PuyoPair(int c1, int c2) {
this.c1 = c1; this.c2 = c2;
}
// 获取两个气泡的相对坐标 (dx, dy)
int[] getOffset() {
switch (rotation) {
case 0: return new int[]{0, -1}; // 上
case 1: return new int[]{1, 0}; // 右
case 2: return new int[]{0, 1}; // 下
case 3: return new int[]{-1, 0}; // 左
default: return new int[]{0, -1};
}
}
// 获取两个气泡的绝对坐标 (col, row)，假设主气泡在 (x, landingY)
int[][] getAbsolutePositions(int landingY) {
int[] off = getOffset();
return new int[][]{{x, landingY}, {x + off[0], landingY + off[1]}};
}
}
/**
* AI 决策结果
*/
static class Decision {
int x, rotation;
double score;
int chainDepth;
int puyosCleared;
Decision(int x, int rotation) {
this.x = x; this.rotation = rotation;
}
}
/**
* AI 主决策函数
*/
public Decision decideBestMove(int[][] currentField, int c1, int c2) {
this.field = currentField;
List<Decision> candidates = new ArrayList<>();
for (int rot = 0; rot < 4; rot++) {
PuyoPair pair = new PuyoPair(c1, c2);
pair.rotation = rot;
int[] off = pair.getOffset();
int minX = Math.max(0, -off[0]);
int maxX = Math.min(COLS - 1, COLS - 1 - off[0]);
for (int x = minX; x <= maxX; x++) {
pair.x = x;
Decision d = evaluatePlacement(pair);
if (d != null) {
d.x = x;
d.rotation = rot;
candidates.add(d);
}
}
}
if (candidates.isEmpty()) return null;
candidates.sort((a, b) -> Double.compare(b.score, a.score));
return candidates.get(0);
}
/**
* 评估一个放置位置
*/
Decision evaluatePlacement(PuyoPair pair) {
int[][] simField = cloneField();
// 计算两个气泡的下落位置
int[][] pos = computeLandingPosition(pair, simField);
if (pos == null) return null;
// 放置气泡
simField[pos[0][1]][pos[0][0]] = pair.c1;
simField[pos[1][1]][pos[1][0]] = pair.c2;
Decision d = new Decision(pair.x, pair.rotation);
// 模拟连锁消除
ChainResult chain = simulateChain(simField);
d.chainDepth = chain.depth;
d.puyosCleared = chain.totalCleared;
// 综合评分
d.score = computeScore(simField, chain, pos);
return d;
}
/**
* 计算气泡对的最终落点
*/
int[][] computeLandingPosition(PuyoPair pair, int[][] simField) {
int[] off = pair.getOffset();
int c1x = pair.x;
int c2x = pair.x + off[0];
// 找到每列当前高度
int h1 = getColumnHeight(simField, c1x);
int h2 = getColumnHeight(simField, c2x);
int c1y = ROWS - 1 - h1;
int c2y = ROWS - 1 - h2;
// 处理垂直放置的情况（副气泡在主气泡下方）
if (pair.rotation == 2) { // 副在下
if (c1y >= c2y) {
c2y = c1y + 1;
if (c2y >= ROWS) return null;
}
} else if (pair.rotation == 0) { // 副在上
if (c2y >= c1y) {
c1y = c2y + 1;
if (c1y >= ROWS) return null;
}
}
// 检查边界
if (c1y < 0 || c2y < 0 || c1x < 0 || c1x >= COLS || c2x < 0 || c2x >= COLS) {
return null;
}
// 检查目标位置是否已被占据
if (simField[c1y][c1x] != EMPTY || simField[c2y][c2x] != EMPTY) {
return null;
}
return new int[][]{{c1x, c1y}, {c2x, c2y}};
}
int getColumnHeight(int[][] f, int x) {
int h = 0;
for (int y = 0; y < ROWS; y++) {
if (f[y][x] != EMPTY) h++;
}
return h;
}
/**
* 模拟连锁消除
*/
ChainResult simulateChain(int[][] simField) {
int depth = 0;
int totalCleared = 0;
boolean changed;
do {
changed = false;
boolean[][] visited = new boolean[ROWS][COLS];
boolean[][] toClear = new boolean[ROWS][COLS];
// BFS 检测所有连通块
for (int y = 0; y < ROWS; y++) {
for (int x = 0; x < COLS; x++) {
if (simField[y][x] == EMPTY || simField[y][x] == OJAMA || visited[y][x]) continue;
List<int[]> group = bfsGroup(simField, x, y, visited);
if (group.size() >= 4) {
for (int[] p : group) {
toClear[p[1]][p[0]] = true;
}
}
}
}
// 执行消除
int cleared = 0;
for (int y = 0; y < ROWS; y++) {
for (int x = 0; x < COLS; x++) {
if (toClear[y][x]) {
simField[y][x] = EMPTY;
cleared++;
changed = true;
}
}
}
if (changed) {
totalCleared += cleared;
applyGravity(simField);
depth++;
}
} while (changed);
return new ChainResult(depth, totalCleared);
}
/**
* BFS 找到一个连通块的所有气泡
*/
List<int[]> bfsGroup(int[][] f, int sx, int sy, boolean[][] visited) {
List<int[]> group = new ArrayList<>();
int color = f[sy][sx];
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{sx, sy});
visited[sy][sx] = true;
while (!q.isEmpty()) {
int[] cur = q.poll();
group.add(cur);
for (int d = 0; d < 4; d++) {
int nx = cur[0] + DX[d];
int ny = cur[1] + DY[d];
if (inBounds(nx, ny) && !visited[ny][nx] && f[ny][nx] == color) {
visited[ny][nx] = true;
q.add(new int[]{nx, ny});
}
}
}
return group;
}
/**
* 应用重力：让气泡下落
*/
void applyGravity(int[][] f) {
for (int x = 0; x < COLS; x++) {
int writeY = ROWS - 1;
for (int y = ROWS - 1; y >= 0; y--) {
if (f[y][x] != EMPTY) {
if (writeY != y) {
f[writeY][x] = f[y][x];
f[y][x] = EMPTY;
}
writeY--;
}
}
}
}
/**
* 综合评分
*/
double computeScore(int[][] simField, ChainResult chain, int[][] placedPos) {
double score = 0;
// 1. 连锁深度是最重要指标
score += chain.depth * chain.depth * 100;
// 2. 消除气泡数
score += chain.totalCleared * 10;
// 3. 结构潜力：统计"准连通块"（大小为2或3的连通块）
score += countPotentialChains(simField) * 30;
// 4. 高度风险：最高列越接近顶部风险越大
int maxHeight = 0;
for (int x = 0; x < COLS; x++) {
maxHeight = Math.max(maxHeight, getColumnHeight(simField, x));
}
score -= maxHeight * 5;
// 5. 颜色集中度奖励：同色气泡相邻越多潜力越大
score += countColorConcentration(simField) * 2;
// 6. 放置位置奖励：放在中间列通常更灵活
int centerX = (placedPos[0][0] + placedPos[1][0]) / 2;
score -= Math.abs(centerX - COLS / 2) * 3;
return score;
}
/**
* 统计准连通块数量（大小为2或3的连通块）
*/
int countPotentialChains(int[][] f) {
int count = 0;
boolean[][] visited = new boolean[ROWS][COLS];
for (int y = 0; y < ROWS; y++) {
for (int x = 0; x < COLS; x++) {
if (f[y][x] == EMPTY || f[y][x] == OJAMA || visited[y][x]) continue;
List<int[]> group = bfsGroup(f, x, y, visited);
if (group.size() == 2 || group.size() == 3) {
count++;
}
}
}
return count;
}
/**
* 统计颜色集中度：同色相邻对的数量
*/
int countColorConcentration(int[][] f) {
int count = 0;
for (int y = 0; y < ROWS; y++) {
for (int x = 0; x < COLS; x++) {
if (f[y][x] == EMPTY || f[y][x] == OJAMA) continue;
// 检查右邻居
if (x + 1 < COLS && f[y][x + 1] == f[y][x]) count++;
// 检查下邻居
if (y + 1 < ROWS && f[y + 1][x] == f[y][x]) count++;
}
}
return count;
}
boolean inBounds(int x, int y) {
return x >= 0 && x < COLS && y >= 0 && y < ROWS;
}
int[][] cloneField() {
int[][] clone = new int[ROWS][COLS];
for (int i = 0; i < ROWS; i++) {
System.arraycopy(field[i], 0, clone[i], 0, COLS);
}
return clone;
}
static class ChainResult {
int depth, totalCleared;
ChainResult(int d, int t) { depth = d; totalCleared = t; }
}
// 主程序演示
public static void main(String[] args) {
int[][] field = new int[ROWS][COLS];
// 构建一个有潜力的盘面
field[11][1] = RED; field[11][2] = RED;
field[10][1] = RED; field[10][2] = RED;
field[11][3] = BLUE; field[10][3] = BLUE; field[9][3] = BLUE;
field[11][4] = GREEN; field[10][4] = GREEN;
field[9][4] = GREEN;
PuyoPuyoAI ai = new PuyoPuyoAI(field);
// 当前下落的是红色-蓝色气泡对
Decision best = ai.decideBestMove(field, RED, BLUE);
System.out.println("=== 魔法气泡 AI 决策结果 ===");
if (best != null) {
System.out.println("最佳动作：列=" + best.x + ", 旋转=" + best.rotation);
System.out.println("预测连锁深度：" + best.chainDepth);
System.out.println("预测消除气泡数：" + best.puyosCleared);
System.out.println("综合评分：" + String.format("%.2f", best.score));
}
}
}
算法解析
BFS vs DFS 的选择
在连通块检测中，BFS 和 DFS 都能完成任务，但 BFS 有独特优势：
– BFS 按层扩展，天然适合”找所有距离为 k 的邻居”这类操作
– 在魔法气泡中，连通块通常较小（最大 12×6 = 72 格），BFS 的队列开销可以忽略
– BFS 的迭代顺序更稳定，便于调试和可视化
连锁模拟的核心循环
连锁模拟采用”检测 → 消除 → 重力 → 再检测”的循环模式。每次循环称为一个”Step”，Step 数即为连锁深度。关键在于：
1. 消除必须一次性标记所有满足条件的连通块，不能逐次消除
2. 重力下落要按列独立处理，保持每列内部顺序
3. 干扰气泡（Ojama）不参与任何连通，但会阻挡下落
结构潜力评估
高级魔法气泡 AI 不仅看当前能消多少，更关注”下一步能消多少”。countPotentialChains 统计大小为 2 或 3 的连通块数量，这些是”差一点就消除”的结构。AI 倾向于：
– 将新气泡放在准连通块旁边，为下一手创造消除机会
– 避免破坏已有的准连通结构
– 构建”阶梯式”多层连锁架构
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| BFS 连通块检测 | O(ROWS × COLS) | O(ROWS × COLS) |
| 单次连锁模拟 | O(K × ROWS × COLS) | O(ROWS × COLS) |
| 结构潜力统计 | O(ROWS × COLS) | O(ROWS × COLS) |
| 完整决策（约20个候选） | O(20 × K × ROWS × COLS) | O(ROWS × COLS) |
对于 12×6 的场地，单次决策在微秒到毫秒级完成，完全满足实时性要求。
扩展思路
- 树搜索：用 Minimax 或 Expectimax 搜索未来 2-3 步，考虑对手发送的干扰气泡
- 形状识别：识别经典连锁形状（如楼梯、塔、GTR），直接套用最优落点
- 深度学习：用强化学习训练神经网络评估盘面价值，AlphaZero 风格的自对弈训练
总结
本文通过 Java 实现了魔法气泡的 AI 核心系统，涵盖：
– BFS 四连通检测：准确识别所有可消除的连通块
– 连锁深度模拟：迭代消除+重力模拟精确预测连锁结果
– 多维度评估函数：兼顾即时消除、连锁深度、结构潜力和风险控制
读者可以从中学习到：BFS 在网格连通性检测中的应用、消除类游戏的连锁模拟技巧、以及贪心评估函数的设计方法论。
