一、元胞自动机概述

1.通俗解释

元胞自动机(cellular automata,CA) 是一种时间、空间、状态都离散,空间相互作用和时间因果关系为局部的网格动力学模型,具有模拟复杂系统时空演化过程的能力。 不同于一般的动力学模型,元胞自动机不是由严格定义的物理方程或函数确定,而是用一系列模型构造的规则构成。凡是满足这些规则的模型都可以算作是元胞自动机模型。因此,元胞自动机是一类模型的总称,或者说是一个方法框架。其特点是时间、空间、状态都离散,每个变量只取有限多个状态,且其状态改变的规则在时间和空间上都是局部的。

2.动力学分类

元胞自动机的构建没有固定的数学公式,构成方式繁杂,变种很多,行为复杂。故其分类难度也较大,在 基于不同的出发点,元胞自动机可有多种分类,其中,最具影响力的当属S. Wolfram在80年代初做的基于动力学行为的元胞自动机分类:

  • 平稳型

    • 自任何初始状态开始,经过一定时间运行后,元胞空间趋于一个空间平稳的构形,这里空间平稳即指每一个元胞处于固定状态。不随时间变化而变化
  • 周期型

    • 经过一定时间运行后,元胞空间趋于一系列简单的固定结构(Stable Patterns)或周期结构(Perlodical Patterns)。由于这些结构可看作是一种滤波器(Filter),故可应用到图像处理的研究中
  • 混沌型

    • 自任何初始状态开始,经过一定时间运行后,元胞自动机表现出混沌的非周期行为,所生成的结构的统计特征不再变止,通常表现为分形分维特征
  • 复杂型

    • 出现复杂的局部结构,或者说是局部的混沌,其中有些会不断地传播

二、模拟森林火灾原理

下面介绍一种平稳型的元胞自动机的应用,在现实世界中我们有以下概念:

  • 时间
  • 空间
  • 物理法则

因元胞自动机具有模拟复杂系统时空演变的能力,因此我们基于此模拟森林火灾也有其特定的时间、空间、物理法则,下面我们制定属于这个世界的时间空间和物理法则。

  • 定义世界

    • 100x100方格的二维世界
  • 定义元素

    • 没着火的树
    • 着火的树
    • 空地
  • 定义时间

    • CPU时间
  • 定义法则

    • 空地不会着火
    • 没着火的树若四周每有一颗着火的树有一定概率会着火,概率会累加且上限为100%
    • 着火三天的树会变成空地

三、逻辑实现

First Of all

  • 实现世界

    • Java定义100x100的二维数组
  • 实现元素

    • 没着火的树 —— 0
    • 着火的树 —— 1
    • 空地 —— 2
  • 实现时间

    • 遍历一次为现实世界的一个周期
  • 实现法则

    • 0 -> 1:表示树着火了
    • 1 -> 2:表示着火三天的树变成空地【烧没了】
    • 定义同阶状态矩阵来记录着火天数

What’more

考虑到现实世界的森林覆盖率以及提及到的周围有燃烧的树会概率着火,因此我们需要一个自定义函数依概率生成二维数组和状态的改变(例如:25%的概率由0 -> 1),根据Java提供的Random类我们可以自定义我们的随机函数

private static int customProbability(int Pro , int a , int b){
        Random random = new Random();
        if (random.nextInt(100) < Pro){
            return a;
        }
        else return b;
    }

因此我们可以基于customProbability()方法来初始化我们的世界

private static int[][] initializationWorld(int Pro){
        //初始化世界
        int[][] cellWorld = new int[100][100];
        //初始化世界元素
        for (int i = 0; i < cellWorld.length; i++){
            for (int j = 0; j< cellWorld.length; j++){
                cellWorld[i][j] = customProbability(Pro,0,2);
            }
        }

        return cellWorld;
    }

依概率随机给100*100的二维数组赋0【没着火的树】,2【空地】,同时我们还需要记录燃烧天数的状态矩阵,即同阶的全0二维数组

private static int[][] stateMatrix(){
        int[][] stateMatrix = new int[100][100];
        for (int i = 0; i < stateMatrix.length; i++){
            for (int j = 0; j< stateMatrix.length; j++){
                stateMatrix[i][j] = 0;
            }
        }
        return stateMatrix;
    }

为测试世界以及状态矩阵是否符合要求并未后面查看世界做准备,在这里提前写出查看当前世界的方法,即接收一个二维数组并输出

private static void outPut(int[][] Matrix){
        for (int i=0; i< Matrix.length;i++){
            for (int j = 0 ; j< Matrix.length;j++){
                System.out.print(Matrix[i][j] + " ");
            }
            System.out.println();
        }
    }

