为了进行实验，我（很久以前）实现了康威的生命游戏（我知道这个相关的问题！）。
我的实现通过保留 2 个布尔数组来工作，代表“最后一个状态”和“正在更新的状态”（每次迭代时交换 2 个数组）。虽然这相当快，但我经常想知道如何优化它。
例如，一个想法是在迭代 N 时预先计算可以在迭代 (N+1) 时修改的区域（这样如果一个单元不属于这样的区域，它甚至不会被考虑在迭代（N+1））。我知道这很模糊，我从来没有花时间去详细说明......
您对如何优化（以提高速度）生命游戏迭代有任何想法（或经验！）吗？
OysterD
问问题
41923 次
12 回答
37
我将引用另一个问题的答案，因为我提到的章节有一些非常有趣且经过微调的解决方案。一些实现细节在 c 和/或汇编中，是的，但在大多数情况下，算法可以在任何语言中工作：
Michael Abrash 的Graphics Programmer's Black Book第17章和第18章是我读过的最有趣的书之一。这是跳出框框思考的一课。整本书真的很棒，但是生命游戏的最终优化解决方案是令人难以置信的编程。
于 2008-09-02T20:26:32.843 回答
18
有一些超快速的实现（从内存中）将 8 个或更多相邻正方形的单元表示为位模式，并将其用作预先计算值的大型数组的索引，以在单个机器指令中确定单元是活的还是死的.
在这里查看：
http://dotat.at/prog/life/life.html
还有XLife：
于 2008-09-02T20:26:01.207 回答
5
正如 Arbash 的黑皮书中所提到的，获得巨大加速的最简单直接的方法之一就是保留一个更改列表。
不要每次都遍历整个单元格网格，而是保留您更改的所有单元格的副本。
这将缩小您在每次迭代中必须做的工作。
于 2008-09-02T20:34:36.693 回答
5
算法本身本质上是可并行的。在未优化的 CUDA 内核中使用相同的双缓冲方法，在 4096x4096 包装的世界中，我每代的时间大约为 25 毫秒。
于 2011-06-28T07:46:49.270 回答
3
什么是最有效的算法主要取决于初始状态。
如果大多数单元格都死了，您可以通过跳过空白部分而不是逐个单元格计算内容来节省大量 CPU 时间。
我认为，当您的初始状态类似于“随机，但生命几率低于 5%”时，首先检查完全死空间是有意义的。
我只是将矩阵分成两半，然后首先检查较大的矩阵。
所以如果你有一个 10,000 * 10,000 的字段，你首先要累积 5,000 * 5,000 的左上四分之一的状态。
如果第一季度的状态总和为零，您现在可以完全忽略第一季度，然后检查右上方的 5,000 * 5,000 下一个生命周期。
如果它的状态总和 > 0，您现在将第二季度再次分成 4 部分 - 并对这些子空间中的每一个重复此检查。
您现在可以降低到 8*8 或 10*10 的子帧（不确定这里什么最有意义）。
每当你找到生命时，你就将这些子空间标记为“有生命”。
只有“有生命”的空间需要被划分成更小的子空间——可以跳过空的。
当您完成为所有可能的子空间分配“有生命”属性时，您最终会得到一个子空间列表，您现在只需将其扩展到每个方向 +1 - 使用空单元格 - 并执行常规（或修改）游戏生活规则给他们。
您可能认为将 10,000*10,000 空间划分为 8*8 的子空间是很多操作系统任务 - 但实际上，与对每个单元格加上它们的 8 个邻居加比较数字并在某处存储网络迭代的新状态......
但就像我上面说的，对于一个具有 30% 人口的随机初始化状态，这没有多大意义，因为不会有太多完全死掉的 8*8 子空间可以找到（不管死 256*256 子空间）
当然，完美优化的方式将持续但并非最不重要取决于您的语言。
-110
于 2016-06-02T14:13:21.770 回答
1
两个想法：
(1) 许多配置大多是空的。保留活细胞的链接列表（不一定按顺序排列，这将花费更多时间），并且在更新期间，仅在活细胞周围进行更新（这类似于您的模糊建议，OysterD :)
(2) 保留一个额外的数组，该数组存储每行 3 个位置（左-中-右）的活细胞数。现在，当您计算单元格的新死/活值时，您只需要 4 次读取操作（顶部/底部行和中心位置）和 4 次写入操作（更新 3 个受影响的行汇总值和死/新单元格的实时值）。假设写入不比读取慢，这比 8 次读取和 1 次写入略有改进。我猜你可能会更聪明地使用这样的配置，并在这些方面取得更好的改进。
于 2008-09-02T20:39:31.940 回答
0
不完全知道如何做到这一点，但我记得我的一些朋友不得不用四叉树来表示这个游戏的网格来分配任务。我猜这对于优化网格空间非常有用，因为您基本上只代表被占用的单元格。我不知道执行速度。
于 2008-09-02T20:21:12.810 回答
0
这是一个二维自动机，因此您可能可以查找优化技术。您的想法似乎是关于压缩每一步需要检查的单元格数量。由于您只需要检查被占用的单元格或与占用的单元格相邻的单元格，也许您可以保留所有此类单元格的缓冲区，并在处理每个单元格时在每一步更新它。
如果您的字段最初是空的，这将更快。您可能会找到一些平衡点，在该平衡点处，维护缓冲区比处理所有单元格的成本更高。
于 2008-09-02T20:21:28.347 回答
0
对此有表格驱动的解决方案，可以解决每个表格查找中的多个单元格。谷歌查询应该会给你一些例子。
于 2008-09-02T20:25:18.043 回答
0
我在 C# 中实现了这个：
所有小区都有一个位置、一个邻居计数、一个状态和对规则的访问。
- 将数组 B 中的所有活细胞放入数组 A 中。
- 让数组 A 中的所有单元格将其邻居的邻居计数加 1。
- 让数组 A 中的所有单元格将自己和它们的邻居放在数组 B 中。
- Array B 中的所有单元格根据规则及其状态进行更新。
- 数组 B 中的所有单元格都将它们的邻居设置为 0。
优点：
- 忽略不需要更新的单元格
缺点：
- 4 个阵列：一个二维阵列用于网格，一个阵列用于活细胞，一个阵列用于活动细胞。
- 无法处理规则 B0。
- 一个一个地处理细胞。
- 单元格不仅仅是布尔值
可能的改进：
- 单元格也有一个“已更新”值，它们仅在当前刻度未更新时才更新，如上所述消除对数组 B 的需要
- 不是数组 B 是那些有活邻居的，数组 B 可以是没有的单元格，并且这些单元格检查规则 B0。
于 2018-01-28T17:17:27.627 回答
0
如果您不想要任何太复杂的东西，那么您可以使用网格将其分割，如果网格的那部分是空的，请不要尝试模拟它（请查看 Tyler 的答案）。但是，您可以进行一些优化：
- 根据活细胞的数量设置不同的网格大小，所以如果没有很多活细胞，这可能意味着它们在一个很小的地方。
- 当你随机化它时，在用户更改数据之前不要使用网格代码：我已经亲自测试过随机化它，即使经过很长时间，它仍然会填满大部分棋盘（除非网格足够小, 在这一点上它不会有那么大的帮助了)
- 如果要将其显示到屏幕上，请不要使用像素大小 1 和 2 的矩形：而是设置输出的像素。任何更高的像素大小，我发现使用本机矩形填充代码是可以的。此外，预设背景，这样您就不必为死细胞填充矩形（不是活细胞，因为活细胞很快就会消失）
于 2021-11-26T13:56:41.710 回答