發(fā)布時間：2016-09-27 13:23

  本文關(guān)鍵詞：細(xì)胞自動機，由筆耕文化傳播整理發(fā)布。

CellularAutomation(細(xì)胞自動機)

細(xì)胞自動機（英語：Cellular automaton），又稱格狀自動機、元胞自動機，是一種離散模型，在可算性理論、數(shù)學(xué)及理論生物學(xué)都有相關(guān)研究。它是由無限個有規(guī)律、堅硬的方格組成，每格均處于一種有限狀態(tài)。整個格網(wǎng)可以是任何有限維的。同時也是離散的。每格于t時的態(tài)由 t-1時的一集有限格（這集叫那格的鄰域）的態(tài)決定。 每一格的“鄰居”都是已被固定的。（一格可以是自己的鄰居。）每次演進(jìn)時，每格均遵從同一規(guī)矩一齊演進(jìn)。

就形式而言，細(xì)胞自動機有三個特征：

平行計算（parallel computation）：每一個細(xì)胞個體都同時同步的改變
局部的（local）：細(xì)胞的狀態(tài)變化只受周遭細(xì)胞的影響。
一致性的（homogeneous）：所有細(xì)胞均受同樣的規(guī)則所支配

生命游戲

生命游戲中，對于任意細(xì)胞，規(guī)則如下：
每個細(xì)胞有兩種狀態(tài)-存活或死亡，每個細(xì)胞與以自身為中心的周圍八格細(xì)胞產(chǎn)生互動。（如圖，黑色為存活，白色為死亡）

當(dāng)前細(xì)胞為存活狀態(tài)時，當(dāng)周圍低于2個（不包含2個）存活細(xì)胞時， 該細(xì)胞變成死亡狀態(tài)。（模擬生命數(shù)量稀少）
當(dāng)前細(xì)胞為存活狀態(tài)時，，當(dāng)周圍有2個或3個存活細(xì)胞時， 該細(xì)胞保持原樣。
當(dāng)前細(xì)胞為存活狀態(tài)時，當(dāng)周圍有3個以上的存活細(xì)胞時，該細(xì)胞變成死亡狀態(tài)。（模擬生命數(shù)量過多）
當(dāng)前細(xì)胞為死亡狀態(tài)時，當(dāng)周圍有3個存活細(xì)胞時，該細(xì)胞變成存活狀態(tài)。 （模擬繁殖）
可以把最初的細(xì)胞結(jié)構(gòu)定義為種子，當(dāng)所有在種子中的細(xì)胞同時被以上規(guī)則處理后, 可以得到第一代細(xì)胞圖。按規(guī)則繼續(xù)處理當(dāng)前的細(xì)胞圖，可以得到下一代的細(xì)胞圖，周而復(fù)始。

在這個游戲中，還可以設(shè)定一些更加復(fù)雜的規(guī)則，例如當(dāng)前方格的狀況不僅由父一代決定，而且還考慮祖父一代的情況。玩家還可以作為這個世界的“上帝”，隨意設(shè)定某個方格細(xì)胞的死活，以觀察對世界的影響。

在游戲的進(jìn)行中，雜亂無序的細(xì)胞會逐漸演化出各種精致、有形的結(jié)構(gòu)；這些結(jié)構(gòu)往往有很好的對稱性，而且每一代都在變化形狀。一些形狀已經(jīng)鎖定，不會逐代變化。有時，一些已經(jīng)成形的結(jié)構(gòu)會因為一些無序細(xì)胞的“入侵”而被破壞。但是形狀和秩序經(jīng)常能從雜亂中產(chǎn)生出來。

有個可以直接玩這個游戲的鏈接 - 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); } } } } } }

代碼其實就是按照前面算法的描述實現(xiàn)出來。

初始的細(xì)胞分布用了Unity自帶的隨機來生成，然后在OnDrawGizmos函數(shù)中繪制出來。運行起來是這樣的：

可以將初始狀態(tài)設(shè)置為經(jīng)典的glider，修改 initEarth() 函數(shù)就可以了。

//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;

程序生成地形

程序生成有很多中方法，利用細(xì)胞自動機主要用生成地牢等類似的地形，常用于Roguelike類的游戲。主要的算法就是還是利用細(xì)胞生存的規(guī)則，比如現(xiàn)在規(guī)定只要細(xì)胞周圍有四個以上的細(xì)胞，該細(xì)胞就存活，否則死去。

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; } }

不斷迭代，就可以得到一張地圖。當(dāng)然首先還是要在畫布上隨機分布一些細(xì)胞。迭代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); } } } } }

參考

細(xì)胞自動機wiki - https://zh.wikipedia.org/wiki/%E7%B4%B0%E8%83%9E%E8%87%AA%E5%8B%95%E6%A9%9F

Game of Life - 

Procedural Cave Generation Project Icon - https://unity3d.com/learn/tutorials/projects/procedural-cave-generation-tutorial

  本文關(guān)鍵詞：細(xì)胞自動機，由筆耕文化傳播整理發(fā)布。

本文編號：124533