A cellular automaton is an
array of identically programmed automata, or
"cells", which interact with one another. The
arrays usually form either a 1-dimensional string of cells,
a 2-D grid, or a 3-D solid. Most often the cells are
arranged as a simple rectangular grid, but other
arrangements, such as a honeycomb, are sometimes used. The
essential features of a cellular automaton ("CA"
for short) are:
Its State - a variable that takes a
separate value for each cell. The state can be either a number or
Its Neighborhood - the set of cells that it
interacts with. In a grid these are normally the cells
physically closest to the cell in question.
- the set of rules that defined how its state changes
in response to its current state, and that of its neighbors.
Automata models are used to simulate the process of crystal
growth and to generate various patterns that the crystals
create in nature. Crystals form whenever a solid is formed
from fluid. Crystals form from vapors, solutions or molten
materials, and are built from repeating units. Crystals grow
from the outside. Crystal formation is called
crystallization. Crystallization means "become crystals". At a
microscopic level, crystals consist of regular arrays of
atoms laid out much like the cells in a cellular automaton.
Crystals always start from a seed such as a grain of dust
and then progressively adding more atoms to their surface.
Some of the examples are: snowflakes formation from water
vapor, rocks like felsite, and most non-living substances.
This paper reports on some of the work done by researchers
in simulating crystal growth using cellular automata models
and describes the snow crystals in detail.
Description of Crystals
consists of the crystal history, how it came into existence,
the different categories of crystals and description of snow
crystals in detail.
History of Crystals
'Crystal' comes from a Greek word
meaning clear ice. In the late sixteenth century, Andreas
Libavius, made the theory, which said, "Mineral salts
could be identified by studying the shapes of the crystal
grains." In 1669, Nicholas Steno observed that
corresponding angles in two crystals of the same material
were always the same. The first synthetic gemstones were
made in the mid-1800s, and methods for making high-quality
crystals of various materials have been developed over the
course of the past century. Since the mid-1970s such
crystals have been crucial to the semiconductor industry.
Systematic studies of the symmetries of crystals with flat
facets began in the 1700s, and the relationship to internal
structure was confirmed by X-ray crystallography in the
Different Categories of Crystals
are many different shapes and kinds of crystals. There are
about 22 crystal shapes. Some of them are cubes, hexagonal
and prisms. All crystals are not the same shapes. All
perfect crystals have flat surfaces. There are also the
kinds. For example, there is basalt, salt, sand, quartz,
granite, obsidian, shale, marble, slate, petrified wood,
diamonds, snowflakes, rhyolite and felsite, they are all
his book ‘A New Kind Of Science’ has categorized the
crystals as follows:
pool of molten bismuth solidifies it tends to form crystals
like the one shown in Figure 1. What seems to give these
crystals their characteristic “hoppered “ shapes is that
there is more rapid growth at the edges of each face than at
the center. Hoppering has been noticed in many substances
like galena, rose quartz, gold, calcite, salt and ice.
solid can be composed of many crystalline grains, not
aligned with each other. It is called polycrystalline.
In other words, composed of aggregates of crystals. When
solids with complicated forms are seen, it has usually been
assumed that they must be aggregates of many separate
crystals with each crystal having a simple faceted shape.
However, individual crystals can yield highly complex
shapes. There will nevertheless be cases however where
multiple crystals are involved. These can be modeled by
having a cellular automaton in which one starts from several
separated seeds. Polycrystalline
consist of domains. The molecular/atomic order can vary from
one domain to the next. The growth process for polycrystalline
is shown in Figure 2. and can be imagined as follows.
Consider a blank substrate placed inside a growth chamber.
Crystals begin to grow at random locations with random
orientation. Eventually the clusters meet somewhere on the
substrate. Because the clusters have differing crystal
orientations, the region where they meet cannot completely
bond together. This results in the interstitial region
Figure 2. A polycrystalline material showing two separate
crystal phases separated by interstitial material.
idea that crystals are periodically ordered was amazingly
successful. Before the discovery of quasicrystals, it was
known that crystals were solids composed of a periodic
arrangement of identical unit cells. Among the most well
known consequences of periodicity is the fact that the only
rotational symmetries that are possible are 2-, 3-, 4-, and
6-fold rotations. Five-fold rotations (and any n-fold
rotation for n>6) are incompatible with
periodicity. However, on April 8th 1982 Shechtman,
while performing an electron diffraction experiment on an
alloy of Aluminum and Manganese observed a new symmetry. By
orienting the alloy in different directions he found that it
had the symmetry of an icosahedron, containing six axes of
5-fold symmetry, along with ten axes of 3-fold symmetry and
15 axes of 2-fold symmetry. The crystal that Shechtman
discovered was named as ‘quasi crystal’. Quasicrystals
are very different from periodic crystals. They may possess
rotational symmetry, which is incompatible with periodicity.
To this date, quasicrystals have been found that have the
symmetry of a tetrahedron, a cube, an icosahedron. Figure 3.
shows some pictures of quasicrystals.
forms of quasicrystals.
These are the
materials that do not have a well-ordered structure. They
lack distinctive crystalline structure. When solidification
occurs fairly slowly, atoms have time to arrange themselves
in a regular crystalline way. But if the cooling is
sufficiently rapid, amorphous solids such as glasses are
often formed. Amorphous materials do not have any long-range order but they
have varying degrees of short-range order.
of amorphous materials include amorphous silicon, glasses
and plastics. Amorphous silicon provides the
prototypical amorphous material for semiconductors. It has
wide ranging and unique properties for use in solar cells
and thin film transistors.
Amorphous crystals. Lacking distinctive shape.
Snow Crystals and Snowflakes
is one of the well-known examples of crystal formation.
Snowflakes are collections of snow crystals, loosely bound
together into a puff-ball. These can grow to large sizes, up
to about 10 cm across in some cases, when the snow is
especially wet and sticky.
Thus, snow crystals are individual, single ice crystals,
often with six-fold symmetrical shapes. These grow directly
from condensing water vapor in the air, usually around a
nucleus of dust or some other foreign material. Typical
sizes range from microscopic to at most a few millimeters in
diameter. The structure of a given snowflake is determined
by the temperature and humidity of the environment in which
it grows, and the length of the time it spends there. Figure
5. shows some forms of snowflakes that are often seen in
Figure 5. 1) Simple sectored plate; 2) Dendritic sectored
plate; 3) Fern-like stellar dendrite
Six-fold symmetry of snow
water freezes into ice, the water molecules stack together
to form a regular crystalline
lattice, and the ice lattice has six-fold
symmetry. It is this hexagonal crystal symmetry that
ultimately determines the symmetry of snow crystals.
Complex symmetrical shapes of snow
snow crystals form complex shapes because of their simple
six-fold symmetry and also because they are both complex
symmetric, and it is this combination that
gives them their special beauty. To see how such fancy
crystals come about, consider the history of a growing snow
crystal in the atmosphere. The growth usually begins with a
dust particle, which absorbs some water molecules that form
a nucleus for the ice crystal. Typically snow crystals
need some kind of surface on which to get started.
Faceting then causes the newborn crystal to quickly grow
into a tiny hexagonal prism. As the crystal grows larger,
the corners often sprout tiny arms, since they stick out a
bit further into the supersaturated air and thus grow a bit
faster. The crystal growth rate strongly depends on the
temperature. If there are variations in the temperature, the
snow crystal encounters different growth conditions, growing
into an intricate shape. Thus, we see such a rich diversity
in the shapes of snow crystals in nature. When a snow
crystal grows from air supersaturated with water vapor,
there are two dominant mechanisms that govern the growth
rate. The first is diffusion
-- the way water molecules must diffuse through the air to
reach the crystal surface. The second involves the surface
physics of ice -- the efficiency with which
water molecules attach themselves to the ice crystal
Cellular automata applied to
do quite easily reproduce the basic feature of the overall
behavior that occurs in real snowflakes. Snowflakes can be
modeled with the help of cellular automata to produce simple
faceted forms, needle-like forms, tree-like or dendritic
forms, as well as rounded forms.
of the ways to create real snowflake patterns is to use
two-dimensional cellular automata displaying 3-state seven
sum totalistic rules on a hexagonal grid. Each cell has
three states representing growth as a result of different
temperature conditions. The state of a cell is updated based
on the sum of its six neighbors and its current state.
Figure 6. shows some of the snowflake patterns
generated after applying the totalistic rule.
Figure 6. Seven-sum totalistic rule showing intricate
Cellular Automata models
There has been a lot of research work
done in the field of crystals, which make use of cellular
automata models for simulation purposes. I describe below
Packard’s cellular automaton model  and a 3-dimensional
cellular automaton model of ‘free’ dendritic growth.
Packard’s Cellular Automaton Model
Crystal growth is an excellent
example of a physical process that is microscopically very
simple, but that displays a beautiful variety of macroscopic
forms. Many local features are predicted from continuum
theory, but global features may be analytically
inaccessible. For this reason, computer simulation of
idealized models for growth processes has become an
indispensable tool in studying solidification. Packard
presents a new class of models that represent solidification
by sites on a lattice changing from zero to one according to
a local deterministic rule. The strategy is to begin with
very simple models that contain very few elements, and then
to add physical elements gradually, with the goal of finding
those aspects responsible for particular features of growth.
Description of the model
The simplest deterministic lattice
model for solidification is a 2D CA with two states per site
to denote presence or absence of solid, and a nearest
neighbor transition rule. Packard considers rules, which
have the property that a site value of one remains one (no
melting or sublimation). The rules also depend on
neighboring site values only through their sum:
The domain of f
ranges from zero to number of neighbors; f takes on
values of one to zero.
These rules display four types of
behavior for growth from small seeds:
No growth at all. This happens for the rule that maps
all values of σ to zero.
Growth into a plate structure with the shape of the
plate reflecting the lattice structure
Growth of dendrite structure, with side branches
growing along lattice directions; this type of rule is obtained by adding growth inhibitions to the previous rule.
Physically growth inhibition occurs because of the combined
effects of surface tension and radiation of heat of
Growth of an amorphous, asymptotically circular form.
This form is obtained by adding even more growth inhibition.
two ingredients missing from the cellular automaton model
Flow of heat
may be modeled with the addition of a continuous variable at
each lattice site to represent temperature.
Effect of solidification on the temperature field
When solid is
added to a growing seed, latent heat of solidification must
be radiated away. This is modeled by causing an increment in
the temperature field.
In these simulations, the temperature
is set to a constant (high) value when new solid is added.
This means that heat flows to nearby interface sites and
inhibits their solidification.
model is a hybrid of discrete and continuum elements. The
addition of solid happens in a discrete way, which can only
be a very coarse approximation to solid deposition on
molecular length scales. The use of continuum variable at
each lattice site to represent temperature gives the model
unique features lacking in a purely discrete cellular
automaton model. The parameters used in the simulation are
diffusion rate and amount of latent heat added upon
solidification. Other parameters (call it λ) may
characterize the local temperature threshold function. These
parameters may be varied to obtain different macroscopic
forms. Figures 7(a-c) shows a sequence of pictures when
λ is varied from low to high values.
illustrates the case when λ is small so that more heat
diffuses before a boundary site will solidify. Figure 7b
illustrates the effect of raising λ. There is a rather
chaotic network of tendrils that appear to grow in every
direction, but still they show some tendency to grow along
lattice directions. The tip splitting instability is
apparent, preventing the formation of long dendrites with
regular side branching. When λ is raised even further
as shown in Figure 7c, the tips begin to stabilize, and the
tip splitting instability gives away to the side branch
The macroscopic forms yielded by this model show remarkable
similarity to experiments in pattern formation.
growth patterns as parameters are varied in the
deterministic growth rule: (a) Amorphous, isotropic fractal
growth. (b) Tendril growth, dominated by tip splitting. Some
anisotropy is evident. (c) A macroscopic form showing strong
anisotropy, stable parabolic tip with side branching.
A 3D CA model of ‘Free’ Dendritic growth
Dendrites are commonly observed in
materials solidifying with low entropies of fusion. A
dendrite is a branching structure that freezes such that
dendrite arms grow in particular crystallographic
directions. As a dendrite grows it is possible for
additional arms to form behind the growing tip. The growth
of dendritic crystals is of practical importance in metallic
materials. Dendrites are termed ‘free’ dendrites when
they form individually and grow in super-cooled liquid. As
growth occurs the latent heat of fusion released flows into
the supercooled liquid. Both pure materials and alloys can
display free dendritic growth behavior. S. Brown and N.
Bruce  present a 3D CA model of a growing ‘free’
dendrite. This simple model has been able to simulate
changes in dendrite morphology as a function of liquid
supercooling that are similar to some of those observed
The Cellular Automaton Model
In this model, a one million element
grid is used with an initial nucleus of 3x3x3 elements
placed at the center. Each of these is set to a value of 1
(i.e. solid). All
other elements are set to 0. (i.e. liquid). For each
simulation the temperatures of all sites are set to an
initial predetermined value representing supercooling.
Opposite faces of the cubic 100x100x100 computational domain
were treated as periodic, as if in contact with one another.
Details of the simulation procedure are described below
assuming that the dendrites are thermal in nature.
The following rules and
conditions are assumed:
A liquid site may transform to a solid site only if cx
>= 3 and/or cy >=3 and/or cz
>=3 (where cx, cy, and cz
are the number of solid sites present in the surrounding
eight nearest neighbors taken in each of the principal x, y,
and z planes respectively).
Growth can occur only if the temperature of the
liquid site is less than a critical temperature T crit.
T crit =
- γ ( f(cx) + f(cy) + f(cz)
where f(ci) = 1/ ci
ci >= 1
f(ci) = 0
ci < 1 and γ is a constant representing the solid/liquid
If a liquid element transforms to a solid element
then the temperature of the element is raised to a fixed
value to simulate the release of latent heat.
Conductive heat transfer is modeled by updating the
temperature of each element at each time step. The average
temperature of the six nearest neighbor elements is computed
and the temperature of the central element is moved towards
this average by an amount governed by an assumed heat
For all simulations, γ is set to
a value of 20. In each step of the simulation all liquid
sites are tested to determine whether growth will occur. All
sites are then updated simultaneously to their new states of
liquid or solid. Liquid sites that have transformed to solid
have their temperature raised to a fixed value. The process
is then repeated.
Despite the simple nature of the
cellular automaton model, it is possible with judicious
choice of parameters, to simulate the growth of highly
complex 3-D dendritic morphologies that exhibit many of the
features observed in real dendrites.
Results and Observations
A series of simulations are performed
using initial liquid supercoolings ranging from –60 to
–32. Different dendritic shapes are produced. In these
cases, the structures are allowed to grow until the number
of solid sites grown from the center of the 100x100x100 grid
towards the edge along any of the principal axes was 45.
For larger initial supercoolings,
compact structures with large volumes fractions of solid
were produced. As the amount of supercooling was reduced
there was a transistion to plate-like growth. When the
initial supercooling was decreased further the growth
pattern became more spherical with noticeable tip-splitting.Considering
the simplicity of the model, the results show remarkable
similarity to experimentally observed free dendrites. But,
it should be noted that the simulated dendrites produced in
this model all evolved from a single nucleus whereas the
experimentally observed growth patterns often comprised
several interpenetrating dendrites.
Hexlife is a model of Conway’s
Game of Life on a hexagonal grid. This classic game of life,
a cellular automaton algorithm, was invented by British
mathematician John Conway in 1970. Conway's Life plays on a
rectangular grid. Each cell has eight neighbors and survives
only if two or three of its neighbors are alive. If more
than three of its neighbors are alive, it dies from
overcrowding; less than two, it dies of 'loneliness'.
HexLife, a hexagonal grid is used. Each cell has six
neighbors. These are called the first tier neighbors. The
hexlife rule looks at twelve neighbors, six belonging to the
first tier and remaining six belonging to the second tier.
This is shown in Figure 8.
Figure 8. 12
neighbors in HexLife. The first tier six neighbors are
marked by ‘red’ color. The second tier six neighbors
considered are marked by ‘blue’ color. The center white
cell is the current cell, whose state will be
determined by the sum of these 12 neighbors.
As in Conway's Life, whether a
cell is born, dies, or survives to the next generation is
determined by how many of these 12 neighboring spaces
contain live cells. The live cells out of the twelve
neighbors are added up each generation. However, live 2nd
tier neighbors are only weighted as 0.3 in this sum whereas
live 1st tier neighbors are weighted as 1.0. A cell becomes
live if this sum falls within the range of 2.3 - 2.9,
otherwise remains dead. A live cell survives to the next
generation if this sum falls within the range of 2.0 - 3.3.
Otherwise it dies (becomes an empty space).
I have implemented the hexlife
rule by David Ballinger. Each cell of the grid has three
states It is dead, is born, or it survives. A dead cell is
simply shown by an empty cell. A cell that is born is shown
by blue color and a cell that survives (stays live) is shown
by green color. Various
patterns such as gliders and reflection are observed. One
could experiment by setting different initial population
(set of live cells). The snapshot of a hexlife pattern is
shown in Figure 9.
A hexlife pattern, which resembles gliders. A cell that is
born is shown by blue color and a cell that survives to the
next generation is shown by green color.
Class 4 Crystal Growth
Wolfram’s classification of the
four classes is on the basis of asymptotic behavior of
cellular automaton rule acting on a random initial
condition. Under such circumstances the rules discussed in
Packard’s cellular automaton model would lead to fixed
points, and so would be in Wolfram’s class 2. Wolfram’s
class 4 behavior involves crystal growth which is a mixture
of order and randomness: localized structures are produced
which on their own are fairly simple, but these structures
move around and interact with each other in very complicated
Wolfram describes the crystal growth
by considering two states, in which one state represents the
region of solid and other state represents region of liquid
or gas. The most complex snow crystals are formed when a
developing crystal experiences different conditions as it
passes through the atmosphere, each favoring a different
type of crystal growth.
In order to simulate complex crystal growth, we could
consider more than two states (for ex. three states), where
each state could represent a different condition of crystal
growth. Then, if we apply rules based on these states on
random initial conditions, we may get more complex, class
Crystals have been known since the
sixteenth century. There are many different kinds of
crystals seen in nature. It is very fascinating to see the
different intricate and complex forms that one sees during
crystal growth. In this paper, I have described the
different types of crystals, their formation, structure and
patterns generated. One
of the most well known examples of crystal growth is the
snowflake growth. Wolfram  has described cellular
automata models to generate the real snowflake patterns. One
could also use totalistic rules to generate the different
paper shows some of the snowflake patterns generated using
CA model with totalistic rules.
Conway’s game of life, which was originally
modeled on a square grid, can also be modeled on a hexagonal
grid by considering the sum of 12 neighbors. This report
discusses the hex life rule.
This paper also reports on the work
done by Packard , Brown and Bruce . Finally it
concludes by describing the possibility of class 4 behavior
in crystal growth.
Packard, N. “Lattice
Models for Solidification and Aggregation,” Theory and Applications of Cellular Automata,
(1986), pp. 305.
Stephen Wolfram. “A New Kind Of Science”.
Bismuth Crystals. http://www.crystalgrowing.com/bismuth/bismuth1.htm
Gandin, A., and Rappaz, M., “A 3D Cellular
Automaton Algorithm for the prediction of dendritic grain
growth,” Acta Metallurica Inc (1997), pp.2187-2195
Brown, S., and Bruce, N., “A 3D CA model of
‘Free’ Dendritic growth” Scripts Metallurgica et
Materialia (1995), pp. 241-246.
Snow Crystals. http://www.its.caltech.edu/~atomic/snowcrystals/dendrites/dendrite.htm
Condensed Matter Physics. http://www.cmp.caltech.edu/~lifshitz/quasicrystals.html
Ballinger, D., (1999) Hexlife. http://www.well.com/~dgb/hexlife.html.