我正在寻找一种快速和内存高效的方法来实现Conway的生活游戏。
限制: 96x128电路板,大约2kB内存和52 the处理器(请参阅此处的技术规格:http://www.getinpulse.com/features)。
我目前的简单解决方案将每个单元表示为矩阵中的单个位(96*128/8=1,536字节),虽然有效,但速度太慢。可以使用哪些技巧来提高性能?
存储活动单元格的坐标(例如,在此实现中为http://dotat.at/prog/life/life.html)将占用太多内存。
发布于 2011-02-21 14:40:06
看起来像是一个有趣的硬件。96×128像素显示器的每像素存储1位可得到12,288位。这已经超过了你所说的16,384位中“可用”位的一半。如果你甚至不能在每个单元中存储2位,那么就没有多少空间可以做很多事情了。
以下是一些想法:
发布于 2011-02-21 20:20:10
对于小的生命宇宙来说,让它们在所有的边都被包裹起来(形成一个环形的宇宙)是很常见的,但这需要双重缓冲。在您的情况下,这需要3KB的RAM,但您只有2KB。
如果你不包装,那么你就不需要对整个宇宙进行双缓冲。您只需避免在将单元格用作计算输入之前覆盖这些单元格。
假设你的宇宙是以传统的位图布局的。我们将其视为在内存中按顺序排列的一系列行。假设宇宙有四行,编号为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字节。
缺点是你的世界在内存中滚动,你必须有一些机制来处理这一点。或者在每次计算后将其复制回其原始位置(这很慢),或者安排为能够从内存中的任何位置显示它,并确保您的计算和显示系统可以从高地址到低地址回绕。
发布于 2011-02-22 04:12:12
看看Michael Abrash在"The Zen of Code Optimization"中关于生活的游戏的章节。有一种实现将3个单元的当前和先前状态编码到单个字中,并使用查找表和进位位的技巧来生成下一状态。它的速度非常快。
https://stackoverflow.com/questions/5059817
复制相似问题