如何编写初等细胞自动机
书名:代码本色:用编程模拟自然系统
作者: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];
}
}
共有 0 条评论