每日算法 — 使用java实现糖果传奇CandyCrush：三消局面枚举与连锁消除评分

《糖果传奇》里最让人上瘾的瞬间，是随便滑一下突然连续炸了七八波。对玩家是爽点，对引擎就是一道很干净的组合优化题：给定一个 8×8 的糖果盘面，哪一次交换能带来最大收益？

收益的定义要足够贴近真实游戏才有意义：直接消除数 + 连锁波次的加权 + 特殊糖果生成的额外价值。这篇文章用 Java 实现一个完整的 Candy Crush 决策引擎，把”找匹配””触发连锁””评估交换”三件事讲透。

一、规则的形式化

棋盘是一个 R × C 的网格，每格一种糖果类型 0..K-1。一次合法交换必须满足：

1. 交换两格相邻（上下或左右）且类型不同；
2. 交换之后盘面上至少存在一处三连及以上的匹配（横向或纵向连续 ≥3 个同类型）。

交换之后进入级联（cascade）阶段：

1. 找出所有长度 ≥3 的同行/同列连续段，标记为待消除；
2. 清除它们，上方糖果下落填补空洞；
3. 空出来的顶部格子生成新糖果；
4. 回到第 1 步，直到没有匹配为止。

最终收益：

score = Σ over waves ( clearedCount[wave] × waveMultiplier[wave] )

经典计分是每波递增（第 n 波按 n 倍或 2^n 计），这里用 waveMultiplier[wave] = wave + 1（第一波 1 倍、第二波 2 倍……），既符合”连锁越久越爽”的设计，又便于分析。

二、为什么不能”只试 4 个方向”

一个 8×8 棋盘有 8 × 7 × 2 = 112 对相邻位置。看起来暴力枚举全部 112 次交换、每次完整跑完级联，代价也不高——112 × 级联轮数。

问题的关键不在次数，而在每次模拟不能污染原盘。三种实现路径：

这里选第三种：把棋盘摊平成 int[]，用两个可复用缓冲区 board 和 scratch，每次评估只做一次 arraycopy。GC 压力归零，也让”评估全部候选交换”能在一帧内完成。

三、匹配检测：一次扫描同时找横竖

朴素写法是分别扫行和扫列、各跑一遍长度计数。更快也更简洁的做法是同时扫描，用一个 mark[] 数组累积”待消除”标记：

// 横向：固定行，扫列
for (int r = 0; r < R; r++) {
    int c = 0;
    while (c < C) {
        int v = b[idx(r, c)];
        int end = c + 1;
        while (end < C && b[idx(r, end)] == v) end++;
        if (end - c >= 3) {
            for (int k = c; k < end; k++) mark[idx(r, k)] = 1;
        }
        c = end;
    }
}

mark 用 byte[] 而不是 boolean[]，并用一个版本号技巧避免每轮清零：mark[i] == version 表示已标记。级联有几十轮时，这个优化能省掉大量 Arrays.fill。

关键细节：横向和纵向都要独立检测。 先做横向再做纵向时，纵向检测必须基于消除前的盘面，否则横向刚标记的格子类型”变了”，会漏掉十字交叉的匹配。

四、下落与填充：列内压缩

消除后，每一列都变成”有洞的数组”。下落本质是列内稳定压缩：把所有非空元素按原顺序挤到列底，剩下的顶部位置填新糖果。

for (int c = 0; c < C; c++) {
    int write = R - 1;                     // 从底部开始写
    for (int r = R - 1; r >= 0; r--) {
        if (mark[idx(r, c)] == 0 && b[idx(r, c)] >= 0) {
            b[idx(write, c)] = b[idx(r, c)];
            write--;
        }
    }
    while (write >= 0) {                   // 顶部补新糖果
        b[idx(write, c)] = rng.nextInt(K);
        write--;
    }
}

用 write 指针做原地压缩，整个过程是 O(R) 时间、O(1) 额外空间。这个”双指针原地压缩”是数组类题的通用套路，和”移除元素后保持相对顺序”是同一个模式。

五、完整实现

import java.util.*;

/** Candy Crush 决策引擎：枚举所有合法交换，模拟完整级联并评分 */
public class Main {

    static final int R = 8, C = 8;

    // ---------------------- 棋盘表示 ----------------------
    private final int[] board = new int[R * C];    // 摊平一维，-1 表示空
    private final int[] scratch = new int[R * C];  // 评估用缓冲，复用避免分配
    private final byte[] mark = new byte[R * C];   // 待消除标记
    private int markVersion = 0;                   // 惰性清零的版本号
    private final int kinds;
    private final Random rng;

