书名:代码本色:用编程模拟自然系统
作者:Daniel Shiffman
译者:周晗彬
ISBN:978-7-115-36947-5
第7章目录
7.6 生命游戏
- 二维CA
- 二维CA会引入额外的复杂度:每个细胞将有更多邻居,同时也为更多的应用场景开启了大门。毕竟,计算机图形学的大部分应用都是二维的,而本章将展示如何把CA思想应用到Sketch的图形绘制中。
1、生命游戏
- 在20世纪70年代,马丁· 加德纳在《科学美国人》杂志上写了一篇文章,其中引用了数学家约翰·康威的新“生命游戏”模型,并称之为“娱乐”的数学
- 现在,生命游戏早已经成为陈词滥调(有无数项目专门把生命游戏模型显示在各种屏幕上)。呵呵,学习PASCAL时第一个大程序就是生命游戏。
- 但我们仍有必要从头开始构建“生命游戏”模型,因为它让我们有机会实践各种编程技术,如二维数组及面向对象编程。
- 更重要的是,它的核心原理直接关系到我们的最终目标——用代码模拟大自然。
- 虽然我们不喜欢复制别人的实现方式,但这些实现背后的算法和技术将为我们提供更多灵感和基础,有助于我们以后模拟生物繁殖的特性和行为。
2、康威的模型
冯·诺依曼喜欢用非常复杂的状态和规则描述问题,约翰·康威则有所不同,他喜欢用最简单的规则实现“类生命”系统。
马丁·加德纳在《科学美国人》概述了康威的论点:
- (1)没有初始模式可以很简单地证明个体数量能无限制增长。
- (2)存在某种可以无限制增长的初始模式。
- (3)存在某种简单的初始模式,在数次迭代之后,最终变成3种可能情况:
完全消失(由于过于拥挤或者松散)、
固定下来保持不变,
或者进入以一定周期不断重复循环的振荡阶段。
上面的文字从本质上描述了Wolfram提出的4种CA分类。CA应该有固定的模式,但这种模式是无法预测的,随着时间推进,它最终会进入统一或来回交替的状态。也就是说,康威的模型拥有复杂系统的所有特性,尽管他当时没有使用这个术语。
3、生命游戏的工作原理
- 首先,我们要面对的是一个二维细胞矩阵,而不是一行细胞。
对于初等CA模型,每个细胞可能的状态都是0或1。
在本例中,我们讨论的是“生命”的游戏,因此0代表“死亡”,1代表“活着”。 -
细胞的邻居也被扩展了。如果邻居是相邻的细胞,现在我们有9个邻居细胞,而非原先的3个。
- 在只有3个邻居的情况下,状态组合可以用一个3位的二进制数表示,也就是8种可能的组合。现在有9个邻居细胞,对应9位的二进制数,也就是512种可能的状态组合。
- 在大多数情况下,为这512种组合分别定义结果是不可行的。生命游戏根据邻居的一般特征制定了一套规则,从而克服了这一问题。
4、生存规则
生命游戏的生存规则类似于以下问题:周围的个体数量是否过剩,是否被死亡的个体包围,还是刚刚好?
- 1.死亡
如果某个细胞处于“活着”状态(状态为1),在以下情况下,将会变成“死
亡”状态(状态变为0)。
-- 群体过剩: 如果细胞有4个及以上的邻居处于“活着”状态,则该细胞死亡。
-- 孤独: 如果“活着”的邻居数量等于或少于1个,则细胞死亡。 - 2.新生
处于“死亡”状态(状态为0)的细胞,如果它周围刚好有3个“活着”的邻居,
则它也会变为“活着”状态。 -
3.静止
在其他情况下,细胞的状态保持不变。让我们列举所有这样的场景。
-- 保持“活着”: 如果细胞是“活着”的,而且周围有2个或3个活着的邻居,它将继续“活着”。
-- 保持“死亡”: 如果细胞是“死亡”的,而且周围“活着”的邻居数不等于3,它将继续保持“死亡”状态。
5、展示(可视化)
- 在初等CA中,我们将每次迭代的细胞状态堆叠在一起,形成一个二维网格。
- 然而,在生命游戏中,CA本身就是二维的。同样地,我们可以把每一次迭代用立体结构堆叠在一起,形成一个三维的CA可视化视图。
- 但对生命游戏而言,典型的可视化方式是用一帧动画表示一次迭代。
因此,在某一时刻,我们只能看到一次迭代的细胞状态,而无法看到所有迭代的状态,整个运行结果看起来像是培养皿中快速生长的细菌。
6、有趣的特性
生命游戏具有一个有趣的特性:某些初始图案能带来奇妙的结果。
-
以下图案在迭代中保持静止,不会发生任何改变。
-
以下图案将会在两个状态之间交替出现:
-
也有一些图案,会在迭代过程中发生移动。(需要注意的是:我们看到的图案移动是细胞生死交替产生的视觉结果,细胞本身并没有发生移动。)
如果你对这些图案感兴趣,网上有很多“开箱即用”的生命游戏演示程序,你可以在里面设置CA的初始状态,观察它在各种速度下的运行效果。
Exploring Emergence(http://llk.media.mit.edu/projects/emergence/),
开发者是麻省理工学院媒体实验室Lifelong Kindergarten小组的Mitchel Resnick和Brian Silverman;
Conway's Game of Life (http://stevenklise.github.com/ConwaysGameOfLife),
开发者是Steven Klise,开发工具是Processing.js!
网友评论