生命游戏 - 这个算法是什么

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循环的开始，由于“艇员选拔”细胞被排除。