算法 - 关于 Conways 生命游戏的极端细节

Question

我的查询真的很难描述，所以我会尽量简洁地解释它。

在康威的生命游戏中，假设我有一张这样的 map :

_   _   _   _   _
_   _   _   _   _
U   _   R   Y   _
_   T   _   X   _
_   Z   _   C   _

不是遍历每一个细胞，包括那些不可能变得相关的死细胞，假设我把第 0 代中的每个活细胞都放在 LinkedList 中。在每一代更新后，我将遍历整个 LinkedList 并执行 Conway 的生命游戏对每个列表声明的规则。这样我就可以避免无缘无故地迭代大范围的死细胞。

其中一条规则规定一个有 3 个活着的邻居的死细胞变成活的。因为我在我的算法中只迭代活细胞，所以我可以查看死细胞的唯一方法是查看我的中活细胞的邻居>链表。对于我的 LinkedList 中的每个项目，我必须循环遍历所有相邻单元格到该单元格，对于每个相邻单元格，我必须环顾该单元格，计算它是否有三个邻居，然后将其设置为 alive，然后将其作为活细胞添加到 LinkedList 中。

我的问题:

很明显，我的 LinkedList 很快就会变得杂乱无章，并且不再处于左上 -> 右下的顺序。例如，在我上面提供的图中，我的 linkedList 中的第一个单元格可能是 C，第二个可能是 R，第三个可能是T。随着新细胞的诞生，我会将它们添加到我的 LinkedList 中，并在下一代中以它们添加的顺序遍历它们。

这是否符合游戏规则，或者我是否需要从左上角到右下角遍历整个二维数组？规则非常模糊。

Any live cell with fewer than two live neighbours dies, as if caused by under-population.

Any live cell with two or three live neighbours lives on to the next generation.

Any live cell with more than three live neighbours dies, as if by over-population.

Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

我是否需要遍历整个二维数组，做规则:

Any live cell with fewer than two live neighbours dies, as if caused by under-population.

然后再次遍历整个二维数组并做规则:

Any live cell with two or three live neighbours lives on to the next generation.

这到底重要吗？我读了很多帖子，似乎从来没有人提到过这个话题。

谢谢。

Answer 1

在康威的生命游戏中，整个矩阵应该只循环一次:所有的变化都是同时完成的。

这实际上会导致需要两个矩阵:旧状态和新状态。对于旧状态中的每个单元格，您计算一个活邻居数。然后，如果该细胞还活着并且有 2 或 3 个邻居，它就会在新矩阵中继续存在。如果单元格不存在并且有 3 个邻居，它会生成。否则，它就会死亡。

链表的问题是查找邻居计数。产生下一代的活细胞数量为 O(n^2)，因为必须搜索整个列表来计算邻居。此外，您还必须检查链接列表中单元格的每个邻居，因为它们产生了。