Celular automata
Vit Krajcik krajcik@decef.elf.stuba.skFaculty of Electrical Engineering and Information Technologies Slovak University of Technology Bratislava, Slovak Republic |

**Abstract**

This paper deals with one approach designing complex biomorphical shapes
by means of the evolutional processes, which are represented by the cellular automata
with different types of cells.

The paper describes a method for the definition the grammar and simulation of cellular
array (transformation functions for reproduction, aging and dying),
set up the initial state of cellular automata,
graphic interpretation of cell states,
and some experimental results.

**Keywords**

Cellular automata, evolutiaonary process, grammar

**1. Introduction**

Cellular automata have a broad spectrum of applications - from computer games,
to the simulation physical, biological, and social precesses.

For example, there are applications in archeology, where cellular
automata is used for the re-construction of migration and evolution of the old cultures.
In this case the simulation helps to predict the location of archaeological sites [3].

Theoretical base of cellular automatta statet John von Neumann, but the practical
experiments were able when the computers became able to compute and visualize simulations.
Cellular automata require large memory.

This paper is part of the undergraduate course at the Department of Computer Science
and Technology. The main goal of this project is to create a tool for
automatic data base generation in the modelling and rendering complicated shapes.

**2. Cellular automata**

Cellular automata in general, is the set of cells placed in a regular ortogonal
n- dimensional grid.
Single cell can reproduce, depending on its genetic code (rewriting rules), its state,
and the state of neighbouring cells.

General definition of the automata is following.

It is ordered base **(A,S,U,p,v)**, where
** A** is set of input symbols,

** S** is set of states ,

** U** is set of output symbols,

**p** and **v** are transformations

**
p : S x A -> S
v : S -> U
**

Transformation

Output function

Transition functions are defined in a discrete time intervals t:

u(t) = v( s(t) )

where

This paper deals with two-dimension orhogonal cellular arry.

Two cells are neighbouring, if their absolute distance is less than 2

Example:

In matrix array neighbours of cell with coordinates A(X,Y) are:

B(X+1, Y )

C(X+1,Y+1)

D( X ,Y+1)

E(X-1,Y+1)

F(X-1, Y )

G(X-1,Y-1)

H( X ,Y-1)

I(X+1,Y-1)

d = sqrt( sqr( X - (x+1) ) + sqr( y - (y+1) ) )

d = sqrt( 1 + 1 )

d = 1,4142136 ...

,---, ,---, ,---, | E | | D | | C | |___| |___| |___| \ | / ,---, ,---, ,---, | F |__| A |__| B | |___| |___| |___| / | \ ,---, ,---, ,---, | G | | H | | I | |___| |___| |___|Each cell have eight neighbours.

State of cell is represented by the integer number.

State 0 is reserved for dead cell, and other states are aviable for use. Generally we can define arbitrary number of states for different cell behaviour, but if computer allow less colors, then different cells will have the same color on the computer monitor.

Graphical representation of the cellular automata described in this paper is limited by 256 colors of the standard VESA video modes.

Each state of the cell is represented by one color.

The color is defined by three components: RED, GREEN, BLUE

The value of colors for the particular state is calculated from the color values of the first and last state of the cell by the linear interpolation.

Until now, five types of graphic cell interpretations were implemented:

1. point

2. filled square

3. filled square with variable size

4. filled circle

5. filled circle with variable size.

Size is of the object is proportaionl to the screen resolution and the size of cellular array.

Syntax

where

Example

A : 1 : (1,1,1)->(1,1,255) :

Transition functions can be expressed by the rewriting rules in the form:

where

Example:

A B C D -> A A A : A < 5 : 15 ;

Means that at the neighbourhood of cell A - under the condition that the neighbours are cells named B,C and D and at the same time the state of the arbitrary cell A is less than 5 - two new cells A will be created, with the probability of 0.15;

Next transition rule for defining the process of ageing cells is :

where

of the cell after each iteration (new generation).

This extended condition is usefull for the checking of color cycling.

InitState is an integer number from interval [0,MaxState].

This is an inicial state of the cell.

Example:

A : +1 : A < 20 : 1 ;

Means increasing state of the cell A by one,

if its state is less than 20. At the begining the state is 1.

Initialization can be done in three ways:

1. Enumeration - list of cells with their X,Y coordinates

and state numbers

Description see below.

Example

A( 10 , 24 ) = 10 ;

B( 22 , 10 ) = 1 ;

2. Process - in this case rewriting parallel graphs in form of L-systems (see [1])

Syntax:

where

EndCell initial state of the cell at the end of the brach.

Example

LEN = 5 ;

ALFA = 60 ;

A ( 50 , 10 ) = 1 -> A = 1 : ff(+f)(-f)f(+ff(+f)(-f)f)(-ff(+f)(-f)f)ff(+f)(-f)f .

