65.9K
CodeProject 正在变化。 阅读更多。
Home

生命游戏：C# 代码解决方案

Kailash Shastri
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.55/5 (7投票s)

2012年2月17日

CPOL

8分钟阅读

viewsIcon

103808

downloadIcon

4809

Conway 的生命游戏问题的面向对象解决方案（C#）。

引言

让我们从介绍“生命游戏”问题开始。根据维基百科，“生命游戏”，也简单地称为“生命”，是由英国数学家 John Horton Conway 于 1970 年提出的一个细胞自动机。

这个“游戏”是一个零玩家游戏，意味着它的演化由其初始状态决定，无需进一步的输入。通过创建初始配置并观察其如何演化来与生命游戏互动。

生命游戏宇宙是一个无限的二维正交网格，每个细胞都有两种可能的状态：存活或死亡。每个细胞都与其八个邻居互动，这些邻居是直接在水平、垂直或对角线上相邻的细胞。在每个时间步长，会发生以下转变：

  1. 任何拥有少于两个存活邻居的存活细胞都会因孤独而死亡。

  2. 任何拥有多于三个存活邻居的存活细胞都会因过度拥挤而死亡。

  3. 任何拥有两个或三个存活邻居的存活细胞将保持存活，不变，进入下一代。

  4. 任何拥有恰好三个存活邻居的死亡细胞将复活。

初始模式构成了系统的“种子”。第一代是通过同时将上述规则应用于种子中的每个细胞来创建的——出生和死亡同时发生，这个离散的时刻有时被称为一次“滴答”。（换句话说，每一代都是前一代的纯函数。）这些规则会持续重复应用以创建更长的世代。

问题

下面的输入代表宇宙中的细胞，用 X 或 - 表示。X 是一个存活的细胞。- 是一个死亡的细胞或没有细胞。下面的输入提供了宇宙中的模式或初始细胞。输出是下一次“滴答”（所有规则应用一次）时系统的状态，以相同的格式表示。

方块模式

输入 A
输出 A
329881/Square1.png
329881/Square1.png
船型模式
输入 B
输出 B
329881/Input_B.png
329881/Input_B.png
闪烁器模式
输入 C
输出 C
329881/Input_C.png329881/Output_C.png
蟾蜍模式

输入 D
输出 D
329881/Input_D.png329881/Outout_D.png

需要注意的是，在输出 D 中，新增的两行是由于规则 #4，即“任何拥有恰好三个存活邻居的死亡细胞将复活”。因此，下一个状态将包含两行新自动生长的行。

背景

这看起来很有趣，并且似乎用结构化语言实现逻辑不会太难。然而，这里有几个陷阱。

  1. 另一个陷阱是需要以面向对象的方式实现，这有点棘手。这意味着设计应该符合面向对象原则。
  2. 第一代是通过同时将上述规则应用于种子中的每个细胞来创建的。我认为我们可能需要某种形式的线程实现来提供对所有细胞的同步更新。

以面向对象的方式实现这样的解决方案是一项非常具有挑战性的任务。然而，我们将提出一个遵守面向对象原则的设计。

处理网格世代

我脑海中第一个想法是为初始世代和下一世代保留独立的网格。开始时，我们将有两个网格，例如输入网格和输出网格。输入网格是生命游戏开始时的初始状态。输出网格将包含输入网格的下一代。我们需要为输入网格中的每个细胞应用规则，并将细胞的下一代放入输出网格。如果需要行或列的增长，则会将它们添加到输出网格。

请注意，输入网格的状态不会在生成下一代时被更新，因此没有运行时单元格状态变化的考虑。换句话说，将输入网格视为一个冻结单元格的网格，而输出网格将发生变化，直到输入网格中的所有单元格都被评估。请参见下图。

329881/Generation_Overview.png

一代完成后，我们将交换输出网格和输入网格，然后继续这个过程。

二维矩阵的考虑

我们需要实现一个二维矩阵，其中每个单元格包含两个布尔值之一：存活或死亡。这个二维结构应该能够在任何一侧增长，例如，可以在顶部和底部添加新行，可以在第一个列之前和最后一个列之后添加新列。这给了我们列表的感觉，因为我们不需要通过索引来引用单元格，而是需要从第一个元素枚举到最后一个元素。

