元胞自动机（Cellular Automaton, CA）是由冯·诺依曼提出的离散计算模型，由大量简单规则的元胞在网格上并行演化。从康威的生命游戏到沃尔弗拉姆的初等元胞自动机，CA展现了”简单规则产生复杂行为”的涌现特性。本文将用Java实现一个通用元胞自动机引擎，支持一维/二维规则、多种边界条件，并重点分析规则分类与涌现模式检测算法。
元胞自动机的基本结构
元胞自动机由四元组 $(L, S, N, f)$ 定义：
- 网格 $L$：一维线段、二维平面或更高维空间
- 状态集 $S$：每个元胞可能取值的有限集合
- 邻域 $N$：决定元胞下一时刻状态所依赖的邻居集合
- 转移函数 $f$：$S^{|N|} o S$，根据邻居状态计算下一状态
沃尔弗拉姆编码
对于一维二态三邻居（左、中、右）元胞自动机，转移函数可以用8位二进制数编码（$2^3=8$ 种邻居组合），共256种规则，即”初等元胞自动机”。
二维邻域
常用邻域包括冯·诺依曼邻域（4方向）和摩尔邻域（8方向）。生命游戏采用摩尔邻域。
核心算法设计
规则编码与快速查找
将邻居状态组合编码为整数索引，通过查表方式 $O(1)$ 获取下一状态。
涌现模式检测
通过计算时间序列的熵、重复周期和空间相关性，自动识别CA演化进入的稳态、周期或混沌模式。
Java实现
import java.util.*;
/**
* 通用元胞自动机引擎
* 支持：一维/二维、多规则、多种边界条件、涌现模式检测
*/
public class CellularAutomaton {
// 一维元胞自动机
static class CA1D {
final int rule; // 沃尔弗拉姆规则号 (0-255)
final int[] state; // 当前状态
final int size; // 网格大小
final boolean wrap; // 是否循环边界
int[] nextState; // 下一状态缓冲区
final int[] ruleTable; // 规则查找表，索引为 (左<<2)|(中<<1)|右
CA1D(int rule, int size, boolean wrap, int[] initial) {
this.rule = rule; this.size = size; this.wrap = wrap;
this.state = initial.clone();
this.nextState = new int[size];
this.ruleTable = new int[8];
// 解析规则：rule的二进制位对应8种邻居组合
for (int i = 0; i < 8; i++) {
ruleTable[i] = (rule >> i) & 1;
}
}
int getNeighborSum(int idx) {
// 三邻居：左、中、右，编码为3位二进制
int left = wrap ? state[(idx - 1 + size) % size] : (idx > 0 ? state[idx - 1] : 0);
int center = state[idx];
int right = wrap ? state[(idx + 1) % size] : (idx < size - 1 ? state[idx + 1] : 0);
return (left << 2) | (center << 1) | right;
}
void step() {
for (int i = 0; i < size; i++) {
nextState[i] = ruleTable[getNeighborSum(i)];
}
int[] tmp = state;
// 注意：state是final引用，不能直接赋值，需要修改内容
// 修正：让state可变
}
}
// 修正版一维CA
static class CA1DFixed {
int rule, size;
int[] state;
boolean wrap;
int[] ruleTable;
CA1DFixed(int rule, int size, boolean wrap, int[] initial) {
this.rule = rule; this.size = size; this.wrap = wrap;
this.state = initial.clone();
this.ruleTable = new int[8];
for (int i = 0; i < 8; i++) ruleTable[i] = (rule >> i) & 1;
}
int left(int i) { return wrap ? state[(i - 1 + size) % size] : (i > 0 ? state[i - 1] : 0); }
int right(int i) { return wrap ? state[(i + 1) % size] : (i < size - 1 ? state[i + 1] : 0); }
void step() {
int[] next = new int[size];
for (int i = 0; i < size; i++) {
int pattern = (left(i) << 2) | (state[i] << 1) | right(i);
next[i] = ruleTable[pattern];
}
state = next;
}
void print() {
for (int v : state) System.out.print(v == 1 ? "█" : " ");
System.out.println();
}
}
// 二维元胞自动机（通用版）
static class CA2D {
final int rows, cols;
int[][] grid;
final boolean wrap;
final Rule2D rule;
interface Rule2D {
int next(int[][] grid, int r, int c, int rows, int cols, boolean wrap);
}
CA2D(int rows, int cols, boolean wrap, int[][] initial, Rule2D rule) {
this.rows = rows; this.cols = cols; this.wrap = wrap; this.rule = rule;
this.grid = new int[rows][cols];
for (int i = 0; i < rows; i++)
System.arraycopy(initial[i], 0, grid[i], 0, cols);
}
int get(int r, int c) {
if (wrap) {
r = (r + rows) % rows;
c = (c + cols) % cols;
} else {
if (r < 0 || r >= rows || c < 0 || c >= cols) return 0;
}
return grid[r][c];
}
void step() {
int[][] next = new int[rows][cols];
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++)
next[r][c] = rule.next(grid, r, c, rows, cols, wrap);
grid = next;
}
}
// 生命游戏规则
static CA2D.Rule2D gameOfLife() {
return (grid, r, c, rows, cols, wrap) -> {
int liveNeighbors = 0;
for (int dr = -1; dr <= 1; dr++) {
for (int dc = -1; dc <= 1; dc++) {
if (dr == 0 && dc == 0) continue;
int nr = r + dr, nc = c + dc;
if (wrap) {
nr = (nr + rows) % rows;
nc = (nc + cols) % cols;
liveNeighbors += grid[nr][nc];
} else {
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols)
liveNeighbors += grid[nr][nc];
}
}
}
if (grid[r][c] == 1) {
return (liveNeighbors == 2 || liveNeighbors == 3) ? 1 : 0;
} else {
return (liveNeighbors == 3) ? 1 : 0;
}
};
}
// 涌现模式检测器
static class PatternDetector {
/**
* 检测一维CA的时间序列是否进入周期
* 返回周期长度，0表示未进入周期（在maxSteps内）
*/
static int detectPeriod(List<int[]> history, int maxSteps) {
int n = history.size();
if (n < 2) return 0;
int[] last = history.get(n - 1);
// 检查是否与之前某个状态重复
for (int period = 1; period < Math.min(n - 1, maxSteps); period++) {
int[] candidate = history.get(n - 1 - period);
boolean match = true;
for (int i = 0; i < last.length; i++) {
if (last[i] != candidate[i]) { match = false; break; }
}
if (match) return period;
}
return 0;
}
/**
* 计算空间熵，衡量模式的有序程度
* 熵越低说明越有序（稳态或简单周期），熵越高越混沌
*/
static double spatialEntropy(int[] state) {
Map<String, Integer> freq = new HashMap<>();
// 统计长度为3的模式频率
int n = state.length;
for (int i = 0; i < n; i++) {
int a = state[i];
int b = state[(i + 1) % n];
int c = state[(i + 2) % n];
String key = a + "," + b + "," + c;
freq.merge(key, 1, Integer::sum);
}
double entropy = 0;
for (int count : freq.values()) {
double p = (double) count / n;
entropy -= p * Math.log(p) / Math.log(2);
}
return entropy;
}
/**
* 沃尔弗拉姆分类
* 基于长期行为的定性分类：
* Class 1: 趋于均匀稳态（熵趋近于0）
* Class 2: 趋于简单周期结构（熵有界且低）
* Class 3: 混沌随机（熵高且无周期）
* Class 4: 复杂局部结构（熵中等，难以预测）
*/
static String wolframClassify(List<Double> entropyHistory, int detectedPeriod) {
if (detectedPeriod > 0) {
double avgEntropy = entropyHistory.stream().mapToDouble(Double::doubleValue).average().orElse(0);
return avgEntropy < 1.0 ? "Class 1/2 (有序/周期)" : "Class 2 (复杂周期)";
}
double recentEntropy = entropyHistory.get(entropyHistory.size() - 1);
if (recentEntropy > 2.5) return "Class 3 (混沌)";
if (recentEntropy > 1.5) return "Class 4 (复杂局部结构)";
return "Class 1 (均匀稳态)";
}
}
public static void main(String[] args) {
System.out.println("=== 一维元胞自动机演示 ===");
int size = 80;
int[] init = new int[size];
init[size / 2] = 1; // 中间一个点
// Rule 90: Sierpinski三角形
CA1DFixed ca90 = new CA1DFixed(90, size, true, init);
System.out.println("Rule 90 (Sierpinski三角形):");
List<int[]> history90 = new ArrayList<>();
for (int step = 0; step < 40; step++) {
history90.add(ca90.state.clone());
ca90.print();
ca90.step();
}
int period90 = PatternDetector.detectPeriod(history90, 20);
System.out.println("检测到周期: " + period90);
System.out.println("
=== 二维生命游戏演示 ===");
int rows = 20, cols = 40;
int[][] grid = new int[rows][cols];
// 设置一个滑翔机
grid[1][2] = 1; grid[2][3] = 1;
grid[3][1] = 1; grid[3][2] = 1; grid[3][3] = 1;
CA2D life = new CA2D(rows, cols, true, grid, gameOfLife());
for (int step = 0; step < 20; step++) {
System.out.println("Step " + step + ":");
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++)
System.out.print(life.grid[r][c] == 1 ? "█" : " ");
System.out.println();
}
life.step();
}
System.out.println("
=== 规则分类演示 ===");
int[] initRand = new int[size];
Random rand = new Random(123);
for (int i = 0; i < size; i++) initRand[i] = rand.nextInt(2);
for (int rule : new int[]{0, 90, 110, 30}) {
CA1DFixed ca = new CA1DFixed(rule, size, true, initRand.clone());
List<int[]> hist = new ArrayList<>();
List<Double> entropies = new ArrayList<>();
for (int s = 0; s < 100; s++) {
hist.add(ca.state.clone());
entropies.add(PatternDetector.spatialEntropy(ca.state));
ca.step();
}
int p = PatternDetector.detectPeriod(hist, 30);
String cls = PatternDetector.wolframClassify(entropies, p);
System.out.println("Rule " + rule + " -> " + cls + " (周期=" + p + ")");
}
}
}
算法复杂度分析
- 单步演化：一维CA为 $O(n)$，$n$ 为网格大小；二维CA为 $O(r \cdot c)$，$r, c$ 为行列数。每个元胞的下一状态仅依赖常数个邻居，计算是高度并行的。
- 周期检测：使用历史状态比较，时间复杂度 $O(k \cdot n)$，$k$ 为历史长度。可通过滚动哈希优化到 $O(k)$。
- 空间复杂度：存储当前网格和历史记录需要 $O(k \cdot n)$。若仅检测周期，可采用Floyd判圈算法将空间降至 $O(n)$。
扩展方向
- 连续态CA：将元胞状态从离散 ${0,1}$ 扩展到连续区间 $[0,1]$，如Lenia系统可模拟类生命形态。
- 异步更新：打破同步更新假设，按随机顺序或特定调度更新元胞，可产生不同的动力学行为。
- 网络CA：将规则网格替换为任意图结构，研究复杂网络上的涌现行为。
总结
元胞自动机是研究复杂系统的极简模型。通过Java实现通用CA引擎，我们展示了规则编码、多维度演化以及基于熵和周期检测的自动分类方法。从Sierpinski三角形的分形结构到生命游戏的滑翔机，CA证明了一条深刻道理：复杂的宏观行为往往源于简单的微观规则。
