元胞自动机的算法在模拟植物上的实验探究.ppt

元胞自动机的算法在模拟植物上的实验探究 广州市第一一三中学 初一（3）班 胡定均 胡圣和 一、元胞自动机的简介 元胞自动机简称CA(Cellular Automaton），是一种时间和空间都离散的动力系统。 元胞自动机具有广阔的应用范围，它的应用领域涉及社会学、生态学、信息科学、计算机科学、数学、物理学、化学、地理、环境、军事学、生物学等。 元胞自动机能够根据给定的算法进行各种模拟实验，是一个非常有效的模型工具。根据简单的一个算法，大量元胞通过简单的相互作用而构成动态系统的演化。 二、本项目的研究目的 我们想要自己动手实现一个模拟生命的元胞自动机，通过设定不同的环境参数，以及不同的植物DNA来观察生命体的内部因素与环境的外部因素之间的相互影响。这个研究项目可以让我们更好地了解和学习元胞自动机的课题。 三、项目的开发 算法部分 算法部分是程序的核心部分。 算法单独开发与调试，最后在界面窗口上绘图。 界面部分 使用图形用户界面工具包开发，提供更便捷直观的操作功能。 通过规划，我们决定把整个项目分为两部分——算法部分和界面部分。 开发方式 使用面向对象程序设计的方法，先将整个程序分为算法、终端两大部分，再细分为算法类、空间类、控制面板类和窗体框架类。整个程序由不同的完全封装的类依次构成，这种方法能使程序开发更便捷灵活。 运用敏捷开发思想，逐步迭代程序版本，让程序在最短时间内实现基本功能，迭代的开发方式方便每个版本的功能递进。 算法各个迭代版本的更新 0.1 定义了基本的类的调用结构。空间类使用二维列表的数据结构承载多个植物对象的字符串状态（芽或者茎），并记录各植物的状态对应的RGB色值，输出供绘制的二维字符串列表；所有的植物继承于超类， 保存属于植物体的空间格子指针，并且Tree植物子类在重写的算法方法中实现了简单主芽生长的算法。 1.0 改进了植物类的生长算法。新增了防止植物体碰撞的算法，并使Tree子类实现了侧芽的分裂与生长算法。 一、点阵式数据存储 一、点阵式数据存储 1.1-1.2 优化了可以生长的空格子的筛选算法，使用了在每个芽生长后重新排查可生长的格子的算法。 1.3.1 此版本尝试加入重力影响因素，但未实现，原因是格子式的算法虽然简便易编写，却有局限性，不能计算需用斜率表示的生长方向。 二、树状数据结构式存储 2.1 从此版本开始，不再使用格子限定植物的生长，重新定义了数据结构。定义了树状数据结构，并且把原来的格子变成了节点。在空间类的存储也改为存储节点二维坐标系的坐标、生长方向（弧度）和父节点等重要数据。 2.2.1-2.2.2 改变了算法的模式。把一些重要的属性和特征放置在植物的“DNA”属性中，统一依照这些属性运行算法。主要的属性有生长的疏密度、枝干长度、侧芽生长角和侧芽分裂周期长度。其中侧芽生长角是指侧芽的生长方向和主芽生长方向的夹角的弧度。 二、树状数据结构式存储 2.2.3 加入了重力影响。使用了三角函数作为改变生长方向时旋转的算法。但是由于弧度的计算比较复杂，而此算法不会改变茎的生长长度，与最初的构想茎的生长方向较与反重力方向相近茎就较长不符，最后未完全成功。 2.3.1 改用平面向量表示方向。新建mathlib子库作为数学运算的一些基础函数，定义vector向量类，使用向量数学知识，重写向量类的python内置函数和操作符使用时调用的类的方法，使得向量类可以进行数学向量的基础运算，如取正、取负、相加、相减等运算。向量类除了可以用于表示方向的量，还可以表示节点的坐标，这个类给后面的向量叠加算法带来了很大的便利。 二、树状数据结构式存储 2.3.2 加入了重力的影响。重力是用平面向量表示的， 所以可以在算法中把反重力向量叠加， 产生影响。这样产生的效果是生长方向接近反重力方向的节点生长长度长， 反之则短。在这个版本也发现了生长疏密度的判断的问题，研究后发现需要使用矩阵来判断节点之间的线段是否相交，于是暂时取消生长疏密度的判断算法。 2.3.3 此版本加入了光的照射方向的影响，光的照射方向的表示方法与重力一样，所以直接在算法中叠加了反光照射方向向量。 界面各个迭代版本的更新 Main0.1：主程序实现了一个简单的窗口框架。 Main0.1：更新了程序框架，能够绘制图形。 Main0.3：开始导入算法，实现导入数据绘制的功能，尚未完全实现绘制功能。 Main0.4：实现了单帧播放的功能。 Main0.5：实现连续播放功能，优化绘制效果。 Main0.6：提高分辨率，加大规模测试 。 Main0.7：配合算法，改为节点绘制方法。 Main0.7.4：配合算法，改为向量绘制方法，拓展空间，增加重力和光源的调控功能。