Python实现元胞自动机（康威生命游戏）

元胞自动机是很常用的传播/交通模型，因此写下这篇文章，以后忘了可以再翻看

元胞自动机

元胞自动机又被称为康威生命游戏，是英国数学家约翰·何顿·康威在1970年发明的细胞自动机。它最初于1970年10月在《科学美国人》杂志上马丁·葛登能的“数学游戏”专栏出现

元胞自动机是一个零玩家游戏。他包括一个二维矩形世界，这个世界中的每个方格居住着一个活着的或死了的细胞。一个细胞在下一时刻的生死取决于相邻八个方格中或者的或死了的细胞数量

可以先在下面的地址中试玩
http://pmav.eu/stuff/javascript-game-of-life-v3

规则

每个细胞有两种状态-存活或死亡，每个细胞与以自身为中心的周围八格细胞产生互动：

• 细胞过少：当周围低于2个（不包含2个）存活细胞时，本单元活细胞死亡
• 稳定：当周围有2个或3个存活细胞时，本单元细胞保持原样
• 人口过剩：当周围有3个以上的存活细胞时，本单元活细胞死亡
• 繁殖：当周围有3个存活细胞时，本单元细胞存活/活化

初看觉得这就是个模拟细胞繁衍的东西，规则也很简单。

随着游戏的进行，杂乱无序的细胞会逐渐演化出各种精致、有形的结构，这些结构往往有很好的对称性，而且每一代都在变化形状，一些形状已经锁定，不会逐代变化。有时，一些已经成形的结构会因为一些无序细胞的"入侵"而被破坏。但是形状和秩序经常能从杂乱中产生出来。对于生成的形状和秩序，我们称作pattern(模式)

开发准备

首先安装pygame

pip install pygame

开发步骤

我们使用矩阵来记录我们的游戏世界，其中0表示细胞死亡，1表示细胞存活

感谢The Game of Life in Python这篇博文，一行代码解决了计算细胞周围活细胞数量的问题

nbrs_count = sum(np.roll(np.roll(X, i, 0), j, 1)
                 for i in (-1, 0, 1) for j in (-1, 0, 1)
                 if (i != 0 or j != 0))

由于我们的游戏世界是上下左右循环的，所以将矩阵往8个方向进行循环移位得到8个新矩阵，将8个新矩阵相加就能得到每个细胞周围的活细胞数量矩阵了

np.roll操作就是循环移位操作。np.roll(X, i, 0)中的X代表输入矩阵，i代表以为的大小，0代表移位的维度，np.roll(X, 1, 0)代表矩阵下移一格，np.roll(X, 1, 2)代表右移一格，if (i != 0 or j != 0)是为了不计算死亡的细胞

通过活细胞数量矩阵根据更新规则更新我们的世界。因为矩阵单位只有两种状态，这里我们只考虑存货态就可以了。注意到存活的条件是：

• 稳定：当周围有2个或3个存活细胞时，本单元细胞保持原样
• 繁殖：当周围有3个存活细胞时，本单元细胞存活/活化

即细胞周围数量等于3或者本单元细胞存活的同时周围有2个存活细胞时候，本单元细胞将在下一代存活

翻译过来就是

(nbrs_count == 3) | (X & (nbrs_count == 2))

注意到这种方法虽然便捷，但效率显然不怎么样。因为这种做法更新了矩阵的每一个单元，这完全没有必要，大部分情况下矩阵都是稀疏的，如何改进希望读者自己尝试

我们实现生命游戏的操作如下：

• R键：重置世界
• 回车键：进行演化
• 空格键：暂停演化
• 鼠标左键：增添一个细胞
• 鼠标右键：销毁一个细胞

下面是用pygame实现的全部代码

# -*- coding: utf-8 -*-
import pygame, sys, time
import numpy as np
from pygame.locals import *

# Matrix width and matrix height
WIDTH = 80
HEIGHT = 40

