每日算法 — 使用java实现生命游戏：细胞自动机与邻域状态演化

康威生命游戏（Conway’s Game of Life）是数学家约翰·康威于1970年提出的零玩家游戏，也是细胞自动机（Cellular Automaton）领域最具代表性的模型。它看似简单——只有”存活”与”死亡”两种状态，却能在二维网格上涌现出令人惊叹的复杂行为：滑翔机跨越屏幕、脉冲星周期闪烁、甚至某些构型可模拟通用图灵机。本文将用Java完整实现生命游戏模拟器，深入讲解邻域扫描算法与B3/S23状态转移规则的工程实现。

一、规则建模：B3/S23 生存与繁殖

生命游戏的核心规则极度简洁，通常记为 B3/S23：

邻居采用摩尔邻域（Moore Neighborhood），即周围8个方向（上下左右 + 四个对角）。

二、核心数据结构

2.1 网格表示

使用二维布尔数组表示细胞状态，true 为存活，false 为死亡。为简化边界处理，采用固定边界 + 全死亡策略。

/**
 * 生命游戏网格核心类
 * 使用 boolean[][] 表示细胞存活状态
 */
public class LifeGrid {
    private final int rows;
    private final int cols;
    // 当前代与下一代的双缓冲，避免原地更新导致的时序错误
    private boolean[][] current;
    private boolean[][] next;

    public LifeGrid(int rows, int cols) {
        this.rows = rows;
        this.cols = cols;
        this.current = new boolean[rows][cols];
        this.next = new boolean[rows][cols];
    }

    /**
     * 设置初始存活细胞
     */
    public void setAlive(int row, int col) {
        if (inBounds(row, col)) {
            current[row][col] = true;
        }
    }

    /**
     * 设置初始死亡细胞
     */
    public void setDead(int row, int col) {
        if (inBounds(row, col)) {
            current[row][col] = false;
        }
    }

    /**
     * 查询细胞当前状态
     */
    public boolean isAlive(int row, int col) {
        return inBounds(row, col) && current[row][col];
    }

    private boolean inBounds(int row, int col) {
        return row >= 0 && row < rows && col >= 0 && col < cols;
    }

    public int getRows() { return rows; }
    public int getCols() { return cols; }

    /**
     * 获取当前代引用（用于渲染）
     */
    public boolean[][] getCurrentGrid() {
        return current;
    }

2.2 摩尔邻域扫描算法

这是生命游戏最频繁的计算操作。对每个细胞，统计其8个邻居中的存活数量。

    /**
     * 统计指定位置周围8个邻居的存活数量
     * 采用摩尔邻域（Moore Neighborhood）
     *
     * @param row 目标行
     * @param col 目标列
     * @return 存活邻居数（0-8）
     */
    public int countLiveNeighbors(int row, int col) {
        int count = 0;
        // 遍历 3x3 区域，排除中心点自身
        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                if (i == 0 && j == 0) continue; // 跳过自己

                int nr = row + i;
                int nc = col + j;

                // 边界外视为死亡，也可改为环形边界（torus）
                if (inBounds(nr, nc) && current[nr][nc]) {
                    count++;
                }
            }
        }
        return count;
    }

三、状态转移：一代到下一代的演化

状态转移必须基于当前代的全量快照计算下一代，不能边扫描边修改——否则尚未扫描的细胞会读取到已被更新的邻居状态，造成时序错误。我们使用双缓冲（Double Buffering）技术解决此问题。

    /**
     * 计算下一代网格状态
     * 核心逻辑：遍历每个细胞，根据B3/S23规则决定其下一代生死
     */
    public void nextGeneration() {
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                int neighbors = countLiveNeighbors(r, c);
                boolean alive = current[r][c];

                if (alive) {
                    // S23：存活细胞需要 2 或 3 个邻居才能继续存活
                    next[r][c] = (neighbors == 2 || neighbors == 3);
                } else {
                    // B3：死亡细胞恰好有 3 个邻居时复活
                    next[r][c] = (neighbors == 3);
                }
            }
        }

        // 交换缓冲区：下一代变为当前代
        swapBuffers();
    }

    /**
     * 交换 current 与 next 数组引用，时间复杂度 O(1)
     */
    private void swapBuffers() {
        boolean[][] temp = current;
        current = next;
        next = temp;
    }

四、经典图案加载器

生命游戏的魅力在于特定初始构型会产生稳定的周期性行为。我们提供几个经典图案的坐标加载器。

import java.util.List;

/**
 * 经典图案工厂
 * 所有坐标均为相对偏移量，方便在网格任意位置放置
 */
public class PatternFactory {

    /**
     * 滑翔机（Glider）：最小的可移动图案，每4代沿对角线移动一格
     */
    public static List<int[]> glider() {
        return List.of(
            new int[]{0, 1},
            new int[]{1, 2},
            new int[]{2, 0},
            new int[]{2, 1},
            new int[]{2, 2}
        );
    }

