对于低内存使用，Conway的生命游戏的有效实施是什么？

看起来像一个有趣的硬件。 在96x128像素显示器上存储每像素1位可得到12,288位。 这已经超过你所说的16,384位中的一半是“可用的”。 如果你甚至不能每个单元存储2位，那么就没有太大的空间。 一些想法： 你有一个32位处理器。在这样的处理器上采用位图并计算并行计算几个单元的邻居数量有几个比特麻烦的技巧。 存储邻居计数通常更快，在出生时递增所有8个邻居并在死亡时递减所有8个邻居，而不是每一代从头开始重新计算邻居的数量 - 但是看起来你没有足够的内存用于这种方法。 也许你可以使用每个单元2x2像素（因此只有3,072个单元可见）或每个单元3x3像素（因此只有1,376个单元可见），因此您的软件可以减少工作量，因此可以更快地运行。 （这也释放了足够的RAM，你可以做上面提到的邻居计数）。 由于许多生命模式具有大面积死区，因此可能具有“活区域”的小位图 - 例如，12x16位阵列，其中如果相应的8x8单元区域完全死亡则每个位为“0”，并且“ 1“如果相应区域中的任何细胞存活。下一代更新只需要查看活区域和死区的1个单元宽边界;你可以跳过检查死区的6x6细胞核心。此外，如果其最近的4个相邻区域也已死亡，则可以完全跳过整个8x8单元区域。 由于许多生命模式具有大面积静态不变的“静物”模式，因此可能具有“动态区域”的小位图 - 例如，12x16位数组，其中如果相应的8x8单元区域具有“0”，则每个位为“0”。上一代更新没有变化，如果上一次更新中相应区域中的任何单元格发生了变化，则为“1”。下一代更新只需要查看动态区域和静态区域的1个单元宽边界;你可以跳过检查静态区域的6x6单元核心，因为它在下一代中是相同的。 如果模式“足够大”，基于Gosper的Hashlife的表示可能能够将其存储在比直接存储位图更少的RAM中。唉，我怀疑你远远低于“足够大”的门槛。     

小生命宇宙使它们四面环绕（形成环形宇宙）是很常见的，但这需要双重缓冲。在您的情况下，这需要3KB RAM，但您只有2KB。 如果你不包装那么你不需要双重缓冲整个宇宙。在完成将单元格用作计算输入之前，您只需要避免覆盖单元格。 假设您的Universe布局为传统位图。我们将它视为一系列行按顺序排列在内存中。假设宇宙有四行，编号为0到3。

  0
  1
  2
  3
  4
  ...

计算下一代时，使用第2,3和4行（空白）计算第3行的新版本。您可以在第4行的顶部编写第3行的新版本。同样，从第1,2,3行计算新行2并将其写在第3行的顶部，因为在计算第2行后不再需要该数据。新行1从行0,1,2计算并写在第2行。 这意味着您只需要一个额外行的内存。 97 * 128位是1552字节。 缺点是你的宇宙滚动内存，你必须有一些机制来处理这个问题。在每次计算之后将其复制回原始位置（这很慢）或者安排能够从内存中的任何位置显示它，并确保您的计算和显示系统可以从高地址到低地址回绕。     

请看Michael Abrash撰写的“The Code of Code Optimization”中关于生命游戏的章节。有一个实现将3个单元的当前和先前状态编码为单个字，并使用查找表和进位的技巧生成下一个状态。它非常快。     

我建议从一个例程开始读取一行板并生成两个新的行缓冲区H和L，如果两个或多个（bin n + 1，bit n，bit）将设置H的位'n' n-1）被设置在原始行中，如果在原始行中设置了奇数（bin n + 1，bit n，bit n-1），则将设置L的位'n'。 分配总共三对行缓冲区（称为H0..H2和L0..L2）。获取源文件的每一行并计算一对缓冲区并将其存储在HL对中，保留它和前两个。检查所有六个缓冲区中的一个单词将显示原始矩阵中的32个单元格中的哪一个应该是活的，当且仅当它们之前是，并且无论以前的状态如何都应该是活的。 为了在机器代码中获得最佳性能，可以交错三对缓冲器;这可以使得每像素的执行速度小于两个周期成为可能。也许在52MHz（仅有12288像素，即帧速率为~4000fps）的过度杀伤，但速度很酷。     

如果您有许可滥用设备上30KB的剩余部分（也可以是闪存），您可以随时将其存储在那里，这并不理想，但它是一种可以在有限的RAM上工作的方法。 效率说你会相互交换CPU和内存性能： 对于内存效率，位数组可能是最佳解决方案，但是通过迭代该网格会损失CPU效率。 根据内存地址的功能和大小，您可以使用链接的单元格列表来避免遍历整个网格：绝对可以节省您扫描死区大区域的时间。     

坚持使用位阵列并使用此技巧跳过邻居计数：创建一个查找表，其中包含创建或维护活动单元的相邻单元块的可能位模式。 如果要最小化存储器，则可以将“索引”模式打包为8位：上行中的3位，列中任意一侧的两位，以及下一行中的3位。您可以将输出编码为查找表中的单个位，总共只占256位。使用索引作为查找数组的位移计数来“计算”结果。位移和算术OR运算仍然非常快，并且该技术消除了动态计算相邻的活细胞 - 或者更确切地说，查找表预处理计数和计算。 最重要的处理瓶颈应该是：检查板边缘条件，即一行的结束;字边界;提取和打包邻居位作为索引值。使用32位处理器，您应该能够在遇到字边界之前非常快速地循环30个单元。如果将位打包成字大小的整数，则寻址单元行可能只需要添加列数/ 32。将结果缓存到两个备用的新生命行中，并在处理完一行后复制整行。 您可以利用一些模式对称来进一步优化事物，但这可能就足够了。我认为这种技术可以将处理和内存使用保持在您的限制之内。