Accretor 4D元胞自动机

埃尔文·德里森斯(Erwin Driessens)和玛丽亚·弗斯塔彭(Maria Verstappen)是合作的荷兰艺术家，自1990年以来一直在一起工作，创作了各种各样有趣的作品。

他们其中一个更吸引人的项目是Accretor，在这个项目中，他们使用细胞自动机和3D打印来创建如下所示的物理对象；

他们在这里提供了一些信息，这些信息链接到本文，提供了更多关于他们的过程的提示，但还不足以让我自己实现细胞自动机。然后我给欧文发了电子邮件，他很友好地澄清了他使用的规则。谢谢欧文。

这篇文章的其余部分介绍了我对Accretor细胞自动机的解释和实验。

通过使用5x5x5随机单元格网格播种空3D网格的中间来启动CA。

最初的Accretor每个单元使用2或3个状态，但我一直在试验每个单元最多5个状态。扩展到更多的细胞是可能的，也是未来尝试的事情。

使用随机细胞种子允许所得到的结构以更不均匀的方式生长。

CA规则使用以下维数的4维数组Rule[0..4，0..6，0..12，0..8]，其对应于[当前小区状态，面邻居计数，边邻居计数，角邻居计数]

对于stateloop：=0到(maxStates-1)，对于faceloop：=0到6，对于edeloop：=0到12，对于角循环，确实开始：=0到8，如果随机<；0.2，则规则[stateloop，faceloop，edgloop，cornerloop]：=Random(MaxStates)，否则规则[stateloop，faceloop，edgloop，cornerloop]：=0；end；end；

上面的IF RANDOM<；0.2给出了设置规则数组条目的20%的可能性。这使得规则数组成为填充的“密度”的1/5。我发现，如果规则数组太密集，则结果结构往往过于“杂乱无章”，没有那么有趣的结果结构。我最终测试了各种概率，最后允许用户配置填充百分比值。

在CA的每个步骤，如下更新空单元(跳过已经具有活动的非状态0单元的单元)；

此方法不是将26个3D相邻单元计为一组并使用该总数(3D CA通常是这种情况)，而是将26个相邻单元分成3组：面、边和角。请参阅下面的代码以了解面、边和角是如何计算的。

2.如果空单元格不与邻居共享至少一个面，则停止处理该单元格，并转到下一个单元格。只需简单的If FaceCount<；1 THEN CONTINUE检查即可。这样可以确保最终的结构完全连接，而不会在其对角处“连接”单元格。它还确保可以3D打印得到的结构。

3.使用规则数组更新新单元格状态(与任何CA一样，您可以为新单元格状态使用临时数组，以便同时更新所有单元格)；

4.必要时重复。当CA结构到达3D阵列/网格的边缘时，我会自动停止。

对于z：=1到z单元格，y：=1到y单元格从x：=1开始到x：=1到x单元格确实开始单元格状态：=c3d[x，y，z]；t3d[x，y，z]：=cell state；//如果cell state=0，则只处理空单元格//计算相邻单元格面计数：=0；//faces if c3d[x，y，z-1]>；0则为Inc(Facecount)；如果c3d[x，y，z-1]>；0，则为Inc(Facecount)；如果c3d[。如果c3d[x，y+1，z]>；0，则Inc(Faceccount)；如果c3d[x+1，y，z]>；0，则Inc(Faceccount)；如果c3d[x-1，y，z]>；0，则Inc(Facecount)；//如果facecount>；0，则必须至少有一个面接触如果faceccount>；0，则开始EdgeCount：=0；如果c3d[x，y+1，z]>；0，则必须至少有一个面接触；如果c3d[x+1，y，z]>；0，则开始EdgeCount：=0；如果c3d[x-1，y，z-1]>；0则Inc(Edgecount)；如果c3d[x+1，y，z-1]>；0则Inc(Edgecount)；如果c3d[x，y+1，z-1]>；0则Inc(Edgecount)；如果c3d[x-1，y-1，z]>；0则Inc(Edgecount)；如果c3d[x+1，y，z-1]>；0，则Inc(Edgecount)；如果c3d[x+1，y，z-1]>；0，则Inc(Edgecount)；0则Inc(Edgecount)；如果c3d[x+1，y+1，z]>；0，则Inc(Edgecount)；如果c3d[x，y-1，z+1]>；0，则Inc(Edgecount)；如果c3d[x-1，y，z+1]>；0，则Inc(Edgecount)；如果c3d[x+1，y，z+1]>；//角点如果c3d[x-1，y-1，z-1]>；0则Inc(角计数)；如果c3d[x+1，y-1，z-1]>；0则Inc(角计数)；如果c3d[x-1，y+1，z-1]>；0则Inc(角计数)；如果c3d[x+1，y+1，z-1]>；0则Inc(角计数)；If c3d[x+1，y-1，z+1]>；0 Then Inc(角计数)；If c3d[x-1，y+1，z+1]>；0 Then Inc(角计数)；If c3d[x+1，y+1，z+1]>；0 Then Inc(角计数)；//更新临时CA数组t3d[x，y，z]：=Rule[cell state，faceount，edgecount

