16

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

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

非常感谢

4

2 回答 2

7

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

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

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

于 2009-09-26T23:32:42.787 回答
6

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

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

于 2009-09-26T23:31:03.103 回答