Cellular automata introduction

Cellular automata was originally proposed by Von Neumann in the 1950s to simulate the self-replication of biological cells. Cellular automata came to the attention of scientists in 1970 when John Holden Conway of Cambridge University designed a computer game called “The Game of Life”.

S. Wolram published a series of papers in 1983. In this paper, the models generated by 256 rules of elementary cellular machine are studied and their evolution is described by entropy. Cellular automata are classified into stationary, periodic, chaotic and complex types.

Cellular automata (CA) is a method used to simulate local rules and local connections. Cellular automata are typically defined on a grid, where each point represents a cell and a finite state. The change rule applies to each cell and simultaneously. The rules of change typically depend on the state of the cell and the state of its (4 or 8) neighbors.

Change rules for 3 cells & change rules for cell states typically depend on the state of a cell and the states of its (4 or 8) neighbors.

Application of cellular automata Cellular automata has been applied to physical simulation, biological simulation and other fields.

5 Cellular automata MATLAB programming combined with the above, we can understand cellular automata simulation needs to understand three points. One is cellular, which can be understood as a square block composed of one or more points in the matrix in MATLAB. Generally, we use a point in the matrix to represent a cellular. The second is the change rule. The change rule of cellular determines the state of cellular at the next moment. The third is the state of the cell. The state of the cell is self-defined and usually opposite, such as the living state or death state of the creature, the red light or the green light, the point with or without obstacles, and so on.

One dimensional cellular automata — traffic rulesDefinition: 6.1 Cells are distributed on a one-dimensional linear grid. 6.2 Cells have only two states: car and empty. Two-dimensional cellular automata — The Game of lifeDefinition: 7.1 Cells are distributed on a two-dimensional square grid. 7.2 Cells have only two states of life and death.The cellular state is determined by its eight neighbors. Rules:Skull: death; Smiley face: if there are three smiley faces around you, the middle will become smiley face less than two or more smiley faces, and the middle will become death.

What is cellular automata discrete system: cellular is defined in finite time and space, and the state of cellular is finite. Dynamical system: The behavior of cellular automata is characterized by dynamics. Simplicity and complexity: Cellular automata simulate complex worlds by controlling interacting cells with simple rules.

9 Constituent Elements (1) Cell Cell is the basic unit of cellular automata: state: Every cell has the function of memory storage state. Discrete: In the simple case, there are only two possible states of cellular; In more complex cases, cells have multiple states. Update: cellular states are constantly updated according to dynamic rules.(2) LatticeDifferent dimensional gridCommon two-dimensional grid (3) Neighborhood (4) Boundary Reflective: the state with itself as the boundary absorbing: regardless of the boundary (the car disappears when it reaches the boundary)

(5) Rules (State transition function)Definition: The dynamic function of the cellular state at the next moment is determined according to the current state of the cell and its neighbors. Simply speaking, it is a state transfer function. Classification: Summation type: the state of a cell depends on and only depends on the current state of all its neighbors and its own current state. Legal: The sum rule belongs to the legal rule. However, if the rules of cellular automata are limited to summation type, cellular automata will be limited.6. Forest fires Green: trees; Red: fire; Black: empty space. Tree: Becomes fire when there is fire around or when struck by lightning. Open space: with probability P into trees rational analysis: red for fire; Ash is empty space; Green is the treeThe sum of the three states of cell density is 1The density of fire to open space is equal to the density of open space to trees (new trees are equal to burned trees)F is the probability of lightning: much less than the probability of tree generation; T smax T_{smax}T smax is the time scale for a whole bunch of trees to burnProgram implementationPeriodic boundary condition purchasesThe numbers are numbered to construct the neighbor matrixThe numbers in the above matrix correspond to the upper neighbor numbers of the same position numbers of the original matrix, and 1 and 1 correspond to the same principle: (7) Transportation conceptDistance and densityFlow equationConservation equationSpacetime trajectory (horizontal axis is space and vertical axis is time)The intersection of the red line and the blue line indicates the position of the car at each time. If it’s a vertical line, it’s the time the car was in that position

Macro continuous model:The most commonly used rules:The red bar means the velocity is full.

1 Acceleration rule: do not exceed v max (2 grids /s) v_{Max} (2 grids /s) v Max (2 grids /s) 2 Collision prevention: do not exceed the vehicle distance

Theoretical analysis:Result analysis: density and flowThe first graph: the abscissa is the normalized density, and the ordinate is the traffic flow. Second figure: theoretical value versus CA result

Result analysis: space-time trajectoryThe dark area in the middle is a traffic jam.

