每日算法 — 使用java实现宝石迷阵:交换匹配检测与死锁重排算法

宝石迷阵(Bejeweled)是一款经典的三消益智游戏,玩家通过交换相邻宝石的位置,使三个或更多相同宝石在横向或纵向连成一线即可消除得分。本文将用Java实现完整的核心游戏引擎,重点讲解交换模拟后的匹配检测、级联消除的递归处理、死锁检测与自动重排机制,以及基于贪心策略的AI选步决策算法。

一、游戏规则与核心数据结构

宝石迷阵采用8×8的方形棋盘,每个格子放置一种类型的宝石。玩家每次可以选择两个相邻(上下左右)的宝石进行交换,交换后如果形成三个或以上相同宝石的连线,则这些宝石被消除,上方的宝石下落填补空位,顶部生成新宝石。如果交换后没有形成任何匹配,则交换无效并自动还原。

1.1 棋盘表示

使用二维整数数组表示棋盘,每个数值代表一种宝石类型。为了便于调试和可视化,我们用字符表示不同类型的宝石。

/**
 * 宝石迷阵核心引擎
 * 棋盘大小为8×8,支持7种不同颜色的宝石
 */
public class BejeweledEngine {
    // 棋盘维度
    private static final int ROWS = 8;
    private static final int COLS = 8;
    // 宝石类型数量(0~6分别代表7种不同宝石)
    private static final int GEM_TYPES = 7;

    // 方向数组:上、下、左、右
    private static final int[] DR = {-1, 1, 0, 0};
    private static final int[] DC = {0, 0, -1, 1};

    // 棋盘状态
    private int[][] board;
    private Random random;

    public BejeweledEngine() {
        this.random = new Random();
        this.board = new int[ROWS][COLS];
        initializeBoard();
    }

    /**
     * 初始化棋盘,确保没有任何初始匹配
     * 采用随机填充+冲突检测的方式,保证开局即可玩
     */
    private void initializeBoard() {
        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                int gem;
                do {
                    gem = random.nextInt(GEM_TYPES);
                } while (wouldCreateMatch(r, c, gem));
                board[r][c] = gem;
            }
        }
    }

    /**
     * 检查在指定位置放置某类型宝石是否会形成匹配
     * 用于初始化时避免生成已有三连的局面
     */
    private boolean wouldCreateMatch(int row, int col, int gem) {
        // 检查横向左侧两个是否相同
        if (col >= 2 && board[row][col-1] == gem && board[row][col-2] == gem) {
            return true;
        }
        // 检查纵向上方两个是否相同
        if (row >= 2 && board[row-1][col] == gem && board[row-2][col] == gem) {
            return true;
        }
        return false;
    }
}

1.2 移动操作的数据结构

为了记录一次交换操作及其效果,我们定义Move类来封装坐标信息与预期得分。

/**
 * 表示一次宝石交换操作
 */
public class Move {
    public final int r1, c1; // 第一个宝石坐标
    public final int r2, c2; // 第二个宝石坐标
    public int score;        // 该移动的预估得分

    public Move(int r1, int c1, int r2, int c2) {
        this.r1 = r1; this.c1 = c1;
        this.r2 = r2; this.c2 = c2;
        this.score = 0;
    }

    @Override
    public String toString() {
        return String.format("Move(%d,%d)->(%d,%d) score=%d", r1, c1, r2, c2, score);
    }
}

二、交换模拟与匹配检测算法

匹配检测是宝石迷阵的核心算法。与消消乐的Flood Fill不同,宝石迷阵采用行列扫描法:对每一行从左到右扫描连续相同宝石的长度,对每一列从上到下扫描连续相同宝石的长度,长度大于等于3即构成匹配。

2.1 行列扫描匹配检测

/**
 * 检测棋盘上所有匹配区域
 * 采用行列扫描法,时间复杂度O(ROWS×COLS)
 * @return 匹配区域的集合,每个匹配用起始坐标、方向和长度表示
 */
