消除类游戏（Match-3等）的核心算法在于快速检测棋盘上的连通区域、执行消除逻辑并处理连锁反应。本文用Java实现消除游戏引擎，涵盖BFS连通区域检测、重力下落填充与连锁消除递归算法。
算法核心思路
1. 连通区域检测（Flood Fill / BFS）
从棋盘每个未访问的位置出发，使用BFS或DFS搜索颜色相同的相邻格子，记录连通块的大小和坐标集合。若连通块大小≥消除阈值（如3个），则标记为待消除。
2. 消除与重力下落
将被标记的格子置为空，然后对每一列从下往上扫描，将非空方块下移填补空缺。顶部空位随机生成新方块。该过程可抽象为”压缩数组”操作。
3. 连锁消除判定
下落填充后，新形成的相邻关系可能产生新的可消除连通块。因此需要循环检测：消除→下落→重新检测，直到没有新的连通块产生为止。连锁次数越多，玩家得分倍数越高。
4. 特殊方块生成
一次性消除4个或更多方块时，生成特殊方块（如炸弹、激光、彩虹球）。特殊方块的触发逻辑需要单独处理，可能引发更大范围的消除。
Java实现
import java.util.*;
public class MatchGameEngine {
static final int EMPTY = 0;
static final int MATCH_MIN = 3; // 最小消除数量
private int rows;
private int cols;
private int[][] board;
private int score = 0;
private int combo = 0;
private Random rand = new Random();
private int colorCount = 5; // 颜色种类数
public MatchGameEngine(int rows, int cols) {
this.rows = rows;
this.cols = cols;
this.board = new int[rows][cols];
fillBoard();
// 确保初始状态无预消除（可选）
while (findMatches().size() > 0) {
fillBoard();
}
}
private void fillBoard() {
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
board[r][c] = rand.nextInt(colorCount) + 1;
}
}
}
/**
* BFS查找所有连通块，返回待消除坐标集合
*/
public List<int[]> findMatches() {
boolean[][] visited = new boolean[rows][cols];
List<int[]> toRemove = new ArrayList<>();
int[][] dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (board[r][c] == EMPTY || visited[r][c]) continue;
int color = board[r][c];
List<int[]> group = new ArrayList<>();
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{r, c});
visited[r][c] = true;
while (!q.isEmpty()) {
int[] cur = q.poll();
group.add(cur);
for (int[] d : dirs) {
int nr = cur[0] + d[0];
int nc = cur[1] + d[1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
&& !visited[nr][nc] && board[nr][nc] == color) {
visited[nr][nc] = true;
q.offer(new int[]{nr, nc});
}
}
}
if (group.size() >= MATCH_MIN) {
toRemove.addAll(group);
}
}
}
return toRemove;
}
/**
* 执行消除并重力下落，返回本步消除的方块数
*/
public int eliminateAndFall() {
List<int[]> matches = findMatches();
if (matches.isEmpty()) return 0;
// 标记消除
for (int[] pos : matches) {
board[pos[0]][pos[1]] = EMPTY;
}
// 重力下落：每列从下往上压缩
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] = rand.nextInt(colorCount) + 1;
}
}
return matches.size();
}
/**
* 执行一步交换并处理连锁消除
* @return 总消除方块数（含连锁）
*/
public int playMove(int r1, int c1, int r2, int c2) {
// 交换两个相邻方块
if (!isAdjacent(r1, c1, r2, c2)) return -1;
swap(r1, c1, r2, c2);
// 检查是否有消除
if (findMatches().isEmpty()) {
// 无消除则交换回来
swap(r1, c1, r2, c2);
return 0;
}
int totalRemoved = 0;
combo = 0;
while (true) {
int removed = eliminateAndFall();
if (removed == 0) break;
combo++;
totalRemoved += removed;
// 连击加成得分
score += removed * 10 * combo;
}
return totalRemoved;
}
private boolean isAdjacent(int r1, int c1, int r2, int c2) {
return Math.abs(r1 - r2) + Math.abs(c1 - c2) == 1;
}
private void swap(int r1, int c1, int r2, int c2) {
int tmp = board[r1][c1];
board[r1][c1] = board[r2][c2];
board[r2][c2] = tmp;
}
public void printBoard() {
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
System.out.print(board[r][c] == EMPTY ? ". " : board[r][c] + " ");
}
System.out.println();
}
}
public void printStats() {
System.out.printf("当前得分: %d | 最高连击: %d%n", score, combo);
}
public static void main(String[] args) {
MatchGameEngine game = new MatchGameEngine(8, 8);
System.out.println("初始棋盘：");
game.printBoard();
// 寻找可消除的相邻交换（暴力搜索演示）
boolean found = false;
outer:
for (int r = 0; r < 8 && !found; r++) {
for (int c = 0; c < 7 && !found; c++) {
int removed = game.playMove(r, c, r, c + 1);
if (removed > 0) {
System.out.printf("%n交换 (%d,%d) 与 (%d,%d)，消除 %d 个方块！%n", r, c, r, c+1, removed);
found = true;
}
}
}
if (!found) {
// 强制演示一次交换
game.playMove(3, 3, 3, 4);
System.out.println("演示交换 (3,3) 与 (3,4)：");
}
System.out.println("消除后棋盘：");
game.printBoard();
game.printStats();
}
}
复杂度分析
- 时间复杂度：每次连通块检测为O(R·C)，R行C列。一次完整连锁消除最多进行O(R·C)轮检测，最坏O((R·C)²)。实际游戏中棋盘尺寸固定且连锁深度有限，性能足够。
- 空间复杂度：O(R·C)，BFS队列和访问标记数组。
扩展方向
- 特殊方块联动：炸弹消除周围3×3区域，激光消除整行/列，彩虹球消除全屏同色。触发顺序影响最终得分。
- 可行步检测：预判当前棋盘是否存在至少一步可消除的交换，若无则自动重排（Shuffle）。
- AI自动求解：将棋盘状态建模为图节点，每一步交换为边，用BFS/DFS搜索最高得分路径，实现自动通关演示。
