CellularAutomation(细胞自动机)

CellularAutomation(细胞自动机)

细胞自动机（英语：Cellular automaton），又称格状自动机、元胞自动机，是一种离散模型，在可算性理论、数学及理论生物学都有相关研究。它是由无限个有规律、坚硬的方格组成，每格均处于一种有限状态。整个格网可以是任何有限维的。同时也是离散的。每格于t时的态由 t-1时的一集有限格（这集叫那格的邻域）的态决定。 每一格的“邻居”都是已被固定的。（一格可以是自己的邻居。）每次演进时，每格均遵从同一规矩一齐演进。

就形式而言，细胞自动机有三个特征：

平行计算（parallel computation）：每一个细胞个体都同时同步的改变
局部的（local）：细胞的状态变化只受周遭细胞的影响。
一致性的（homogeneous）：所有细胞均受同样的规则所支配

生命游戏

生命游戏中，对于任意细胞，规则如下：
每个细胞有两种状态-存活或死亡，每个细胞与以自身为中心的周围八格细胞产生互动。（如图，黑色为存活，白色为死亡）

当前细胞为存活状态时，当周围低于2个（不包含2个）存活细胞时， 该细胞变成死亡状态。（模拟生命数量稀少）
当前细胞为存活状态时，当周围有2个或3个存活细胞时， 该细胞保持原样。
当前细胞为存活状态时，当周围有3个以上的存活细胞时，该细胞变成死亡状态。（模拟生命数量过多）
当前细胞为死亡状态时，当周围有3个存活细胞时，该细胞变成存活状态。 （模拟繁殖）
可以把最初的细胞结构定义为种子，当所有在种子中的细胞同时被以上规则处理后, 可以得到第一代细胞图。按规则继续处理当前的细胞图，可以得到下一代的细胞图，周而复始。

在这个游戏中，还可以设定一些更加复杂的规则，例如当前方格的状况不仅由父一代决定，而且还考虑祖父一代的情况。玩家还可以作为这个世界的“上帝”，随意设定某个方格细胞的死活，以观察对世界的影响。

在游戏的进行中，杂乱无序的细胞会逐渐演化出各种精致、有形的结构；这些结构往往有很好的对称性，而且每一代都在变化形状。一些形状已经锁定，不会逐代变化。有时，一些已经成形的结构会因为一些无序细胞的“入侵”而被破坏。但是形状和秩序经常能从杂乱中产生出来。

有个可以直接玩这个游戏的链接 - Game of Life

下面用Unity自己写一下。

using UnityEngine;  
using System.Collections;  
public enum State{  
    Died,  
    Living  
};  
public class Cell  
{  
    public State currentState;  
}  
public class Earth : MonoBehaviour {  
    public int width;  
    public int height;  
    public string seed;  
    public bool useRandomSeed;  
    public float updateInterval = 1.0f;  
    float refreshTime = -1f;  
    [Range(0, 100)]  
    public int randomFillPercent;  
    Cell[,] map;  
    Cell[,] mapTmp;  
    // Use this for initialization  
    void Start () {  
        map = new Cell[width,height];  
        mapTmp = new Cell[width, height];  
        for (int i = 0; i < width; i )  
            for (int j = 0; j < height; j )  
            {  
                map[i,j] = new Cell();  
                map[i, j].currentState = State.Died;  
                mapTmp[i, j] = new Cell();  
                mapTmp[i, j].currentState = State.Died;  
            }  
        initEarth();  
    }  
    // Update is called once per frame  
    void Update () {  
        if(Time.time - refreshTime > updateInterval)  
        {  
            UpdateEarth();  
            refreshTime = Time.time;  
        }  
    }  
    void UpdateEarth()  
    {  
        for (int x = 0; x < width; x )  
        {  
            for (int y = 0; y < height; y )  
            {  
                mapTmp[x, y].currentState = map[x, y].currentState;  
                int neighbourLiveCells = GetSurroundingLiveCells(x, y);  
                if (map[x, y].currentState == State.Died && neighbourLiveCells == 3)  
                {  
                    mapTmp[x, y].currentState = State.Living;  
                }  
                if (map[x, y].currentState == State.Living)  
                {  
                    if(neighbourLiveCells < 2)  
                    {  
                        mapTmp[x, y].currentState = State.Died;  
                    }else if( neighbourLiveCells > 3)  
                    {  
                        mapTmp[x, y].currentState = State.Died;  
                    }  
                    else  
                    {  
                        mapTmp[x, y].currentState = State.Living;  
                    }  
                }  
            }  
        }  
        for (int x = 0; x < width; x )  
            for (int y = 0; y < height; y )  
            {  
                map[x, y].currentState = mapTmp[x, y].currentState;  
            }  
    }  
    int GetSurroundingLiveCells(int gridX, int gridY)  
    {  
        int count = 0;  
        for (int neighbourX = gridX - 1; neighbourX <= gridX   1; neighbourX )  
        {  
            for (int neighbourY = gridY - 1; neighbourY <= gridY   1; neighbourY )  
            {  
                if (neighbourX >= 0 && neighbourX < width && neighbourY >= 0 && neighbourY < height)  
                {  
                    if (neighbourX != gridX || neighbourY != gridY)  
                    {  
                        count  = map[neighbourX, neighbourY].currentState == State.Living? 1 : 0;  
                    }  
                }  
            }  
        }  
        return count;  
    }  
    void initEarth()  
    {  
        if (useRandomSeed)  
        {  
            seed = Time.time.ToString();  
        }  
        System.Random pseudoRandom = new System.Random(seed.GetHashCode());  
        for (int x = 0; x < width; x )  
        {  
            for (int y = 0; y < height; y )  
            {  
                if (x == 0 || x == width - 1 || y == 0 || y == height - 1)  
                {  
                    map[x, y].currentState = State.Living;  
                }  
                else  
                {  
                    map[x, y].currentState = (pseudoRandom.Next(0, 100) < randomFillPercent) ? State.Living : State.Died;  
                }  
            }  
        }  
    }  
    void OnDrawGizmos()  
    {  
        if (map != null)  
        {  
            for (int x = 0; x < width; x )  
            {  
                for (int y = 0; y < height; y )  
                {  
                    if (map[x, y] != null)  
                    {  
                        Gizmos.color = (map[x, y].currentState == State.Living) ? Color.black : Color.white;  
                        Vector3 pos = new Vector3(-width / 2   x   .5f, 0, -height / 2   y   .5f);  
                        Gizmos.DrawCube(pos, Vector3.one);  
                    }  
                }  
            }  
        }  
    }  
} 