public List<Match> findMatches() {
    List<Match> matches = new ArrayList<>();
    boolean[][] marked = new boolean[ROWS][COLS]; // 标记已匹配的格子

    // 横向扫描:逐行检查连续相同宝石
    for (int r = 0; r < ROWS; r++) {
        int c = 0;
        while (c < COLS) {
            int gem = board[r][c];
            int count = 1;
            int start = c;
            // 向右扩展,统计连续相同宝石数量
            while (c + 1 < COLS && board[r][c + 1] == gem) {
                count++;
                c++;
            }
            // 如果连续3个或以上,记录匹配
            if (count >= 3) {
                for (int i = 0; i < count; i++) {
                    marked[r][start + i] = true;
                }
                matches.add(new Match(r, start, 0, count, gem)); // 方向0表示横向
            }
            c++;
        }
    }

    // 纵向扫描:逐列检查连续相同宝石
    for (int c = 0; c < COLS; c++) {
        int r = 0;
        while (r < ROWS) {
            int gem = board[r][c];
            int count = 1;
            int start = r;
            while (r + 1 < ROWS && board[r + 1][c] == gem) {
                count++;
                r++;
            }
            if (count >= 3) {
                for (int i = 0; i < count; i++) {
                    marked[start + i][c] = true;
                }
                matches.add(new Match(start, c, 1, count, gem)); // 方向1表示纵向
            }
            r++;
        }
    }

    return matches;
}

/**
 * 匹配区域的数据结构
 */
public static class Match {
    public final int row, col;    // 起始坐标
    public final int dir;         // 方向:0横向,1纵向
    public final int length;      // 连续长度
    public final int gemType;     // 宝石类型

    public Match(int row, int col, int dir, int length, int gemType) {
        this.row = row; this.col = col;
        this.dir = dir; this.length = length;
        this.gemType = gemType;
    }
}

2.2 执行交换并验证合法性

玩家选择两个相邻宝石交换后,需要先检测是否产生匹配。如果没有匹配,交换无效。

/**
 * 尝试交换两个相邻宝石
 * @return 如果交换后形成匹配则返回true,否则撤销交换返回false
 */
public boolean trySwap(int r1, int c1, int r2, int c2) {
    // 校验坐标合法性
    if (!isValid(r1, c1) || !isValid(r2, c2)) {
        return false;
    }
    // 校验是否相邻
    if (Math.abs(r1 - r2) + Math.abs(c1 - c2) != 1) {
        return false;
    }

    // 执行交换
    swapGems(r1, c1, r2, c2);

    // 检测是否有匹配
    List<Match> matches = findMatches();
    if (matches.isEmpty()) {
        // 没有匹配,撤销交换
        swapGems(r1, c1, r2, c2);
        return false;
    }

    return true;
}

private void swapGems(int r1, int c1, int r2, int c2) {
    int temp = board[r1][c1];
    board[r1][c1] = board[r2][c2];
    board[r2][c2] = temp;
}

private boolean isValid(int r, int c) {
    return r >= 0 && r < ROWS && c >= 0 && c < COLS;
}

三、级联消除与宝石下落

消除匹配宝石后,上方的宝石需要下落填补空位,顶部生成新的随机宝石。新下落的宝石可能再次形成匹配,引发级联消除(Cascade)。我们需要递归处理直到没有新的匹配为止。

3.1 单次消除与下落

/**
 * 消除所有匹配区域,宝石下落,顶部生成新宝石
 * @return 本次消除的宝石总数(用于计算得分)
 */
public int removeMatchesAndCollapse() {
    List<Match> matches = findMatches();
    if (matches.isEmpty()) {
        return 0;
    }

    // 标记所有需要消除的位置
    boolean[][] toRemove = new boolean[ROWS][COLS];
    int removeCount = 0;
    for (Match m : matches) {
        for (int i = 0; i < m.length; i++) {
            int rr = m.dir == 0 ? m.row : m.row + i;
            int cc = m.dir == 0 ? m.col + i : m.col;
            if (!toRemove[rr][cc]) {
                toRemove[rr][cc] = true;
                removeCount++;
            }
        }
    }

    // 按列处理下落:从每列底部向上扫描
    for (int c = 0; c < COLS; c++) {
        int writeRow = ROWS - 1; // 写入位置从底部开始
        // 从底部向上,将不需要消除的宝石下移
        for (int r = ROWS - 1; r >= 0; r--) {
            if (!toRemove[r][c]) {
                board[writeRow][c] = board[r][c];
                writeRow--;
            }
        }
        // 顶部空位填充新宝石
        while (writeRow >= 0) {
            board[writeRow][c] = random.nextInt(GEM_TYPES);
            writeRow--;
        }
    }

    return removeCount;
}

3.2 级联消除的递归处理