如果我的数学是正确的，使用具有3个状态(0、1和2)、6个面、12条边和8个角的规则可以得出3^2457(2457=3*7*13*9)个可能的规则。一个巨大的搜索空间，可以在其中找到有趣的规则。7而不是6，因为0也是可能的面数，因此0、1、2、3、4、5和6是可能的面邻居数。

这大约是1.9×10^1172。如果估计地球上的沙粒只有7.5x10^18，而人体内的原子是7x10^27，那么这个10^1172是大得离谱的。如果写出来的话就是。

多次单击随机规则按钮以查看是否出现了有趣的结果，很快就会变得非常无聊。寻找好的规则就像谚语所说的大海捞针，尽管在这种情况下，大海捞针要比普通的大海捞针大得多。

搜索涉及遍历多个随机规则，以寻找可能感兴趣的结果。搜索结果可以归类为多种“类别”；

1.停滞不前。这些规则导致最初的小种子根本不生长，或者只长了几个步骤，然后就停止了。这些将被忽略且不会保存。

2.从起始种子开始呈小直线生长。这些被归类为“无聊”。一旦增长到达网格的边缘，就可以通过检查活动单元格计数与网格大小来检测它们，如果小于0.5%，则认为规则很无聊。

3.八面体形状。许多由此产生的结构填充了一个八面体形状的区域。在搜索开始之前，生成已知可创建八面体形状的规则，并记住活动单元格计数。在生成随机规则时，如果单元格计数在+/-20%的八面体计数范围内，则将其分类为八面体，并将其放入单独的文件夹中。

4.球体形状。另一个常见的结果是。在搜索开始之前，生成已知可创建球形形状的规则，并记住活动单元格计数。在生成随机规则时，如果单元格计数在+/-20%范围内，则球体计数会将其分类为球体，并将其放入单独的文件夹中。

5.生长缓慢。欧文观察到，有趣的规则往往是种植速度慢的人。检查缓慢增长的一种简单方法是计算CA到达网格边缘所需的步骤。如果步骤数大于网格大小乘以3，则认为该规则增长缓慢，并将其保存到单独的文件夹中。

6.其余的。如果随机规则通过了上述所有检查，则认为有可能。保存参数和样本图像以供将来检查。

并不是所有上述分类器都是防弹的、100%可靠的，因此您会得到一些错误的分类结果。单独进行活跃细胞计数并不是最准确的分类方法，但它似乎确实导致了对不想要的结果的普遍剔除。

在让搜索运行几个小时或一夜之后，您回来快速扫描一下结果目录，看看是否有任何可能的好规则值得进一步研究。一旦你有了一堆看起来不错的可能的规则，它们就可以以更大的网格大小以更好的质量呈现出来。我已经包括了搜索功能与混沌的愿景，所以你也可以狩猎有趣的规则，如果你愿意，如果你这样做，让我知道如果你发现任何有趣的规则。

使用立方体或球体渲染栅格单元。OpenGL可以用于快速测试渲染，但缺少适当的阴影和环境光遮挡可能会使查看实际结构变得困难。

就像一段时间以来的情况一样，我更喜欢使用最优秀的三菱渲染器。还支持Pixar的RenderMan。

立方体栅格也可以导出为Wavefront OBJ文件，以便在其他3D程序(如Blender、Maya、Cinema 4D等)中导入和渲染。

下面是使用本文描述的方法生成的CA的4K样例电影。

使用规则数组意味着不能有用户可以选中/取消选中以手动设置规则的一系列复选框。为了使用户可设置“规则”，我使用随机数生成器种子值作为规则编号。例如，将规则编号设置为1234会在使用随机值填充规则数组之前将伪随机生成器种子设置为1234。这允许相同的步骤是可重复的，并且相同的规则可以再次运行。然而，它不允许我轻易地与他人分享好的规则。例如，如果您编写了自己版本的Accretor CA(我鼓励任何使用CA的人都可以尝试)，那么您的语言的伪随机生成器可能不会使用与我的代码相同的代码，因此您会得到与我的不同的结果。你会得到你自己独特的结果，但我们不能分享有趣的规则。我在实现体素自动机地形时也遇到了同样的问题。

使用随机数生成器作为阵列种子的另一个问题是可以生成的随机数序列数量有限。在我的例子中，伪随机生成器(线性同余生成器)接受一个32位整数值的种子值。这意味着我最多只能生成和检查4,294,967,296条可能的随机规则。4,294,967,296看起来可能很多，但它只占整个可能的规则空间的一小部分，从统计学上讲，您会认为使用随机数生成器播种会遗漏一些其他有趣的规则。

在开始之前，计算包含每个单元格到栅格中心的距离的数组。这节省了循环期间昂贵的SQRT计算。我使用距离数组计算出离网格中心最远的单元格是什么，它允许在生成过程中提供完成百分比统计数据。

当新的单元格激活时，使用其位置更新最小/最大x、y和z变量。像这样的东西；

然后，当循环3D网格的每一步时，您只需要从zmin循环到zmax，从ymin循环到ymax，再从xmin循环到xmax。当最初的增长结构很小时，这有助于加快速度。当一个新的细胞没有机会在那里诞生时，就没有点在空格的其余部分中循环。

将邻居扩展到相邻的26个小区之外。看看是否会出现更复杂的结构。

有关Accretor细胞自动机2D版本的实验结果，请参阅此博客文章。