代码其实就是按照前面算法的描述实现出来。

初始的细胞分布用了Unity自带的随机来生成，然后在OnDrawGizmos函数中绘制出来。运行起来是这样的：

可以将初始状态设置为经典的glider，修改 initEarth() 函数就可以了。

//Glider  
map[20, 20].currentState = State.Living;  
map[20, 21].currentState = State.Living;  
map[20, 22].currentState = State.Living;  
map[21, 22].currentState = State.Living;  
map[22, 21].currentState = State.Living; 

程序生成地形

程序生成有很多中方法，利用细胞自动机主要用生成地牢等类似的地形，常用于Roguelike类的游戏。主要的算法就是还是利用细胞生存的规则，比如现在规定只要细胞周围有四个以上的细胞，该细胞就存活，否则死去。

for (int x = 0; x < width; x )  
        {  
            for (int y = 0; y < height; y )  
            {  
                int neighbourWallTiles = GetSurroundingWallCount(x, y);  
                if (neighbourWallTiles > 4)  
                    map[x, y] = 1;  
                else if (neighbourWallTiles < 4)  
                    map[x, y] = 0;  
            }  
        }  

不断迭代，就可以得到一张地图。当然首先还是要在画布上随机分布一些细胞。迭代5次，最终生成地图如下

    

代码清单

using UnityEngine;  
using System.Collections;  
public class MapGenerator : MonoBehaviour {  
    public int width;  
    public int height;  
    public string seed;  
    public bool useRandomSeed;  
    [Range(0, 100)]  
    public int randomFillPercent;  
    int[,] map;  
    // Use this for initialization  
    void Start () {  
        GenerateMap();  
    }  
    // Update is called once per frame  
    void Update () {  
        if (Input.GetMouseButtonDown(0))  
        {  
            GenerateMap();  
        }  
    }  
    void GenerateMap()  
    {  
        map = new int[width, height];  
        RandomFillMap();  
        for (int i = 0; i < 5; i )  
        {  
            SmoothMap();  
        }  
    }  
    void RandomFillMap()  
    {  
        if (useRandomSeed)  
        {  
            seed = Time.time.ToString();  
        }  
        System.Random pseudoRandom = new System.Random(seed.GetHashCode());  
        for (int x = 0; x < width; x )  
        {  
            for (int y = 0; y < height; y )  
            {  
                if (x == 0 || x == width - 1 || y == 0 || y == height - 1)  
                {  
                    map[x, y] = 1;  
                }  
                else  
                {  
                    map[x, y] = (pseudoRandom.Next(0, 100) < randomFillPercent) ? 1 : 0;  
                }  
            }  
        }  
    }  
    void SmoothMap()  
    {  
        for (int x = 0; x < width; x )  
        {  
            for (int y = 0; y < height; y )  
            {  
                int neighbourWallTiles = GetSurroundingWallCount(x, y);  
                if (neighbourWallTiles > 4)  
                    map[x, y] = 1;  
                else if (neighbourWallTiles < 4)  
                    map[x, y] = 0;  
            }  
        }  
    }  
    int GetSurroundingWallCount(int gridX, int gridY)  
    {  
        int wallCount = 0;  
        for (int neighbourX = gridX - 1; neighbourX <= gridX   1; neighbourX )  
        {  
            for (int neighbourY = gridY - 1; neighbourY <= gridY   1; neighbourY )  
            {  
                if (neighbourX >= 0 && neighbourX < width && neighbourY >= 0 && neighbourY < height)  
                {  
                    if (neighbourX != gridX || neighbourY != gridY)  
                    {  
                        wallCount  = map[neighbourX, neighbourY];  
                    }  
                }  
                else  
                {  
                    wallCount ;  
                }  
            }  
        }  
        return wallCount;  
    }  
    void OnDrawGizmos()  
    {  
        if (map != null)  
        {  
            for (int x = 0; x < width; x )  
            {  
                for (int y = 0; y < height; y )  
                {  
                    Gizmos.color = (map[x, y] == 1) ? Color.black : Color.white;  
                    Vector3 pos = new Vector3(-width / 2   x   .5f, 0, -height / 2   y   .5f);  
                    Gizmos.DrawCube(pos, Vector3.one);  
                }  
            }  
        }  
    }  
}