细胞自动机初探之生命游戏

t1174779123

浏览: 70413 次
性别:
来自: 青岛

最近访客更多访客>>

u012363178

lostage

tianhandigeng

dengchao220

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

人工智能

细胞自动机初探——生命游戏

细胞自动机（Cellular Automaton），简单说就是能在生成许多自行演变的“小细胞”的程序，是一种很强大的人工智能实现，强大到几乎可以用来仿真研究社会和自然科学各个领域的问题，比如：构建模拟人群研究经济危机爆发过程，构建模拟生物群落研究生态系统演变，构建微观粒子群研究物理化学问题，构建“军队”模拟军事战场等等。由它引申出了数量地理学等学科，它更是分布式计算中的重要工具。。。。嘿嘿，是不是听起来很高端？想深入了解么？鄙人不才，今天带大家初步了解一下元胞自动机背后的故事。

1950年，计算机之父冯·诺伊曼写了一段程序用来模拟细胞复制过程，这就是最早的细胞自动机，只不过连冯诺伊曼本人也没太重视，所以这项研究很快就沉了。。。直到20年后的1970年，剑桥大学的约翰·何顿·康威设计了一个名为生命游戏（Life）的电脑游戏，细胞自动机才进入了科学家们的视野。后来，又有了模拟蚂蚁行为的兰顿蚂蚁（Langton ant）、模拟二极管电子逻辑的线世界（Wire world），再有史蒂芬·沃尔夫勒姆对初等细胞机256种规则所产生的模型进行了深入研究，并用熵来描述其演化行为，将细胞自动机分为平稳型、周期型、混沌型和复杂型，以至于今天应用到各个领域问题的研究……当然这是后话了，今天我们就以《生命游戏》为起点，揭开细胞自动机的神秘面纱。

生命游戏是一段很经典的仿真程序，我在网上可以找到很多实现代码，在Matlab上也有自带的demo。今天我就带大家从Matlab的demo入手，用java重写一个生命游戏。

首先我们运行Matlab中自带的demo文件我也传到了附件中（MATLAB\R2010b\toolbox\matlab\demos\life.m），运行结果如下：

屏幕中每个蓝点即所谓的“细胞”，当程序跑起来，你会看到很多神奇的现象，如某些区域出现像核爆一样的“细胞爆发”，然后归于沉寂，只剩零星的固定细胞，或者有像小飞船一样的细胞“小飞船”在平移；但是经过几十秒后，整个画面几乎都沉寂了：只有个别区域还有稳定存在的小细胞团。

事实上，这个程序中的“细胞”只遵循以下几个简单的规则：

1、当前细胞为死亡状态时，当周围有3个存活细胞时，该细胞变成存活状态。（模拟繁殖）

2、当前细胞为存活状态时，当周围低于2个（不包含2个）存活细胞时，该细胞变成死亡状态。（模拟人口稀少）

3、当前细胞为存活状态时，当周围有2个或3个存活细胞时，该细胞保持原样。

4、当前细胞为存活状态时，当周围有3个以上的存活细胞时，该细胞变成死亡状态。（模拟过度拥挤）

可以把最初的细胞结构定义为种子，当所有种子中的细胞同时被以上规则处理后, 可以得到第一代细胞图。按规则继续处理当前的细胞图，可以得到下一代的细胞图，周而复始，我们就看到了屏幕中的神奇的效果。

怎么样，是不是迫不及待了？下面我们就可以动手用java再现一个这样的生命游戏。

这个程序用到四个类：

MainUI：主窗体类，用来画出图形

Earth：地球（想不出更好的比喻了），承载”细胞”的容器，里面的land数组模拟地面上的细胞分布情况

LifeThread：用来不断更新数组以及执行重绘操作的线程类

MyListener：按钮监听器类，实现界面上start与stop按钮的功能

程序的逻辑其实很简单：用二维数组模拟地面空间的细胞图，1代表存活，0代表死亡，不断地遍历数组，根据上述规则更新数组，然后重绘，就实现了生命游戏。当然这里涉及到了线程的简单应用，很想我另一篇文章中的彩蛋程序，具体细节我就不再赘述了。

运行效果如下：

下面直接贴源代码：

MainUI类
import java.awt.BorderLayout;
import java.awt.Dimension;
import java.awt.Graphics;

import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JPanel;

public class MainUI extends JFrame{
	//地球
	private Earth earth;
	//窗体组件
	private JButton jb_start,jb_stop;
	private JPanel jp_center,jp_west;
	//初始化程序的方法
	public void init(){
		this.initEarth();
		this.showUI();
	}
	//显示界面的方法
	public void showUI(){
		this.setTitle("生命游戏");
		this.setSize(500,500);
		this.setDefaultCloseOperation(3);
		this.setLocationRelativeTo(null);
		this.jb_start = new JButton("start");
		this.jb_stop = new JButton("stop");
		
		this.jp_west = new JPanel();
		this.jp_west.setPreferredSize(new Dimension(80,100));
		this.jp_west.add(jb_start);
		this.jp_west.add(jb_stop);
		//this.jp_west.setBackground(Color.green);
		this.add(jp_west,BorderLayout.WEST);
		
		this.jp_center = new JPanel();
		//this.jp_center.setBackground(Color.red);
		this.add(jp_center,BorderLayout.CENTER);
		
		MyListener ml = new MyListener(this);
		this.jb_start.addActionListener(ml);
		this.jb_stop.addActionListener(ml);
		
		this.setVisible(true);
		Graphics g = this.jp_center.getGraphics();
		this.earth.setG(g);
		this.repaint();
	}
	//初始化大地的方法
	public void initEarth(){
		this.earth = new Earth();
		this.earth.initLand();
		this.repaint();
	}
	//重绘方法
	public void repaint(Graphics g){
		super.repaint();
		//System.out.println("在重绘");
		earth.drawCells();
	}
	public static void main(String [] args){
		new MainUI().init();
	}
	public Earth getEarth() {
		return this.earth;
	}
}