/**
 * 执行完整的回合消除:包括初次消除和所有级联消除
 * @return 总消除宝石数(级联次数越多得分越高)
 */
public int executeRound() {
    int totalRemoved = 0;
    int cascadeLevel = 0;

    while (true) {
        int removed = removeMatchesAndCollapse();
        if (removed == 0) break;

        // 级联奖励:第n层级联的宝石得分权重为n
        totalRemoved += removed * (1 + cascadeLevel);
        cascadeLevel++;

        // 可选:打印级联信息用于调试
        // System.out.println("Cascade level " + cascadeLevel + ": removed " + removed);
    }

    return totalRemoved;
}

级联消除的算法复杂度为O(k × ROWS × COLS),其中k是级联层数。由于棋盘只有8×8,且级联层数通常不超过5层,实际运行效率非常高。

四、死锁检测与自动重排

当棋盘上不存在任何可以形成匹配的相邻交换时,游戏进入死锁(Deadlock)状态。此时需要自动重排棋盘,或者提示玩家当前无可行移动。

4.1 死锁检测算法

死锁检测的核心思路是:遍历棋盘上所有相邻的宝石对,模拟交换后调用findMatches()检查是否产生匹配。如果在所有可能的交换中都没有匹配,则判定为死锁。

/**
 * 检测当前棋盘是否存在死锁
 * 遍历所有相邻宝石对,模拟交换后检查是否产生匹配
 * 时间复杂度:O(ROWS×COLS)次交换模拟,每次模拟O(ROWS×COLS)检测
 * 整体为O((ROWS×COLS)²),对于8×8棋盘约为O(4096),完全可接受
 */
public boolean hasDeadlock() {
    for (int r = 0; r < ROWS; r++) {
        for (int c = 0; c < COLS; c++) {
            // 尝试与右侧邻居交换
            if (c + 1 < COLS) {
                swapGems(r, c, r, c + 1);
                boolean hasMatch = !findMatches().isEmpty();
                swapGems(r, c, r, c + 1); // 还原
                if (hasMatch) return false; // 存在合法移动,非死锁
            }
            // 尝试与下方邻居交换
            if (r + 1 < ROWS) {
                swapGems(r, c, r + 1, c);
                boolean hasMatch = !findMatches().isEmpty();
                swapGems(r, c, r + 1, c); // 还原
                if (hasMatch) return false;
            }
        }
    }
    return true; // 所有交换都无法形成匹配,死锁
}

4.2 自动重排

检测到死锁后,需要重新排列棋盘上的宝石,同时确保重排后不立即出现匹配(否则玩家还没操作就自动消除了)。

/**
 * 当检测到死锁时,重新排列棋盘
 * 采用随机打乱+合法性验证的策略
 */
public void shuffleBoard() {
    // 收集所有宝石
    List<Integer> gems = new ArrayList<>();
    for (int r = 0; r < ROWS; r++) {
        for (int c = 0; c < COLS; c++) {
            gems.add(board[r][c]);
        }
    }

    // 随机打乱并重新放置,同时确保不产生匹配
    boolean valid = false;
    int attempts = 0;
    while (!valid && attempts < 1000) {
        Collections.shuffle(gems, random);
        int idx = 0;
        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                board[r][c] = gems.get(idx++);
            }
        }
        // 确保重排后没有匹配且不是死锁
        if (findMatches().isEmpty() && !hasDeadlock()) {
            valid = true;
        }
        attempts++;
    }

    // 如果多次随机都失败,采用构造法重排
    if (!valid) {
        regenerateBoard();
    }
}

/**
 * 构造法重新生成棋盘:逐格随机填充并检测冲突
 */
private void regenerateBoard() {
    for (int r = 0; r < ROWS; r++) {
        for (int c = 0; c < COLS; c++) {
            int gem;
            int attempts = 0;
            do {
                gem = random.nextInt(GEM_TYPES);
                attempts++;
            } while (attempts < 50 && wouldCreateMatch(r, c, gem));
            board[r][c] = gem;
        }
    }
}

五、贪心AI策略:寻找最优移动

为宝石迷阵设计一个AI玩家,核心问题是:在所有合法移动中,选择哪一步能获得最高分数?由于级联消除的存在,单次交换的潜在收益不仅取决于直接消除的宝石数,还取决于可能触发的级联层数。

5.1 基于模拟的贪心选步