从上面的讨论可以清楚地看出，我们正在转向利用 C# 的列表集合类。我们有一个自定义的 Cell 类，它有一个布尔属性 IsAlive。这将使实现更具可扩展性。

此外，为了容纳一个单元格列表，我们有一个名为 Row 的自定义对象，它包含一个单元格列表。因此，我们的网格将包含此类行的列表，而这些行又包含列的列表。

让我们看看我们的 Grid 会是什么样子。

    public class Grid
    {
        // List of Rows in Grid        
        public List<Row> GridObj { set; get; }

        // other code ...

    }

每一行表示如下：

    public class Row
    {
       //List of Cells
        public List<Cell> Cells { get; set; } 

        // other code ...

    }

最后，每个 Cell 会是这样的：

    public class Cell
    {
         //A Cell can be alive or dead based on this property - true = alive and false = dead
         public Boolean IsAlive { get; set; }  

        // other code ...

    }
此外，如果需要在单元格级别添加任何其他行为，可以在 Cell 类中轻松完成。

同步更新所有单元格的考虑

这是关于同步更新生命游戏网格中所有单元格的一个非常重要的点。乍一看这似乎微不足道。在继续之前，让我们分析一下以下问题：

我们如何同时更新所有单元格？
单元格的更新是否依赖于其他单元格的更新？

问题 1 的答案很简单。这里不需要 CPU 同时执行单元格更新操作，而是要求所有任务在不同的线程中并行完成，因为单元格的下一代不依赖于其他单元格的下一代。在这里，我们需要实现多线程来同时更新所有单元格。

第二个问题的答案有点棘手。正如最后一个句子所讨论的，单元格的下一代不依赖于其他单元格的下一代。这是真的，我们总是需要读取输入网格（它是冻结的），并将结果写入输出网格单元格。所以输出网格单元格的状态独立于输出网格中其他单元格的状态。然而，在某些情况下，输出网格可能会增长；可能会向输出网格添加新行或新列。这会导致并行操作出现问题。怎么会？想象一下 Thread1 正在更新网格的第一行。但是，其他线程 Thread2 在 Thread1 完成操作之前向输出网格添加了一行。现在，当 Thread1 更新第一行的单元格时，结果将是不正确的，因为（在 Thread2 执行之前）的第一行现在变成了第二行，但更改已应用于第一行。因此，输出网格将需要两种类型的任务：

  1. 更新输出网格中现有单元格的任务。
  2. 添加输出网格中行或列的任务。

329881/Parallel_Task_1_-_Copy.png

329881/Parallel_Task_2.png

在讨论代码时，我将详细解释这些任务。

使用代码

以下是实现生命游戏所使用的类列表：

