另一个生命游戏问题（无限网格）？
我一直在玩 Conway 的生命游戏，最近发现了一些令人惊讶的快速实现，例如 Hashlife 和 Golly。 （在这里下载 Golly - http://golly.sourceforge.net/）
有一件事我无法理解围绕的是程序员如何实现无限网格？我们不能保持任何东西的无限阵列，如果你运行天哪，让几架滑翔机飞过边缘，等待几分钟并向右缩小，你会看到滑翔机仍然在太空中逃跑，那么，以上帝的名义，这个无穷大的概念是如何以编程方式处理的呢？是否有一个记录良好的模式或什么？
非常感谢
I have been playing around with Conway's Game of life and recently discovered some amazingly fast implementations such as Hashlife and Golly. (download Golly here - http://golly.sourceforge.net/)
One thing that I cant get my head around is how do coders implement the infinite grid? We can't keep an infinite array of anything, if you run golly and get a few gliders to fly off past the edges, wait for a few mins and zoom right out, you will see the gliders still there out in space running away, so how in gods name is this concept of infinity dealt with programmatically? Is there a well documented pattern or what?
Many thanks
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
维基百科对此进行了解释。
基本思想是康威的生命游戏表现出局域性，因为与图案大小相比，信息传播的速度较慢，并且填充单元的最大密度约为任何区域中单元的 1/2。 （更多会因过度拥挤而杀死细胞。）
由于存在局部性，因此您可以将场分成不同的部分并独立模拟每个部分。如果你选择得当，你经常会看到相同的模式。您可以模拟它们的演变方式并将结果存储在查找表中，这样同一模式的其他实例就不需要多次模拟。将相邻模式组合成更大的“元模式”还可以让您预先计算这些模式，等等。
Wikipedia explains it.
The basic idea is that Conway's Game of Life exhibits locality, since information travels at a slow speed compared to the pattern size and the maximum density of filled cells is around 1/2 of the cells in any region. (More will kill off cells due to overcrowding.)
Since there is locality, you can separate the field in different sections and simulate each section independently. If you choose your locality well, you will often see the same patterns. You can simulate how those evolve and store the results in a lookup table, so that other instances of the same pattern do not need to be simulated more than once. Combining adjacent patterns into larger 'metapatterns' allows you to precalculate those as well, and so on.
在这种情况下，可以用某种类型的稀疏矩阵来表示活动节点。例如，如果我们存储一个
(LivingNode, Cooperative) 对列表，而不是一个Nodes数组，其中每个节点要么是活的，要么是死的，那么我们只需更改>坐标而不是增加数组的大小。因此，所需的空间与LivingNodes的数量成正比。该解决方案不适用于活动节点数量不断增加的状态，但对于滑翔机来说非常有效。
编辑：所以这就是我的想法。结果维基百科有一篇文章展示了一个经过深思熟虑的解决方案。那好吧！ ：） 享受。
It is possible to represent living nodes with some type of sparse matrix in this situation. For instance, if we store a list of
(LivingNode, Coordinate)pairs instead of an array ofNodeswhere each is either living or dead, we are simply changing theCoordinatesrather than increasing an array's size. Thus, the space required for this is proportional to the number ofLivingNodes.This solution doesn't work for states where the number of living nodes is constantly increasing, but it works very well for gliders.
EDIT: So that was off the top of my head. Turns out Wikipedia has an article that shows a much more well-thought out solution. Oh well! :) Enjoy.