优化康威生命游戏

Question

我正忙于编写康威生命游戏，并尝试使用一些数据结构来优化它，记录每个生命周期应该检查哪些单元格。

我正在使用一个动态的ArrayList作为数据结构来记录所有活着的单元格及其邻居。有没有更好的数据结构或方法来保持更短的列表，以增加游戏速度？

我问这个问题是因为经常会检查很多单元格，但没有发生变化，所以我觉得我的实现可以改进。

- Gottfried

---

对于不熟悉的人来说，添加一个指向“康威生命游戏”的链接可能会很有帮助，或者至少很有趣。 - Jordan

我几年前看到过一种使用LinkedList实现的非常快速的方法，但不幸的是我没有详细信息。它在一本旧的Sam编程书中。 - Kon

我认为具有4个指向其他节点的指针的节点可能非常快。 - progrenhard

不管你做什么，尝试一下这个。超越大多数人盲目尝试并希望取得最佳效果的方式。 - Mike Dunlavey

你可以使用BitSet来标记活细胞，这样可以一次跳过64个非活细胞。你可以为细胞添加前向和后向链接，避免辅助列表的开销。你可以采用Hashlife的思想，忘记低级别的优化。 - maaartinus

Answer 1

我相信Hashlife算法能够帮助你。

它提出了使用四叉树（一种树形数据结构，每个内部节点恰好有四个子节点）来存储数据，并使用哈希表来存储四叉树节点的想法。

如需更多阅读材料，请参考Eric Burnett撰写的这篇文章，详细讲解了Hashlife的工作原理、性能和实现方法（虽然是基于Python编写）。值得一读。

- Natan Streppel

---

为什么需要使用哈希表来存储叶子？四叉树可以被实现为“树”，非常美观，不需要哈希。 - Ira Baxter

@progenhard：不是的。关键是你可以缓存整个子树的结果，这是一个巨大的收益。 - maaartinus

我认为四叉树编码和莫尔斯曲线更快，同时也能以良好的空间质量减少维度。 - Micromega

@Ira Baxter：不，这些数字来自于网上，并且（在某种程度上）证明了你所说的话是错误的。在Dr. Dobb's中有一个很好的解释说明了它的工作原理。 - maaartinus

@Ira Baxter：四叉树的最小叶子节点为1x1，除了两个例外，其余都是重复的（因为只有两个唯一实例）。Hashlife自上而下地查找已计算的部分，所以如果你幸运的话，可以节省很多工作。此外，块越大，它允许保存的未来距离就越远，这可能会导致巨大的加速。 - maaartinus

Answer 2

我在20世纪70年代使用2Mhz 6800 8位计算机构建了一个生命引擎，直接映射到屏幕像素的256x512位网格上。我直接在显示像素上进行操作（它们是一位开/关白色/黑色），因为我想看到结果，而不认为将Life图像复制到显示器上有意义。

它的基本技巧是将问题视为根据生命规则评估“此单元格是否打开”布尔逻辑公式的问题，而不是像通常那样计算活着的邻居数量。这个公式很容易解决，所以留作家庭作业练习。使它快速的是，布尔公式是按位计算的，每次处理8位。如果您在屏幕上向下扫过并横跨行，您实际上可以同时评估N位（6800上的8位，现代PC上的64位），开销非常低。如果你疯狂起来，你可能会使用SIMD向量扩展，一次处理256位或更多位。超出极限的是使用GPU完成此操作。

6800版本将在约0.5秒内处理完整个屏幕；您可以看到更新从顶部到底部波动（60 Hz刷新）。在具有1000倍时钟速率（1 GHz很容易获得）和每次处理64位的现代CPU上，它应该能够产生数千帧每秒。跑得太快了，你看不到它运行 :-{

一个有用的观察是，大部分生命世界都是空白的，处理这部分主要会产生更多的死细胞。这表明使用稀疏表示。另一篇文章建议使用四叉树，我认为这是一个非常好的建议。您的四叉树区域也不必是正方形。

将两个想法结合起来，对于由四叉树指定的位块进行按位处理的四叉树非空白区域可能会提供惊人的快速Life算法。

- Ira Baxter