每日算法 — 使用java实现消消乐：BFS连通消除与级联反应模拟

消消乐（Match-3）是三消类益智游戏的代表，玩家通过交换相邻元素使三个或以上相同元素连成一线以消除得分。本文用Java实现消消乐核心算法，重点讲解BFS连通检测用于识别可消除区域，以及级联反应模拟用于计算连锁消除的得分。

游戏机制与问题建模

消消乐的核心算法挑战包括：

1. 匹配检测：找出棋盘上所有三个或以上相同元素的连通区域
2. 消除与下落：消除匹配元素后，上方元素下落填补空缺
3. 级联反应：下落后可能形成新的匹配，需要递归检测
4. 可移动判定：判断当前棋盘是否存在至少一个合法交换

BFS连通检测算法

BFS（广度优先搜索）是检测连通区域的最优选择。我们以每个未访问的格子为起点，向上下左右四个方向搜索相同类型的元素，标记整个连通区域。

import java.util.*;

/**
 * 消消乐 - BFS连通检测与消除算法
 */
public class Match3Solver {

    private static final int ROWS = 8;
    private static final int COLS = 8;
    private static final int[] DR = {-1, 1, 0, 0}; // 上下左右
    private static final int[] DC = {0, 0, -1, 1};

    private int[][] board; // 棋盘，0表示空，1-6表示不同元素类型

    public Match3Solver(int[][] board) {
        this.board = new int[ROWS][COLS];
        for (int i = 0; i < ROWS; i++) {
            System.arraycopy(board[i], 0, this.board[i], 0, COLS);
        }
    }

    /**
     * BFS连通检测：找出所有大小>=3的连通区域
     * 返回所有需要消除的坐标集合
     */
    public List<List<int[]>> findMatches() {
        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 (board[r][c] == 0 || visited[r][c]) continue;

                // BFS搜索连通区域
                List<int[]> group = new ArrayList<>();
                Queue<int[]> queue = new LinkedList<>();
                queue.offer(new int[]{r, c});
                visited[r][c] = true;
                int type = board[r][c];

                while (!queue.isEmpty()) {
                    int[] curr = queue.poll();
                    group.add(curr);

                    // 向四个方向扩展
                    for (int d = 0; d < 4; d++) {
                        int nr = curr[0] + DR[d];
                        int nc = curr[1] + DC[d];

                        if (nr < 0 || nr >= ROWS || nc < 0 || nc >= COLS) continue;
                        if (visited[nr][nc] || board[nr][nc] != type) continue;

                        visited[nr][nc] = true;
                        queue.offer(new int[]{nr, nc});
                    }
                }

                // 只保留大小>=3的连通区域
                if (group.size() >= 3) {
                    allMatches.add(group);
                }
            }
        }

        return allMatches;
    }

    /**
     * 线性扫描版本：更高效地检测横向和纵向的连续三个及以上
     * 时间复杂度 O(ROWS * COLS)，无需BFS的队列开销
     */
    public boolean[][] findMatchesLinear() {
        boolean[][] toRemove = new boolean[ROWS][COLS];

        // 横向扫描
        for (int r = 0; r < ROWS; r++) {
            int count = 1;
            for (int c = 1; c < COLS; c++) {
                if (board[r][c] != 0 && board[r][c] == board[r][c-1]) {
                    count++;
                } else {
                    if (count >= 3) {
                        for (int k = c - count; k < c; k++) {
                            toRemove[r][k] = true;
                        }
                    }
                    count = 1;
                }
            }
            if (count >= 3) {
                for (int k = COLS - count; k < COLS; k++) {
                    toRemove[r][k] = true;
                }
            }
        }

        // 纵向扫描
        for (int c = 0; c < COLS; c++) {
            int count = 1;
            for (int r = 1; r < ROWS; r++) {
                if (board[r][c] != 0 && board[r][c] == board[r-1][c]) {
                    count++;
                } else {
                    if (count >= 3) {
                        for (int k = r - count; k < r; k++) {
                            toRemove[k][c] = true;
                        }
                    }
                    count = 1;
                }
            }
            if (count >= 3) {
                for (int k = ROWS - count; k < ROWS; k++) {
                    toRemove[k][c] = true;
                }
            }
        }

        return toRemove;
    }

    /**
     * 执行消除并让上方元素下落
     * 返回本次消除获得的分数
     */
    public int eliminateAndDrop() {
        boolean[][] toRemove = findMatchesLinear();
        int removed = 0;

        // 统计消除数量
        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                if (toRemove[r][c]) {
                    board[r][c] = 0;
                    removed++;
                }
            }
        }

        // 重力下落：每列从下往上填充
        for (int c = 0; c < COLS; c++) {
            int writeRow = ROWS - 1;
            for (int r = ROWS - 1; r >= 0; r--) {
                if (board[r][c] != 0) {
                    board[writeRow][c] = board[r][c];
                    if (writeRow != r) {
                        board[r][c] = 0;
                    }
                    writeRow--;
                }
            }
            // 顶部空缺用随机新元素填充
            Random rand = new Random();
            for (int r = writeRow; r >= 0; r--) {
                board[r][c] = rand.nextInt(6) + 1;
            }
        }

        // 分数 = 消除数量的平方（鼓励大规模消除）
        return removed * removed;
    }

    /**
     * 级联反应模拟：递归消除直到没有新匹配
     * 返回总分和每次消除的详细信息
     */
    public CascadeResult simulateCascade() {
        int totalScore = 0;
        int cascadeLevel = 0;
        List<Integer> scores = new ArrayList<>();

        while (true) {
            boolean[][] matches = findMatchesLinear();
            int matchCount = 0;
            for (boolean[] row : matches) {
                for (boolean b : row) if (b) matchCount++;
            }

            if (matchCount == 0) break;

            cascadeLevel++;
            int score = eliminateAndDrop();
            // 级联加成：第n次级联分数乘以n
            score *= cascadeLevel;
            totalScore += score;
            scores.add(score);
        }

        return new CascadeResult(totalScore, cascadeLevel, scores);
    }

    static class CascadeResult {
        int totalScore;
        int maxLevel;
        List<Integer> levelScores;

        CascadeResult(int total, int level, List<Integer> scores) {
            this.totalScore = total; this.maxLevel = level; this.levelScores = scores;
        }
    }
}

