如何模拟大规模的元胞自动机？

Question

以Minecraft中的红石为例 - 它基本上是一个具有15种状态的元胞自动机，其基本规则如下：

Redstone -> Redstone, powered of level Max(neighbours)-1

以及各种相关元素的附加规则

Repeater, inactive -> Repeater, active, level 2 if its input is powered
Repeater, active, level 2 -> Repeater, active, level 1
Repeater, active, level 1 -> Repeater, inactive
Redstone, unpowered -> Redstone, powered if there is a neighbouring Repeater, level 1 or another source

我已经写了更多关于如何使用CAs实现Minecraft物品的内容：http://madflame991.blogspot.com/2011/10/cellular-automata-in-minecraft.html 现在，我的问题是：游戏如何管理更新庞大的红石装置？它使用什么数据结构？它是否真正作为细胞自动机实现？如果不是，那么你的最佳猜测是什么？

附言：我并不要求任何人窥探实际源代码，只是猜测这个技术问题是如何实现的。……而且我把这个问题发布在此处，而不是在gamedev上，因为这是一个CA问题，而不是一个gamedev相关的问题。

- adrianton3

---

这是你的一篇很棒的博客文章。我特别喜欢玩光级模拟器，并看到变化通过矩阵传播。 - Li-aung Yip

Answer 1

另一种模拟 令人难以置信的大规模细胞自动机（例如生命游戏中的生命游戏）的可能方法是检测模式（滑翔机、滑翔机生成器等），预测它们的未来演化并仅计算未知部分（滑翔机演化）。

- OB1

---

Hashlife基本上就是这样做的，但是它可以适用于任何规则，基本上是自动检测重复模式。 - masterxilo

Answer 2

Hashlife (1) 可以加速计算超大空间的运算，这可能是您所需要的。

- Jean-Baptiste Yunès

---

http://golly.sourceforge.net/ 实现了 hashlife 算法，同时也有一个应用程序 https://play.google.com/store/apps/details?id=net.sf.golly - masterxilo

Answer 3

一种明显的方法是将世界划分成块（嘿，Minecraft已经这样做了！），并将每个块分配给一个服务器。每个服务器负责处理该块的更新，并与负责相邻块的服务器通信，向它们传播状态。

对于这样的细胞自动机，每个块都必须将其边缘单元格的当前状态与所有相邻块进行通信，反之亦然，然后才能增加时间步长。请注意，随着块大小的增大，通信开销会减少，因为块面积随O（n ^ 2）增长，而周长只随O（n）增长。

事实上，我怀疑你会发现它不那么同步，每个块异步地模拟其中的红石，仅在发生事件时向相邻块传输更新，并且不尝试与其他人保持同步。

- Nick Johnson

---

我更倾向于相信，当红石电路的任何元素改变状态时，Minecraft只会将更改传播到直接相邻的区块，而不考虑区块边界。 - Li-aung Yip

@Li-aungYip 你说得对，当然 - 我一直在想这个虚构的分布式Minecraft客户端。我怀疑它仍然是异步的。 - Nick Johnson

实际上，（纯）红石由于传播距离在15个方块之后需要一个中继器，因此被有效地“分块”。这限制了任何时刻需要完成的工作量。 - Li-aung Yip