Two, some source code

Cellular automata to simulate the function main % among three lanes distributor roads on both sides of the big companies have one lane travelling during peak % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % Sidex1 Sidex2% +---------------+ Sidey =2% % % | | | | = = = = = = = = = = = = = = = = = = = = = = = = = Mainy % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % T always simulate actual time arrivals from total traffic % Mainlength Main road length % Mainy main road ordinate % Mainwide main road width % Sidewide secondary road width % Sidex1 Sidex2 secondary road abscess % Sidey secondary road ordinate % Sidelengthh Secondary road north-south length % Sidelengthw Side Road is long from east to westmapMatrix %1 空 2 车 3Border % lightMP traffic light % lightTime traffic light interval % V vehicle speed matrix % vMainmax trunk maximum speed % vSIDEMax side maximum speed % Time vehicle spend time matrix % DT unit time % TT image refresh time % h Handle % SumTime % AllTime % ChangePro Right lane paving probability clear; clc T =3000; 
Mainlength = 200; Mainwide = 3; vmainmax = 6;
%Sidelengthh = 25; Sidelengthw = 100; Sidewide = 1; 
changepro = 0;
vsidemax = 4;
Sidex1 = 30; Sidex2 = 150; Sidey = 2; Mainy = 26;
[mp, v, time,lightmp] = init_mp(Sidex1,Sidex2,Sidey,Mainy,Mainlength,Mainwide);

h = print_mp(mp, NaN, 0.1);
dt = 1.2; tt=0.1;
sumtime = 0; sumpassed =0;
lighttime = 20; % car washif(rem(i,2)&(mp(27.8) ~ =2||v(27.8) ~ =0))[mp, v] = new_cars(dt,mp,v,vmainmax); end; % software parkif(rem(i,2))mp(24,cy2)=1;else mp(24,cy2)=2; end; mp(26,cy2)=2; v(26,cy2)=0; % chos_road2 Aggressive chos_road Conservative [mp, v,time] = chos_road(mp,v,time); % speed [mp, v,time] = change_speed(mp,v,time,vmainmax); flag = (mp(Mainy,Sidex2)==0) % causewayif(flag) [mp, v, time] = fulu(mp,v,time,vsidemax,Sidex1,Sidex2,Sidey,changepro); end; % displacement & away car [alltime, mp, v, time, sumpassed] = move (alltime, sumpassed, mp, v, time, dt); % causewayif(~flag) [mp, v, time] = fulu(mp,v,time,vsidemax,Sidex1,Sidex2,Sidey,changepro); end; % h = print_mp(mp,h,tt); xlabel({strcat(strcat('time = ',num2str(sumtime,'%.1f')),'s'),
            strcat('total number of vehicles =',num2str(sumpassed)),
            strcat('average passing time =',num2str(alltime/sumpassed,'%.4f')),'Not opening side roads, influence of software park, conservative strategy'});
%     w= getframe;
%     imind  =frame2im(w);
%     [imind ,cm]=rgb2ind(imind,256);
%     if(i~=1)
%         imwrite(imind, cm, 'example2.gif'.'gif'.'WriteMode'.'append'.'DelayTime'.0.01);
%     else
%         imwrite(imind, cm, 'example2.gif'.'gif'.'Loopcount',inf,'DelayTime'.0.01);
%     end;
end

function [mp, v, time] = chos_road(mp,v,time)
%
% 
%  
% 
% 
% 
%

[N, M] = size(mp);
for y=M- 1:- 1:2
    for x=26:28
        if(mp(x,y)==2 & mp(x,y+1) ~ =1)
            if(mp(x- 1,y)==1 & mp(x+1,y)==1 )
                if(rand<0.5)
                    mp(x+1,y)=2;
                    mp(x,y)=1;
                    v(x+1,y)=v(x,y);
                    v(x,y)=0;
                    time(x+1,y)=time(x,y);
                    time(x,y)=0;
                else
                    mp(x- 1,y)=2;
                    mp(x,y)=1;
                    v(x- 1,y)=v(x,y);
                    v(x,y)=0;
                    time(x- 1,y)=time(x,y);
                    time(x,y)=0;
                end;
            elseif(mp(x+1,y)==1)
                mp(x+1,y)=2;
                mp(x,y)=1;
                v(x+1,y)=v(x,y);
                v(x,y)=0;
                time(x+1,y)=time(x,y);
                time(x,y)=0;
            elseif(mp(x- 1,y)==1)
                mp(x- 1,y)=2;
                mp(x,y)=1;
                v(x- 1,y)=v(x,y);
                v(x,y)=0;
                time(x- 1,y)=time(x,y);
                time(x,y)=0;
            end;
        end;
    end;