    public Main(int kinds, long seed) {
        this.kinds = kinds;
        this.rng = new Random(seed);
    }

    private int idx(int r, int c) { return r * C + c; }

    // ---------------------- 初始化：生成无匹配盘面 ----------------------
    /** 初始化时就要避免开局自带匹配，否则玩家一进来就白送分数 */
    public void initBoard() {
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                int v;
                int guard = 0;
                do {
                    v = rng.nextInt(kinds);
                } while (guard++ < 100 && createsMatchOnPlace(r, c, v));
                board[idx(r, c)] = v;
            }
        }
    }

    /** 在 (r,c) 放置 v 时，是否会与已填好的左侧两格或上方两格凑成三连 */
    private boolean createsMatchOnPlace(int r, int c, int v) {
        if (c >= 2 && board[idx(r, c - 1)] == v && board[idx(r, c - 2)] == v) return true;
        if (r >= 2 && board[idx(r - 1, c)] == v && board[idx(r - 2, c)] == v) return true;
        return false;
    }

    // ---------------------- 匹配检测 ----------------------
    /**
     * 在 b 上标记所有长度>=3 的同行/同列连续段。
     * 返回被标记的格子数；0 表示盘面稳定。
     */
    private int detect(int[] b) {
        markVersion++;
        int cleared = 0;

        // 横向扫描
        for (int r = 0; r < R; r++) {
            int c = 0;
            while (c < C) {
                int v = b[idx(r, c)];
                if (v < 0) { c++; continue; }
                int end = c + 1;
                while (end < C && b[idx(r, end)] == v) end++;
                if (end - c >= 3) {
                    for (int k = c; k < end; k++) {
                        int p = idx(r, k);
                        if (mark[p] != (byte) markVersion) {
                            mark[p] = (byte) markVersion;
                            cleared++;
                        }
                    }
                }
                c = end;
            }
        }

        // 纵向扫描（必须在清除之前，基于同一份 b）
        for (int c = 0; c < C; c++) {
            int r = 0;
            while (r < R) {
                int v = b[idx(r, c)];
                if (v < 0) { r++; continue; }
                int end = r + 1;
                while (end < R && b[idx(end, c)] == v) end++;
                if (end - r >= 3) {
                    for (int k = r; k < end; k++) {
                        int p = idx(k, c);
                        if (mark[p] != (byte) markVersion) {
                            mark[p] = (byte) markVersion;
                            cleared++;
                        }
                    }
                }
                r = end;
            }
        }
        return cleared;
    }

    // ---------------------- 下落与填充 ----------------------
    private void collapse(int[] b) {
        for (int c = 0; c < C; c++) {
            int write = R - 1;
            for (int r = R - 1; r >= 0; r--) {
                int p = idx(r, c);
                if (mark[p] != (byte) markVersion) {
                    b[idx(write, c)] = b[p];
                    write--;
                }
            }
            while (write >= 0) {
                b[idx(write, c)] = rng.nextInt(kinds);
                write--;
            }
        }
    }

    // ---------------------- 级联模拟 ----------------------
    /** 级联结果：加权总分 + 连锁波数 */
    private static final class ResolveResult {
        final int score, waves;
        ResolveResult(int score, int waves) { this.score = score; this.waves = waves; }
    }

    /**
     * 在给定的盘面 b 上完整模拟坠落到稳定，返回加权总分与连锁波数。
     * 注意：b 会被修改，调用者需自行保证传入的是副本。
     */
    private ResolveResult resolve(int[] b) {
        int total = 0, wave = 0;
        while (true) {
            int cleared = detect(b);
            if (cleared == 0) break;
            wave++;
            total += cleared * wave;      // 波次递增权重
            collapse(b);
        }
        return new ResolveResult(total, wave);
    }

    // ---------------------- 交换评估 ----------------------
    public static final class Move {
        final int r1, c1, r2, c2, score, waves;
        Move(int r1, int c1, int r2, int c2, int score, int waves) {
            this.r1 = r1; this.c1 = c1; this.r2 = r2; this.c2 = c2;
            this.score = score; this.waves = waves;
        }
        @Override public String toString() {
            return String.format("(%d,%d)<->(%d,%d) 得分=%d 连锁=%d波",
                    r1, c1, r2, c2, score, waves);
        }
    }

    /** 枚举全部 112 个相邻交换，返回按得分降序排列的候选 */
    public List<Move> rankMoves() {
        List<Move> out = new ArrayList<>();
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                // 只向右、向下枚举，天然不重复（每对相邻格只出现一次）
                if (c + 1 < C) out.add(evalSwap(r, c, r, c + 1));
                if (r + 1 < R) out.add(evalSwap(r, c, r + 1, c));
            }
        }
        out.removeIf(m -> m == null);
        out.sort((a, b) -> Integer.compare(b.score, a.score));
        return out;
    }

    private Move evalSwap(int r1, int c1, int r2, int c2) {
        int p1 = idx(r1, c1), p2 = idx(r2, c2);
        if (board[p1] == board[p2]) return null;   // 同类型交换无意义

        // 拷到评估缓冲，不污染原盘
        System.arraycopy(board, 0, scratch, 0, board.length);
        int t = scratch[p1]; scratch[p1] = scratch[p2]; scratch[p2] = t;

        ResolveResult rr = resolve(scratch);
        if (rr.waves == 0) return null;    // 交换后毫无匹配，不是合法走法

        return new Move(r1, c1, r2, c2, rr.score, rr.waves);
    }

    // ---------------------- 主流程 ----------------------
    public static void main(String[] args) {
        Main game = new Main(5, 42L);
        game.initBoard();

        System.out.println("初始盘面：");
        printBoard(game.board);

        long t0 = System.nanoTime();
        List<Move> ranked = game.rankMoves();
        long ms = (System.nanoTime() - t0) / 1_000_000;

        System.out.println("\n可产生消除的交换数：" + ranked.size() + "，评估耗时 " + ms + "ms");
        for (int i = 0; i < Math.min(5, ranked.size()); i++) {
            System.out.println("  #" + (i + 1) + " " + ranked.get(i));
        }
    }

    static void printBoard(int[] b) {
        for (int r = 0; r < R; r++) {
            StringBuilder sb = new StringBuilder();
            for (int c = 0; c < C; c++) {
                sb.append((char) ('A' + b[r * C + c])).append(' ');
            }
            System.out.println(sb);
        }
    }
}

