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

Question

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

在康威的生命游戏中，假设我有一张这样的地图：

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

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

其中一条规则规定 a dead cell with 3 living neighbors becomes living。因为我在我的算法中只迭代 living 细胞，所以 only 我可以查看死细胞的方法是查看我 LinkedList 中的活细胞。对于 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) 活细胞的数量，因为必须搜索整个列表来计算邻居。此外，您还必须检查链接列表中单元格的每个邻居，因为它们产生了。

Answer 2

您应该在每一步都重新创建链表。康威的生命游戏是轮流进行的，所有会变成活细胞的死细胞在当前回合不算活，所有会死的活细胞在当前回合不算死。所以，使用 LinkedList 方法，你有两个列表（我会说哈希表，因为你需要一个快速函数来检查一个对象是否已经在列表中），一个代表当前的活细胞集， other 代表收集的一组细胞，这些细胞将在下一轮存活。然后，您遍历第一组单元格，获取当前单元格的相邻单元格，将它们填充到下一轮的列表中，使 "neighbors" 等于 1，并增加每个处理的活单元格的值。此外，应将当前活细胞添加到设置了 "living" 标志且邻居为 0 的集合中。伪代码：

ArrayCollection.<Cell> existing; // currently alive cells
ArrayCollection.<Cell> next; // next turn
void processTurn() {
    next.clear();
    for each (Cell cell in existing) {
        Cell nextTC=next.getByParameters(cell); // check presence by X and Y
        if (nextTC) nextTC.alive=true; else   
            next.addNewCell(cell.x,cell.y,0,true); // add a new element
            // 0 is current neighbors, true is alive flag
        for each (Cell neigh in cell.neighbors) {
            nextTC=next.getByParameters(neigh);
            if (nextTC) nextTC.neighbors++; else   
                next.addNewCell(cell.x,cell.y,1,false); // add a new element
                // added a dead cell with 1 neighbor - currently processed alive cell
        }
    }
    for each (cell in next) {
        if (!cell.alive && (cell.neighbors==3)) cell.alive=true; else
        if (cell.alive && ((cell.neighbors==2) || (cell.neighbors==3))) ; // no change
        else next.remove(cell); // dead cell that either was alive or failed to become alive
    }
    swap(current,next);
}

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

Algorithms - Extreme specifics about Conways Game of Life

algorithm

conways-game-of-life