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

Question

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

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

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

与其循环每个单元，包括那些不可能变得相关的死单元，不如假设我将每个活的单元放在第0代的LinkedList中。在每一代更新时，我都会遍历整个LinkedList，并执行康威的“生命游戏”中每一个状态的规则。这样，我就不必无缘无故地重复大范围的死细胞。

其中一条规则声明为a dead cell with 3 living neighbors becomes living。因为我只是通过我的算法中的活细胞来迭代，所以我可以通过查看我的中活的单元格的邻居来查看死细胞的唯一的方法。我必须，对我的LinkedList中的每一个项目，循环遍历所有相邻的单元到那个单元，而对于每个相邻的单元，我必须环顾这个单元格，计数它是否有三个邻居，然后将它设置为alive，然后将它作为一个活的单元添加到LinkedList中。

我的问题：

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

根据游戏规则，是合法的，还是需要从左上角到右下角遍历整个2D数组？规则非常模糊。

任何活的细胞，如果少于两个活的邻居，就会死亡，就好像是由人口不足引起的。 任何有两三个活邻居的活细胞都会活到下一代。 任何有三个以上活邻居的活细胞都会死亡，好像是因为人口过多。 任何有三个活邻居的死细胞都会变成活细胞，就像通过繁殖一样。

我需要循环遍历整个2D数组吗，执行规则：

任何活的细胞，如果少于两个活的邻居，就会死亡，就好像是由人口不足引起的。

然后再次循环整个2D数组并执行规则：

任何有两三个活邻居的活细胞都会活到下一代。

到底有什么关系吗？我读过这么多帖子，似乎没人提过这个话题。

谢谢。

Answer 1

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

实际上，这将导致需要两个矩阵:旧状态和新矩阵。对于处于旧状态的每个单元，计算一个活邻居计数。然后，如果细胞是活的，并且有两个或三个邻居，它就生活在新的矩阵中。如果这个细胞没有生命并且有三个邻居，它就会繁殖。否则它就死定了。

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

Answer 2

你应该重新创建你的链接列表每一个移动。康威的“生命游戏”是轮流进行的，在这个过程中，所有会变成活生生的死细胞都不算活在当下，而所有会死的活细胞在这个回合里也不算死。因此，使用LinkedList方法，您持有两个列表(我会说哈希表，因为您需要一个快速函数来检查对象是否已经在列表中)，一个表示当前的活单元格集，另一个表示收集到的单元格集，这些单元格将在下一轮中存活。然后，迭代第一组单元格，获取当前单元格的相邻单元格，将它们填充到下一轮的列表中，“邻居”值等于1，并将处理后的每个活单元格的值增加。此外，应该将当前活动单元格添加到具有“活动”标志集和邻居为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);
}