生命遊戲 - 這個算法是什麼

Question

我創造了一個簡化的生命遊戲。

這是我的手機在實際的事情發生：

class Cell 
{ 
    public Cell(MainWindow correspondingMainWindow){ 
     this.mainWindow = correspondingMainWindow; 
    } 

    public bool excluded; 

    public Boolean Occupied { get; set; } 

    public Control correspondingPanel; 

    private int[] coordinates; 

    private MainWindow mainWindow; 

    public int[] Coordinates 
    { 
     get { return this.coordinates; } 
     set { 
      if(value.Length != 2) 
      { 
       throw new ArgumentException(); 
      } 
      else if(value[0] < 0 || value [1] < 0 
        || value[0] > Settings.FIELDWIDTH 
        || value[1] > Settings.FIELDHEIGHT) 
      { 
       throw new ArgumentException(); 
      } 
      else{ 
       correspondingPanel = mainWindow.FieldArea.Controls 
         .Find(String.Format("panel{0}_{1}", value[0], value[1]), true) 
         .FirstOrDefault(); 
       this.coordinates = value; 
      } 
     } 

    } 

    //Surrounding Cells in the 3x3 around the current cell 
    //this is to speed up the updating as soon as the algorithm runs on many cells 
    public Cell Top { get; set; } 
    public Cell TopRight { get; set; } 
    public Cell Right { get; set; } 
    public Cell BotRight { get; set; } 
    public Cell Bot { get; set; } 
    public Cell BotLeft { get; set; } 
    public Cell Left { get; set; } 
    public Cell TopLeft { get; set; } 

    public void die() 
    { 
     this.Occupied = false; 
     this.correspondingPanel.BackColor = Color.Beige; 
    } 

    public void populate() 
    { 
     this.Occupied = true; 
     this.correspondingPanel.BackColor = Color.DarkRed; 
    } 
} 

這裏是有問題的算法：

//should return true if there were any changes to any "living" state 
bool Algorithm.runOver(Cell target) 
{ 
    if (target.Occupied && !target.excluded) 
    { 
     target.Right.populate(); 
     target.Left.populate(); 
     target.Top.populate(); 
     target.Bot.populate(); 

     target.Right.excluded = true; 
     target.Left.excluded = true; 
     target.Top.excluded = true; 
     target.Bot.excluded = true; 
     return true; 
    } 
    else 
    { 
     return false; 
    } 
} 

排除和已經運行的重置了假每次算法運行完畢所有細胞一次。這是爲了防止在此步行中更新的Cell上的walkOver（）的調用。

現在，當我把我的細胞放在我的領域的左上角（像簡單的蛇場一樣繼續）時，標記它並運行算法，它在第一次運行後停止更改。

它實際上以設計的方式更新Cell，但隨後停止。

我將我的單元格保存到程序中的一個靜態列表（我知道我不應該，但它是最簡單的方法，直到它正常工作）。細胞有一些面板匹配。這些面板位於名爲FieldArea的GroupBox中。它們是根據一些靜態常量設置（您在座標集驗證中看到的）動態生成的。

我確定單元格與面板正確匹配。這個問題似乎發生在從左上角（0,0）到右下角的FieldArea的對角線上。任何其他起點都可以正常工作。不知何故，當大量細胞從「頂部」進入時，細胞在該區域的頂部和左側邊緣形成邊界。

現在的問題是：我做錯了什麼？爲什麼我的字段無法正常工作？

Answer 1

你必須保留你的「世界」的兩個副本，因爲在你應用規則時必須保持不變。如果將規則應用於唯一的世界，這將導致混合配置，其中一些單元格將具有舊狀態，而其他單元格將已經具有新狀態。

因此做這樣的事情：

private Cell[,] activeWorld = new Cell[w,h]; 
private Cell[,] hiddenWorld = new Cell[w,h]; 

Populate(activeWorld); 
while (true) { 
    Display(activeWorld); 
    ApplyRules(activeWorld, hiddenWorld); 

    // Swap worlds 
    var temp = activeWorld; 
    activeWorld = hiddenWorld; 
    hiddenWorld = temp; 
} 

的方法ApplyRules必須從「activeWorld」讀細胞，並將結果寫入hiddenWorld。

---

更新：您的實際設計似乎是過度設計給我。一個簡單的2-D布爾數組告訴單元格是否被佔用應該是足夠的。不要從優化開始。這很可能會導致一個複雜的，難以閱讀和錯誤的代碼。而應將注意力集中在算法和良好的代碼結構上。如果後來出現性能問題，請分析問題並應用適當的優化。在> 95％的情況下，問題與編碼細節和算法無關，但與I/O無關。在這個遊戲的情況下，顯示單元格可能比應用規則花費更多的時間。無論如何，它可能會太快，你將不得不在遊戲循環中添加一個暫停。

不要試圖優化獲得周圍細胞索引的邏輯。這不值得痛苦。

解決邊緣單元問題的一個好方法是環繞世界。讓事情在右側重新出現在左側，等等。爲此使用模運算（％）。 x % N的值始終爲0 ... N-1。你可以得到3×3的細胞像這樣給出的x和y座標座標：

for (int dx = -1; dx <= +1; dx++) { 
    int i = (x + dx + Width) % Width; 
    for (int dy = -1; dy <= +1; dy++) { 
     int j = (y + dy + Height) % Height; 
     bool occupied = world[i, j]; 
     ... 
    } 
} 

的+ Width和+ Height確保我們始終爲正值。

Answer 2

好吧，這裏許是我個人的勝利的最周：

上述算法是「錯誤的」

不幸的是，我不包括細胞，沒有改變。當我從「左上角」走過列表時，出現了錯誤。

我將排除移動到die（）和populate（）函數。

public void die(){ 
    this.Occupied = false; 
    this.correspondingPanel.BackColor = Color.Beige; 
    this.excluded = true; 
} 

那麼我也只好以確保循環被正確地打破：

public Algorithm.walkOver(Cell target) 
{ 
    if (target.Occupied && !target.excluded) 
    { 
     bool b = true; 

    //if there could no changes be made, we also have to return there were no changes... 
    //else the while loop continues forever and we lose the process :(
     if (target.Right.Occupied && target.Left.Occupied 
      && target.Bot.Occupied && target.Top.Occupied) 
     b = false; 

     if(!target.Right.Occupied) 
      target.Right.populate(); 

     if (!target.Left.Occupied) 
      target.Left.populate(); 

     if (!target.Top.Occupied) 
      target.Top.populate(); 

     if (!target.Bot.Occupied) 
      target.Bot.populate(); 

     return b; 
    } 
    else 
    { 
     return false; 
    } 
} 

我也感動復位到while循環的開始，由於「艇員選拔」細胞被排除。