/**
 * 使用贪心策略寻找当前最佳移动
 * 对每个合法移动进行模拟,计算预期得分,选择得分最高的移动
 * @return 最佳移动,如果无合法移动返回null
 */
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) {
                int score = simulateMove(r, c, r, c + 1);
                if (score > bestScore) {
                    bestScore = score;
                    bestMove = new Move(r, c, r, c + 1);
                    bestMove.score = score;
                }
            }
            // 尝试与下方交换
            if (r + 1 < ROWS) {
                int score = simulateMove(r, c, r + 1, c);
                if (score > bestScore) {
                    bestScore = score;
                    bestMove = new Move(r, c, r + 1, c);
                    bestMove.score = score;
                }
            }
        }
    }

    return bestMove;
}

5.2 移动模拟与评估

/**
 * 模拟一次移动并评估其得分
 * 方法:复制当前棋盘 -> 执行交换 -> 执行完整消除 -> 计算得分
 * @return 该移动的预期总得分
 */
private int simulateMove(int r1, int c1, int r2, int c2) {
    // 保存当前棋盘状态
    int[][] saved = saveBoard();

    // 执行交换
    swapGems(r1, c1, r2, c2);

    // 检查是否有匹配
    if (findMatches().isEmpty()) {
        restoreBoard(saved);
        return -1; // 非法移动
    }

    // 执行完整消除并获取得分
    int score = executeRound();

    // 恢复棋盘
    restoreBoard(saved);

    return score;
}

private int[][] saveBoard() {
    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[][] saved) {
    for (int r = 0; r < ROWS; r++) {
        System.arraycopy(saved[r], 0, board[r], 0, COLS);
    }
}

5.3 AI运行循环

/**
 * AI自动运行一局游戏,执行指定步数
 */
public void runAI(int maxMoves) {
    int totalScore = 0;

    for (int moveCount = 0; moveCount < maxMoves; moveCount++) {
        // 检测死锁
        if (hasDeadlock()) {
            System.out.println("Deadlock detected! Shuffling board...");
            shuffleBoard();
        }

        // 寻找最佳移动
        Move move = findBestMove();
        if (move == null) {
            System.out.println("No valid moves available!");
            break;
        }

        // 执行移动
        trySwap(move.r1, move.c1, move.r2, move.c2);
        int score = executeRound();
        totalScore += score;

        System.out.println("Move " + (moveCount + 1) + ": " + move + 
                          ", Score=" + score + ", Total=" + totalScore);
    }

    System.out.println("AI finished. Total score: " + totalScore);
}

六、完整可运行代码

以下是将所有模块整合后的完整Java代码,包含主函数可直接运行。

import java.util.*;

/**
 * 宝石迷阵核心引擎与AI演示
 * 包含:棋盘初始化、交换检测、级联消除、死锁检测、贪心AI
 */
public class BejeweledEngine {
    private static final int ROWS = 8;
    private static final int COLS = 8;
    private static final int GEM_TYPES = 7;

    private int[][] board;
    private Random random;

    public BejeweledEngine() {
        this.random = new Random();
        this.board = new int[ROWS][COLS];
        initializeBoard();
    }

    // ==================== 初始化 ====================