Earth类
import java.awt.Color;
import java.awt.Graphics;
import java.util.ArrayList;
import java.util.Random;

public class Earth {
	//表示地面的数组
	private int[][] land;
	//图像处理类
	private Graphics g;
	public void setG(Graphics g){
		this.g = g;
	}
	public Graphics getG() {
		return g;
	}
	//初始化大地的方法(增加边缘方便后面判断)
	public void initLand(){
		this.land = new int [102][102];
		for(int ii = 0;ii<102;ii++){
			for (int jj = 0;jj < 102;jj++){
				land[ii][jj] = 0;
			}
		}//初值为0
		//生成种子细胞
		System.out.println("生成种子之前：");
		printLand();
		this.setSeeds();
	}
	//生成种子细胞的方法
	public void setSeeds(){
		Random rand = new Random();
		int count = rand.nextInt(2000)+1000;//生成种子数
		//随机创建细胞种子
		int x=  0,y = 0;
		for (int ii = 0;ii < count;ii++){
			x = rand.nextInt(100)+1;
			y = rand.nextInt(100)+1;
			land[x][y] = 1;
		}
		System.out.println("生成种子之后：");
		printLand();
	}
	//更新地面数组的方法
	public void updataLand(){
		//创建临时数组，避免之前的改动影响后面
		int [][] tland = new int [102][102];
		for(int ii = 0;ii < 102;ii++){
			for(int jj = 0;jj< 102;jj++){
				tland[ii][jj] = land[ii][jj];
			}
		}
		//根据规则更新临时数组
		for(int ii = 1;ii<= 100;ii++){
			for(int jj = 1;jj <= 100;jj++){
				//计算周围存活数
				int neighbor = this.countNeighbors(jj, ii);
				//执行规则
				//规则1：	当前细胞为死亡状态时，当周围有3个存活细胞时，该细胞变成存活状态。
				if(land[ii][jj] == 0 && neighbor == 3){
					tland[ii][jj] = 1;
				}
				//规则2.当前细胞为存活状态时，当周围低于2个（不包含2个）存活细胞时， 该细胞变成死亡状态。（模拟人口稀少）
				if(land[ii][jj] == 1 && neighbor < 2){
					tland[ii][jj] = 0;
				}
				//规则3.当前细胞为存活状态时，当周围有2个或3个存活细胞时， 该细胞保持原样。
				if(land[ii][jj] == 1 && (neighbor == 2 || neighbor == 3)){
					tland[ii][jj] = 1;
				}
				//规则4.当前细胞为存活状态时，当周围有3个以上的存活细胞时，该细胞变成死亡状态。（模拟过度拥挤）
				if(land[ii][jj] == 1 && neighbor > 3){
					tland[ii][jj] = 0;
				}
			}
		}
		//最后替换以更新数组
		this.land = tland;
	}
	//计数细胞周围细胞数的方法
	public int countNeighbors(int x,int y){
		int count = 0;
		if(land[x-1][y] == 1){
			count++;
		}
		if(land[x+1][y] == 1){
			count++;
		}
		if(land[x][y-1] == 1){
			count++;		
		}
		if(land[x][y+1] == 1){
			count++;
		}
		if(land[x-1][y-1] == 1){
			count++;
		}
		if(land[x-1][y+1] == 1){
			count++;
		}
		if(land[x+1][y-1] == 1){
			count++;
		}
		if(land[x+1][y+1] == 1){
			count++;
		}
		return count;
	}
	//画出细胞的方法
	public void drawCells(){
		for(int ii  = 1;ii <= 100;ii++){
			for(int jj = 1;jj<= 100;jj++){
				if(land[ii][jj] == 1){
					g.setColor(Color.BLUE);
					g.drawRect(4*jj, 4*ii, 4, 4);
				}
			}
		}
	}
	//打印land数组的方法
	public void printLand(){
		for(int ii = 0;ii< 102;ii++){
			for(int jj = 0;jj < 102;jj++){
				System.out.print(land[jj][ii]+" ");
			}
			System.out.println();
		}
	}
}

LifeThread类
public class LifeThread extends Thread{
	private boolean running = true;
	private Earth earth;
	private MainUI mainUI;
	//传入窗体对象
	public LifeThread(MainUI mainUI){
		this.mainUI = mainUI;
		this.earth = mainUI.getEarth();
	}
	public void run(){
		while(running){
			earth.updataLand();
			mainUI.repaint(earth.getG());
			//earth.printLand();
			try {
				sleep(10);
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
		mainUI.init();
	}
	public void setRunning(boolean running) {
		this.running = running;
	}
}

MyListener类
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;

public class MyListener implements ActionListener{
	private LifeThread life;
	private MainUI mainUI;
	boolean pressstart = false;
	//传入窗体对象
	public MyListener(MainUI mainUI){
		this.mainUI = mainUI;
	}
	//监听方法
	public void actionPerformed(ActionEvent e) {
		String com = e.getActionCommand();
		if(com.equals("start")){
			System.out.println("点击了start！");
			if(!pressstart){
				pressstart = true;
				life = new LifeThread(this.mainUI);
				life.start();
			}
		}
		if(com.equals("stop")){
			System.out.println("点击了stop");
			if(this.life != null){
				this.life.setRunning(false);
				this.pressstart = false;
			}
		}
	}
}