hashlife 算法如何在 Golly 中永远持续下去？
在 hashlife 中，该字段通常被视为理论上的无限网格，所讨论的模式以原点附近为中心。四叉树用于表示字段。给定一个由 2^(2k) 个单元格组成的正方形，边长为 2k，在树的第 k 层，哈希表在中心存储 2^(k-1) x 2^(k-1) 个单元格的正方形，未来2^(k-2)代。例如，对于 4x4 的正方形，它存储 2x2 中心，向前 1 代；对于 8x8 的正方形，它存储 4x4 的中心，向前 2 代。
因此，给定 8x8 初始配置，我们得到一个以 8x8 正方形为中心的 4x4 正方形 1 代前向中心，以及以 8x8 正方形为中心的 2x2 正方形 2 代前向（4x4 正方形的第一代前向）。随着每一代新人的诞生，我们对网格的看法都会减少，反过来我们也会得到自动机的下一个状态。在得到最里面的 2x2 平方 2^(k-2) 代之后，我们不能再继续了。
那么 Golly 中的哈希生活是如何永远持续下去的呢？而且它的视野似乎从未减少。它似乎显示了2^(k-2)代后整个自动机的状态。更重要的是，考虑到初始配置会随着时间的推移而扩展，算法的视野似乎会增加。网格视图缩小以显示扩展的自动机？
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.
So given a 8x8 initial configuration we get a 4x4 square 1 generation forward centered w.r.t. the 8x8 square and a 2x2 square 2 generations forward (1 generation forward w.r.t the 4x4 square) centered w.r.t the 8x8 square. With every new generation our view of the grid reduces, in-turn we get the next state of the automata. We canot go any further after getting the inner most 2x2 square 2^(k-2) generations forward.
So how does the hashlife in Golly go on forever? Also its view of the field never seems to reduce. It seems to show the state of the whole automata after 2^(k-2) generations. More so given a starting configuration which expands with time, the view of the algorithm seems to increase. The view of the grid zooms out to show the expanding automata?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
有一篇关于 Dobb 博士的好文章，其中详细介绍了 HashLife作品。基本答案是，您不仅在现有节点上运行算法，还使用新的移位节点来获得下一代。
There's a good article on Dr. Dobb's which goes into detail about how HashLife works. The basic answer is that you don't merely run the algorithm on the existing nodes, you also use new shifted nodes to get the next generation.
为了清楚起见（因为您的 ^ 符号丢失），您要问：
不要从 8x8 图案开始，而是想象一下您从一个更大图案开始，而该图案恰好包含您的 8x8 图案。例如，您可以从 16x16 图案开始，其中 8x8 图案位于中心，边缘周围有 4 行空白单元格。通过将空白 4x4 节点与 8x8 起始模式的 4x4 子节点组装在一起，可以轻松构建这样的模式。
给定这样一个 16x16 的模式，HashLife 算法可以给你一个 8x8 的答案，未来 4 代。
你想要更多吗？好的，从 32x32 图案开始，其中大部分为空白，8x8 图案位于中心。这样你就可以获得未来 8 代的 16x16 答案。
如果您的图案包含移动物体，其移动速度足够快，以至于在 8 代后超出了 16x16 区域，该怎么办？很简单——从 64x64 启动模式开始，但不要尝试运行整个 16 代，而是运行 8 代。
一般来说，在任意长的时间内，所有任意大的、可能扩展的模式的情况都可以通过添加尽可能多的值来处理（事实上在 Golly 中都可以处理）根据需要在图案外部周围留出空白。
To be clear (because your ^ symbols were missing), you are asking:
Instead of starting with your 8x8 pattern, imagine instead that you start with a bigger pattern that happens to contain your 8x8 pattern inside it. For example, you could start with a 16x16 pattern that has your 8x8 pattern in the center, and a 4-row margin of blank cells all around the edges. Such a pattern is easy to construct, by assembling blank 4x4 nodes with the 4x4 subnodes of your 8x8 start pattern.
Given such a 16x16 pattern, the HashLife algorithm can give you an 8x8 answer, 4 generations in the future.
You want more? Okay, start with a 32x32 pattern that contains mostly blank space, with the 8x8 pattern in the center. With this you can get a 16x16 answer that is 8 generations into the future.
What if your pattern contains moving objects that move fast enough that they go outside that 16x16 area after 8 generations? Simple -- start with a 64x64 start pattern, but instead of trying to run it for a whole 16 generations, just run it for 8 generations.
In general, all cases of arbitrarily large, possibly expanding patterns, over arbitrarily long periods of time, can be handled (and in fact are handled in Golly) by adding as much blank space as needed around the outside of the pattern.
居中的方块只是预先计算的东西。该算法确实始终保留整个宇宙并更新其所有部分，而不仅仅是中心。
The centered squares are only the precomputed stuff. The algorithm indeed keeps the whole universe at all times and updates all parts of it, not just the centers.