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

引言

康威生命游戏（Conway’s Game of Life）是英国数学家约翰·康威于1970年设计的细胞自动机。它由无限二维方格组成，每个格子有”存活”或”死亡”两种状态，依据简单的邻域规则逐代演化。尽管规则极简，生命游戏却能涌现出极其复杂的模式——从静止的稳定结构到移动的”滑翔机”，甚至能够模拟图灵机。本文将用Java实现一个带图形界面的生命游戏模拟器，重点讲解Moore邻域状态转移规则、周期性检测算法与边界条件处理。

核心算法原理

1. Moore邻域与状态转移规则

每个细胞考察其周围8个邻居（Moore邻域），遵循以下规则：

• 诞生：死亡细胞恰有3个存活邻居时，下一代复活
• 存活：存活细胞有2或3个存活邻居时，继续存活
• 死亡：其他情况（过 lonely 或过 crowded）死亡

用数学语言描述，设 $N$ 为存活邻居数，$S$ 为当前状态（1=存活，0=死亡）：

$$
S_{next} = \begin{cases} 1 & (S=0 \land N=3) \lor (S=1 \land N \in {2,3}) \ 0 & \text{otherwise} \end{cases}
$$

2. 边界条件处理

实现时常用三种边界策略：

本文采用循环边界，使有限网格行为更接近无限平面。

3. 周期性检测

生命游戏可能进入周期振荡（如”闪光灯”周期为2）。检测方法：

• 维护最近 $K$ 代状态队列
• 每代用Zobrist哈希或字符串哈希生成状态指纹
• 若当前指纹与历史指纹匹配，则检测到周期

Java完整实现

package conway;

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

/**
 * 康威生命游戏模拟器
 * 核心算法：Moore邻域状态转移 + 循环边界 + 周期性检测
 */
public class ConwayLifeGame extends JPanel implements Runnable {
    private static final int CELL_SIZE = 10;
    private static final int GRID_WIDTH = 80;
    private static final int GRID_HEIGHT = 60;
    private static final int DELAY_MS = 100;

    // 当前代与下一代的网格状态
    private boolean[][] currentGrid;
    private boolean[][] nextGrid;

    // 周期性检测：存储最近20代的状态哈希
    private LinkedList<Long> stateHistory = new LinkedList<>();
    private static final int HISTORY_SIZE = 20;
    private boolean isPaused = false;

    public ConwayLifeGame() {
        currentGrid = new boolean[GRID_HEIGHT][GRID_WIDTH];
        nextGrid = new boolean[GRID_HEIGHT][GRID_WIDTH];

        // 初始化经典模式：滑翔机 + 闪光灯 + 蜂巢
        initClassicPatterns();

        setPreferredSize(new Dimension(GRID_WIDTH * CELL_SIZE, GRID_HEIGHT * CELL_SIZE));
        setBackground(Color.BLACK);

        // 鼠标点击切换细胞状态
        addMouseListener(new MouseAdapter() {
            @Override
            public void mouseClicked(MouseEvent e) {
                int col = e.getX() / CELL_SIZE;
                int row = e.getY() / CELL_SIZE;
                if (row >= 0 && row < GRID_HEIGHT && col >= 0 && col < GRID_WIDTH) {
                    currentGrid[row][col] = !currentGrid[row][col];
                    repaint();
                }
            }
        });

        // 空格键暂停/继续
        setFocusable(true);
        addKeyListener(new KeyAdapter() {
            @Override
            public void keyPressed(KeyEvent e) {
                if (e.getKeyCode() == KeyEvent.VK_SPACE) {
                    isPaused = !isPaused;
                }
            }
        });
    }

    /**
     * 初始化经典模式：
     * - 滑翔机(Glider)：周期性移动的模式
     * - 闪光灯(Blinker)：周期为2的振荡器
     * - 蜂巢(Beehive)：静止稳定结构
     */
    private void initClassicPatterns() {
        // 滑翔机（左上角）
        int[][] glider = {{1,0}, {2,1}, {0,2}, {1,2}, {2,2}};
        for (int[] p : glider) currentGrid[p[0]+5][p[1]+5] = true;

        // 闪光灯（中央）
        int[][] blinker = {{1,0}, {1,1}, {1,2}};
        for (int[] p : blinker) currentGrid[p[0]+20][p[1]+30] = true;

        // 蜂巢（右下角）
        int[][] beehive = {{1,0}, {2,0}, {0,1}, {3,1}, {1,2}, {2,2}};
        for (int[] p : beehive) currentGrid[p[0]+40][p[1]+50] = true;
    }

