免费基于细胞自动机的生命活力模拟的实现

繁杂的，甚至是不可能解决的，但最重要的是在这个过程中，微分方程也失去了它的自身最重要的特性―精确性、连续性。甚至，我们可能因变数太多而根本无法得到合适的方程式，要么方程式本身极其复杂难以求解。
而对于细胞自动机来讲，脱离计算机环境来进行运算几乎是不可能的，但是借助计算机进行计算，却非常自然而合理，甚至它还是下一代并行计算机的原型。因此，在现代计算机的计算环境下，以细胞自动机为代表的离散计算方式在求解方面，尤其是动态系统模拟方面有着更大的优势。
因为细胞自动机的计算能力等价于图灵机，所以细胞自动机在理论上具备计算的完备性。但是，其满足特定目的的构模尚无完备的理论支持，其构造往往是一个直觉过程。用细胞自动机得到一个定量的结果非常困难，即便是可能的话，细胞自动机也将陷入一个尴尬，细胞自动机的状态、规则等构成必然会复杂化，从而不可避免地失去其简单、生动的特性。
然而，诚如物理学家玻尔所说，“相对的并不一定是矛盾的，有可能是相互补充和相互完善的”。二者互有优缺点，相互补充，都有其存在的理由。在现代计算机环境下，对于细胞自动机这一类相对来讲还处于幼年阶段的离散计算方式，需要予以更多的关注和支持。
并行与串行
前面说过，若从计算视角理解细胞自动机，则细胞自动机可能是下一代并行计算机的雏形。细胞自动机的出现，让人们更好的展望并行计算的前景。
生命游戏是一维细胞自动机的一个特例。它之所以能展现出这么复杂美妙的图形，是因为它的规则使他恰恰处于一个“混沌边缘”（一个介于周期状态和复杂随机状态的边界，下面还要详细论述这个现象）的状态。所以，下面，我们来介绍一下生命游戏。
1.4 生命游戏
生命游戏是由剑桥大学的数学家康维于 1970 年发表于《科学美国人》上的论文所提出的。理论上，它是一个二维细胞自动机。在这个细胞自动机中，细胞空间是一个分割成很多四方格子（类似棋盘）的平面，初始状态时，某些方格上存活着单个细胞。播种可以是随机的，也可以指定确定的模式，以便考察一些特殊的行为。每一个细胞有八个邻居，即采用摩尔邻居形式。这些细胞有两种状态：“生”或“死”，存活的细胞我们在方格内涂上特定单一的颜色，而死亡的细胞我们则不涂色。一个细胞的生死由其在该时刻本身的生死状态和周围八个邻居的状态决定，更确切的讲是周围八个邻居的状态的和决定。其规则叙述如下：
1 对于存活的细胞（涂色的方格）：当八个邻近细胞中只有零个或一个是活细胞时，则该细胞会因孤独而死亡；当八个邻近细胞中，恰有二或三个是活细胞时，则该细胞继续存活；当八个邻近细胞中，有四个或超过四个是活细胞时，则该细胞会因拥挤而死亡
2 对于死亡的细胞（未涂色的空方格）：当八个邻近细胞中，恰有三个是活细胞时，则该处诞生一个活细胞
生命游戏的演化规则近似地描述了生物群体的生存繁殖规律：在生命密度过小(相邻细胞数<2)时，由于孤单、缺乏配种繁殖机会、缺乏互助也会出现生命危机，细胞状态值由“生”变为“死”；在生命密度过大 (相邻细胞数>3)时，由于环境恶化、资源短缺以及相互竞争而出现生存危机，细胞状态值由“生”变为“死”；只有处于个体适中(相邻细胞数为2或3)位置的生物才能生存(保持细胞的状态值为“生”)和繁衍后代(细胞状态值由“死”变为“生”)。正由于它能够模拟生命活动中的生存、灭绝、竞争等等复杂现象，因而得名“生命游戏”。
尽管生命游戏的规则看上去很简单，但是它具有产生动态图案和动态结构的能力。它能产生丰富的、有趣的图案。生命游戏的游戏截图图3如下：

图3 生命游戏模拟图
运行这个程序的时候，我们发现，透过不同的设计，生命游戏可以展现无限的多样性。其演化结果与初始细胞状态值的分布有关，给定某个的初始状态分布，即随意的设置一些活着的细胞，经过若干步的运算，有时候它们会全部死亡，即变成全黑的图案，有时候则生成固定不动的图案，有时候生成翻滚不已的图案，有时候则得到周而复始重复的几个图案，更多的时候，是得到沸腾着的各种结构，有的图案蜿蜒而行，有的则保持图案定向移动，形似阅兵阵……，其中最为著名的是“滑翔机”的图案，即一小簇以常速滑过屏幕的活细胞，在四个世代的一个循环中，它沿着对角线的方向在方格上爬行，转换自己的位置，一个正方形向右，一个正方形向下，直到与其它结构相撞，产生出新的结构。
1970年康维在《科学美国人》杂志上发表了关于生命游戏的文章，并利用细胞自动机的一些现象，成功了构造了与、或、非等逻辑门，然后更进一步证明了生命游戏足以支持通用的计算，即这个细胞自动机具有通用图灵机的计算能力，与图灵机计算等价。也就是说给定适当的初始条件，生命游戏模型能够模拟任何一种计算机。
2 细胞自动机的程序算法实现
2.1 通用模块的设计
由于下面这几个算法的实现都有一些共同的特点：
1 需要一个二维的空间
2 在程序运行时，需要频繁的刷新绘图区域
3 运动的个体都是一些离散的个体
所以，我设计了一个通用的模块，实现下面的功能的时候，都是调用了这个模块。这个模块包含了两个部分：
（1）在二维空间上绘制离散的个体
（2）对这些离散个体的存储
另外，为了证明这个模块通用的程度，我利用这个模块轻易实现了贪吃蛇、五子棋等小游戏，证明了这个模块的功能确实超出了预期的设想。
下面介绍一下这个模块的组成。先看图4：

图4 生命游戏模拟图
观察黑色的绘图区域，我们就可以发现，要实现各种功能，我们首先要用一个数据结构来记录各种离散个体的信息，也就是布局，然后把这些离散信息绘制出来。
布局
布局相对来说比较简单。因为绘图区域是个二维图形。我们可以先创建一个int类型的二维数组cell，然后使二维数组的元素和对上面的每一个小区域一一对应起来。比如，某一个元素数值是 1 的话，那么就代表这个相应的区域存在一个个体，如果数值是 0 的话，就说明这块区域没有个体。我们可以先对这个数组进行处理，然后再一次性绘制出来。实践证明，这样的方法是可行的。由于程序是动态运行，也就是说，当前的数组状态须根据相应的规则，产生下一代的状态。所以，单单只有一个数组，没办法实现这个功能。所以，我定义了另外一个数组：workcopy 。这个数组保存的就是cell状态的一个备份。当需要演化时，我们逐个对cell上的个体进行判断，邻居在workcopy 上判断。修改直接体现在cell数组上。
绘制离散个体
离散的个体我们可以调用图形来，然后把它画在黑色的画布上。由于画布是个二维的矩阵，所以，要规整的在画布上布局这些个体，我们使用的图形必须是正方形的，并且，图形的背景要透明，看起来才比较自然。至于个体在画布上的擦除，我们可以采用对整个画布进行刷新的办法。但是这个方法不仅低效，而且程序运行的时候，整个画面非常闪烁，令人很不愉快。我采取了一个小技

首页上一页 1 2 3 4 5 6 7 下一页尾页 3/8/8

免费基于细胞自动机的生命活力模拟的实现(三)