    private void initializeBoard() {
        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                int gem;
                do {
                    gem = random.nextInt(GEM_TYPES);
                } while (wouldCreateMatch(r, c, gem));
                board[r][c] = gem;
            }
        }
    }

    private boolean wouldCreateMatch(int row, int col, int gem) {
        if (col >= 2 && board[row][col-1] == gem && board[row][col-2] == gem) return true;
        if (row >= 2 && board[row-1][col] == gem && board[row-2][col] == gem) return true;
        return false;
    }

    // ==================== 核心操作 ====================

    private boolean isValid(int r, int c) {
        return r >= 0 && r < ROWS && c >= 0 && c < COLS;
    }

    private void swapGems(int r1, int c1, int r2, int c2) {
        int temp = board[r1][c1];
        board[r1][c1] = board[r2][c2];
        board[r2][c2] = temp;
    }

    public boolean trySwap(int r1, int c1, int r2, int c2) {
        if (!isValid(r1, c1) || !isValid(r2, c2)) return false;
        if (Math.abs(r1 - r2) + Math.abs(c1 - c2) != 1) return false;

        swapGems(r1, c1, r2, c2);
        boolean hasMatch = !findMatches().isEmpty();
        if (!hasMatch) {
            swapGems(r1, c1, r2, c2); // 还原
        }
        return hasMatch;
    }

    // ==================== 匹配检测 ====================

    public List<Match> findMatches() {
        List<Match> matches = new ArrayList<>();

        // 横向扫描
        for (int r = 0; r < ROWS; r++) {
            int c = 0;
            while (c < COLS) {
                int gem = board[r][c];
                int count = 1, start = c;
                while (c + 1 < COLS && board[r][c + 1] == gem) {
                    count++; c++;
                }
                if (count >= 3) {
                    matches.add(new Match(r, start, 0, count, gem));
                }
                c++;
            }
        }

        // 纵向扫描
        for (int c = 0; c < COLS; c++) {
            int r = 0;
            while (r < ROWS) {
                int gem = board[r][c];
                int count = 1, start = r;
                while (r + 1 < ROWS && board[r + 1][c] == gem) {
                    count++; r++;
                }
                if (count >= 3) {
                    matches.add(new Match(start, c, 1, count, gem));
                }
                r++;
            }
        }

        return matches;
    }

    // ==================== 消除与级联 ====================

    public int removeMatchesAndCollapse() {
        List<Match> matches = findMatches();
        if (matches.isEmpty()) return 0;

        boolean[][] toRemove = new boolean[ROWS][COLS];
        int removeCount = 0;
        for (Match m : matches) {
            for (int i = 0; i < m.length; i++) {
                int rr = m.dir == 0 ? m.row : m.row + i;
                int cc = m.dir == 0 ? m.col + i : m.col;
                if (!toRemove[rr][cc]) {
                    toRemove[rr][cc] = true;
                    removeCount++;
                }
            }
        }

        // 按列下落
        for (int c = 0; c < COLS; c++) {
            int writeRow = ROWS - 1;
            for (int r = ROWS - 1; r >= 0; r--) {
                if (!toRemove[r][c]) {
                    board[writeRow--][c] = board[r][c];
                }
            }
            while (writeRow >= 0) {
                board[writeRow--][c] = random.nextInt(GEM_TYPES);
            }
        }

        return removeCount;
    }

    public int executeRound() {
        int total = 0, level = 0;
        while (true) {
            int removed = removeMatchesAndCollapse();
            if (removed == 0) break;
            total += removed * (1 + level++);
        }
        return total;
    }

    // ==================== 死锁检测与重排 ====================

    public boolean hasDeadlock() {
        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                if (c + 1 < COLS) {
                    swapGems(r, c, r, c + 1);
                    boolean ok = !findMatches().isEmpty();
                    swapGems(r, c, r, c + 1);
                    if (ok) return false;
                }
                if (r + 1 < ROWS) {
                    swapGems(r, c, r + 1, c);
                    boolean ok = !findMatches().isEmpty();
                    swapGems(r, c, r + 1, c);
                    if (ok) return false;
                }
            }
        }
        return true;
    }

    public void shuffleBoard() {
        List<Integer> gems = new ArrayList<>();
        for (int r = 0; r < ROWS; r++)
            for (int c = 0; c < COLS; c++)
                gems.add(board[r][c]);

        for (int attempt = 0; attempt < 1000; attempt++) {
            Collections.shuffle(gems, random);
            int idx = 0;
            for (int r = 0; r < ROWS; r++)
                for (int c = 0; c < COLS; c++)
                    board[r][c] = gems.get(idx++);
            if (findMatches().isEmpty() && !hasDeadlock()) return;
        }
        initializeBoard();
    }

    // ==================== AI策略 ====================

    public Move findBestMove() {
        Move best = null;
        int bestScore = -1;

        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                if (c + 1 < COLS) {
                    int s = simulateMove(r, c, r, c + 1);
                    if (s > bestScore) { bestScore = s; best = new Move(r, c, r, c + 1); best.score = s; }
                }
                if (r + 1 < ROWS) {
                    int s = simulateMove(r, c, r + 1, c);
                    if (s > bestScore) { bestScore = s; best = new Move(r, c, r + 1, c); best.score = s; }
                }
            }
        }
        return best;
    }

    private int simulateMove(int r1, int c1, int r2, int c2) {
        int[][] saved = saveBoard();
        swapGems(r1, c1, r2, c2);
        if (findMatches().isEmpty()) {
            restoreBoard(saved);
            return -1;
        }
        int score = executeRound();
        restoreBoard(saved);
        return score;
    }

    private int[][] saveBoard() {
        int[][] c = new int[ROWS][COLS];
        for (int r = 0; r < ROWS; r++) System.arraycopy(board[r], 0, c[r], 0, COLS);
        return c;
    }

    private void restoreBoard(int[][] s) {
        for (int r = 0; r < ROWS; r++) System.arraycopy(s[r], 0, board[r], 0, COLS);
    }

    public void runAI(int maxMoves) {
        int total = 0;
        for (int i = 0; i < maxMoves; i++) {
            if (hasDeadlock()) { shuffleBoard(); System.out.println("Shuffled due to deadlock"); }
            Move m = findBestMove();
            if (m == null) break;
            trySwap(m.r1, m.c1, m.r2, m.c2);
            int s = executeRound();
            total += s;
            System.out.println("Move " + (i+1) + ": " + m + " Score=" + s + " Total=" + total);
        }
        System.out.println("Final Score: " + total);
    }

    // ==================== 可视化 ====================

    public void printBoard() {
        char[] symbols = {'R', 'G', 'B', 'Y', 'P', 'O', 'W'};
        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++) {
                System.out.print(symbols[board[r][c]] + " ");
            }
            System.out.println();
        }
    }

    // ==================== 数据结构 ====================

    public static class Match {
        public final int row, col, dir, length, gemType;
        public Match(int r, int c, int d, int l, int g) {
            row = r; col = c; dir = d; length = l; gemType = g;
        }
    }

    public static class Move {
        public final int r1, c1, r2, c2;
        public int score;
        public Move(int r1, int c1, int r2, int c2) {
            this.r1 = r1; this.c1 = c1; this.r2 = r2; this.c2 = c2;
        }
        public String toString() {
            return String.format("(%d,%d)<->(%d,%d)[%d]", r1, c1, r2, c2, score);
        }
    }

    // ==================== 主函数 ====================

    public static void main(String[] args) {
        BejeweledEngine engine = new BejeweledEngine();
        System.out.println("=== Initial Board ===");
        engine.printBoard();
        System.out.println();

        // 运行AI演示
        engine.runAI(20);

        System.out.println();
        System.out.println("=== Final Board ===");
        engine.printBoard();
    }
}