    /**
     * 核心算法：计算下一代网格状态
     * 使用循环边界(toroidal)处理边缘
     */
    public void nextGeneration() {
        for (int row = 0; row < GRID_HEIGHT; row++) {
            for (int col = 0; col < GRID_WIDTH; col++) {
                int neighbors = countLiveNeighbors(row, col);
                boolean isAlive = currentGrid[row][col];

                // 康威生命规则
                if (isAlive) {
                    nextGrid[row][col] = (neighbors == 2 || neighbors == 3);
                } else {
                    nextGrid[row][col] = (neighbors == 3);
                }
            }
        }

        // 交换当前代与下一代
        boolean[][] temp = currentGrid;
        currentGrid = nextGrid;
        nextGrid = temp;

        // 周期性检测
        detectPeriodicity();
    }

    /**
     * 计算指定位置的存活邻居数（Moore邻域，8方向）
     * 使用循环边界：(row + r + GRID_HEIGHT) % GRID_HEIGHT
     */
    private int countLiveNeighbors(int row, int col) {
        int count = 0;
        for (int dr = -1; dr <= 1; dr++) {
            for (int dc = -1; dc <= 1; dc++) {
                if (dr == 0 && dc == 0) continue; // 跳过自身

                // 循环边界处理
                int nr = (row + dr + GRID_HEIGHT) % GRID_HEIGHT;
                int nc = (col + dc + GRID_WIDTH) % GRID_WIDTH;

                if (currentGrid[nr][nc]) count++;
            }
        }
        return count;
    }

    /**
     * 周期性检测：使用Zobrist哈希快速比较状态
     * 若检测到周期，在控制台输出警告
     */
    private void detectPeriodicity() {
        long hash = computeZobristHash();

        // 检查是否在历史中出现
        int period = 0;
        for (int i = stateHistory.size() - 1; i >= 0; i--) {
            period++;
            if (stateHistory.get(i) == hash) {
                System.out.println("检测到周期振荡！周期=" + period + " 代");
                break;
            }
        }

        stateHistory.addLast(hash);
        if (stateHistory.size() > HISTORY_SIZE) {
            stateHistory.removeFirst();
        }
    }

    /**
     * Zobrist哈希：为每个(r,c)预生成随机数，快速计算状态指纹
     * 时间复杂度O(存活细胞数)，远快于字符串哈希
     */
    private static final long[][] ZOBRIST_TABLE = generateZobristTable();

    private static long[][] generateZobristTable() {
        long[][] table = new long[GRID_HEIGHT][GRID_WIDTH];
        Random rand = new Random(42); // 固定种子保证可复现
        for (int i = 0; i < GRID_HEIGHT; i++) {
            for (int j = 0; j < GRID_WIDTH; j++) {
                table[i][j] = rand.nextLong();
            }
        }
        return table;
    }

    private long computeZobristHash() {
        long hash = 0;
        for (int i = 0; i < GRID_HEIGHT; i++) {
            for (int j = 0; j < GRID_WIDTH; j++) {
                if (currentGrid[i][j]) {
                    hash ^= ZOBRIST_TABLE[i][j];
                }
            }
        }
        return hash;
    }

    @Override
    protected void paintComponent(Graphics g) {
        super.paintComponent(g);
        g.setColor(Color.GREEN);
        for (int row = 0; row < GRID_HEIGHT; row++) {
            for (int col = 0; col < GRID_WIDTH; col++) {
                if (currentGrid[row][col]) {
                    g.fillRect(col * CELL_SIZE, row * CELL_SIZE, CELL_SIZE - 1, CELL_SIZE - 1);
                }
            }
        }
    }

    @Override
    public void run() {
        while (true) {
            if (!isPaused) {
                nextGeneration();
                repaint();
            }
            try {
                Thread.sleep(DELAY_MS);
            } catch (InterruptedException e) {
                break;
            }
        }
    }

    public static void main(String[] args) {
        JFrame frame = new JFrame("康威生命游戏 - Java实现");
        ConwayLifeGame game = new ConwayLifeGame();
        frame.add(game);
        frame.pack();
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setLocationRelativeTo(null);
        frame.setVisible(true);

        new Thread(game).start();
    }
}

算法复杂度分析

扩展思考

1. 大规模并行：可用Java Fork/Join框架将网格分块并行计算，适合 $10^6 \times 10^6$ 级别模拟
2. 规则泛化：将规则参数化为 $B3/S23$（诞生/存活），可探索 $B36/S23$ 等变体的”高生命”行为
3. 图灵完备性：生命游戏已被证明是图灵完备的，理论上可用滑翔机碰撞实现任意计算

总结

康威生命游戏展示了”简单规则产生复杂行为”的涌现现象。通过Java实现，我们掌握了细胞自动机的核心编程范式：离散网格 + 局部规则 + 同步更新。Zobrist哈希的引入也展示了博弈状态编码技巧在实际仿真中的妙用。