end;
   function [mp, v, time] = fulu(mp,v,time,vsidemax,Sidey1,Sidey2,Sidex,changepro)
%  
%
%
speedpro =0.9;
[N, M] = size(mp);  
step=0; x=25; y=Sidey2;
while(1)
    step=step+1;
    if(mp(x,y)==2) break; end;if(x==Sidex) break; end; x=x- 1;
end;
if(mp(x,y)==2&&v(x,y)>=step)
    v(25,y)=1; mp(25,y)=2; time(25,y)=time(x,y)+1.2;
    v(x,y)=0; mp(x,y)=1; time(x,y)=0;
end;
dis=zeros(N,M)- 1;
x=25; y=Sidey2; dis(26,Sidey2)=0;
while(1)
    if(x==26) break; end;if(mp(x,y)==2) dis(x,y)=0; end;if(y==Sidey2&&x~=Sidex)
        x=x- 1;
    elseif(x==Sidex&&y~=Sidey1)
        y=y- 1;
    elseif(y==Sidey1&&x~=26)
        x=x+1;
    end;
end;
lastx=26; lasty=Sidey2; x=25; y=Sidey2;
while(1)
    if(x==26) break; end;if(dis(x,y)==- 1) dis(x,y)=dis(lastx,lasty)+1; end; lastx=x; lasty=y;if(y==Sidey2&&x~=Sidex)
        x=x- 1;  
    elseif(x==Sidex&&y~=Sidey1)
        y=y- 1;
    elseif(y==Sidey1&&x~=26)
        x=x+1;
    end;
end;
x=25; y=Sidey1; nxtx=0; nxty=0;
while(1)
    if(x==26) break; end;if(y==Sidey1&&x~=Sidex)
        nxtx=x- 1; nxty=y;
    elseif(x==Sidex&&y~=Sidey2)
        nxty=y+1; nxtx=x;
    elseif(y==Sidey2&&x~=26)
        nxtx=x+1; nxty=y;
    end;
    if(dis(x,y)==0)dis(x,y)=dis(nxtx,nxty)+1; end; x=nxtx; y=nxty; end; x=25; y=Sidey2;
tot=0;
X=1:500; Y=1:500;
while(1)
    if(x==26) break; end; tot=tot+1;
    if(mp(x,y)==2)
        if(rand<speedpro) rlv = min(vsidemax,min(v(x,y)+1,dis(x,y)- 1));
        else rlv= min(vsidemax,min(max(0,v(x,y)- 1),dis(x,y)- 1));
        end;
        if(rlv~=0) 
            tox = X(tot-rlv); toy=Y(tot-rlv);
            mp(tox,toy)=2; v(tox,toy)=rlv;
            time(tox,toy)=time(x,y)+1.2; time(x,y)=0;
            mp(x,y)=1; v(x,y)=0;
        end;
    end;
    X(tot)=x; Y(tot)=y;
    if(y==Sidey2&&x~=Sidex)
        x=x- 1;  
    elseif(x==Sidex&&y~=Sidey1)
        y=y- 1;
    elseif(y==Sidey1&&x~=26)
        x=x+1;

    end;
end;  

Copy the code

3. Operation results

Matlab version and references

1 matlab version 2014A

2 Reference [1] CAI Limei. MATLAB Image Processing — Theory, Algorithm and Case Analysis [M]. Tsinghua University Press, 2020. [2] Yang Dan, ZHAO Haibin, LONG Zhe. Examples of MATLAB Image Processing In detail [M]. Tsinghua University Press, 2013. [3] Zhou Pin. MATLAB Image Processing and Graphical User Interface Design [M]. Tsinghua University Press, 2013. [4] LIU Chenglong. Proficient in MATLAB Image processing [M]. Tsinghua University Press, 2015. [5] MENG Yifan, LIU Yijun. [6] Zhang Na, Liu Kun, Han Meilin, Chen Chen. A PCA-SVM based Face Recognition Method [J]. Science and Technology Vision, 2021,(07) A face recognition algorithm based on PCA and LDA fusion [J]. Electronic measurement technology, 2020,43(13) [7] Chen yan. [8] dai lirong, Chen wanmi, guo sheng. Analysis of face recognition method based on BP neural network [J]. Information and computer (theory edition), 2020,32(23). Research on face recognition based on skin color model and SURF algorithm [J]. Industrial control computer, 2014,27(02)