元胞自动机

Posted on | Edited on

我是通过生命游戏这个词，进而了解到元胞自动机的，先看生命游戏 这个听起来很”有趣”的游戏到底是怎么玩的：

生命游戏

注：本文讨论的生命游戏是指 康威生命游戏（Conway’s Game of Life）

定义：
  • 二维空间上的一个网格（正方形）代表一个元胞
  • 元胞具有两种状态：”死亡”、”存活”
  • 元胞周围的 8 个网格称为元胞的邻居
规则：
  • 当前元胞为”存活”，当存活的邻居个数小于 2 时，该元胞死亡（模拟生命数量稀少）
  • 当前元胞为”存活”，当存活的邻居个数为 2 或 3 时，该元胞保持存活
  • 当前元胞为”存活”，当存活的邻居个数大于 3 时，该元胞死亡（模拟生命数量过多）
  • 当前元胞为”死亡”，当存活的邻居个数等于 3 时，该元胞状态转成存活（模拟生命繁殖）
开始游戏：

在一定范围的二维空间中，创建一定量的初始元胞，然后根据游戏规则，迭代该范围中元胞的状态变化

游戏欣赏：

（域名没有备案……所以没图）

程序实现（伪代码）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
cells; // 空间中元胞二维数组（已包含初始元胞的）
newCells; // 暂存每次时间迭代产生的新元胞

// 时间迭代
Timer.interval(1000){ 
   // 空间中的元胞迭代
   for(x=0;x<width;x++){
     for(y=0;x<height;y++){
       // 计算邻居数
       neighborsCount = countNeighbors(cells,width,height,x,y); 
       // 这里有个疑问：
       // 是在迭代的同时就改变当前元胞状态，即该元胞状态改变并对后续迭代产生影响，如下：
       // cells[x][y] = updateCellStatus(cells[x][y],neighborsCount);
       // 还是将元胞的新状态用新的二维数组存起来？？？
       // 个人觉得这里应该后者比较符合，但模拟其它问题就不一定：
       newCells[x][y] = updateCellStatus(cells[x][y],neighborsCount);
     }
   }
   // 更新界面
   updateViews(newCells);
   // 交换引用，准备迭代下一个时刻
   temp = newCells;
   newCells = cells;
   cells = temp;
}

元胞自动机（cellular automata，CA）

先简单看一下百科的解析（后面几段就不复制粘贴了）：

元胞自动机 是一种时间、空间、状态都离散，空间相互作用和时间因果关系为局部的网格动力学模型，具有模拟复杂系统时空演化过程的能力。

还是很懵……

再结合 生命游戏 来理解：

生命游戏 可以说是简单模拟了一个种群内部生命的演化（网上也有很多文章讨论——根据初始元胞设定的不同而产生的各种”神奇”演进图案，但不是本文的重点），我们也可以称其为一种模拟生命演化的模型。其次，我们完全可以通过修改或说变化 生命游戏 的一些定义、规则、应用场景等，做出另一个东西的演化模型。如：

  • 生命游戏 中定义的空间网格，其实重点就是平铺一个空间的想法，我们完全可以用平铺的等边三角形、菱形、等边六边型，甚至一维问题的线段、三维问题的正四、八面体等来替换
  • 生命游戏 中网格代表元胞，我们也可以把线段、晶格等代表其它东西，如：一维的方格中每个方格代表路况，来模拟交通情况
  • 生命游戏 中元胞有”存活”和”死亡”状态，而用一维的方格模拟交通状况时，每个”路况”方格也有”有车”和”没车”的状态，这类模型的状态通常都只考虑有限个的
  • 生命游戏 中以统计周围邻居数来模拟种群生命的演化，而路况问题可根据前面和后面”路况”有没有车来更新当前的”路况”状态，关键是根据实际模拟的问题设定单元的状态更新规则，当然这个规则要覆盖所模拟的单元的状态
元胞自动机 则是这一类模型的总称，总结几个描述性的特点：
  • 时间迭代，模拟问题的演化
  • 空间中的单元存在有限个状态
  • 单元的状态会受到空间内局部区域的其它单元的影响 
元胞自动机的应用

了解元胞自动机的概念之后，关键还是遇到类似上述特点的问题时，能不能想到用元胞自动机来解决，或是用元胞自动机来模拟一些有趣的东西或者玩法。网上也有很多，我就不找了，我自己倒是想了 2 个觉得比较有意思：

  • 用元胞自动机能不能解答数独问题，重点是格子的数字更新规则，我想如果遇到冲突便随机一个尽量不冲突的，再加一些标记等，这样做能不能做到一定有解
  • 玩游戏时，经常主角队都有几个伙伴要安排站位，这样可以利用元胞自动机与五行相生相克来设计对战时阵法变化，规则就是根据角色出招的元素、对方的阵法等来更新站位的元素