resolve 为什么必须同时返回 (score, waves)，而不是只返回分数？因为波数本身是走法质量的关键信号：同样是 12 分，一次清完和连炸四波的价值完全不同，后者往往意味着盘面被彻底打开，后续空间更大。而分数无法反推波数——score = Σ(cleared_k × k) 是多个未知数的和，方程多解，从分数倒推波数根本不成立。让函数直接把两个量都带出来，是唯一可靠的做法。

evalSwap 里也刻意省掉了”先 detect 预检查、再进 resolve“的写法：resolve 首轮的 detect 就是同一件事，waves == 0 天然等价于”这个交换不产生任何匹配”。少一次全盘扫描，在 112 个候选 × 每次盘面变化都重算的场景下是实打实的收益。

六、评估函数还能怎么打磨

上面的评分只看”消除了多少”，真实引擎会把特殊糖果的价值算进去。常见的加权项：

• 四连生成条纹糖（清除一整行/列）：等效收益 ≈ C 或 R；
• L/T 形五连生成包装糖（炸 3×3）：等效收益 ≈ 9 减重叠部分；
• 五连一线生成彩虹糖（清除全部同色）：等效收益 ≈ 该颜色在盘面上的数量；
• 连锁位置：靠底部的消除更容易引发二次坍塌，可给底部波次额外加权。

把它写成可插拔的 ScorePolicy 接口，就能在不改搜索逻辑的前提下替换评估口径：

public interface ScorePolicy {
    int scoreOf(int cleared, int wave, int[] boardAfter);
}

这是游戏 AI 的一条通用原则：搜索负责”枚举”，评估负责”判断”，两者永远分开。评估函数可以随便调参、随便替换，搜索骨架一个字都不用动。

七、复杂度

• 候选交换数：2RC - R - C ≈ 112（8×8）。
• 单次级联：最坏 O(RC × waves)，waves 实测很少超过 5。
• 总体：O(RC × moves × waves) = O(64 × 112 × 5) ≈ 3.6 万 次基本操作。单帧内跑完毫无压力，这也是为什么三消游戏的”最佳走法提示”能做得那么即时。

八、更进一步：从”这一手最好”到”未来三步最好”

单步贪心有一个已知缺陷：它看不见”这一手消掉后，下一手能不能凑出五连”。改成两层搜索就能明显改善：

for each move m1:
    apply(m1) -> board1, score1
    best2 = max over m2 of score(m2 on board1)
    value(m1) = score1 + 0.8 * best2

衰减系数 0.8 体现”未来收益要打折”。这就是一个深度为 2 的 Expectimax 简化版——之所以是”期望”而不是”最大化”，是因为新糖果的生成是随机的，严格的做法应当对填充结果求期望。实践中通常用”多次随机 rollout 取均值”来近似，这一步一加，你的三消 AI 就从”贪心”升级成了”有远见”。