c - hashlife alg 如何在 Golly 永远持续下去？

Question

In hashlife the field is typically treated as a theoretically infinite grid, with the pattern in question centered near the origin. A quadtree is used to represent the field. Given a square of 2^(2k) cells, 2k on a side, at the kth level of the tree, the hash table stores the 2^(k-1) by 2^(k-1) square of cells in the center, 2^(k-2) generations in the future. For example, for a 4x4 square it stores the 2x2 center, 1 generation forward; and for an 8x8 square it stores the 4x4 center, 2 generations forward.

因此，给定一个 8x8 的初始配置，我们得到一个 4x4 正方形的第 1 代前向中心 w.r.t. 8x8 正方形和 2x2 正方形向前 2 代(第 1 代向前 w.r.t 4x4 正方形)以 8x8 正方形为中心。随着每一代新人的出现，我们对网格的看法都会减少，反过来我们会得到自动机的下一个状态。在将最里面的 2x2 正方形 2^(k-2) 代向前移动后，我们不能再进一步了。

那么 Golly 的 hashlife 是如何永远持续下去的呢？此外，它对该领域的看法似乎从未减少。它似乎显示了整个自动机在 2^(k-2) 代之后的状态。更重要的是，给定一个随时间扩展的起始配置，算法的 View 似乎会增加。 GridView 缩小以显示扩展的自动机？

Answer 1

有一个 good article on Dr. Dobb's其中详细介绍了 HashLife 的工作原理。基本答案是，您不仅要在现有节点上运行算法，还要使用新的移位节点来获得下一代。