"oh my god, its spreading !!" Steve McQueen '58' movie "The Blob"
- To: mathgroup at yoda.physics.unc.edu
- Subject: "oh my god, its spreading !!" Steve McQueen '58' movie "The Blob"
- From: gaylord at ux1.cso.uiuc.edu
- Date: Fri, 3 Jul 1992 09:33:19 -0500
I said i'd post the 'spreading' algorithm by independence day so here it is
i also told "Mathematica in Education" which is publishing the full article
in their Fall 1992 issue that i would not put out the full text.
if you can't figure out the program, 'call' me and we can discuss it.
alternatively, you can simply run the program and see what it does.
[btw - i am now writing a column for Mathematica in Education on
Programming in Mathematica {we're still thinking of a nifty name like
"Simulating Experiences with Mathematica" (not so good, huh? suggestions
are welcomed) and any contributions, including entire guest columns are
more hereby solicited. we are especially interested in programs that the
reader can play with on his own (like these simulations). send any
contributions you might have to me. you will be fully credited in the
column and if you 'guest-host' a column you can even list it as a
publication on your resume].
someone actually sent me some code of his own (on bond percolation) in
response to to my DLA program posting, it was really neat and we're now
talking about doing some other simulations together. someone else 'talked
to me' about some improvements that could be made in the dla code. very
useful.
this is why i'm posting this stuff (in addition to the ego boost of
course).
'keep them cards and letters coming' as Dean Martin used to say.
=========================================
========= "Spreading it around" [something i am occasionalluy accused of
doing] ==============
The General Kinetic Growth Algortihm
1. create an occupied site at the origin {0,0}, called seed, and place it
into a list {{0,0}} (called cluster).
create a list {{1,0},{-1,0},{0,1},{0,-1}}, called choices.
sum seed and choices to create a list {{1,0},{-1,0},{0,1},{0,-1}} which
contains the unoccupied nearest-neighbor 'perimeter' sites to the occupied
site and then pair each site with a randomly generated number between 0 and
1 to create a list called 'per'.
2. using a specified selection criterion (discussed below), choose and
remove one of the perimeter sites and its associated value from per.
using a specified acceptance criterion, determine if the selected site
should be added to cluster.
if the site passes the test:
(a) place the site in cluster.
(b) sum choices and the site to create a list of
nearest-neighbor sites to the selected site, called nn.
(c) use nn, per and cluster to create a list of those
nearest-neighbor sites not already in per or cluster,
called new.
(d) pair the sites in new with randomly generated numbers
to create a list called newper,and join it to per.
3. repeat step 2 until cluster reaches a size specified by an inputted
value n or until per becomes empty.
Specific KG Models
(1) the Eden model: (used for tumor growth, this was the first kg model and
it is named after the biologist who proposed it). Perimeter sites are
randomly selected and converted to cluster sites.
(2) the percolation model: (used for gelation). This is a variation of the
Eden model, in which perimeter sites are randomly selected, given
associated values by random number generation and, based on that value,
accepted into or rejected from the cluster.This is also known as the
'single percolation cluster' model.
(3) the invasion percolation model: (used for fluid flow through porous
media). This is a variation of the percolation model in which perimeter
sites become cluster sites by virtue being the perimeter site with the
lowest associated value. This is said to 'follow the path of least
resistance'.
the EPIDEMIC model
-----------------------
selection criterion - an element in per is randomly chosen using testsite.
acceptance criterion - if the value associated with a selected site is less
then some inputted value p, the site is added to cluster.
note: a threshold acceptance value of p = 1 corresponds to the 'Eden' model
while a threshold value between 0 and 1 corresponds to the 'single
percolation cluster' model.
the INVASION PERCOLATION model
selection and acceptance criterion - the site in per with the lowest
associated value is added to cluster.
The KG Program
explaining terms not previously described.
The anonymous function 'perTocluster' is the main computing engine of the
program, implementinmg step 2 in the algorithm.
For the invasion percolation model, it is not necessary to input p, in
which case a default value of p = -1 is used and Cases[per,{{x__},
Min[Transpose[per][[2]]]}] is fed into perTocluster.
For the percolation model, if the value associated with the selected site
is less than or equal to p, {per[[testsite]]} is fed into perTocluster and
if the value is greater than p, {per[[testsite]]} is removed from per and
perTocluster is not used.
Finally, the anonymous function in PlotRange is used to give the largest
possible graphic of the final pattern.
spreading[n_Integer,p_Real:-1.0]:=
Module[
{cluster = {{0, 0}}, choices = {{1, 0},{0, 1},{-1, 0},{0, -1}},
per = Transpose[{{{1,0},{0,1},{-1,0},{0,-1}}, Table[Random[],{4}]}],
perTocluster, nn, new, newper, testsite},
perTocluster :=
(Module[{nn, new, newper},
AppendTo[cluster, Flatten[#, 1][[1]] ];
per = Complement[per, #];
nn = Map[Function[x, x + Last[cluster]], choices];
new = Complement[nn, cluster, Transpose[per][[1]] ];
newper = Transpose[{new,Table[Random[],{Length[new]}]} ];
per = Join[per,newper]])&;
While[Length[cluster] < n + 1 && Length[per] >0,
testsite = Random[Integer,{1, Length[per]}];
Which[
p < 0, perTocluster[Cases[per,{{x__}, Min[Transpose[per][[2]]]}]],
per[[testsite, 2]] <= p, perTocluster[{per[[testsite]]}],
True, per = Complement[per, {per[[testsite]]}] ]
];
Show[Graphics[
{RGBColor[0.3,0.3,0.6],Map[(Rectangle[#-{0.5,0.5},#+{0.5,0.5}])&,cluster]}]
,
AspectRatio -> 1, PlotRange->Map[({Min[#], Max[#]})&,Transpose[cluster]]]
]
===================================
comments on the code are always appreciated.
, compsimclass, compsimclass, Irene&Victor
Have a happy fourth, folks: we can celebrate that the supreme court is now
out-of-session so they won't be taking away any more of our rights until
next fall.
richard j. gaylord, university of illinois, gaylord at ux1.cso.uiuc.edu
"if you're not programming functionally, then you must be programming
dysfunctionally"