I'm busy coding Conways Game of Life and I'm trying to optimise it using some data structure that records which cells should be checked on each life cycle.
I'm using an arrayList as a dynamic data structure to keep a record of all living cells and their neighbours. Is there a better data structure or way of keeping a shorter list that will increase the games speed?
I ask this because often many cells are checked but not changed so I feel like my implementation could be improved.
我相信Hashlife 算法可以帮到你。
它给出了使用四叉树（每个内部节点恰好有四个子节点的树数据结构）来保存数据的想法，然后它使用哈希表来存储四叉树的节点。
为了进一步阅读，这篇由 Eric Burnett 撰写的文章对Hashlife的工作原理、性能和实现（尽管使用 Python）提供了深刻的见解。值得一读。
早在 1970 年代，我就使用 2Mhz 6800 8 位计算机构建了一个 Life 引擎，该引擎在直接映射到屏幕像素的 256x512 位网格上运行。我直接在显示像素上进行（它们是一位开/关白/黑），因为我想查看结果并且没有看到将 Life 图像复制到显示器的意义。
它的基本技巧是将问题视为基于生命规则评估“此单元已打开”的布尔逻辑公式之一，而不是像往常一样计算活邻居。这个公式很容易弄清楚，所以留作家庭作业。让它快速的原因是布尔公式是按位计算的，一次计算 8 位。如果您向下扫过屏幕并跨行，您实际上可以一次评估 N 位（6800 上为 8，现代 PC 上为 64），而且开销非常低。如果您发疯了，您可能会使用 SIMD 矢量扩展并“一次”执行 256 位或更多位。最重要的是使用 GPU 执行此操作。
6800 版本将在大约 0.5 秒内处理一个完整的屏幕；您可以在屏幕上从上到下观看更新涟漪（60 Hz 刷新）。在具有 1000 倍时钟速率（1 GHz 很容易获得）和一次 64 位的现代 CPU 上，它应该能够每秒产生数千帧。如此之快，您无法看到它运行：-{
一个有用的观察是生命世界的大部分是死的（空白），处理这部分主要会产生更多的死细胞。这建议使用稀疏表示。另一位发帖人建议使用四叉树，我认为这是一个非常好的建议。您的四叉树区域也不必是正方形的。
结合这两个想法，非空白区域的四叉树与四叉树指定的位块的位级处理可能会给出一个惊人的快速生命算法。