为了进行实验，我(很久以前)实现了Conway的《人生游戏》(而且我知道这个相关问题！)。

我的实现通过保留2个布尔数组来表示"最后状态"和"状态正在更新"(每次迭代都会交换2个数组)而起作用。虽然这相当快，但是我经常想知道如何优化它。

例如，一种想法是在迭代N处预先计算可以在迭代(N + 1)处修改的区域(这样，如果一个单元格不属于该区域，则甚至不考虑在该区域进行修改)迭代(N + 1))。我知道这很模糊，而且我从不花时间去研究细节...

我们对如何优化(速度)生命游戏迭代有任何想法(或者经验！)？

解决方案

回答

不完全知道该怎么做，但是我记得我的一些朋友不得不用四叉树来代表游戏的网格。我猜这对于优化网格的空间确实很有用，因为我们基本上只代表占用的单元格。我不知道执行速度。

回答

这是一个二维自动机，因此我们可能可以查找优化技术。想法似乎与压缩每个步骤需要检查的单元格数量有关。由于我们只需要检查被占用的单元格或者与之相邻的单元格，也许我们可​​以保留所有此类单元格的缓冲区，并在处理每个单元格的每一步对其进行更新。

如果字段最初为空，则速度会更快。我们可能会发现一些平衡点，在这个平衡点上，维护缓冲区要比处理所有单元格花费更多。

回答

有一些表驱动的解决方案，可以解决每个表查找中的多个单元格。谷歌查询应该给你一些例子。

回答

有一些超快的实现(从内存中)将8个或者更多相邻正方形的单元表示为位模式，并使用它作为一大批预先计算的值的索引，以在单个机器指令中确定单元是活的还是死的。

在这里查看：

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

还有XLife：

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

回答

我将引用另一个问题的答案，因为我提到的各章提供了一些非常有趣且经过微调的解决方案。是的，一些实现细节是用c和/或者汇编语言编写的，是的，但是在大多数情况下，算法可以在任何语言下工作：

Chapters 17 and 18 of
  Michael Abrash's Graphics
  Programmer's Black Book are one of
  the most interesting reads I have ever
  had.  It is a lesson in thinking
  outside the box.  The whole book is
  great really, but the final optimized
  solutions to the Game of Life are
  incredible bits of programming.

回答

正如Arbash的《黑皮书》中提到的那样，获得巨大加速的最简单直接的方法之一就是保留更改列表。

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

这将缩小我们在每次迭代中要做的工作。

回答

两个想法：

(1)许多配置大多是空白空间。保留活动单元的链接列表(不一定要按顺序进行，这会花费更多时间)，并且在更新期间，仅在活动单元周围进行更新(这与我们含糊的建议OysterD相似)

(2)保留一个额外的数组，该数组在3个位置(左-中-右)的每一行中存储活细胞。现在，当我们计算单元格的新无效/有效值时，我们仅需要4个读取操作(顶部/底部行和中心位置)和4个写入操作(更新3个受影响的行摘要值，以及无效/新单元格的实时价值)。假设写入速度不慢于读取速度，则与8次读取和1次写入相比，这是一个略微的改进。我猜我们可能会更聪明地使用此类配置，并在这些方面实现更好的改进。

回答

我们应该研究Hashlife，这是最终的优化。它使用了skinp提到的四叉树方法。