猫仔面的世界
0%

细胞自动机

Posted on Edited on Disqus:

细胞自动机

备注：文末有自己用Javascript简单实现的网页版细胞自动机（还挺好玩）

什么是细胞自动机

Imgur

细胞自动机（英语：Cellular automaton），又称格状自动机、元胞自动机,它是由无限个有规律、坚硬的方格组成，每格均处于一种有限状态。每格于t时的态由t-1时的一集有限格（这集叫那格的邻域）的态决定。每一格的“邻居”都是已被固定的。每次演进时，每格均遵从同一规矩一齐演进。

当然这个细胞自动机有一个游戏实现 ——康威生命游戏（英语：Conway’s Game of Life）

康威生命游戏规则

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

  1. 当前细胞为存活状态时，当周围低于2个（不包含2个）存活细胞时， 该细胞变成死亡状态。（模拟生命数量稀少）
  2. 当前细胞为存活状态时，当周围有2个或3个存活细胞时， 该细胞保持原样。
  3. 当前细胞为存活状态时，当周围有3个以上的存活细胞时，该细胞变成死亡状态。（模拟生命数量过多）
  4. 当前细胞为死亡状态时，当周围有3个存活细胞时，该细胞变成存活状态。 （模拟繁殖）

可以把最初的细胞结构定义为种子，当所有在种子中的细胞同时被以上规则处理后, 可以得到第一代细胞图。按规则继续处理当前的细胞图，可以得到下一代的细胞图，周而复始。

康威生命游戏的自由

有了核心的算法（游戏规则），康威生命就是一个具有生命的自由游戏。你可以在游戏中创造出自己的细胞世界。周而复始。

Conways_game_of_life_breeder_animation

自己实现的一个生命游戏

生命游戏其实并不是很复杂，自己实现一个还是挺好玩的。所以自己就用Vue实现了一个小小的生命游戏

核心思想

  • 下一步要做什么，生命游戏最重要就是下一步，不管游戏规则是如何，下一步状态是这个游戏发展的动力。

    1
    2
    3
    4
    5
    function nextStep(map) {
      let newMap;
      	//@TODO对newMap进行核心算法的编写
      return newMap;
    }

    此函数就是游戏的生命，将游戏规则编写进这个函数，Vue只负责渲染这个newMap就好了。

所以我们有以下函数

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
26
27
28
29
30
31
function nextStep(map) {
  let newMap = Array(map.length).fill(Array(map.length).fill(0)).map((i) => i.map((j) => 0));
  let countAlive = 0;
  for (let i = 0; i < map.length; i++) {
    for (let j = 0; j < map.length; j++) {
      countAlive =
        getMap(i + 1, j, map) +
        getMap(i - 1, j, map) +
        getMap(i, j + 1, map) +
        getMap(i, j - 1, map) +
        getMap(i + 1, j + 1, map) +
        getMap(i + 1, j - 1, map) +
        getMap(i - 1, j + 1, map) +
        getMap(i - 1, j - 1, map);
      if (map[i][j] === 0 && countAlive < 3) {
        newMap[i][j] = 0;
      }
      if (map[i][j] === 1 && 2 <= countAlive && countAlive <= 3) {
        newMap[i][j] = 1;
      }
      if (map[i][j] === 1 && (countAlive > 3 || countAlive < 2)) {
        newMap[i][j] = 0;
      }
      if (map[i][j] === 0 && countAlive === 3) {
        newMap[i][j] = 1;
      }
      countAlive = 0;
    }
  }
  return newMap;
}
  • 边界问题，最外层肯定都是没有细胞的，所以我们做了边界判断函数。
1
2
3
4
5
6
function getMap(i, j, map) {
  if (i >= map.length || j >= map.length || i < 0 || j < 0) {
    return 0;
  }
  return map[i][j];
}

  • 文件导出导入 当然加了扩展功能，保存自己喜欢的细胞自动机成文件。

  • 速度调整 扩展功能，调整下一步的速度。

实现的效果

img

Github源代码，喜欢就给个Star。细胞自动机