我正在寻找一种快速且内存高效的方法来实现康威的生命游戏。
限制条件：一块 96x128 板、大约 2kB 可用 RAM 和 52MHz 处理器（请参阅此处的技术规格：http: //www.getinpulse.com/features）。
我当前将每个单元格表示为矩阵中的单个位（96*128/8=1,536 字节）的幼稚解决方案有效，但速度太慢。可以使用哪些技巧来提高性能？
存储活细胞的坐标（例如在这个实现中http://dotat.at/prog/life/life.html）会占用太多内存。
看起来像一个有趣的硬件。在 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”上一代更新中没有变化，如果相应区域中的任何单元格在上一次更新中发生变化，则为“1”。下一代更新只需要查看动态区域和静态区域的 1-cell-wide 边界；您可以跳过检查静态区域的 6x6 单元核心，因为它在下一代中将是相同的。
如果模式“足够大”，则基于 Gosper 的 Hashlife 的表示可能能够将其存储在比直接存储位图更少的 RAM 中。唉，我怀疑你远远低于“足够大”的门槛。
在小生命宇宙中，使它们四面环绕（形成环形宇宙）是很常见的，但这需要双重缓冲。在您的情况下，这需要 3KB RAM，但您只有 2KB。
如果你不包装，那么你不需要对整个宇宙进行双重缓冲。您只需要在完成将单元格用作计算的输入之前避免覆盖单元格。
假设您的宇宙布局为传统位图。我们将把它视为一系列在内存中按顺序排列的行。假设宇宙有四行，编号为 0 到 3。
0
1
2
3
4
...
计算下一代时，第 3 行的新版本是使用第 2、3 和 4 行（空白）计算的。您可以将第 3 行的新版本写在第 4 行之上。类似地，从第 1、2、3 行计算新的第 2 行并将其写在第 3 行之上，因为在计算第 2 行之后不再需要该数据。新的第 1 行是根据第 0、1、2 行计算并覆盖第 2 行的。
这意味着您只需要额外一行的内存。97*128 位是 1552 字节。
缺点是你的宇宙在记忆中滚动，你必须有一些机制来处理这个问题。每次计算后将其复制回其原始位置（这很慢）或安排能够从内存中的任何位置显示它，并确保您的计算和显示系统可以从高地址到低地址环绕。
查看Michael Abrash的“代码优化之禅”中关于生命游戏的章节。有一个实现将 3 个单元的当前和先前状态编码为一个字，并使用查找表和进位位的技巧来生成下一个状态。它的速度非常快。
我建议从一个例程开始读取电路板的一行并生成两个新的行缓冲区 H 和 L 以便如果两个或多个 (bin n+1, bit n, bit n-1) 被设置在原始行中，如果在原始行中设置了奇数个 (bin n+1, bit n, bit n-1)，则将设置 L 的 bit 'n'。
总共分配三对行缓冲区（称它们为 H0..H2 和 L0..L2）。获取源文件的每一行并计算一对缓冲区并将其存储在一个 HL 对中，保留它和前两个。检查所有六个缓冲区中的一个单词将揭示原始矩阵中的 32 个单元中的哪些应该是活的，当且仅当它们以前是活的，而无论以前的状态如何，哪些应该是活的。
For optimal performance in machine code, the three pairs of buffers may be interleaved; this may make it possible to achieve an execution speed of less than two cycles per pixel. Perhaps overkill at 52MHz (with only 12288 pixels, that would be a frame rate of ~4000fps) but speed is cool.
如果您有许可滥用设备上剩余的 30 KB（也称为闪存），您可以始终将其存储在那里，这并不理想，但这是一种潜在地解决有限 RAM 的方法。
从效率上讲，您将相互交换 CPU 和内存性能：
对于内存效率，位数组可能是最佳解决方案，但通过迭代该网格会损失 CPU 效率。
根据内存地址的功能和大小，您可以使用单元的链接列表来避免遍历整个网格：肯定会节省您扫描大量死单元区域的时间。
坚持使用位数组并使用此技巧跳过邻居计数：创建一个查找表，其中包含创建或维护活动单元的相邻单元块的可能位模式。
如果要最小化内存，可以将“索引”模式打包成 8 位：上一行 3 位，两侧各列 2 位，下一行 3 位。您可以将输出编码为查找表中的单个位，总共仅占用 256 位。使用索引作为查找数组的位移计数来“计算”结果。位移和算术或运算仍然非常快，并且这种技术消除了动态计算相邻活细胞的数量 - 或者更确切地说，查找表对计数和计算进行了预处理。
最重要的处理瓶颈应该是：检查板边缘条件，即一行结束；单词边界；提取和打包相邻位作为索引值。使用 32 位处理器，您应该能够在到达字边界之前非常快速地循环通过 30 个单元。如果将位打包成字大小的整数，则寻址单元行可能只是添加列数/32 的问题。将结果缓存到两个备用的新生命行中，并在处理完一个后复制一整行。
您可能可以利用一些模式对称性来进一步优化事物，但这可能就足够了。我认为这种技术将使处理和内存使用保持在您的限制范围内。