七、复杂度分析

算法模块 时间复杂度 空间复杂度 说明
匹配检测(findMatches) O(ROWS × COLS) O(ROWS × COLS) 行列扫描各一次
消除与下落(removeMatchesAndCollapse) O(ROWS × COLS) O(ROWS × COLS) 标记+逐列下落
级联消除(executeRound) O(k × ROWS × COLS) O(ROWS × COLS) k为级联层数,通常k≤5
死锁检测(hasDeadlock) O(ROWS² × COLS²) O(ROWS × COLS) 约2×ROWS×COLS次模拟交换
AI选步(findBestMove) O(ROWS² × COLS² × k) O(ROWS × COLS) 对每个合法移动进行完整模拟

对于8×8的棋盘,死锁检测的约4096次操作在现代计算机上几乎可以瞬时完成。AI选步需要对约100个候选移动逐一模拟,每次模拟包含匹配检测和级联消除,整体运行时间在毫秒级别。

八、优化方向与扩展思考

  1. 着法排序优化:在AI选步时,优先检测可能产生4连或5连的移动,可以更快找到高分移动,减少不必要的模拟。
  2. 置换表(Transposition Table):记录已评估过的棋盘状态,避免在级联模拟中重复计算相同局面。
  3. 蒙特卡洛树搜索(MCTS):将贪心策略扩展为多步 lookahead,通过随机模拟评估未来几步的收益,适用于更复杂的变体规则。
  4. 特殊宝石机制:实现4连生成的条纹宝石(消除整行/整列)和5连生成的彩虹宝石(消除所有同色宝石),可以大幅扩展AI评估函数的设计空间。

九、总结

本文完整实现了宝石迷阵的核心游戏引擎,重点展示了交换匹配检测的行列扫描法、级联消除的递归处理、死锁检测的暴力枚举策略,以及基于模拟评估的贪心AI选步算法。宝石迷阵虽规则简单,但其背后的状态空间搜索与评估函数设计,与棋类AI的核心思想一脉相承,是理解博弈搜索算法的绝佳入门案例。