游戏简介与算法目标
消消乐（Match-3）是一款家喻户晓的益智消除类游戏，玩家通过交换相邻的两个宝石，使三个或三个以上同色宝石连成一线即可消除得分。消除后上方的宝石受重力影响下落填补空缺，新的宝石从顶部生成，由此可能触发连续消除——即”级联消除”（Cascade），带来额外分数奖励。
本文的目标是剥离绚丽的界面特效，聚焦于消消乐的核心算法逻辑，用 Java 实现一个可在控制台运行的完整版本。读者将学到以下四种关键算法：
- Flood Fill 连通分量检测：通过 DFS 找出棋盘上所有同色连通的宝石簇，判定哪些满足消除条件（数量 ≥ 3）。
- 重力模拟算法：消除后让上方宝石逐格下落，并在顶部生成新宝石。
- 级联消除检测：循环执行”检测→消除→重力”，直到没有新的匹配产生。
- 贪心最优消除策略：评估所有合法的相邻交换，选择能触发最多消除或最高得分的步。
核心算法一：Flood Fill 连通分量检测
消消乐的第一步是判断”当前棋盘上有哪些宝石可以消除”。这本质上是一个连通分量（Connected Component）问题：将棋盘视为无向图，每个格子与其上下左右相邻且颜色相同的格子之间存在边。我们需要找出所有大小不小于 3 的连通分量。
Flood Fill（洪水填充）算法是解决此类问题的经典方案。它从每一个未访问的格子出发，使用深度优先搜索（DFS）或广度优先搜索（BFS）向四周”漫延”，标记所有颜色相同且可达的格子，从而得到该连通分量的全部成员。
算法步骤
- 创建一个与棋盘等大的
visited布尔矩阵，初始全为false。 - 遍历棋盘的每一个格子
(r, c)，若该格子未被访问： - 以其为起点执行 DFS/BFS，收集所有同色连通格子。
- 若连通分量的大小 ≥ 3，则记录为一个”匹配”。
- 返回所有匹配列表。
该算法的时间复杂度为 O(ROWS × COLS)，因为每个格子最多被访问一次。
核心算法二：重力模拟与级联消除
当一组宝石被消除后，它们所在的位置变成”空洞”。为了让游戏继续进行，需要模拟重力效果：每一列中，空洞下方的宝石应向上移动填补空缺，空缺位置则由顶部新随机生成的宝石填充。
重力模拟步骤
对每一列 c 独立处理：
1. 从底部向上遍历，将所有非空宝石按从下到上的顺序”压缩”到列底。
2. 列顶剩余的空位用随机颜色的新宝石填充。
级联消除
重力填充后，新落下的宝石可能与周围宝石形成新的匹配。因此需要循环执行：
while (存在匹配) {
消除匹配宝石;
应用重力;
级联计数器++;
}
通常级联消除会伴随分数倍率奖励，例如第 n 次级联的得分为 消除数量 × n。
核心算法三：贪心最优消除策略
在实现 AI 自动游玩时，我们需要一种策略来决定”下一步交换哪两个相邻宝石”。消消乐的状态空间巨大，精确求解属于 PSPACE-Complete 问题。实践中常采用贪心策略：枚举所有合法的相邻交换，模拟执行后的得分，选择得分最高的那一步。
贪心评估步骤
- 遍历所有水平相邻和垂直相邻的格子对。
- 对每一对，临时交换后调用
processMatches()计算得分。 - 恢复棋盘状态（通过深拷贝备份实现）。
- 返回得分最高的交换动作。
虽然贪心策略无法保证全局最优，但在消消乐这类具有局部奖励结构的游戏中表现优异，且计算复杂度可控。
完整 Java 实现
以下代码是一个完整的、可直接编译运行的单文件 Java 项目。它包含棋盘管理、匹配检测、重力模拟、级联消除和贪心 AI 决策的全部逻辑。
import java.util.*;
/**
* 消消乐（Match-3）核心算法实现
*
* 核心算法：
* 1. Flood Fill (DFS) 连通分量检测 —— 找出可消除的宝石簇
* 2. 重力模拟 —— 消除后宝石下落、顶部生成新宝石
* 3. 级联消除 —— 循环检测直至无新匹配
* 4. 贪心策略 —— 评估所有合法交换，选择最优步
*/
public class Match3Game {
// 棋盘配置
private static final int ROWS = 8; // 行数
private static final int COLS = 8; // 列数
private static final int COLORS = 5; // 宝石颜色种类数（0~4）
private static final int MATCH_SIZE = 3; // 最少消除数量
private static final int EMPTY = -1; // 空位标记
// 颜色对应的控制台显示字符（便于观察）
private static final char[] COLOR_CHARS = {'R', 'G', 'B', 'Y', 'P'};
private int[][] board; // 当前棋盘
private Random random; // 随机数生成器
private int totalScore; // 累计得分
public Match3Game() {
this.random = new Random();
this.board = new int[ROWS][COLS];
this.totalScore = 0;
initializeBoard();
}
/**
* 初始化棋盘，确保没有任何初始匹配
*/
private void initializeBoard() {
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
int color;
do {
color = random.nextInt(COLORS);
} while (wouldFormMatch(r, c, color));
board[r][c] = color;
}
}
}
/**
* 检查：如果在 (row, col) 放置指定颜色，是否会形成 >=3 的连线
* 用于初始化时避免预设匹配
*/
private boolean wouldFormMatch(int row, int col, int color) {
// 水平方向计数
int count = 1;
for (int c = col - 1; c >= 0 && board[row][c] == color; c--) count++;
for (int c = col + 1; c < COLS && board[row][c] == color; c++) count++;
if (count >= MATCH_SIZE) return true;
// 垂直方向计数
count = 1;
for (int r = row - 1; r >= 0 && board[r][col] == color; r--) count++;
for (int r = row + 1; r < ROWS && board[r][col] == color; r++) count++;
return count >= MATCH_SIZE;
}
/**
* Flood Fill (DFS) 查找从 (r, c) 出发的连通分量
* @return 连通分量中所有格子的坐标列表
*/
private List<int[]> floodFill(int r, int c, boolean[][] visited) {
List<int[]> component = new ArrayList<>();
int color = board[r][c];
Deque<int[]> stack = new ArrayDeque<>();
stack.push(new int[]{r, c});
visited[r][c] = true;
// 四方向：上、下、左、右
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!stack.isEmpty()) {
int[] curr = stack.pop();
component.add(curr);
for (int[] d : directions) {
int nr = curr[0] + d[0];
int nc = curr[1] + d[1];
if (inBounds(nr, nc) && !visited[nr][nc] && board[nr][nc] == color) {
visited[nr][nc] = true;
stack.push(new int[]{nr, nc});
}
}
}
return component;
}
private boolean inBounds(int r, int c) {
return r >= 0 && r < ROWS && c >= 0 && c < COLS;
}
/**
* 查找棋盘上所有满足消除条件的匹配（连通分量大小 >= 3）
*/
private List<List<int[]>> findAllMatches() {
List<List<int[]>> matches = new ArrayList<>();
boolean[][] visited = new boolean[ROWS][COLS];
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
if (board[r][c] != EMPTY && !visited[r][c]) {
List<int[]> component = floodFill(r, c, visited);
if (component.size() >= MATCH_SIZE) {
matches.add(component);
}
}
}
}
return matches;
}
/**
* 将匹配列表中的宝石消除（标记为 EMPTY）
* @return 本次消除的宝石总数
*/
private int removeMatches(List<List<int[]>> matches) {
int removed = 0;
for (List<int[]> match : matches) {
for (int[] pos : match) {
board[pos[0]][pos[1]] = EMPTY;
removed++;
}
}
return removed;
}
/**
* 重力模拟：每一列中，非空宝石下落到底部，顶部生成新宝石
*/
private void applyGravity() {
for (int c = 0; c < COLS; c++) {
int writeRow = ROWS - 1;
// 从下到上收集非空宝石
for (int r = ROWS - 1; r >= 0; r--) {
if (board[r][c] != EMPTY) {
board[writeRow][c] = board[r][c];
if (writeRow != r) {
board[r][c] = EMPTY;
}
writeRow--;
}
}
// 顶部空缺填充新随机宝石
for (int r = writeRow; r >= 0; r--) {
board[r][c] = random.nextInt(COLORS);
}
}
}
/**
* 处理一轮完整的消除流程：检测匹配 -> 消除 -> 重力 -> 重复（级联）
* @return 本轮总得分
*/
public int processMatches() {
int roundScore = 0;
int cascade = 1; // 级联倍率
while (true) {
List<List<int[]>> matches = findAllMatches();
if (matches.isEmpty()) break;
int removed = removeMatches(matches);
roundScore += removed * cascade; // 级联越高，倍率越大
cascade++;
applyGravity();
}
return roundScore;
}
/**
* 判断交换 (r1,c1) 和 (r2,c2) 后是否能产生新的匹配
* 仅允许相邻交换（上下左右）
*/
public boolean isValidSwap(int r1, int c1, int r2, int c2) {
if (Math.abs(r1 - r2) + Math.abs(c1 - c2) != 1) {
return false; // 非相邻
}
// 临时交换
int temp = board[r1][c1];
board[r1][c1] = board[r2][c2];
board[r2][c2] = temp;
boolean valid = formsMatch(r1, c1) || formsMatch(r2, c2);
// 还原
temp = board[r1][c1];
board[r1][c1] = board[r2][c2];
board[r2][c2] = temp;
return valid;
}
/**
* 检查位置 (r, c) 是否在当前棋盘状态下形成了 >=3 的连线
*/
private boolean formsMatch(int r, int c) {
int color = board[r][c];
if (color == EMPTY) return false;
// 水平
int count = 1;
for (int nc = c - 1; nc >= 0 && board[r][nc] == color; nc--) count++;
for (int nc = c + 1; nc < COLS && board[r][nc] == color; nc++) count++;
if (count >= MATCH_SIZE) return true;
// 垂直
count = 1;
for (int nr = r - 1; nr >= 0 && board[nr][c] == color; nr--) count++;
for (int nr = r + 1; nr < ROWS && board[nr][c] == color; nr++) count++;
return count >= MATCH_SIZE;
}
/**
* 贪心策略：枚举所有合法交换，模拟执行后返回得分最高的动作
*/
public Move findBestMove() {
Move bestMove = null;
int bestScore = -1;
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
// 尝试与右侧交换
if (c + 1 < COLS && isValidSwap(r, c, r, c + 1)) {
int score = simulateSwapScore(r, c, r, c + 1);
if (score > bestScore) {
bestScore = score;
bestMove = new Move(r, c, r, c + 1, score);
}
}
// 尝试与下方交换
if (r + 1 < ROWS && isValidSwap(r, c, r + 1, c)) {
int score = simulateSwapScore(r, c, r + 1, c);
if (score > bestScore) {
bestScore = score;
bestMove = new Move(r, c, r + 1, c, score);
}
}
}
}
return bestMove;
}
/**
* 模拟一次交换并计算得分，模拟结束后恢复棋盘状态
*/
private int simulateSwapScore(int r1, int c1, int r2, int c2) {
// 备份当前棋盘
int[][] backup = deepCopyBoard();
// 执行交换
int temp = board[r1][c1];
board[r1][c1] = board[r2][c2];
board[r2][c2] = temp;
// 计算消除得分
int score = processMatches();
// 恢复棋盘
restoreBoard(backup);
return score;
}
/**
* 深拷贝棋盘
*/
private int[][] deepCopyBoard() {
int[][] copy = new int[ROWS][COLS];
for (int r = 0; r < ROWS; r++) {
System.arraycopy(board[r], 0, copy[r], 0, COLS);
}
return copy;
}
/**
* 从备份恢复棋盘
*/
private void restoreBoard(int[][] backup) {
for (int r = 0; r < ROWS; r++) {
System.arraycopy(backup[r], 0, board[r], 0, COLS);
}
}
/**
* 执行一次真实的交换（用于 AI 自动运行或玩家操作）
*/
public int executeSwap(int r1, int c1, int r2, int c2) {
if (!isValidSwap(r1, c1, r2, c2)) {
return 0;
}
int temp = board[r1][c1];
board[r1][c1] = board[r2][c2];
board[r2][c2] = temp;
int score = processMatches();
totalScore += score;
return score;
}
/**
* 控制台打印棋盘
*/
public void printBoard() {
System.out.println(" 0 1 2 3 4 5 6 7");
for (int r = 0; r < ROWS; r++) {
System.out.print(r + " ");
for (int c = 0; c < COLS; c++) {
if (board[r][c] == EMPTY) {
System.out.print(". ");
} else {
System.out.print(COLOR_CHARS[board[r][c]] + " ");
}
}
System.out.println();
}
System.out.println("累计得分: " + totalScore);
System.out.println();
}
public int getTotalScore() {
return totalScore;
}
/**
* 动作封装类：记录一次交换的坐标与预期得分
*/
public static class Move {
public final int r1, c1, r2, c2;
public final int score;
public Move(int r1, int c1, int r2, int c2, int score) {
this.r1 = r1; this.c1 = c1;
this.r2 = r2; this.c2 = c2;
this.score = score;
}
@Override
public String toString() {
return String.format("交换 (%d,%d) 与 (%d,%d)，预期得分: %d",
r1, c1, r2, c2, score);
}
}
// ==================== 主程序入口 ====================
public static void main(String[] args) {
Match3Game game = new Match3Game();
System.out.println("=== 消消乐核心算法演示 ===\n");
System.out.println("初始棋盘：");
game.printBoard();
// 演示贪心 AI 自动运行 10 步
for (int step = 1; step <= 10; step++) {
Move best = game.findBestMove();
if (best == null) {
System.out.println("第 " + step + " 步：无可行移动，游戏结束。");
break;
}
System.out.println("第 " + step + " 步 —— " + best);
int score = game.executeSwap(best.r1, best.c1, best.r2, best.c2);
System.out.println("实际得分: " + score);
game.printBoard();
}
System.out.println("最终累计得分: " + game.getTotalScore());
}
}
代码设计要点
| 模块 | 职责 | 关键算法 |
|---|---|---|
floodFill |
连通分量检测 | DFS 四方向搜索，O(n) 时间 |
findAllMatches |
全局匹配扫描 | 遍历 + Flood Fill，O(ROWS×COLS) |
applyGravity |
重力模拟 | 列内双指针压缩，O(ROWS×COLS) |
processMatches |
级联消除 | 循环调用上述方法直至稳定 |
findBestMove |
贪心决策 | 枚举所有合法交换并模拟评估 |
simulateSwapScore |
模拟器 | 深拷贝备份 → 交换 → 计分 → 恢复 |
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 初始化棋盘 | O(ROWS × COLS × COLORS) | O(ROWS × COLS) | 最坏情况下反复尝试颜色 |
| 连通分量检测 | O(ROWS × COLS) | O(ROWS × COLS) | 每个格子仅访问一次 |
| 重力模拟 | O(ROWS × COLS) | O(1) | 列内原地操作 |
| 级联消除（一轮） | O(k × ROWS × COLS) | O(ROWS × COLS) | k 为级联次数，通常 k ≤ 5 |
| 贪心最优步 | O(ROWS × COLS × ROWS × COLS) | O(ROWS × COLS) | 约 2×ROWS×COLS 次交换模拟 |
对于标准的 8×8 棋盘，贪心策略每步评估约 112 种交换，每种交换需要一次级联消除（约 64×5 次操作），单步决策耗时在毫秒级，完全满足实时性要求。
总结
本文以消消乐为切入点，系统讲解了四种核心算法：Flood Fill 连通分量检测用于识别可消除区域，重力模拟实现消除后的状态更新，级联消除处理连锁反应，贪心策略为 AI 提供决策能力。通过完整的 Java 代码，读者可以直接编译运行，观察 AI 如何在无人工干预的情况下自动消除得分。
消消乐的算法思想具有很强的迁移价值：Flood Fill 广泛应用于图像填充、岛屿计数；连通分量检测是图论基础；贪心策略则是众多 AI 问题的首选启发式方法。掌握这些基础算法，将为后续学习更复杂的搜索与强化学习打下坚实基础。
