算法 - 有关Conways的极端细节生活游戏

Question

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

在康威生命游戏，让我们说我有一个地图，像这样：

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

相反遍历每一个细胞，包括死者那些不可能成为相关的，比方说我把每一个生命第0代的细胞在LinkedList之内。在每一代更新之后，我会遍历整个LinkedList并执行Conway的生命游戏在其中的每个规则上的规则。这样我就可以避免无缘无故地迭代大量死亡单元。

其中一个规则状态为a dead cell with 3 living neighbors becomes living。由于我只是在迭代生活细胞在我的算法，只有我可以看死细胞的方式是通过查看我的LinkedList中的活细胞的邻居。我必须为我的LinkedList中的每个项目遍历所有相邻的单元格到该单元格，并且对于每个相邻的单元格，我必须查看该单元格，计算它是否有三个邻居，然后将其设置为alive，然后添加它作为LinkedList内的活细胞。

我的问题：

显然，我的LinkedList将很快得到杂乱无章，将不是在左上角 - >右下角的顺序了。在上面提供的图例中，我的linkedList中的第一个单元可能是C，第二个单元可能是R，第三个单元可能是T。随着新细胞诞生我会以任何顺序，他们在加入下一代将它们添加到我的LinkedList和遍历他们。

是由游戏的规则，这一法律，或者我需要通过迭代整个二维数组从左上角到右下角？规则难以置信地模糊。

任何有两个以上活的邻居的活细胞都会死亡，好像是由于人口不足造成的。

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

任何有三个以上活着的邻居的活细胞都会死亡，好像是由于人口过多一样。

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

我需要遍历整个二维数组，做规则：

少于两只活邻居去世的任何活细胞，仿佛引起下人口。

然后通过整个二维数组再次循环，做规则：

有两个或三个邻居住任何活细胞生命到下一代。

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

谢谢。

Answer 1

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

这实际上会导致需要两个矩阵：旧状态和新状态。对于旧状态中的每个小区，您计算一个活的邻居数量。然后，如果细胞还活着，并且有2或3个邻居，它就生活在新的矩阵中。如果细胞没有活着并且有3个邻居，它就会产生。否则，它会死亡。

链接列表的问题将发现邻居计数。产生下一代将是O(n^2)关于活细胞的数量，因为整个列表必须被搜索以计算邻居。此外，你将不得不在链接列表中检查每个邻居的细胞。

Answer 2

你应该重新创建你的链表，每一个动作。康威的生命游戏轮流进行处理，所有死亡的细胞都将不会被视为生活在当前阶段，所有活着的细胞在当前阶段都不会死亡。所以，用LinkedList的方法，你有两个列表（我会说散列表，因为你需要一个快速的函数来检查一个对象是否已经在列表中），一个代表当前的一组活体细胞，另一个代表收集的下一回合将会活着的一组细胞。然后，您遍历第一组单元格，抓取当前单元格的相邻单元格，将它们填入下一回合的“邻居”列表中，等于1，并增加每个活动单元格的处理值。当前的活细胞应该添加到具有“活”标志集和邻居的集合中。伪代码：

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); 
}