如何编写初等细胞自动机

2024-04-10 06:20:15 阅读数 933

书名：代码本色：用编程模拟自然系统
作者：Daniel Shiffman
译者：周晗彬
ISBN：978-7-115-36947-5
第7章目录

先掌握用Processing Sketch创建和可视化Wolfram CA模型的方法。

7.3　如何编写初等细胞自动机

1、数组表示CA

你也许会想：“我知道模拟细胞的思路，它有一些属性（状态、迭代次数、邻居细胞和在屏幕上的像素位置）。除此之外，它可能还有一些功能（显示自身、产生新状态）……”这样的思路是正确的
但我们不想采用这种方法。在本章的后面，我们会讨论面向对象方法在CA模拟上的重要性；但在最开始，本例可以使用更初级的数据结构。毕竟，这个初等CA只是由“0和1”构成的状态列表，我们可以用一个数组表示CA的一次迭代。

int[] cells = {1,0,1,0,0,0,0,1,0,1,1,1,0,0,0,1,1,1,0,0};

为了绘制这个数组，我们可以根据元素的状态填充对应的颜色。

for (int i = 0; i < cells.length; i++) { 遍历每个细胞
    if (cell[i] == 0) fill(255);
        else fill(0); 根据状态（0或1）填充细胞颜色
    stroke(0);
    rect(i*50,0,50,50);
}

2、当前要做的事

现在，我们用数组描述一次迭代（只考虑“当前”的迭代）的细胞状态，下面还要引入计算下一次迭代的机制。我们先用伪代码表示当前要做的事。
对数组中的每个细胞：

获取邻居的状态——左右两边的细胞和自身的状态；
根据先前设定的规则查询新的状态；
把细胞的状态设为新值。

for (int i = 0; i < cells.length; i++) { 对数组中的每个细胞 ......
    int left = cell[i-1]; 获取邻居的状态
    int middle = cell[i];
    int right = cell[i+1];
    int newstate = rules(left,middle,right); 根据先前设定的规则查询新的状态
    cell[i] = newstate; 把细胞的状态设为新值
}

3、如何处理没有左右邻居的边界细胞？

现在有3种解决方案可供选择。

1.让边界细胞的状态是常量。
这也许是最简单的方案，我们不需要管任何边界细胞，只需让它们保持常量状态（0或1）。
2.边界环绕。
把CA想象成一张纸条，把纸条两端相连，变成一个环。如此一来，最左边的细胞和最右边细胞就成了邻居，反过来也是如此。用这种方法我们可创建出无限网格的外形，这或许也是最常用的解决方案。
3.边界细胞有特殊的邻居和计算规则。
我们可以将边界细胞区别对待，为其创建特殊的规则：让它们只有两个邻居。在某些情况下，你可能会这么做，但是在本例中，这么做会引入很多额外代码，收益却很少

为了让代码尽可能地易读易理解，我们采用第一种方案：直接略过边界细胞，让它们的状态保持常量。这种方案的实现很简单，只需要让循环从下标1开始，并提前一个元素结束：

for (int i = 1; i < cells.length-1; i++) { 忽略第一个和最后一个细胞
    int left = cell[i-1];
    int middle = cell[i];
    int right = cell[i+1];
    int newstate = rules(left,middle,right);
    cell[i] = newstate;
}

4、使用两个数组

上面代码看起来并没有错误：一旦我们得到新状态，确实需要将它赋给当前细胞。但在下一次迭代中，你会发现一个严重的漏洞。会覆盖当前代的状态。
这个问题的解决方案是：使用两个数组，一个数组用于保存当前代的状态，另一个数组用于保存下一代的状态。

int [] newcells = new int[cells.length]; 用另一个数组保存下一代状态
for (int i = 1; i < cells.length-1; i++) {
    int left = cell[i-1]; 从当前数组获取细胞状态
    int middle = cell[i];
    int right = cell[i+1];
    int newstate = rules(left,middle,right);
    newcells[i] = newstate; 在新数组中保存新状态
}

处理完数组的每个元素后，我们就可以丢弃旧的数组，让它的值等于新数组。
cells = newcells; 新一代状态变成了当前代状态

5、rules()函数

这个函数的功能是根据邻居（左边、自身和右边的细胞）计算当前细胞的新状态。它的返回值是一个整数（0或1），有3个参数（3个邻居）。
首先，我们需要建立规则的存储方式。
我们可以用数组存储这些规则。

int[] ruleset = {0,1,0,1,1,0,1,0};

然后：

if (a == 1 && b == 1 && c == 1) return ruleset[0];

如果左边、自身和右边细胞的状态都为1，函数就返回组合“111”对应的结果，也就是规则数组中的第一个元素。下面，我们用这种方法实现所有可能的组合：

int rules (int a, int b, int c) {
    if (a==1 && b == 1 && c == 1) return ruleset[0];
    else if (a == 1 && b == 1 && c == 0) return ruleset[1];
    else if (a == 1 && b == 0 && c == 1) return ruleset[2];
    else if (a == 1 && b == 0 && c == 0) return ruleset[3];
    else if (a == 0 && b == 1 && c == 1) return ruleset[4];
    else if (a == 0 && b == 1 && c == 0) return ruleset[5];
    else if (a == 0 && b == 0 && c == 1) return ruleset[6];
    else if (a == 0 && b == 0 && c == 0) return ruleset[7];
    return 0; 为了让函数的定义合法，必须加上这个返回值，虽然我们知道不可能出现不符合这8种情况}

我喜欢这种实现方式，因为它把每种邻居组合都描述清楚了。但这不是一个好方案。
如果CA中的细胞有4种可能的状态（0~3），这样就会有64种可能的邻居状态组合；
如果有10种可能的状态，邻居细胞的状态组合将达到1000种。我们肯定不想输入1000行这样的代码！

6、另一种解决方案

另一种解决方案有点难以理解，就是把邻居状态的组合（3位二进制数）转换成一个普通整数，并把该值作为规则数组的下标。实现方式如下：

int rules (int a, int b, int c) {
    String s = "" + a + b + c; 将3位转化为字符串
    int index = Integer.parseInt(s,2); 第二个参数“2”告诉parseInt()函数要把s当成二进制数
    return ruleset[index];
}

7、CA类

class CA {
    int[] cells; 我们需要两个数组，一个用来存放细胞，另一个用来存放规则
    int[] ruleset;
    CA() {
        cells = new int[width];
        ruleset = {0,1,0,1,1,0,1,0}; 随意选取规则90
        for (int i = 0; i < cells.length; i++) {
            cells[i] = 0;
        }
        cells[cells.length/2] = 1; 除了中间的细胞以状态1开始，其余所有细胞都从状态0开始
      }
    void generate() {
        int[] nextgen = new int[cells.length]; 计算下一代状态
        for (int i = 1; i < cells.length-1; i++) {
            int left = cells[i-1];
            int me = cells[i];
            int right = cells[i+1];
            nextgen[i] = rules(left, me, right);
        }
      cells = nextgen;
      }
    int rules (int a, int b, int c) { 在规则集中查询新状态
        String s = "" + a + b + c;
        int index = Integer.parseInt(s,2);
        return ruleset[index];
      }
}

7.3 如何编写初等细胞自动机