我正在寻找一种快速且内存效率高的方法来实现康威生命游戏。
约束条件：一个96x128的棋盘，大约有2KB的RAM可用和52MHz的处理器（参见这里的技术规格：http://www.getinpulse.com/features）。
我的当前幼稚的解决方案是将每个单元格表示为矩阵中的一个位（96*128/8=1,536字节），但它太慢了。有什么技巧可以用来提高性能？
将活细胞的坐标存储下来（例如在这个实现http://dotat.at/prog/life/life.html中）会使用太多的内存。
康威生命游戏的低内存高效实现方法是什么？
13
- tlrobinson
2
能否从显示内存中读取数据？如果可以的话，最好直接从显示缓冲区访问状态，而不是在内存中复制所有内容。我注意到手表本身有8kB的RAM - 你只使用了四分之一，有什么原因吗？ - Anon.
最好的解决方案似乎是不要在神知道什么上浪费剩余的RAM内存。根据那个链接，你有8kb的RAM。尽可能释放其他6kb的空间...即使你有一个很大的堆栈，比如1kb，你也需要一个相当庞大的应用程序才能使用那么多内存。首先摆脱浮点数和动态内存。 - Lundin
6个回答
9
看起来是一件有趣的硬件。
每个96x128像素显示器存储1位像素需要12,288位。
这已经超过了你所说的“可用”的16,384位的一半以上。
如果你甚至不能存储2位/单元，那么就没有多少空间可以做很多事情了。
一些想法： - 你有一个32位处理器。在这样的处理器上，有几种位操作技巧可以将位图并行计算出多个单元的邻居数。 - 存储邻居计数通常比每代重新计算邻居数量快，可以在出生时增加所有8个邻居，在死亡时减少所有8个邻居。但是看起来你没有足够的内存来采用这种方法。 - 或许你可以每个单元使用2x2像素（只能看到3072个单元）或3x3像素（只能看到1376个单元），这样你的软件可以做更少的工作，从而给人以运行更快的幻觉。（这也释放了足够的RAM，可以进行上述邻居计数）。 - 由于许多生命模式具有大量的死空间，因此可能会有一个小的“活区域”位图 - 例如，一个12x16的位数组，其中每个位是“0”，如果相应的8x8单元格区域完全死亡，则为“1”，如果相应区域中的任何单元格是活动的，则为“1”。下一代更新只需要查看活动区域和死区域的1个单元宽度边框；您可以跳过检查死区域的6x6单元格核心。此外，如果其4个最近的相邻区域也已死亡，则可以完全跳过整个8x8单元格区域。 - 由于许多生命模式具有大量的静态不变的“静物”模式，因此可能会有一个小的“动态区域”位图 - 例如，一个12x16的位数组，其中每个位是“0”，如果相应的8x8单元格区域在上次更新中没有变化，则为“1”，如果相应区域中的任何单元格在上次更新中发生了变化，则为“1”。下一代更新只需要查看动态区域和静态区域的1个单元宽度边框；您可以跳过检查静态区域的6x6单元格核心，因为它在下一代中将保持不变。 - 如果一个模式足够“大”，则基于Gosper的Hashlife表示法可能能够将其存储在比直接存储位图更少的RAM中。遗憾的是，我怀疑你远远低于“足够大”的阈值。
一些想法： - 你有一个32位处理器。在这样的处理器上，有几种位操作技巧可以将位图并行计算出多个单元的邻居数。 - 存储邻居计数通常比每代重新计算邻居数量快，可以在出生时增加所有8个邻居，在死亡时减少所有8个邻居。但是看起来你没有足够的内存来采用这种方法。 - 或许你可以每个单元使用2x2像素（只能看到3072个单元）或3x3像素（只能看到1376个单元），这样你的软件可以做更少的工作，从而给人以运行更快的幻觉。（这也释放了足够的RAM，可以进行上述邻居计数）。 - 由于许多生命模式具有大量的死空间，因此可能会有一个小的“活区域”位图 - 例如，一个12x16的位数组，其中每个位是“0”，如果相应的8x8单元格区域完全死亡，则为“1”，如果相应区域中的任何单元格是活动的，则为“1”。下一代更新只需要查看活动区域和死区域的1个单元宽度边框；您可以跳过检查死区域的6x6单元格核心。此外，如果其4个最近的相邻区域也已死亡，则可以完全跳过整个8x8单元格区域。 - 由于许多生命模式具有大量的静态不变的“静物”模式，因此可能会有一个小的“动态区域”位图 - 例如，一个12x16的位数组，其中每个位是“0”，如果相应的8x8单元格区域在上次更新中没有变化，则为“1”，如果相应区域中的任何单元格在上次更新中发生了变化，则为“1”。下一代更新只需要查看动态区域和静态区域的1个单元宽度边框；您可以跳过检查静态区域的6x6单元格核心，因为它在下一代中将保持不变。 - 如果一个模式足够“大”，则基于Gosper的Hashlife表示法可能能够将其存储在比直接存储位图更少的RAM中。遗憾的是，我怀疑你远远低于“足够大”的阈值。
- David Cary
2
小型生命宇宙通常会在所有边缘上进行包裹（制作环形宇宙），但这需要双重缓冲。在您的情况下，这需要3KB RAM，但您只有2KB。
如果不进行包裹，则不需要对整个宇宙进行双重缓冲。您只需要在使用单元格作为计算输入之前避免覆盖它们。
假设您的宇宙是按传统位图布局的。我们将把它视为按顺序排列在内存中的一系列行。假设该宇宙有四行，编号从0到3。
0
1
2
3
4
...
当您计算下一代时，使用第2、3、4行（空白行）来计算第3行的新版本。您可以将第3行的新版本写在第4行上方。同样，从第1、2、3行计算新的第2行，并将其写在第3行上，因为在计算第2行后不再需要该数据。使用第0、1、2行计算新的第1行，并将其覆盖第2行。
这意味着您只需要额外的一行内存。 97*128位是1552字节。
缺点是您的宇宙通过内存滚动，您必须有某种机制来处理这个问题。要么在每次计算后将其复制回原始位置（这很慢），要么安排能够从内存的任何位置显示它，并确保您的计算和显示系统可以从高地址环绕到低地址。
- Tony Finch
1
使用从上到下计算的环面宇宙将需要在计算底行之前保留顶行的副本，但只需要双缓冲该行和最近计算的一两行，而不是整个宇宙。 - supercat
2
看看迈克尔·阿布拉什的《代码优化禅》一书中关于“生命游戏”的章节。其中有一种实现方式，将3个单元格的当前和前一个状态编码为一个单词，并使用查找表和进位位技巧生成下一个状态。它运行速度非常快。
- AShelly
1
我建议从编写一个读取棋盘一行并生成两个新行缓冲区H和L的例程开始，使得在原始行中如果(bin n+1, bit n, bit n-1)中有两个或更多被设置，则H的第'n'位将被设置为1，如果(bin n+1, bit n, bit n-1)中有奇数个被设置，则L的第'n'位将被设置为1。
分配三对行缓冲区（称之为H0..H2和L0..L2）。对源文件的每一行进行计算，并将其存储在HL对中，保留它和前两个。检查来自所有六个缓冲区的单词将揭示原始矩阵中应该是活动的32个单元格，仅当它们以前是活动的时才是活动的，而无论先前状态如何，哪些单元格应该是活动的。
为了在机器代码中实现最佳性能，可以交错使用三对缓冲区；这可能使执行速度小于每像素两个周期成为可能。也许在52MHz下过于夸张（只有12288个像素，帧速率约为4000fps），但速度很酷。
- supercat
0
如果您有权利滥用设备上剩余的30KB（即闪存），您可以将其存储在那里，虽然不是理想的解决方案，但这是一种潜在的解决有限RAM的方法。
就效率而言，您将牺牲CPU和内存性能：
为了内存效率，位数组可能是最优解，但通过迭代该网格会损失CPU效率。
根据内存地址的能力和大小，您可以使用单元格的链接列表来避免遍历整个网格：这肯定会节省您扫描大量死亡单元格区域的时间。
- David Elner
1
我认为在这种情况下实际上并没有时空权衡。将单元状态存储为单独的位允许您使用处理器按位整数操作的固有并行性，而将每个单元状态与其自己的整数原语一起存储则承载了高阶位上的计算成本。话虽如此，我还没有实现这种技术，因此可能存在减轻性能增益的开销。将单元状态存储在单独的位中的另一个潜在性能优势是提高缓存效率。 - M.J. Rayburn
0
使用位数组并跳过邻居计数，采用以下技巧：创建一个查找表，其中包含创建或维护活细胞的相邻单元块的可能位模式。
如果要最小化内存，则可以将“索引”模式打包到8位中：从上面的行中取3位，从两侧的列中取2位，从下面的行中取3位。您可以将输出编码为查找表中的单个位，总共只占用256位。使用索引作为查找数组的位移计数器来“计算”结果。位移和算术OR操作仍然非常快，而此技术消除了即时计算相邻活细胞的计数 - 或者更确切地说，查找表预处理了计数和计算。
顶部处理瓶颈应该是：检查板边缘条件，即一行的末尾；字边界；提取和打包邻居位作为索引值。使用32位处理器，在命中字边界之前，您应该能够快速循环遍历30个单元。寻址单元行可能只是添加列数/32（如果将位打包到字大小的int中）。将结果缓存到两个备用的新生命行中，并在处理完一个行后复制整个行。
可能有一些模式对称性可以利用，以进一步优化事物，但这可能已经足够了。我认为这种技术将使处理和内存使用保持在您的限制范围内。
- Suncat2000
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接