Game: 这是解决方案的主要类，将用作游戏的**主接口**。该类的用户需要在初始级别提供行数和列数。
    public Game(int rows, int columns)
    {
        if (rows <= 0 || columns <= 0) throw new ArgumentOutOfRangeException("Row 
        and Column size must be greater than zero");
        _inputGrid = new Grid(rows, columns);
        _outputGrid = new Grid(rows, columns);           
    }


用户可以选择设置生命游戏的**最大世代数**。
       objLifeGame.MaxGenerations  = maxGenerations;

此外，用户需要通过调用 `TogglegridCell` 方法来设置网格中的一些单元格为**存活**。
    Game objLifeGame = new Game(3, 3);
    objLifeGame.ToggleGridCell(0, 1);
    objLifeGame.ToggleGridCell(1, 1);
它还包含两个**并行执行的任务**来同时更新网格。请注意，我们正在使用两个并行执行的任务。
    // 1. Task for changing all existing Cell Status        
    private Task EvaluateCellTask;
    // 2. Task for expanding output gird if respective rule satisfies
    private Task EvaluateGridGrowthTask;
Grid: 这个类是一个动态的二维数据结构，用于保存单元格矩阵。它包含行（`List`）的泛型列表，而行又包含单元格（`List`）的列表。
Row: 这个类是单元格的泛型列表。用户可以在单元格列表的末尾添加一个单元格，或在指定索引处插入一个单元格。

Cells: 这个类以布尔属性 `IsAlive` 保存单元格数据的实际表示，`IsAlive` 为 true 表示存活，为 false 表示死亡。
Coordinates: 这是一个结构体，用于保存网格的 x 和 y 坐标。
    public struct CoOrdinates
    {
        public int X;
        public int Y;
        public CoOrdinates(int x, int y)
        {
            X = x;
            Y = y;
        }
    }

Rule: 这个类将网格转换到下一代的算法分离开来。它公开 `ChangeCellsState` 和 `ChangeGridState` 方法来对网格应用更改。它具有以下静态方法。
        public static void ChangeCellsState(Grid inputGrid, Grid outputGrid, CoOrdinates coOrdinates) 
    private static int CountAliveNeighbours(Grid grid, CoOrdinates coOrdinates)
    private static int IsAliveNeighbour(Grid grid, CoOrdinates baseCoOrdinates, CoOrdinates offSetCoOrdinates)
    private static Boolean IsAliveInNextState(Cell cell, int liveNeighbourCount)
    public static void ChangeGridState(Grid inputGrid, Grid outputGrid)
    private static void CheckColumnGrowth(Grid inputGrid, Grid outputGrid, int colId)
    private static void CheckRowGrowth(Grid inputGrid, Grid outputGrid, int rowId)

ReachableCell: 这是一个专门的类，用于简化从给定单元格遍历相邻单元格的过程。它为任何大小的网格上的唯一单元格类型保留可达的相邻单元格位置。单元格类型是共享相似相邻单元格的不同单元格位置。
        // Dictionary to hold list of reachable cells co-ordinates for specified cell type
    public static Dictionary<CellTypeEnum, List<CoOrdinates>> ReachableCellDictionary;

网格中的每个单元格都将具有一组唯一的、相邻的可达单元格。例如，索引为 (0,0) 的左上角单元格可以有三个可达的相邻单元格 (0,1)、(1,0) 和 (1,1)。类似地，任何顶部单元格，索引为 (0,1)，可以有 5 个可达的相邻单元格 (0,2)、(1,2)、(1,1)、(1,0) 和 (0,0)。下面是一些示例：

从左上角单元格可达的单元格
从顶部单元格可达的单元格
从中心单元格可达的单元格
329881/Reachable_Cell_1.png329881/Reachable_Cell_2.png329881/Reachable_Cell_3.png

根据单元格坐标的位置，可以将其大致分为以下几类：
       /// <summary>
    /// Cell types are unique types of cell in grid of any size
    /// Every cell type has distinct reachable djacent cells which can be traversed
    /// </summary>
    public enum CellTypeEnum
    {
        TopLeftCorner,
        TopRightCorner,
        BottomLeftCorner,
        BottomRightCorner,
        TopSide,
        BottomSide,
        LeftSide,
        RightSide,
        Center,
        OuterTopSide,
        OuterRightSide,
        OuterBottomSide,
        OuterLeftSide,
        None
    }

下图显示了 4x4 网格中所有可用的单元格类型。对于任何其他网格，单元格类型都可以以类似的方式使用。

329881/Cell_Enum_Types.png


GridHelper: 这是一个静态助手类，用于执行诸如显示网格和将源网格复制到目标网格等操作。

    /// <summary>
    /// Display the grid
    /// </summary>
    public static void Display(Grid grid)
    /// <summary>
    /// Deep copy Copy Source grid to target grid
    /// </summary>
    /// <param name="sourceGrid"></param>
    /// <param name="targetGrid"></param>
    public static void Copy(Grid sourceGrid, Grid targetGrid)
    /// <summary>
    /// Set target grid schema similar to source grid schema 
    /// </summary>
    /// <param name="sourceGrid"></param>
    /// <param name="targetGrid"></param>
    private static void MatchSchema(Grid sourceGrid, Grid targetGrid)
    /// <summary>
    /// Assign Source grid cell values to target grid
    /// </summary>
    /// <param name="sourceGrid"></param>
    /// <param name="targetGrid"></param>
    private static void AssignCellValues(Grid sourceGrid, Grid targetGrid)

参考文献

历史  

这是文章的第一个版本。欢迎读者评论。

© . All rights reserved.