每日算法 — 使用java实现Columns：DFS连通检测与级联消除算法

游戏简介

Columns是一款经典的益智消块游戏，玩法类似于俄罗斯方块但又有独特之处。彩色宝石从顶部以三格一列的形式下落，玩家可以左右移动和旋转列内宝石的顺序。当三个或更多相同颜色的宝石在水平、垂直或对角线方向上相连时，这些宝石会被消除，上方的宝石在重力作用下下落，可能引发连锁消除反应。

本文将用Java实现Columns游戏的核心引擎，重点讲解DFS连通块检测算法用于识别可消除的宝石组合，以及级联消除的递归处理逻辑。

核心算法设计

1. 游戏板与数据结构

Columns的游戏板是一个二维网格，每个格子记录宝石的颜色编号（0表示空）。我们用int[][] board表示当前状态，用常量定义宝石颜色。

public class ColumnsGame {
    // 游戏板尺寸
    private static final int ROWS = 13;
    private static final int COLS = 6;
    // 宝石颜色：0=空, 1=红, 2=绿, 3=蓝, 4=黄, 5=紫, 6=青
    private static final int EMPTY = 0;
    private static final int COLORS = 6;

    private int[][] board; // 当前游戏板状态
    private Random random;

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

    /**
     * 打印当前游戏板状态，用于调试
     */
    public void printBoard() {
        for (int r = ROWS - 1; r >= 0; r--) {
            for (int c = 0; c < COLS; c++) {
                System.out.print(board[r][c] + " ");
            }
            System.out.println();
        }
        System.out.println("--------");
    }
}

2. DFS连通块检测

消除规则要求三个及以上同色宝石在任意方向上相邻（水平、垂直、对角线共8个方向）。我们使用深度优先搜索（DFS）遍历每个方向的相邻格子，找到所有连通的同色宝石。

public class ColumnsGame {
    // 8个方向的偏移量：上、下、左、右、4个对角线
    private static final int[][] DIRS = {
        {-1, 0}, {1, 0}, {0, -1}, {0, 1},
        {-1, -1}, {-1, 1}, {1, -1}, {1, 1}
    };

    /**
     * 使用DFS检测从(r,c)出发的所有连通同色宝石
     * @param r 起始行
     * @param c 起始列
     * @param color 目标颜色
     * @param visited 访问标记数组
     * @param group 存储连通块坐标的列表
     */
    private void dfs(int r, int c, int color, boolean[][] visited, List<int[]> group) {
        // 边界检查：越界、已访问、颜色不同、空格子
        if (r < 0 || r >= ROWS || c < 0 || c >= COLS 
                || visited[r][c] || board[r][c] != color || color == EMPTY) {
            return;
        }

        visited[r][c] = true;
        group.add(new int[]{r, c});

        // 向8个方向递归搜索
        for (int[] d : DIRS) {
            int nr = r + d[0];
            int nc = c + d[1];
            dfs(nr, nc, color, visited, group);
        }
    }

    /**
     * 扫描整个游戏板，找到所有需要消除的宝石组
     * @return 所有可消除的坐标集合
     */
    public Set<String> findMatches() {
        boolean[][] visited = new boolean[ROWS][COLS];
        Set<String> toEliminate = new HashSet<>();

        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                if (board[r][c] != EMPTY && !visited[r][c]) {
                    List<int[]> group = new ArrayList<>();
                    dfs(r, c, board[r][c], visited, group);

                    // 只有连通块大小>=3才需要消除
                    if (group.size() >= 3) {
                        for (int[] pos : group) {
                            toEliminate.add(pos[0] + "," + pos[1]);
                        }
                    }
                }
            }
        }
        return toEliminate;
    }
}

3. 重力下落与级联消除

消除宝石后，上方宝石受重力影响下落填补空位。下落完成后，可能形成新的连通组合，需要递归检测直到没有可消除的宝石为止。

public class ColumnsGame {
    /**
     * 应用重力：让每列中的宝石下落到最低的空位置
     */
    public void applyGravity() {
        for (int c = 0; c < COLS; c++) {
            int writePos = 0; // 从底部开始填充
            // 先收集该列所有非空宝石（从底向上）
            List<Integer> columnGems = new ArrayList<>();
            for (int r = 0; r < ROWS; r++) {
                if (board[r][c] != EMPTY) {
                    columnGems.add(board[r][c]);
                }
            }
            // 清空该列
            for (int r = 0; r < ROWS; r++) {
                board[r][c] = EMPTY;
            }
            // 从底部重新放置宝石
            for (int i = 0; i < columnGems.size(); i++) {
                board[i][c] = columnGems.get(i);
            }
        }
    }

    /**
     * 消除指定坐标的宝石
     * @param toEliminate 待消除的坐标集合
     * @return 消除的宝石数量
     */
    public int eliminate(Set<String> toEliminate) {
        int count = 0;
        for (String key : toEliminate) {
            String[] parts = key.split(",");
            int r = Integer.parseInt(parts[0]);
            int c = Integer.parseInt(parts[1]);
            board[r][c] = EMPTY;
            count++;
        }
        return count;
    }

