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

Question

我的问题很难描述，所以我会尽可能简洁地解释。

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

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

与其在每个单元格上循环，包括不可能相关的死单元格，不如让我将第0代中的每个活单元格放在链接列表中。在每一代人更新时，我都会遍历整个LinkedList，并执行Conway的生活游戏对每一代人的规则。这样我就避免了无缘无故地迭代大跨度的死单元。

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

我的问题：

显然，我的LinkedList会很快变得杂乱无章，不会出现在左上方-

按照游戏规则，这合法吗？还是我需要从左上角到右下角遍历整个2D数组？这些规则非常模糊。

任何少于两个活邻居的活细胞都会死亡，就好像是由于人口不足造成的一样。

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

任何有三个以上活邻居的活细胞都会死亡，就好像是因为人口过多。

任何有三个活邻居的死细胞都会变成活细胞，就像通过繁殖一样。

我需要循环通过整个2D数组，做规则：

任何少于两个活邻居的活细胞都会死亡，就好像是由于人口不足造成的一样。

然后再次循环遍历整个二维数组，并执行以下规则：

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

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

谢谢。




Answer 1

您应该在每次移动时重新创建链接列表。康威的生命游戏是按轮次进行的，所有活细胞在当前轮次不算作活细胞，所有死细胞在当前轮次不算作死细胞。因此，使用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);
}

Answer 2

在康威的人生游戏中，整个矩阵应该只循环一次：所有的变化都是同时进行的。

实际上，这将需要两个矩阵：旧状态和新状态。对于旧状态下的每个单元格，计算实时邻居计数。然后，如果细胞是活的，并且有2或3个邻居，它就会在新的矩阵中继续存在。如果细胞不是活的，并且有3个邻居，它会产卵。否则，它就死了。

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