ZMonster's Blog 巧者劳而智者忧，无能者无所求，饱食而遨游，泛若不系之舟

生命游戏(Game of Life)及其Python实现

2014-07-04

生命游戏(The Game of Life)

生命游戏 是数学家John Horton Conway 发明的一个"零玩家游戏"，因此也被称为"Conway's Game of Life"。实际上它并非是一个游戏，其本质为一个元胞自动机(cellular automaton)。生命游戏由一个无限二维平面以及被定义在这个平面上的几条简单规则组成，一般来说，这个无限二维平面是由无限个相同大小的方形网格组成的，定义于其上的规则有：

  1. 每个网格称为cell
  2. 每个cell有两种状态，alive和dead，分别用两种不同的颜色来表示
  3. 每个cell的状态变化受其周围8个cell影响
  4. 如果一个活的(alive)cell，其周围的活的cell数量少于2——即为0或1，则这个cell将死去(dead)
  5. 如果一个活的cell，其周围的活的cell数量超过3——即为4至8，则这个cell将死去
  6. 如果一个活的cell，其周围的活的cell数量为2或3，则它继续存活
  7. 如果一个死的cell，其周围的活的cell数量为3，则它成为活的cell，否则仍然为死的cell

前面三条规则定义了"世界"的表示，后面四条规则定义了"世界"的变化规律。在这几条简单的规则下，生命游戏产生了难以想象的复杂、有规律的图像。

首先来看看一些简单的、经典的模式(pattern):

  1. 滑翔机(Glider)

    这个模式里的图案在不断变化时，形似一个在不断运行的滑翔机，因而得名。

  2. 滑翔机枪(Gosper Glider Gun)

    滑翔机枪可以源源不断地制造出滑翔机。最初John Horton Conway悬赏50美金希望有人创造出滑翔机枪，MIT的黑客Bill Gosper尝试了上百种可能，最后率先发现了这个模式并得到了奖金，这个模式也因此冠以Gosper的名字。

然后来看一些复杂的模式：

  1. 旅行者(Weekender)

  2. 蜘蛛(Spider)

    gol-spider.gif

生命游戏是Conway对John von Neumann提出的"可自我复制的机器"产生兴趣后创作出来的，并于1970年10月在《科学美国人》(Scientific American)上发表。从理论上来说，生命游戏与通用图灵机(Universal Turing Machine)是等价的。由于生命游戏的"可进化性"，在其发表后，就吸引了大批的人，时至今日，也仍然有不少人热衷于收集各种不同的模式，Unix/Linux系统上也还有生命游戏的实现，编辑器Emacs中也内置了一个生命游戏实现。

此外，生命游戏中还展现出了"涌现(Emergence)"和"自组织(Self-organization)"现象，甚至还催生出了人工生命(Artificial Life)这一领域。

Python实现

就生命游戏的规则而言，实现它是不需要多少工作量的，麻烦的是怎么通过图形来表现出来。最后我用Tkinter实现了一个简单的生命游戏，可以用鼠标点击的方式来设定初始模式，也可以通过下拉列表选择内置的模式，同时提供将自定义模式保存的功能。

为了保持代码逻辑上的简洁，我将状态更新的逻辑封装到了一个类里： 

class GOL():
    """Status manager of GOL(Game of Life).

    Each world in game of life is a set of cells, and status of
    every cell should be alive or dead. Status changes from gen
    -eration to generation.
    """
    def __init__(self, row = 0, col = 0):
        """Init size and status of world."""
        self.row = row
        self.col = col
        self.now = {}
        self.next = {}
        self.init_status([])

    def init_status(self, init_cells):
        """Set status of world.

        if the begining status given is not empty, then use them
        to initialize the world.

        Args:
          init_cells: begining status given. It's a tow-dimensional
                      array. Becase its size maybe smaller than the
                      world, we should be map each coordinate to the
                      center area of world.
        """
        # code is hiden

    def update(self):
        """Update status of world by status before.

        For each cell in world, do these things:
        1. look and find how many alive neighbors around,each cell
        have eight neighbors
        2. update status of cell according the number of its alive
           neighbors. The following are the rules
           + if cell is alive, and number of neighbors is too small
             (less than 2) or too too much(more than 3), this cell
             will die, or it will be keep alive
          + if cell is dead, and number of neighbors is three, then
            cell will be alive
        """
        # code is hiden

    def neighbors(self, row, col):
        """Compute number of alive neighbors around a cell."""
        # code is hiden

在这个类里，通过两个分别代表当前状态与将来状态的dict来进行状态的更新。在开始实现时犯了一个错误，就是在方法update()中，计算完self.next后，进行了一个错误的操作： 

self.now = self.next

结果导致这两个类成员变量称为了同一个对象的引用，修改其中一者，另一者也发生改变，最后导致结果不正确。最后update()方法如下所示： 

def update(self):
  """Update status of world by status before.

  For each cell in world, do these things:
  1. look and find how many alive neighbors around,each cell
     have eight neighbors
  2. update status of cell according the number of its alive
     neighbors. The following are the rules
     + if cell is alive, and number of neighbors is too small
       (less than 2) or too too much(more than 3), this cell
       will die, or it will be keep alive
     + if cell is dead, and number of neighbors is three, then
       cell will be alive
  """
  self.next = self.now.copy()
  for crow in range(self.row):
      for ccol in range(self.col):
          around = self.neighbors(crow, ccol)
          if (around < 2 or around > 3):
              self.next[crow, ccol] = False

          elif ((not self.now[crow, ccol]) and
                around == 3):
              self.next[crow, ccol] = True

  self.now = self.next.copy()

图形前端的实现大致如下： 

class ShowGOL(tk.Tk):
    """Diasplay the Game of Life

    Use Tkinter to draw the world of cells and the changes in
    the world.
    """
    def __init__(self, *args, **kwargs):
        """Init resource and world"""
        # init resource
        tk.Tk.__init__(self, *args, **kwargs)
        self.setup_members()    # initialize class members
        self.setup_window()     # root window
        self.setup_toolbar()    # tool bar
        self.setup_canvas()     # canvas to draw world

        # init world
        self.create_world()

        # make world alive
        self.after(5, lambda: self.life(5))

另外一些类方法就不列出来了，无非是绘图啊、事件响应啊什么的。代码我放到了Github上，如果需要，可以到这里 查看，或在本地执行： 

git clone [email protected]:Linusp/pygol

后记

老实说，我也算是生命游戏的忠实粉丝了——嗯，我不太喜欢"粉丝"这个词，不过姑且就这么用吧。以前也用ncurses库实现过一个简单的终端版本，也实现过兰顿蚂蚁(Langton's Ant)这个同为元胞自动机的例子。当然，要说我的实现，都是很简陋的，比如说生命游戏，在网上有非常多的相关实现，Linux下有一个名为gtklife的软件，内置了很多的模式，其中不乏一些复杂、绚丽的模式，这款软件也是被我列为Linux上必装的软件之一。

现在虽然实现了图形化的生命游戏，但我不想止步于此。目前用的是Python的Tkinter库，这个库上手简单，但功能有限。所以我会继续完善这个生命游戏实现的！

Naringu is designed by Rizky Ariestiyansyah
Copyright © 2024