问优化康威人生游戏

EN

我相信Hashlife算法可以帮助你。

它给出了使用四叉树 (树数据结构，每个内部节点恰好有四个子节点)来保存数据的思想，然后使用哈希表存储四叉树的节点。

为了进一步阅读，Eric编写的这个职位给出了关于Hashlife如何工作、它的性能和实现(虽然是用Python编写)的深刻见解。值得一读。

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

它的基本技巧是把这个问题作为一个基于“生活规则”的“这个单元格是基于”的布尔逻辑公式来处理，而不是像往常一样计算活的邻居。这个公式很容易找出来，所以把它当作家庭作业练习。使它更快的是，布尔公式是在每比特的基础上计算出来的，一次做8位。如果你扫下屏幕，跨越行，你就可以一次计算N位( 6800上的8位，现代PC上的64位)，并且开销很低。如果你发疯了，你可能会使用SIMD矢量扩展，在“一次”时执行256位或更多的操作。在顶部使用GPU就可以做到这一点。

6800版本将在大约.5秒内处理一个完整的屏幕；您可以看到从上到下屏幕上的更新(60 Hz刷新)。在具有1000倍时钟速率(1 GHz相当容易获得)和64位一次的现代CPU上，它应该能够每秒产生数千帧。太快了，你不能看它跑-{

一个有用的观察是，大部分的生命世界是死亡的(空白)，处理这部分主要产生更多的死细胞。这建议使用稀疏表示。另一张海报建议使用四叉树，我认为这是一个很好的建议。你的四叉树区域也不必是正方形的。

结合这两种思想，对于非空白区域的四叉树和由四叉树指定的比特块进行比特级处理，可能会给出一种惊人的快速生命算法。