优化康威的"生命游戏"

为了实验,我(很久以前)实施了康威的生命游戏(我知道这个相关的问题!).

我的实现通过保留2个布尔数组来表示"最后状态"和"正在更新状态"(每次迭代时交换2个数组).虽然速度相当快,但我常常想知道如何优化它.

例如,一个想法是在迭代N处预先计算可以在迭代(N + 1)处修改的区域(因此,如果一个单元不属于这样的区域,则甚至不会考虑在迭代(N + 1)).我知道这很模糊,我从来没有花时间详细介绍......

你对如何优化(速度)Game of Life迭代有任何想法(或经验!)吗？

我将从另一个问题引用我的答案,因为我提到的章节有一些非常有趣和精细的解决方案.一些实现细节是c和/或汇编,是的,但大多数情况下算法可以使用任何语言:

章17和18迈克尔·亚伯拉什的的图形程序员的黑皮书是最有趣的阅读,我曾经有一个.这是在盒子外思考的一课.整本书真的很棒,但生命游戏的最终优化解决方案是令人难以置信的编程.

有一些超快速实现(从内存中)将8个或更多相邻方块的单元表示为位模式,并将其用作大量预先计算值的索引,以在单个机器指令中确定单元是活还是死.

点击这里:

http://dotat.at/prog/life/life.html

还有XLife:

http://linux.maruhn.com/sec/xlife.html

您应该了解Hashlife,这是最终的优化.它使用了skinp提到的四叉树方法.