高潮就要到来…某一天的早晨这片森林的若干颗树意外着火的,即将上面已经初始化好的二维数组中的若干个0变成1,并在相同位置的状态矩阵加1表示开始燃烧

//随机点火,需要接收initializationWorld返回的世界,a表示失火树的个数
    //这个方法有bug,有时间优化一下
    //Matrix_1 初始化世界,Matrix_2 初始化状态矩阵
    private static Map<String,int[][]> runFire(int[][] Matrix_1,int[][] Matrix_2, int a){
        Random random = new Random();
        Map<String, int[][]> result = new HashMap<String, int[][]>();
        int count = 0;
        //随机找a颗没有着火的树并让它们着火
        while (true){
            int i = random.nextInt(100);
            int j = random.nextInt(100);
            if (Matrix_1[i][j] == 0){
                Matrix_1[i][j] = 1;
                Matrix_2[i][j] += 1;
                count += 1;
            }
            if (count == a )
                break;
        }
        result.put("世界矩阵",Matrix_1);
        result.put("状态矩阵",Matrix_2);
        return result;
    }
  • 解释:这个方法设计之初考虑到需要返回世界矩阵和状态矩阵两个二维数组,同时还需要接收用户自定义燃烧颗,因此我用了Map这个数据结构,当时觉得自己怎么这么聪明^_^

现在初始的树已经点着了,逻辑告诉我需要一个方法来告诉我们一颗没着火的树“上下左右”有多少颗着火的树,考虑到如果它是树就只有两种状态着火或者没着火,因此只需要一个方法接收4个布尔值并返回布尔值有多少个true或false

private static int stateChangeNum(boolean a, boolean b, boolean c, boolean d){
        int num = 0;
        boolean[] isTrue ={a,b,c,d};
        for (boolean Num : isTrue){
            if (Num){
                num += 1;
            }
        }
        return  num;
    }

到这里我们开始烧树了,即改变世界矩阵和状态矩阵

//基于runFire(initializationWorld(80,0,2),1000)矩阵开始改变状态
    //Pro森林覆盖面积,即以此概率生成世界
    //num初始燃烧树的个数
    //year燃烧年数
    private static int[][] /*void*/ stateChange(int Pro, int num, int year){
        Map<String, int[][]> map =runFire(initializationWorld(Pro),stateMatrix(),num);
        int[][] worldMatrix = map.get("世界矩阵");
        int[][] stateMatrix = map.get("状态矩阵");

        System.out.println("==============初始世界==============");
        outPut(worldMatrix);

        for (int Year = 1; Year <= year; Year++){

            for (int i = 0; i < worldMatrix.length; i++){
                for (int j = 0; j< worldMatrix.length; j++){
                    if (worldMatrix[i][j] == 1){
                        stateMatrix[i][j] += 1;
                        if (stateMatrix[i][j] > 3){
                            worldMatrix[i][j] = 2;
                        }
                    }
                    if (worldMatrix[i][j] == 0){
                        try {
                            boolean judge_1 = worldMatrix[i-1][j] == 1;
                            boolean judge_2 = worldMatrix[i+1][j] == 1;
                            boolean judge_3 = worldMatrix[i][j-1] == 1;
                            boolean judge_4 = worldMatrix[i][j+1] == 1;
                            int isTrueNum = stateChangeNum(judge_1,judge_2,judge_3,judge_4);
                            if (judge_1 || judge_2|| judge_3 || judge_4){
                                worldMatrix[i][j] = customProbability(25 * isTrueNum, 1, 0);
                            }
                        }
                        catch (Exception e){
                            //边界树假设永远不会着火
                        }
                    }
                }
            }
            System.out.println("==============第" + Year + "年世界==============");
            outPut(worldMatrix);
        }

        return worldMatrix;     //预留给GUI
    }
  • 解释:有些小伙伴已经发现了这个方法有bug,那就是当处于边缘的树它最多只有三个邻居,这儿样的话这个方法可能会发生数组越界Exception,其实不难解决只需要单独加一个判断当数组下表有0的时候我们单独判断,但是,哈哈哈我已经写了三个for循环嵌套,还有n个if判断,虽然我的逻辑依然清晰,但是我懒,直接来个异常处理并假设边界树不会着火[着火了有人灭],毕竟数学建模嘛怎么简单怎么来,还不许人写几个假设???

考虑到封装,上面的所有方法我都用了private,是时候留一个公开的接口来启动程序

public static void start(int Pro, int num, int year){
        stateChange(Pro,num,year);
    }

Last But Not Least

完整代码如下

package ForestFire;

