算法 - 有關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); 
}