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);
}
}
}
}
}
參考
细胞自己主动机wiki - https://zh.wikipedia.org/wiki/%E7%B4%B0%E8%83%9E%E8%87%AA%E5%8B%95%E6%A9%9F
Game of Life - http://www.bitstorm.org/gameoflife/
Procedural Cave Generation Project Icon - https://unity3d.com/learn/tutorials/projects/procedural-cave-generation-tutorial
最新文章
- python爬取github数据
- MarkdownPad2 Pro v2.4.2.29969 专业中文破解版完美支持table表格语法
- make phpexcel working with XAMPP7.0.9
- php基础09:提取表单数据
- Linux-dd命令详解【转】
- HDU 5437 Alisha’s Party (优先队列)——2015 ACM/ICPC Asia Regional Changchun Online
- aspx页面记住密码
- Windows进程间通信的各种方法
- unmount的时候报错
- 玩转Vim-札记
- php 开发调试的常用技巧和工具​
- JPA数据懒加载LAZY配合事务@Transactional使用(三)
- 安卓开发JAVA基础之初识JAVA
- Weblogic10 集群配置
- Python开发爬虫之BeautifulSoup解析网页篇:爬取安居客网站上北京二手房数据
- 【easy】349. Intersection of Two Arrays
- 20175208 实验一 Java开发环境的熟悉
- 转《Angular4项目部署到服务器上刷新404解决办法》
- Spark之standalone模式
- 基于jquery横向手风琴效果
热门文章
- Django框架简介及模板Template,filter
- server 08 R2 NBL 报错:RPC 服务器在指定计算机上不可用
- Java-转换Unicode和utf-8
- 大数据学习——Storm+Kafka+Redis整合
- centos 7 安装vmware 12
- 多线程下,多次操作数据库报错,There is already an open DataReader associated with this Command which must be closed first.
- 【bzoj2901】矩阵求和 前缀和
- 2016 ACM-ICPC China Finals #F Mr. Panda and Fantastic Beasts
- HDU——1059Dividing(母函数或多重背包)
- BZOJ 1813 [Cqoi2017]小Q的棋盘 ——树形DP