import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class World {
    //初始化世界和元素
    private static int[][] initializationWorld(int Pro){
        //初始化世界
        int[][] cellWorld = new int[100][100];
        //初始化世界元素
        for (int i = 0; i < cellWorld.length; i++){
            for (int j = 0; j< cellWorld.length; j++){
                cellWorld[i][j] = customProbability(Pro,0,2);
            }
        }

        return cellWorld;
    }

    //初始化状态矩阵
    private static int[][] stateMatrix(){
        int[][] stateMatrix = new int[100][100];
        for (int i = 0; i < stateMatrix.length; i++){
            for (int j = 0; j< stateMatrix.length; j++){
                stateMatrix[i][j] = 0;
            }
        }
        return stateMatrix;
    }

    //自定义概率
    private static int customProbability(int Pro , int a , int b){
        Random random = new Random();
        if (random.nextInt(100) < Pro){
            return a;
        }
        else return b;
    }

    //输出世界状态
    private static void outPut(int[][] Matrix){
        for (int i=0; i< Matrix.length;i++){
            for (int j = 0 ; j< Matrix.length;j++){
                System.out.print(Matrix[i][j] + " ");
            }
            System.out.println();
        }
    }

    //随机点火,需要接收initializationWorld返回的世界,a表示失火树的个数
    //这个方法有bug,有时间优化一下
    //Matrix_1 初始化世界,Matrix_2 初始化状态矩阵
    private static Map<String,int[][]> runFire(int[][] Matrix_1,int[][] Matrix_2, int a){
        Random random = new Random();
        Map<String, int[][]> result = new HashMap<String, int[][]>();
        int count = 0;
        //随机找a颗没有着火的树并让它们着火
        while (true){
            int i = random.nextInt(100);
            int j = random.nextInt(100);
            if (Matrix_1[i][j] == 0){
                Matrix_1[i][j] = 1;
                Matrix_2[i][j] += 1;
                count += 1;
            }
            if (count == a )
                break;
        }
        result.put("世界矩阵",Matrix_1);
        result.put("状态矩阵",Matrix_2);
        return result;
    }
    //返回一棵树周围有多少个燃烧的树
    private static int stateChangeNum(boolean a, boolean b, boolean c, boolean d){
        int num = 0;
        boolean[] isTrue ={a,b,c,d};
        for (boolean Num : isTrue){
            if (Num){
                num += 1;
            }
        }
        return  num;
    }


    //基于runFire(initializationWorld(80,0,2),1000)矩阵开始改变状态
    //Pro森林覆盖面积,即以此概率生成世界
    //num初始燃烧树的个数
    //year燃烧年数
    private static int[][] /*void*/ stateChange(int Pro, int num, int year){
        Map<String, int[][]> map =runFire(initializationWorld(Pro),stateMatrix(),num);
        int[][] worldMatrix = map.get("世界矩阵");
        int[][] stateMatrix = map.get("状态矩阵");

        System.out.println("==============初始世界==============");
        outPut(worldMatrix);

        for (int Year = 1; Year <= year; Year++){

            for (int i = 0; i < worldMatrix.length; i++){
                for (int j = 0; j< worldMatrix.length; j++){
                    if (worldMatrix[i][j] == 1){
                        stateMatrix[i][j] += 1;
                        if (stateMatrix[i][j] > 3){
                            worldMatrix[i][j] = 2;
                        }
                    }
                    if (worldMatrix[i][j] == 0){
                        try {
                            boolean judge_1 = worldMatrix[i-1][j] == 1;
                            boolean judge_2 = worldMatrix[i+1][j] == 1;
                            boolean judge_3 = worldMatrix[i][j-1] == 1;
                            boolean judge_4 = worldMatrix[i][j+1] == 1;
                            int isTrueNum = stateChangeNum(judge_1,judge_2,judge_3,judge_4);
                            if (judge_1 || judge_2|| judge_3 || judge_4){
                                worldMatrix[i][j] = customProbability(25 * isTrueNum, 1, 0);
                            }
                        }
                        catch (Exception e){
                            //边界树假设永远不会着火
                        }
                    }
                }
            }
            System.out.println("==============第" + Year + "年世界==============");
            outPut(worldMatrix);
        }

        return worldMatrix;     //预留给GUI
    }

    public static void start(int Pro, int num, int year){
        stateChange(Pro,num,year);
    }

}

最后我打了jar包jar包在这里这个jar包会实时更新,不间断的完善这个类加入更多的注释,自定义世界等功能,最最重要的是预留了一个GUI数据的接口,接下来的时间我会学习Swing框架最终时间一个有界面的模拟森林,当然有大佬看见欢迎过来索要最新的jar包。

四、效果展示


只喜欢学习