    /**
     * 脉冲星（Pulsar）：周期为3的稳定振荡器，由三个十字交叉组成
     */
    public static List<int[]> pulsar() {
        return List.of(
            // 上侧十字
            new int[]{2, 4}, new int[]{2, 5}, new int[]{2, 6},
            new int[]{2, 10}, new int[]{2, 11}, new int[]{2, 12},
            // 上中横条
            new int[]{4, 2}, new int[]{4, 7}, new int[]{4, 9}, new int[]{4, 14},
            new int[]{5, 2}, new int[]{5, 7}, new int[]{5, 9}, new int[]{5, 14},
            new int[]{6, 2}, new int[]{6, 7}, new int[]{6, 9}, new int[]{6, 14},
            // 中间横条
            new int[]{7, 4}, new int[]{7, 5}, new int[]{7, 6},
            new int[]{7, 10}, new int[]{7, 11}, new int[]{7, 12},
            // 下侧（镜像对称）
            new int[]{9, 4}, new int[]{9, 5}, new int[]{9, 6},
            new int[]{9, 10}, new int[]{9, 11}, new int[]{9, 12},
            new int[]{10, 2}, new int[]{10, 7}, new int[]{10, 9}, new int[]{10, 14},
            new int[]{11, 2}, new int[]{11, 7}, new int[]{11, 9}, new int[]{11, 14},
            new int[]{12, 2}, new int[]{12, 7}, new int[]{12, 9}, new int[]{12, 14},
            new int[]{14, 4}, new int[]{14, 5}, new int[]{14, 6},
            new int[]{14, 10}, new int[]{14, 11}, new int[]{14, 12}
        );
    }

    /**
     * 信标（Beacon）：周期为2的简单振荡器
     */
    public static List<int[]> beacon() {
        return List.of(
            new int[]{0, 0}, new int[]{0, 1},
            new int[]{1, 0}, new int[]{1, 1},
            new int[]{2, 2}, new int[]{2, 3},
            new int[]{3, 2}, new int[]{3, 3}
        );
    }

    /**
     * 将图案加载到网格指定位置
     */
    public static void loadPattern(LifeGrid grid, List<int[]> pattern, int offsetRow, int offsetCol) {
        for (int[] cell : pattern) {
            grid.setAlive(offsetRow + cell[0], offsetCol + cell[1]);
        }
    }
}

五、主控引擎与终端渲染

为保持示例的纯粹性，我们使用终端字符渲染。你可以轻松替换为 JavaFX 或 Swing 图形界面。

/**
 * 生命游戏主控引擎
 * 负责演化调度与终端可视化
 */
public class GameOfLifeEngine {
    private final LifeGrid grid;
    private final int maxGenerations;
    private final int delayMs;

    public GameOfLifeEngine(int rows, int cols, int maxGenerations, int delayMs) {
        this.grid = new LifeGrid(rows, cols);
        this.maxGenerations = maxGenerations;
        this.delayMs = delayMs;
    }

    public LifeGrid getGrid() {
        return grid;
    }

    /**
     * 启动模拟循环
     */
    public void run() throws InterruptedException {
        System.out.println("=== 康威生命游戏模拟器 ===");
        System.out.println("初始状态：");
        render();

        for (int gen = 1; gen <= maxGenerations; gen++) {
            Thread.sleep(delayMs);
            grid.nextGeneration();
            System.out.println("\n第 " + gen + " 代：");
            render();
        }
    }

    /**
     * 终端渲染：用 '█' 表示存活，'·' 表示死亡
     */
    private void render() {
        boolean[][] state = grid.getCurrentGrid();
        for (int r = 0; r < grid.getRows(); r++) {
            StringBuilder line = new StringBuilder();
            for (int c = 0; c < grid.getCols(); c++) {
                line.append(state[r][c] ? "█" : "·");
            }
            System.out.println(line);
        }
    }
}

5.1 可运行的入口程序

/**
 * 生命游戏入口
 * 演示滑翔机与脉冲星的演化过程
 */
public class GameOfLifeDemo {
    public static void main(String[] args) throws InterruptedException {
        // 创建 20x40 的模拟网格
        GameOfLifeEngine engine = new GameOfLifeEngine(20, 40, 50, 300);
        LifeGrid grid = engine.getGrid();

        // 加载滑翔机（左上角）
        PatternFactory.loadPattern(grid, PatternFactory.glider(), 1, 1);

        // 加载信标（中部）
        PatternFactory.loadPattern(grid, PatternFactory.beacon(), 5, 15);

        // 加载脉冲星（右下区域）
        PatternFactory.loadPattern(grid, PatternFactory.pulsar(), 2, 22);

        // 额外随机播种一些细胞增加趣味性
        grid.setAlive(10, 10);
        grid.setAlive(10, 11);
        grid.setAlive(10, 12);
        grid.setAlive(9, 12);
        grid.setAlive(8, 11);

        // 启动演化
        engine.run();
    }
}

六、算法优化：从 O(8RC) 到 O(RC) 的常数优化

虽然时间复杂度已经是网格规模的线性级，但每个细胞需要访问8次内存。利用字节掩码，我们可以将8个方向预先编码，减少分支预测失败的概率。对于超大规模网格（如 10^4 × 10^4），可进一步采用以下策略：

七、复杂度分析

八、结语

康威生命游戏用最简单的局部规则，演绎了涌现（Emergence）的深刻思想：复杂的全局行为并不需要复杂的底层指令。本文实现的邻域扫描与双缓冲状态转移机制，不仅是细胞自动机的基础，更是图像处理、物理模拟、甚至某些加密算法中常用的技术范式。试着修改 B3/S23 规则为其他数字组合（如 B36/S23 的 HighLife），你会观察到完全不同的宇宙。