algorithm - 另一个生命游戏问题（无限网格）？

Question

我一直在玩 Conway 的生命游戏，最近发现了一些非常快的实现，例如 Hashlife 和 Golly。（在这里下载 Golly - http://golly.sourceforge.net/）

我无法理解的一件事是编码人员如何实现无限网格？我们不能保留无限的任何东西，如果你跑得好，让几架滑翔机飞过边缘，等待几分钟并立即缩小，你会看到滑翔机仍然在太空中逃跑，那么以上帝的名义如何以编程方式处理这个无穷大的概念呢？是否有一个有据可查的模式或什么？

非常感谢

Answer 1

在这种情况下，可以用某种类型的稀疏矩阵来表示活节点。例如，如果我们存储一个(LivingNode, Coordinate)对的列表而不是一个数组，Nodes其中每个数组要么活着要么死，我们只是在改变Coordinates而不是增加数组的大小。因此，为此所需的空间与 的数量成正比LivingNodes。

该解决方案不适用于活节点数量不断增加的状态，但它对滑翔机非常有效。

编辑：所以这不是我的想法。原来维基百科有一篇文章展示了一个经过深思熟虑的解决方案。那好吧！：） 享受。

Answer 2

维基百科解释它。基本思想是康威的生命游戏展示了局部性，因为与图案大小相比，信息以较慢的速度传播，并且填充细胞的最大密度约为任何区域细胞的 1/2。（由于过度拥挤，更多会杀死细胞。）

由于存在局部性，您可以将字段分隔在不同的部分中，并独立模拟每个部分。如果你选择好你的位置，你会经常看到相同的模式。您可以模拟它们如何演变并将结果存储在查找表中，这样就不需要多次模拟相同模式的其他实例。将相邻的模式组合成更大的“元模式”允许您预先计算它们，等等。