合法交换检测

游戏需要确保棋盘始终存在至少一个合法交换，否则需要重新生成棋盘。我们使用贪心策略预计算所有可能的交换：

/**
 * 消消乐 - 合法移动检测与AI提示
 */
public class Match3MoveFinder {

    private static final int ROWS = 8;
    private static final int COLS = 8;
    private static final int[] DR = {-1, 1, 0, 0};
    private static final int[] DC = {0, 0, -1, 1};

    /**
     * 检查交换(r1,c1)和(r2,c2)是否能产生匹配
     * 只检查与交换位置相关的区域，避免全棋盘扫描
     */
    public boolean isValidSwap(int[][] board, int r1, int c1, int r2, int c2) {
        // 执行临时交换
        int temp = board[r1][c1];
        board[r1][c1] = board[r2][c2];
        board[r2][c2] = temp;

        boolean valid = checkMatchAt(board, r1, c1) || checkMatchAt(board, r2, c2);

        // 还原交换
        temp = board[r1][c1];
        board[r1][c1] = board[r2][c2];
        board[r2][c2] = temp;

        return valid;
    }

    /**
     * 检查指定位置是否属于某个长度>=3的连续序列
     */
    private boolean checkMatchAt(int[][] board, int r, int c) {
        int type = board[r][c];
        if (type == 0) return false;

        // 检查横向连续
        int left = 0, right = 0;
        for (int k = c - 1; k >= 0 && board[r][k] == type; k--) left++;
        for (int k = c + 1; k < COLS && board[r][k] == type; k++) right++;
        if (left + right + 1 >= 3) return true;

        // 检查纵向连续
        int up = 0, down = 0;
        for (int k = r - 1; k >= 0 && board[k][c] == type; k--) up++;
        for (int k = r + 1; k < ROWS && board[k][c] == type; k++) down++;
        if (up + down + 1 >= 3) return true;

        return false;
    }

    /**
     * 贪心查找最优移动：返回能引发最大级联得分的交换
     * 时间复杂度 O(ROWS * COLS * 4 * cascade_cost)
     */
    public int[] findBestMove(int[][] board) {
        int bestScore = -1;
        int[] bestMove = null;

        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                // 尝试四个方向的交换
                for (int d = 0; d < 4; d++) {
                    int nr = r + DR[d];
                    int nc = c + DC[d];
                    if (nr < 0 || nr >= ROWS || nc < 0 || nc >= COLS) continue;

                    if (!isValidSwap(board, r, c, nr, nc)) continue;

                    // 模拟执行交换并计算级联得分
                    int[][] copy = deepCopy(board);
                    int temp = copy[r][c];
                    copy[r][c] = copy[nr][nc];
                    copy[nr][nc] = temp;

                    Match3Solver solver = new Match3Solver(copy);
                    Match3Solver.CascadeResult result = solver.simulateCascade();

                    if (result.totalScore > bestScore) {
                        bestScore = result.totalScore;
                        bestMove = new int[]{r, c, nr, nc, result.totalScore};
                    }
                }
            }
        }

        return bestMove;
    }

    private int[][] deepCopy(int[][] board) {
        int[][] copy = new int[ROWS][COLS];
        for (int i = 0; i < ROWS; i++) {
            System.arraycopy(board[i], 0, copy[i], 0, COLS);
        }
        return copy;
    }
}

