tlr*_*son 13 embedded low-memory conways-game-of-life
我正在寻找一种快速且节省内存的方法来实现Conway的生命游戏.
限制因素: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",则每个位为"0".上一代更新没有变化,如果上一次更新中相应区域中的任何单元格发生了变化,则为"1".下一代更新只需要查看动态区域和静态区域的1个单元宽边界; 你可以跳过检查静态区域的6x6单元核心,因为它在下一代中是相同的.
如果模式"足够大",基于Gosper的Hashlife的表示可能能够将其存储在比直接存储位图更少的RAM中.唉,我怀疑你远远低于"足够大"的门槛.