    /**
     * 级联消除：递归执行消除-下落-再检测，直到没有可消除的宝石
     * @return 总消除的宝石数量
     */
    public int cascadeEliminate() {
        int totalEliminated = 0;
        int chain = 0;

        while (true) {
            Set<String> matches = findMatches();
            if (matches.isEmpty()) {
                break; // 没有可消除的宝石，结束级联
            }

            chain++;
            int eliminated = eliminate(matches);
            totalEliminated += eliminated * chain; // 连锁倍率加分
            applyGravity();

            System.out.println("连锁" + chain + "：消除了" + eliminated + "个宝石");
        }

        return totalEliminated;
    }
}

4. 三格列的下落与旋转

玩家控制的三格列可以左右移动，也可以循环旋转列内三个宝石的顺序。

public class ColumnsGame {
    /**
     * 当前下落的三格列，数组长度为3
     */
    private int[] currentColumn;
    private int currentCol; // 当前所在列位置
    private int currentRow; // 当前底部所在行

    /**
     * 生成新的三格列，随机三种颜色
     */
    public void spawnColumn() {
        currentColumn = new int[3];
        for (int i = 0; i < 3; i++) {
            currentColumn[i] = random.nextInt(COLORS) + 1;
        }
        currentCol = COLS / 2; // 从中间列开始
        currentRow = ROWS - 1; // 从顶部开始下落
    }

    /**
     * 旋转三格列：将宝石顺序循环上移
     * 例如 [红,绿,蓝] -> [绿,蓝,红]
     */
    public void rotateColumn() {
        int temp = currentColumn[0];
        currentColumn[0] = currentColumn[1];
        currentColumn[1] = currentColumn[2];
        currentColumn[2] = temp;
    }

    /**
     * 将当前三格列固定到游戏板上
     * @return 是否成功固定（如果顶部被堵住则游戏结束）
     */
    public boolean placeColumn() {
        for (int i = 0; i < 3; i++) {
            int targetRow = currentRow - i;
            if (targetRow < 0 || targetRow >= ROWS) continue;
            if (board[targetRow][currentCol] != EMPTY) {
                return false; // 碰撞，游戏结束
            }
            board[targetRow][currentCol] = currentColumn[i];
        }
        return true;
    }

    /**
     * 尝试将列向左/右移动
     * @param delta -1表示左移，1表示右移
     * @return 是否移动成功
     */
    public boolean moveColumn(int delta) {
        int newCol = currentCol + delta;
        if (newCol < 0 || newCol >= COLS) {
            return false; // 超出边界
        }
        // 检查目标列是否有足够的空间
        for (int i = 0; i < 3; i++) {
            int targetRow = currentRow - i;
            if (targetRow >= 0 && targetRow < ROWS && board[targetRow][newCol] != EMPTY) {
                return false; // 有障碍物
            }
        }
        currentCol = newCol;
        return true;
    }
}

5. 完整游戏循环

public class ColumnsGame {
    private boolean gameOver;
    private int score;

    public ColumnsGame() {
        this.board = new int[ROWS][COLS];
        this.random = new Random();
        this.gameOver = false;
        this.score = 0;
    }

    /**
     * 执行一步：下落并固定列，然后触发级联消除
     * @return 本轮获得的分数
     */
    public int step() {
        if (gameOver) return 0;

        spawnColumn();

        // 这里简化处理：直接让列下落到最底部可放置位置
        // 实际游戏中玩家可以控制下落过程
        while (canFall()) {
            currentRow--;
        }

        if (!placeColumn()) {
            gameOver = true;
            System.out.println("游戏结束！最终得分：" + score);
            return 0;
        }

        int roundScore = cascadeEliminate();
        score += roundScore;
        return roundScore;
    }

    /**
     * 检查当前列是否还能继续下落
     */
    private boolean canFall() {
        if (currentRow - 3 < 0) return false; // 已经到达底部
        for (int i = 0; i < 3; i++) {
            int belowRow = currentRow - 3 - i;
            if (belowRow >= 0 && board[belowRow][currentCol] != EMPTY) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        ColumnsGame game = new ColumnsGame();

        // 模拟10步游戏
        for (int i = 0; i < 10 && !game.isGameOver(); i++) {
            System.out.println("=== 第" + (i + 1) + "步 ===");
            game.step();
            game.printBoard();
        }
    }

    public boolean isGameOver() {
        return gameOver;
    }
}

算法复杂度分析

其中 k 为连锁消除的轮数。由于 ROWS=13、COLS=6，实际运行非常快。

扩展方向

1. 启发式AI玩家：使用蒙特卡洛模拟评估每种落地方案的期望得分，选择最优列位置和旋转顺序。
2. 死局检测：当没有任何落地方案能避免游戏结束时提前判定。
3. 高级消除规则：支持4连、5连的额外奖励和特殊宝石（如炸弹、彩虹宝石）。

小结

Columns游戏的核心算法围绕DFS连通块检测和重力下落级联消除展开。通过8方向DFS可以准确识别所有可消除的宝石组合，递归的级联处理则模拟了真实的物理连锁反应。这种”检测-消除-下落-再检测”的模式是众多消除类游戏（如消消乐、宝石迷阵）的共同算法骨架。