完整可运行项目

import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.util.*;
import java.util.List;

/**
 * 消消乐完整游戏实现
 */
public class Match3Game extends JPanel implements MouseListener, ActionListener {

    private static final int ROWS = 8;
    private static final int COLS = 8;
    private static final int CELL_SIZE = 60;
    private static final int TYPES = 6;

    private int[][] board = new int[ROWS][COLS];
    private int selectedRow = -1, selectedCol = -1;
    private int score = 0;
    private int moves = 0;
    private Timer animTimer;
    private boolean isAnimating = false;
    private Random rand = new Random();

    // 颜色映射
    private Color[] colors = {
        Color.RED, Color.BLUE, Color.GREEN, 
        Color.YELLOW, Color.ORANGE, Color.MAGENTA
    };

    public Match3Game() {
        setPreferredSize(new Dimension(COLS * CELL_SIZE, ROWS * CELL_SIZE + 50));
        setBackground(Color.DARK_GRAY);
        addMouseListener(this);

        // 初始化棋盘，确保没有初始匹配
        do {
            generateBoard();
        } while (hasMatches() || !hasValidMoves());

        animTimer = new Timer(50, this);
    }

    private void generateBoard() {
        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                board[r][c] = rand.nextInt(TYPES) + 1;
            }
        }
    }

    /**
     * 贪心策略：检查是否存在匹配
     */
    private boolean hasMatches() {
        // 横向
        for (int r = 0; r < ROWS; r++) {
            int count = 1;
            for (int c = 1; c < COLS; c++) {
                if (board[r][c] == board[r][c-1]) count++;
                else {
                    if (count >= 3) return true;
                    count = 1;
                }
            }
            if (count >= 3) return true;
        }
        // 纵向
        for (int c = 0; c < COLS; c++) {
            int count = 1;
            for (int r = 1; r < ROWS; r++) {
                if (board[r][c] == board[r-1][c]) count++;
                else {
                    if (count >= 3) return true;
                    count = 1;
                }
            }
            if (count >= 3) return true;
        }
        return false;
    }

    /**
     * 检查是否存在合法移动
     */
    private boolean hasValidMoves() {
        int[][] dirs = {{0,1},{1,0}};
        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                for (int[] d : dirs) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= ROWS || nc >= COLS) continue;
                    if (isValidSwap(r, c, nr, nc)) return true;
                }
            }
        }
        return false;
    }

    private boolean isValidSwap(int r1, int c1, int r2, int c2) {
        int temp = board[r1][c1];
        board[r1][c1] = board[r2][c2];
        board[r2][c2] = temp;
        boolean valid = checkMatchAt(r1, c1) || checkMatchAt(r2, c2);
        board[r2][c2] = board[r1][c1];
        board[r1][c1] = temp;
        return valid;
    }

    private boolean checkMatchAt(int r, int c) {
        int type = board[r][c];
        int left = 0, right = 0, up = 0, down = 0;
        for (int k = c-1; k >= 0 && board[r][k] == type; k--) left++;
        for (int k = c+1; k < COLS && board[r][k] == type; k++) right++;
        for (int k = r-1; k >= 0 && board[k][c] == type; k--) up++;
        for (int k = r+1; k < ROWS && board[k][c] == type; k++) down++;
        return left + right + 1 >= 3 || up + down + 1 >= 3;
    }

    @Override
    public void mousePressed(MouseEvent e) {
        if (isAnimating) return;

        int c = e.getX() / CELL_SIZE;
        int r = e.getY() / CELL_SIZE;
        if (r >= ROWS || c >= COLS) return;

        if (selectedRow == -1) {
            selectedRow = r;
            selectedCol = c;
        } else {
            // 检查是否相邻
            if (Math.abs(r - selectedRow) + Math.abs(c - selectedCol) == 1) {
                if (isValidSwap(selectedRow, selectedCol, r, c)) {
                    // 执行交换
                    int temp = board[selectedRow][selectedCol];
                    board[selectedRow][selectedCol] = board[r][c];
                    board[r][c] = temp;
                    moves++;

                    // 触发级联消除
                    processMatches();
                }
            }
            selectedRow = -1;
            selectedCol = -1;
        }
        repaint();
    }

    /**
     * 处理匹配消除与级联反应
     */
    private void processMatches() {
        isAnimating = true;
        int cascade = 0;

        while (true) {
            boolean[][] toRemove = findMatches();
            int count = 0;
            for (boolean[] row : toRemove) {
                for (boolean b : row) if (b) count++;
            }
            if (count == 0) break;

            cascade++;

            // 消除
            for (int r = 0; r < ROWS; r++) {
                for (int c = 0; c < COLS; c++) {
                    if (toRemove[r][c]) board[r][c] = 0;
                }
            }

            // 下落与填充
            for (int c = 0; c < COLS; c++) {
                int write = ROWS - 1;
                for (int r = ROWS - 1; r >= 0; r--) {
                    if (board[r][c] != 0) {
                        board[write--][c] = board[r][c];
                    }
                }
                for (int r = write; r >= 0; r--) {
                    board[r][c] = rand.nextInt(TYPES) + 1;
                }
            }

            score += count * count * cascade;
            repaint();

            // 模拟动画延迟
            try { Thread.sleep(200); } catch (InterruptedException e) {}
        }

        isAnimating = false;

        if (!hasValidMoves()) {
            JOptionPane.showMessageDialog(this, "Game Over! Score: " + score);
        }
    }

    private boolean[][] findMatches() {
        boolean[][] remove = new boolean[ROWS][COLS];
        // 横向
        for (int r = 0; r < ROWS; r++) {
            int count = 1;
            for (int c = 1; c < COLS; c++) {
                if (board[r][c] != 0 && board[r][c] == board[r][c-1]) count++;
                else {
                    if (count >= 3) {
                        for (int k = c - count; k < c; k++) remove[r][k] = true;
                    }
                    count = 1;
                }
            }
            if (count >= 3) {
                for (int k = COLS - count; k < COLS; k++) remove[r][k] = true;
            }
        }
        // 纵向
        for (int c = 0; c < COLS; c++) {
            int count = 1;
            for (int r = 1; r < ROWS; r++) {
                if (board[r][c] != 0 && board[r][c] == board[r-1][c]) count++;
                else {
                    if (count >= 3) {
                        for (int k = r - count; k < r; k++) remove[k][c] = true;
                    }
                    count = 1;
                }
            }
            if (count >= 3) {
                for (int k = ROWS - count; k < ROWS; k++) remove[k][c] = true;
            }
        }
        return remove;
    }

    @Override
    protected void paintComponent(Graphics g) {
        super.paintComponent(g);

        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                int x = c * CELL_SIZE;
                int y = r * CELL_SIZE;

                if (board[r][c] == 0) {
                    g.setColor(Color.DARK_GRAY);
                    g.fillRect(x, y, CELL_SIZE, CELL_SIZE);
                } else {
                    g.setColor(colors[board[r][c] - 1]);
                    g.fillRoundRect(x + 2, y + 2, CELL_SIZE - 4, CELL_SIZE - 4, 10, 10);
                }

                g.setColor(Color.GRAY);
                g.drawRect(x, y, CELL_SIZE, CELL_SIZE);
            }
        }

        // 高亮选中
        if (selectedRow != -1) {
            g.setColor(Color.WHITE);
            g.drawRect(selectedCol * CELL_SIZE + 1, selectedRow * CELL_SIZE + 1, 
                      CELL_SIZE - 2, CELL_SIZE - 2);
        }

        // UI信息
        g.setColor(Color.WHITE);
        g.setFont(new Font("Arial", Font.BOLD, 16));
        g.drawString("Score: " + score + "  Moves: " + moves, 10, ROWS * CELL_SIZE + 30);
    }

    @Override public void actionPerformed(ActionEvent e) { repaint(); }
    @Override public void mouseClicked(MouseEvent e) {}
    @Override public void mouseReleased(MouseEvent e) {}
    @Override public void mouseEntered(MouseEvent e) {}
    @Override public void mouseExited(MouseEvent e) {}

    public static void main(String[] args) {
        SwingUtilities.invokeLater(() -> {
            JFrame frame = new JFrame("消消乐 - BFS连通检测");
            Match3Game game = new Match3Game();
            frame.add(game);
            frame.pack();
            frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
            frame.setVisible(true);
        });
    }
}

算法复杂度分析

BFS适合检测不规则连通区域（如L形、T形匹配），线性扫描适合标准的三消规则（仅横纵直线）。实际游戏中可根据规则灵活选择。

扩展方向

1. 特殊元素生成：消除4个或5个时生成炸弹、彩虹等特殊元素，扩展匹配规则
2. 关卡目标系统：引入收集指定元素、消除障碍等多样化目标
3. A*搜索最优解：对于步数限制的关卡，用A*搜索最少步数完成方案