三消游戏（Match-3）是休闲益智游戏的经典类型，代表作包括《宝石迷阵》《糖果传奇》等。玩家通过交换相邻元素，使三个或以上相同元素连成一线即可消除，并触发级联反应。本文用Java实现三消游戏的核心算法引擎。
核心规则建模
游戏面板通常是一个 M × N 的二维网格，每个格子包含一种颜色/类型的宝石。玩家可以交换水平或垂直相邻的两个宝石，如果交换后形成三个或以上同色连线，则触发消除。
public class Match3Engine {
// 宝石类型枚举
enum GemType {
EMPTY(0), RED(1), BLUE(2), GREEN(3), YELLOW(4), PURPLE(5), ORANGE(6);
final int code;
GemType(int c) { this.code = c; }
}
private final int rows, cols;
private GemType[][] board;
private final Random random = new Random();
public Match3Engine(int rows, int cols) {
this.rows = rows;
this.cols = cols;
this.board = new GemType[rows][cols];
initializeBoard();
}
/**
* 初始化面板，确保没有初始匹配
*/
private void initializeBoard() {
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
GemType gem;
do {
gem = randomGem();
} while (wouldFormMatch(r, c, gem));
board[r][c] = gem;
}
}
}
private GemType randomGem() {
return GemType.values()[1 + random.nextInt(6)]; // 排除EMPTY
}
/**
* 检查在(r,c)放置gem是否会形成匹配
*/
private boolean wouldFormMatch(int r, int c, GemType gem) {
// 临时放置检查
GemType original = board[r][c];
board[r][c] = gem;
boolean match = hasMatchAt(r, c);
board[r][c] = original;
return match;
}
}
BFS连通检测算法
消除的核心是检测所有满足匹配条件的连通区域。我们使用BFS从每个宝石出发，搜索水平或垂直方向的同色连续序列。
public class Match3Engine {
/**
* 使用BFS查找所有可消除的连通组
* @return 所有匹配组的坐标集合
*/
public List<List<int[]>> findAllMatches() {
boolean[][] visited = new boolean[rows][cols];
List<List<int[]>> allMatches = new ArrayList<>();
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (visited[r][c] || board[r][c] == GemType.EMPTY) continue;
// BFS搜索水平方向连续同色
List<int[]> horizontal = new ArrayList<>();
horizontal.add(new int[]{r, c});
// 向右扩展
for (int nc = c + 1; nc < cols && board[r][nc] == board[r][c]; nc++) {
horizontal.add(new int[]{r, nc});
}
// 向左扩展
for (int nc = c - 1; nc >= 0 && board[r][nc] == board[r][c]; nc--) {
horizontal.add(new int[]{r, nc});
}
// BFS搜索垂直方向连续同色
List<int[]> vertical = new ArrayList<>();
vertical.add(new int[]{r, c});
// 向下扩展
for (int nr = r + 1; nr < rows && board[nr][c] == board[r][c]; nr++) {
vertical.add(new int[]{nr, c});
}
// 向上扩展
for (int nr = r - 1; nr >= 0 && board[nr][c] == board[r][c]; nr--) {
vertical.add(new int[]{nr, c});
}
// 如果任一方向达到3个或以上，记录匹配
if (horizontal.size() >= 3) {
allMatches.add(horizontal);
for (int[] pos : horizontal) visited[pos[0]][pos[1]] = true;
}
if (vertical.size() >= 3) {
allMatches.add(vertical);
for (int[] pos : vertical) visited[pos[0]][pos[1]] = true;
}
}
}
return allMatches;
}
/**
* 检查特定位置是否有匹配（用于交换合法性判断）
*/
private boolean hasMatchAt(int r, int c) {
GemType gem = board[r][c];
if (gem == GemType.EMPTY) return false;
// 水平计数
int hCount = 1;
for (int nc = c + 1; nc < cols && board[r][nc] == gem; nc++) hCount++;
for (int nc = c - 1; nc >= 0 && board[r][nc] == gem; nc--) hCount++;
// 垂直计数
int vCount = 1;
for (int nr = r + 1; nr < rows && board[nr][c] == gem; nr++) vCount++;
for (int nr = r - 1; nr >= 0 && board[nr][c] == gem; nr--) vCount++;
return hCount >= 3 || vCount >= 3;
}
}
级联消除与重力下落
消除后上方的宝石需要下落填补空缺，新的宝石从顶部生成。这个过程中可能再次形成匹配，触发级联反应。
public class Match3Engine {
/**
* 执行完整的消除-下落-级联流程
* @return 每次消除的得分记录
*/
public List<CascadeResult> executeCascades() {
List<CascadeResult> cascades = new ArrayList<>();
int round = 0;
while (true) {
List<List<int[]>> matches = findAllMatches();
if (matches.isEmpty()) break;
round++;
int gemsCleared = 0;
Set<int[]> uniquePositions = new HashSet<>();
// 计算得分：基础分 × Combo加成
int baseScore = 0;
for (List<int[]> group : matches) {
gemsCleared += group.size();
uniquePositions.addAll(group);
// 匹配长度奖励：3个=30分, 4个=60分, 5个=100分
baseScore += group.size() * 10 + (group.size() - 3) * 20;
}
int comboMultiplier = Math.min(round, 8); // Combo上限8倍
int totalScore = baseScore * comboMultiplier;
cascades.add(new CascadeResult(round, gemsCleared, totalScore,
new ArrayList<>(uniquePositions)));
// 标记消除位置
for (int[] pos : uniquePositions) {
board[pos[0]][pos[1]] = GemType.EMPTY;
}
// 重力下落
applyGravity();
// 顶部生成新宝石
fillTop();
}
return cascades;
}
/**
* 重力下落：每列从下往上检查，非空宝石下落到最低可用位置
*/
private void applyGravity() {
for (int c = 0; c < cols; c++) {
int writePos = rows - 1; // 从底部开始写入
for (int r = rows - 1; r >= 0; r--) {
if (board[r][c] != GemType.EMPTY) {
if (r != writePos) {
board[writePos][c] = board[r][c];
board[r][c] = GemType.EMPTY;
}
writePos--;
}
}
}
}
/**
* 填充顶部空位
*/
private void fillTop() {
for (int c = 0; c < cols; c++) {
for (int r = 0; r < rows; r++) {
if (board[r][c] == GemType.EMPTY) {
board[r][c] = randomGem();
} else {
break; // 遇到非空停止，因为重力已保证连续性
}
}
}
}
static class CascadeResult {
int round;
int gemsCleared;
int score;
List<int[]> positions;
CascadeResult(int r, int g, int s, List<int[]> p) {
this.round = r;
this.gemsCleared = g;
this.score = s;
this.positions = p;
}
@Override
public String toString() {
return String.format("第%d轮消除: %d个宝石, 得分%d", round, gemsCleared, score);
}
}
}
最优交换搜索策略
为了构建AI玩家，需要评估所有可能的交换并选择最优的一步。这涉及到对每次交换后的级联结果进行预测。
public class Match3Engine {
/**
* 评估所有合法交换，返回最优动作
* 使用贪心策略评估未来1-2步的级联收益
*/
public SwapMove findBestMove() {
SwapMove bestMove = null;
int bestScore = -1;
// 遍历所有可能的交换
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
// 尝试右交换
if (c + 1 < cols) {
int score = evaluateSwap(r, c, r, c + 1);
if (score > bestScore) {
bestScore = score;
bestMove = new SwapMove(r, c, r, c + 1, score);
}
}
// 尝试下交换
if (r + 1 < rows) {
int score = evaluateSwap(r, c, r + 1, c);
if (score > bestScore) {
bestScore = score;
bestMove = new SwapMove(r, c, r + 1, c, score);
}
}
}
}
return bestMove;
}
/**
* 评估一次交换的预期收益
* 方法：模拟交换并执行级联，计算总得分
*/
private int evaluateSwap(int r1, int c1, int r2, int c2) {
// 保存当前状态
GemType[][] backup = deepCopy(board);
// 执行交换
GemType temp = board[r1][c1];
board[r1][c1] = board[r2][c2];
board[r2][c2] = temp;
// 检查是否形成匹配
if (!hasMatchAt(r1, c1) && !hasMatchAt(r2, c2)) {
// 无匹配，撤销交换
board = backup;
return -1; // 非法移动
}
// 执行级联并计算总分
List<CascadeResult> cascades = executeCascades();
int totalScore = cascades.stream().mapToInt(c -> c.score).sum();
// 额外奖励：创造特殊宝石的机会
totalScore += evaluateSpecialGemPotential(r1, c1, r2, c2);
// 恢复状态
board = backup;
return totalScore;
}
/**
* 评估创造特殊宝石的潜力（4连、5连、T型、L型）
*/
private int evaluateSpecialGemPotential(int r1, int c1, int r2, int c2) {
int potential = 0;
// 4连奖励
potential += countDirection(r1, c1, 0, 1) + countDirection(r1, c1, 1, 0) >= 4 ? 50 : 0;
potential += countDirection(r2, c2, 0, 1) + countDirection(r2, c2, 1, 0) >= 4 ? 50 : 0;
// T型和L型检测（简化版）
if (hasLShape(r1, c1) || hasLShape(r2, c2)) potential += 100;
return potential;
}
private int countDirection(int r, int c, int dr, int dc) {
GemType gem = board[r][c];
int count = 1;
int nr = r + dr, nc = c + dc;
while (inBounds(nr, nc) && board[nr][nc] == gem) {
count++;
nr += dr;
nc += dc;
}
nr = r - dr; nc = c - dc;
while (inBounds(nr, nc) && board[nr][nc] == gem) {
count++;
nr -= dr;
nc -= dc;
}
return count;
}
private boolean hasLShape(int r, int c) {
int h = countDirection(r, c, 0, 1);
int v = countDirection(r, c, 1, 0);
return h >= 3 && v >= 3;
}
private boolean inBounds(int r, int c) {
return r >= 0 && r < rows && c >= 0 && c < cols;
}
private GemType[][] deepCopy(GemType[][] src) {
GemType[][] copy = new GemType[src.length][];
for (int i = 0; i < src.length; i++) {
copy[i] = src[i].clone();
}
return copy;
}
static class SwapMove {
int r1, c1, r2, c2;
int expectedScore;
SwapMove(int r1, int c1, int r2, int c2, int score) {
this.r1 = r1; this.c1 = c1;
this.r2 = r2; this.c2 = c2;
this.expectedScore = score;
}
@Override
public String toString() {
return String.format("交换(%d,%d)和(%d,%d), 预期得分:%d", r1, c1, r2, c2, expectedScore);
}
}
}
运行演示
public class Match3Demo {
public static void main(String[] args) {
Match3Engine engine = new Match3Engine(8, 8);
System.out.println("=== 初始面板 ===");
engine.printBoard();
// AI寻找最优移动
Match3Engine.SwapMove best = engine.findBestMove();
System.out.println("\nAI推荐移动: " + best);
// 执行移动并触发级联
if (best != null) {
engine.swap(best.r1, best.c1, best.r2, best.c2);
List<Match3Engine.CascadeResult> cascades = engine.executeCascades();
System.out.println("\n=== 级联消除结果 ===");
int total = 0;
for (Match3Engine.CascadeResult c : cascades) {
System.out.println(c);
total += c.score;
}
System.out.println("总得分: " + total);
}
}
}
算法复杂度分析
- BFS匹配检测：遍历每个格子，对每个格子进行四方向的线性扫描，时间复杂度
O(rows × cols × max(rows, cols))。对于常见的8×8面板，完全可接受。 - 级联消除：每轮消除后重力和填充操作是
O(rows × cols)，级联轮数通常不超过5轮。 - 最优交换搜索：需要评估
2 × rows × cols种交换，每种评估需要一次完整的级联模拟，最坏情况O(rows² × cols² × max(rows, cols))。对于小面板可用，大面板需要引入剪枝或蒙特卡洛采样。
扩展方向
- 特殊宝石系统：实现炸弹、激光、彩虹球等特殊宝石的生成和爆炸效果
- 蒙特卡洛树搜索：用MCTS评估多步后的最优策略，而非单步贪心
- 模式识别：预计算常见有利图案（如”可形成4连的预备形状”）
- 关卡生成：使用约束满足算法生成有解且有趣的初始面板