# A global variable that records mouse button conditions
pygame.button_down = False

# A matrix that records the game world
pygame.world=np.zeros((HEIGHT,WIDTH))

# Create a Cell class to facilitate Cell drawing
class Cell(pygame.sprite.Sprite):

    size = 10

    def __init__(self, position):

        pygame.sprite.Sprite.__init__(self)

        self.image = pygame.Surface([self.size, self.size])

        # Fill in the white
        self.image.fill((255,255,255))

        # Creates a rectangle with the upper-left corner as the anchor point
        self.rect = self.image.get_rect()
        self.rect.topleft = position

# Drawing function
def draw():
    screen.fill((0,0,0))
    for sp_col in range(pygame.world.shape[1]):
        for sp_row in range(pygame.world.shape[0]):
            if pygame.world[sp_row][sp_col]:
                new_cell = Cell((sp_col * Cell.size,sp_row * Cell.size))
                screen.blit(new_cell.image,new_cell.rect)

# Update the map according to cell update rules
def next_generation():
    nbrs_count = sum(np.roll(np.roll(pygame.world, i, 0), j, 1)
                 for i in (-1, 0, 1) for j in (-1, 0, 1)
                 if (i != 0 or j != 0))

    pygame.world = (nbrs_count == 3) | ((pygame.world == 1) & (nbrs_count == 2)).astype('int')

# init Map
def init():
    pygame.world.fill(0)
    draw()
    return 'Stop'

# Stop operation
def stop():
    for event in pygame.event.get():
        if event.type == QUIT:
            pygame.quit()
            sys.exit()

        if event.type == KEYDOWN and event.key == K_RETURN:
            return 'Move'

        if event.type == KEYDOWN and event.key == K_r:
            return 'Reset'

        if event.type == MOUSEBUTTONDOWN:
            pygame.button_down = True
            pygame.button_type = event.button

        if event.type == MOUSEBUTTONUP:
            pygame.button_down = False

        if pygame.button_down:
            mouse_x, mouse_y = pygame.mouse.get_pos()

            sp_col = int(mouse_x / Cell.size);
            sp_row = int(mouse_y / Cell.size);

            if pygame.button_type == 1: # The left mouse button
                pygame.world[sp_row][sp_col] = 1
            elif pygame.button_type == 3: # The right mouse button
                pygame.world[sp_row][sp_col] = 0
            draw()

    return 'Stop'

# Timer, control frame rate
pygame.clock_start = 0


# Evolution operations
def move():
    for event in pygame.event.get():
        if event.type == QUIT:
            pygame.quit()
            sys.exit()
        if event.type == KEYDOWN and event.key == K_SPACE:
            return 'Stop'
        if event.type == KEYDOWN and event.key == K_r:
            return 'Reset'
        if event.type == MOUSEBUTTONDOWN:
            pygame.button_down = True
            pygame.button_type = event.button

        if event.type == MOUSEBUTTONUP:
            pygame.button_down = False

        if pygame.button_down:
            mouse_x, mouse_y = pygame.mouse.get_pos()

            sp_col = mouse_x / Cell.size;
            sp_row = mouse_y / Cell.size;

            if pygame.button_type == 1:
                pygame.world[sp_row][sp_col] = 1
            elif pygame.button_type == 3:
                pygame.world[sp_row][sp_col] = 0
            draw()


    if time.clock() - pygame.clock_start > 0.02:
        next_generation()
        draw()
        pygame.clock_start = time.clock()

    return 'Move'



if __name__ == '__main__':

    # init, stop, move
    state_actions = {
            'Reset': init,
            'Stop': stop,
            'Move': move
        }
    state = 'Reset'

    pygame.init()
    pygame.display.set_caption('Conway\'s Game of Life')

    screen = pygame.display.set_mode((WIDTH * Cell.size, HEIGHT * Cell.size))

    while True:

        state = state_actions[state]()
        pygame.display.update()