我正在寻找一种快速且节省内存的方法来实现康威的生命游戏。
限制:96x128 板、大约 2kB 可用 RAM 和 52MHz 处理器(请参阅此处的技术规格:http://www.getinpulse.com/features http://www.getinpulse.com/features).
我当前的简单解决方案将每个单元表示为矩阵中的单个位(96*128/8=1,536 字节),但速度太慢。可以使用哪些技巧来提高性能?
存储活细胞的坐标(例如在此实现中http://dotat.at/prog/life/life.html 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 单元核心。此外,如果整个 8x8 单元区域的 4 个最近的相邻区域也已失效,则您可以完全跳过整个 8x8 单元区域。
由于许多生活模式都有大面积的静态不变的“静物”模式,因此可能有一个小的“动态区域”位图——例如,一个 12x16 位数组,如果相应的 8x8 单元区域有,则每个位都是“0”上一代更新中没有变化,如果相应区域中的任何单元格在上一次更新中发生变化,则为“1”。下一代更新只需要查看动态区域和静态区域的1-cell宽边界;您可以跳过检查静态区域的 6x6 单元核心,因为它在下一代中是相同的。
如果一个模式“足够大”,基于 Gosper 的 Hashlife 的表示可能能够将其存储在比直接存储位图更少的 RAM 中。唉,我怀疑你远远低于“足够大”的门槛。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)