优化康威的"生命游戏"

Question

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

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

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

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

Answer 1

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

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

Answer 2

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

点击这里:

还有XLife:

Answer 3

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

Answer 4

正如 Arbash 的 Black Book 中提到的，获得巨大加速的最简单直接的方法之一是保留更改列表。

不要每次都遍历整个单元格网格，而是保留您更改的所有单元格的副本。

这将缩小您在每次迭代中必须完成的工作。

Answer 5

算法本身是可并行化的。在未优化的 CUDA 内核中使用相同的双缓冲方法，我在 4096x4096 包装的世界中每代大约 25 毫秒。

Answer 6

不完全知道如何做到这一点，但我记得我的一些朋友必须用四叉树来表示这个游戏的网格才能完成作业。我猜这对于优化网格空间确实很有好处，因为您基本上只代表占用的单元格。但我不知道执行速度。