Snapshot of a run of the simulation described below,
on a 50x50 grid, with H = P = 0.98, after 2126 generations.
Hosts are green, parasites are red, empty squares are black.
Spiral formation in cellular automata of predator-prey systems
Snapshot of a run of the simulation described below,
on a 50x50 grid, with H = P = 0.98, after 2126 generations.
Hosts are green, parasites are red, empty squares are black.
Introduction
Cellular automata are ''games'' (or ''simulations'') in which various entities in the squares of a chessboard are in each turn of the game updated according to fixed rules, such that the new state of a square depends only on the state of the square plus a set of neighbouring squares in the previous turn. The famous ''Life'' game of Conway is an example.
In various types of cellular automata systems, e.g. the one reported in the 1997 paper by Savill, Rohani and Hogeweg, "Self-Reinforcing Spatial Patterns Enslave Evolution in a Host-Parasitoid System" [1] and the one reported in the 1998 by paper by Stassinopoulos et al., "Spatial Autocatalytic Dynamics: An Approach to Modelling Prebiotic Evolution" [2], it is found that ''spiral'' apatterns appear in the simulated entities, where these spirals rotate around points that pretty much remain in the same place, and where a rotating spiral pattern, once formed, remains ''alive'' during a large number of turns. The picture above shows an example of such spirals. The two papers referenced above contain many futher literature references on other systems in which these spirals were observed, and also give pictures of spirals in their systems.
It seems that the reason why these spirals are formed up to now is regarded as somewhat of a mystery. I believe that I can explain why these spirals are formed. Below, I present a simplified version of the cellular automaton system used in Savill, Rohani and Hogeweg [1], and I explain how and why spirals appear that simplified system. The simple version below *may* be a minimally complex case of a cellular automaton system that exhibits spirals. It seems likely that in the other, more complicated, systems where spiral appear, the same reason is behind spiral formation.
A conclusion from the below is that necessary ingredients for spiral formation are: (1) that there are at least two kinds of entities in the system where one (the predator or parasite) ''chases'' the other (the prey or host), and (2) that there is a time delay between the movement of the prey and the time when the predator becomes aware of the new location of the prey.
Description of minimal predator-prey cellular automata
system
As in Savill, Rohani and Hogeweg [1], my version contains two types of entities, namely ''hosts'' and ''parasites''. The hosts diffuse uniformly to each neighbouring square, while the parasites by preference diffuse (or ''aggregate'') to squares with higher host concentrations. Parasites kill off hosts and reproduce at the expense of hosts, thus parasites ''chase'' the hosts.
My simple version is as follows :
(This is a simplification of Savill, Rohani & Hogeweg, where each square contains two real-valued concentrations, namely the concentration of hosts and the concentration of parasites.)
1. The hosts disperse, as follows: For all squares in the old
situation containing a host, do :
{
1a. Fill the corresponding square in the new situation
with a host.
1b. For all neighbouring squares of the currenly considered
square that are EMPTY in the old sitation, do :
{
With probability H, fill this empty square in the
new situation with a new host. (And with
probability 1-H leave it empty).
(Host offspring grows with ''speed'' H into
neighbouring empty square.)
}
}
2. The parasites disperse, as follows: For all squares in the old
situation containing a parasite, do :
{
2a. Fill the corresponding square in the new situation
with a parasite.
2b. For all neighbouring squares of the currenly
considered square that contain a host in the OLD
situation, do :
{
With probability P replace the contents of that
neighbouring square in the new situatio with a
parasite. (And with probability 1-P leave the
square intact.)
(Parasite eats host and multiplies at host's
expense, with ''speed'' P).
}
}
3. Remove from the new-situation chessboard all parasites that do
not have a host in at least one neighbour square.
(Parasites not directly in contact with a host on which they
feed, die.)
To get clearly pronounced spirals, P and H must be close to 1, say between 1 and 0.85. As P and H get smaller, the spirals become more ''fuzzy'', and for very small P and H the visual appearance of the evolving simulation approaches the ''turbulence'' reported by Savill, Rohani and Hogeweg [1].
For P = H = 1, when the computation of the next state from the old state involves no probabilities and is therefore entirely deterministic (and the only random thing is the initial situation), we definitely get very clearly pronounced spirals. Below, I explain why these spirals form in the P = H = 1 case. (In the ''Explanation'' section below, always P = H = 1.)
It seems obvious that the same mechanism that is responsible for spiral formation in the P = H = 1 case is also responsible for spiral formation when P and H are smaller than 1. Observing the runs of a series of simulations with gradualy smaller values of P and H, no sudden jump or discontinuity in behaviour is seen.
Explanation of spiral formation in the minimal predator-prey
system
I think that when running the above simple simulation with H = P = 1 it's in fact quite easy to see *why* these spirals arise.
The key to why the spirals form, is, briefly expressed, that the hosts in the precise center of the spirals always grow ''just around the corner'' -- one square beyond reach -- of the body of parasites ''chasing'' them. Thus, the parasites never get all the hosts, and therefore the spiral is kept alive.
Suppose the following initial situation (time t0) :
|
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . * o . . . . . . . --
. . . . . * * . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
o = host
* = parasite
. = empty
Then the situation in the next few time-steps t1, t2,
... will be
t1 :
|
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . o o o . . . . . .
. . . . . * * o . . . . . . --
. . . . . . * o . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
t2 :
|
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . o o o o o . . . . .
. . . . o * * * o . . . . .
. . . . o * . * o . . . . . --
. . . . . . * * o . . . . .
. . . . . . o o o . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
t3 :
|
. . . . . . . . . . . . . .
. . . o o o o o o o . . . .
. . . o * * * * * o . . . .
. . . o * . . . * o . . . .
. . . o * * . . * o . . . . --
. . . o o o * . * o . . . .
. . . . . o * * * o . . . .
. . . . . o o o o o . . . .
. . . . . . . . . . . . . .
t4 :
|
. . o o o o o o o o o . . .
. . o * * * * * * * o . . .
. . o * . . . . . * o . . .
. . o * . . . . . * o . . .
. . o * . * o . . * o . . . --
. . o * * * * . . * o . . .
. . o o o * . . . * o . . .
. . . . o * * * * * o . . .
. . . . o o o o o o o . . .
In the t4 situation we see in the center the 4-entity pattern
* o
* *
of t0 reappearing. Continuing the simulation, we see that since the ''waves'' in t4 other than this 4-entity nucleus pattern only grow (or ''move'') outwards and don't bother the center, the pattern growing from this 4-entity nucleus is the same as in t0...t3 above; and therefore the above keeps repeating.
The above pattern consists of two spirals that are ''spiralling'' simultaneously.
The 4-entity nucleus position, including the necessary empty squares around it neighbouring at least the host, is, since it is extremely simple, very likely to appear numerous times in a random initial ''seeding'' of an sufficiently large chessboard with an approproate ratio of the ''seeding'' probablities Pinit,p : Pinit,h : Pinit,0. The above 4-entity configuration is the simplest and smallest, but not the only, configuration that engenders spirals. Examples of other simple configurations that do this are parallel rows of hosts and parasites of at least length 3:
*** **** *****
ooo oooo ooooo ...
If the chessboard is large enough and the ''seeding'' probabilities are favourable, it is therefore extremely likely that the initial contents of the chessboard will contain at least one of these patterns. (Computing the likelihood of at least one of these patterns appearing somewhere on a chessboard with given size and with given ''seeding'' probabilities is very straightforward.) Thus, this shows how spirals appear spontaneously.
If two such double spirals as above are close together, then they *do* bother
each other and get in each other's way, which may result in one of the two
halves of the double spiral getting annihilated, and only one half remaining.
The center of this remaining spiral has the following form:
o o o o o o... this end connected to rest of the outward
o * * * * *... moving spiral
o *
o * * <--- this parasite is the center of the spiral
o o o
In each time-step, this rotates 90 degrees anti-clockwise, around the parasite
(*) exactly in the center of the spiral, as follows ( the position of the
center is indicated by the | and ___ ) :
ti :
|
. o o o o o o
. o * * * * *
. o * . . . *
. o * * . . * --
. o o o . . *
. . . . . . *
. . . . . . *
ti+1 :
|
o * * * * * *
o * . . . . .
o * . . . . .
o * . * o . . --
o * * * o . .
o o o o o . .
. . . . . . .
What happens here in each time-step is this :
|
. o o o o o o
. o * * * * *
. o * . . . *
. o * * A . * --
. o o o A . *
. . . . . . *
. . . . . . *
The reason why the spiral keeps going is therefore that there is a time delay between the dispersal of the hosts and the moment at which the parasites sense the newly grown hosts in the new positions.
It seems likely that any system with local interactions, and with different types of entities where at least one type entity A ''chases'' and (if successfully neared to it) annihilates at least one other type of entity B -- e.g. in chemical reactions where chemicals are used up (= ''chased'' and annihilated) as in [2] -- and in which there is also a which there is such a (small) time delay between the movement of B and the time when A perceives that B is in a new position, will exhibit these spirals. Maybe spirals will even form in systems that use entity positions that are continuously variable instead of discrete grid positions as in cellular automata.
Conclusion/discussion
To become *really* sure that this is the reason behind the spirals *also* in the more complex situations in which such spirals were found to arise -- e.g. when the concentrations of entities in each square are not either ''on'' or ''off'' (fully present or absent) but are non-negative real concentration values as in the Savill, Rohani and Hogeweg article [1]; and/or when there are more types of entities involved and their ''interrelationship'' behaviour is more complex as in Stassinopoulos et al. [2] -- one would have to construct a range of situations that *gradually* increase in complexity from my case as described above to the target case (= e.g. as with you or e.g. as with Hogeweg et al.).
( I believe that when constructing rule sets for how cellular automata are updated (or when constructing any kind of simulation design), it is *always* possible to invent infinite gradations of intermediate cases/constructions between any two given architectures (rule sets) of the simulation. E.g. to extend my simple case above to the Hogeweg et al. case, extend first the binary on-off ''concentration'' to an integer in small a set of possible values, then allow hosts and parasites to be present into the same squares, then then extend to real-valued concentrations. )
If, while gradually changing the simulation construction from the simple case to the target case, the spirals keep forming, then that would (I think) prove that the ''reason'' behind the spiral formation is the same in both the simple and the target case.
References
[1]
N.J. Savill, P. Rohani and P. Hogeweg,
1997,
"Self-Reinforcing Spatial Patterns
Enslave Evolution in a Host-Parasitoid System",
J. Theor. Biol., 188, p. 25-32.
Avaliable on the WWW as PDF (600 kbyte), at
http://www-binf.bio.uu.nl/pdf/savilljtb188-97.pdf
[2]
D. Stassinopoulos, S.P. Colombano, J.D. Lohn, G.L. Haith,
J. Scargle, and S. Liang,
1998,
"Spatial Autocatalytic Dynamics: An Approach to
Modelling Prebiotic Evolution",
Proc. of the 1998 International Conference of Complex Systems,
Nashua, NH.
Avaliable on the WWW as gzipped Postscript (2 Mbyte), at
http://ic.arc.nasa.gov/ic/people/jlohn/NECSI98.ps.gz
SOURCE FILES of a C program 'xpar2'
that performs the simulation of hosts and parasites described above,
can be found here:
This also contains source files of a similar program 'xhexpar2' that does the same on a hexagonal instead of square grid.
Both programs are for Unix/Linux, and use X-Windows for screen graphics.