另一个生命游戏问题(无限网格)？

Question

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

我无法理解的一件事是编码器如何实现无限网格？我们无法保持无限的任何东西,如果你跑得很好并且让几个滑翔机飞过边缘,等待几分钟然后向外缩放,你会看到滑翔机仍在那里空间逃跑,所以在神的名字中如何以编程方式处理这个无限的概念？是否存在记录良好的模式或什么？

非常感谢

Answer 1

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

这个解决方案不适用于生命节点数量不断增加的状态,但它对滑翔机非常有效.

编辑:所以这是我的头脑.事实证明,维基百科有一篇文章,展示了一个更深思熟虑的解决方案.那好吧!:) 请享用.

Answer 2

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

由于存在局部性,您可以在不同的部分中分隔字段并独立模拟每个部分.如果你选择好你的地方,你会经常看到相同的模式.您可以模拟这些进展并将结果存储在查找表中,以便不需要多次模拟同一模式的其他实例.将相邻模式组合成更大的"元模式"允许您预先计算这些模式,等等.