means that the start (root) of the L-system has coordinates (50,10). Line consist from A cells. Each cell has an initial state equal to 1. Length of each brach is 5 units.

This method allows to get the initial state of the cellular array from the result of simulation of another cellular automata.

Program is implemented in BORLAND C language.

The process of simulation consists from three steps:

1. Computing a new generation of the cellular array

1.1 Application of rules for reproduction and mutation - scan array and try apply rule for each living cell ( with the state > 0)

1.2 Application of rules for ageing - scan array and try apply rule for ageing

2. Storing cell array - changes are saved on a disk

3. Display - display cellular arry of the new generation on the monitor

Example 1.

Simple grammar for reproduction cells.

Grammar:

DIM

N=64;

X=100;

Y=100;

f=5;

a=60.

VAR

A : 1 : (1,1,1)->(63,63,63) .

AGE

A : +1 : A < 63 .

STARTUP

A ( 50 50 ) = 1 .

BEGIN

A -> A A : A < 63 : 50 .

END

Sample images after the simulation (after 10,40,100 iterations)

Pixel cell 1

Pixel cell 2

Pixel cell 3

Bar cell 1

Bar cell 2

Bar cell 3

Bar cell 4

Example 2.

Grammar:

DIM

N=64;

X=100;

Y=100;

f=5;

a=60.

VAR

A : 1 : (33,33,33)->(10,10,10) ;

B : 1 : (63,1,63)->(1,1,1) ;

C : 1 : (63,1,63)->(1,1,1) ;

D : 1 : (63,63,63)->(20,20,20) .

AGE

A : +1 : A < 63 ;

D : +1 : D < 63 .

STARTUP

A ( 10 10 ) = 1 ;

D ( 10 90 ) = 1 ;

D ( 40 30 ) = 1 -> A = 2 : f+f--f+f+f+f--f+f--f+f--f+f+f+f--f+f--f+f--f+f+f+f--f+f--f+f--f+f+f+f--f+f--f+f--f+f+f+f--f+f--f+f--f+f+f+f--f+f .

BEGIN

A -> A A : A < 60 : 20 ;

D -> D D : D < 60 : 10 .

END

Sample images after the simulation (after 10,40,100 iterations)

Variable sized bar cell 1

Variable sized bar cell 2

Variable sized bar cell 3

Variable sized ellipses 1

Variable sized ellipses 2

Variable sized ellipses 3

Variable sized ellipses 4

Example 3.

DIM

N=64;

X=100;

Y=100;

f=5;

a=60.

VAR

A : 1 : (1,1,1)->(43,43,43) ;

D : 1 : (20,20,20)->(63,60,63) ;

B : 1 : (1,1,1)->(1,1,1) ;

C : 1 : (1,1,1)->(1,1,1) .

AGE

A : +1 : A < 63 ;

D : +1 : D < 63 .

STARTUP

D ( 90 10 ) = 1 -> A = 1 : f(fff(+f)f)+ff(-f)+f ;

D ( 90 90 ) = 1 -> A = 1 : ---f+f-f ;

D ( 10 50 ) = 1 -> A = 1 : -f-f+f-f+f-f+fff(-f+ff-f+f-f+f-f-f)+ff+f-f+f-f ;

D ( 20 90 ) = 1 -> A = 1 : +++f(+f-f)-f+ff(ff)+f ;

D ( 10 10 ) = 1 -> A = 1 : f(+f-f)-ffff ;

D ( 50 10 ) = 1 -> A = 1 : ff(+f)(-f)f(+ff(+f)(-f)f)(-ff(+f)(-f)f)ff(+f)(-f)f .

BEGIN

A -> A A : A < 60 : 20 ;

D -> D D : D < 60 : 10 .

END

Sample images after the simulation (after 10,40,100 iterations)

Variable sized ellipses 1

Variable sized ellipses 2

Variable sized ellipses 3

Variable sized ellipses 4

This system allows the flexible way of defining behaviour rules and simulation of cellular automata. Results of the simulation are presented in the graphical form after each iteration step. The system allows different graphical cell states interpretations (by means of 2D shapes).

Future work will concentrate on the implementation of cellular automata in three-dimensional grid, and interpretation of 2D and 3D grid by means of three dimensional objects.

One of the alternatives is using metaballs and metaellipses, which will allow to model biomorphical shapes.

At the end I would like to thank associate professor Martin Sperka for some comments during the work on this project.

[1] Fristacky,N.,a kol.: Logicke systemy, Alfa, Bratislava, 1986.

[2] Zara,J.,a kol.: Pocitacova grafika - principy a algoritmy, Grada, Praha, 1992.

[3] Rise v pocitaci, 100+1, jun 1998, pp.6-7.