Club Amiga de Montreal - CAM/CAM_CD_1.iso/files/245.lha/FastGro_v1.0/ReadMe

Text File | 1989-04-10 | 6.6 KB | 163 lines

                FastGro 1.0

            Copyright (c) 1989  Doug Houck

PUBLIC-DOMAIN-NOTICE-PUBLIC-DOMAIN-NOTICE-PUBLIC-DOMAIN-NOTICE-PUBLIC-DOMAIN
P                                       N
P    This program has been placed in the public domain, and so may       N
P    be copied by anyone for any purpose whatsoever.  Enjoy!           N
P                                       N
PUBLIC-DOMAIN-NOTICE-PUBLIC-DOMAIN-NOTICE-PUBLIC-DOMAIN-NOTICE-PUBLIC-DOMAIN


WHAT DOES IT DO?

    FastGro is a fractal program, simulating Diffusion-Limited
Aggregation (DLA).  It was inspired by a column in Scientific American,
(Computer Recreations, December 1988) which described various
implementations of DLA.  The program was called SLO GRO, and took about 4
to 5 hours to run.  FastGro will do the same thing, only in 4 to 5 minutes!

    To quote A. K. Dewdney, the author of the inspiring column,
"It all starts when SLO GRO places a single particle at the center of the
computer screen.  A particle is then set on a random walk from a random
point on a large circle centered on the initial particle.  After a long
and arduous journey the particle happens on the stationary particle and
stops.  As soon as that happens SLO GRO will dispatch another particle
on a similar journey from another random point on the circle.  Particle
after particle collects at the site of the original one and a strange
shape emerges within the circle:  a treelike growth with oddly twisted
branches and twigs.  The shape results from a tendency of a randomly
walking particle to run into an outer part of the crowd long before it
encounters a cohort much deeper in the crowd; twigs are more likely to
grow from branches than from the core, so to speak."

WHAT THE PROMPTS MEAN

    FastGro needs three pieces of information: the size of the
cirle, the number of particles, and how often to change colors.
The acceptable range is given in parentheses (low..high), and the
default is in [brackets].

    The RADIUS defines the maximum size of the fractal.  Of course,
smaller ones take less time, whereas the largest take about an hour.
If you have a PAL screen, or use MoreRows, the radius can be bigger.
Note that a 16 color hires screen is used, so hiding it behind a lo-res
screen will speed up the drawing somewhat.

    The fractal may be stopped after a given number of PARTICLES.
If too large a number is given, it will outline the bounding circle.
You may stop the drawing at any time by clicking on the drawing screen.

    You may CHANGE COLOR AFTER a certain number of particles have
aggregated.  A small number will give a mottled effect, while larger
numbers will give a banding effect, showing the order in which the
points were added.

FURTHER READING

   "Random walks that lead to fractal crowds," A. K. Dewdney in Scientific
    American, Vol. 259, No. 6, pages 88-91; December, 1988

   "Fractal Growth," Leonard M. Sander in Scientific American, Vol. 256,
    No. 1, pages 82-88; January, 1987


OPTIMIZATION & IMPLEMENTATION

    The rest of this ReadMe is technical information for those who
would like to know how this program was optimized.

    Calculation of Random Number for Direction

    BEFORE    direction = random

    AFTER    direction = random_array[index]
        index = index + 1

    The part of the program that does the random walk takes most of
the time, so it was there that I concentrated my efforts.  A random number
is needed for every step of the particle's journey, and since generating
random numbers takes time, I simply generated an array of random numbers
when initializing, and thereafter simply scan through the array to get
the required direction.  Generating the numbers is what takes the thirty
seconds at the beginning.

    True, the numbers read from the array are not truly random.
But were they ever?  Computer-generated random numbers are still
pseudo-random, no matter how many convolutions you go through.  The $64k
question is, "Is it random enough for our purposes?"  In this case, yes.
I use a large array (about 50K), and XOR each byte as I read it, which
seems to mix things up enough.

    Calculation of Starting Points For Particles

    BEFORE    angle = random * 360
        x = radius * cosine(angle) + x_offset
        y = radius * sine(angle) + y_offset

    AFTER    index = random * NumberOfStartLocations
        x = start[index].x
        y = start[index].y


    Each particle must be launched from a random point on the edge
of the circle.  Rather than calculating the x,y coordinates from a
random angle while running, I have precalculated the coordinates for
reasonable number of points around the circle, and stored those in an
array.  To get the starting point for a new particle, I simply get a
random index into the array, and recall those points.  This saves doing
trigonometry while running.

    Calculation of Distance from Center

    BEFORE    distx = x - x_offset
        disty = y - y_offset
        DistanceSquared = distx*distx + disty*disty

    AFTER    if border[x,y]

    Some particles might wander out of the circle.  Those should
be abandoned, and new particles selected.  But how does one determine
if a particle wanders out?  Determining the distance from the center
of the circle requires a multiplication - much too slow for us.
Instead, I create a two-dimensional array of bits, with bits set for
those points corresponding to the edge of the circle.  So, to test
for the edge of the circle merely requires testing a bit.  In effect,
I put a fence of bits around the working area.

    Calculation of Particle Hit

    BEFORE    if particle[x+1,y] <> 0
        or particle[x,y+1] <> 0
        or particle[x-1,y] <> 0
        or particle[x,y-1] <> 0

    AFTER    SetSurroundingBits( x, y )
        ...
        if particle[x,y]

    To detect when a particle hits a stationary particle, I use another
two-dimensional array, one bit for each pixel on the screen.  Each time I
set a pixel on the screen, I do the same in my array, and also set the bits
surrounding it.  To detect if I am next to a particle on the screen, I check
only the bit I am on in my array.  If it is set, I am near a particle.
This is analogous to running a boat near the shore.  When you start to hang
up on the sand, you know the shoreline is near.  This is much faster than
checking all adjacent points at each step.

    The two-dimensional bit arrays are set up with a one-dimensional
array of pointers to the rows.  To get to a given coordinate requires
only a lookup in the pointer array, then adding an offset.

    The routine that does the actual random walk is coded in assembly
language, so as to register-optimize it.

TRADEOFFS

    Of course, optimizing for speed involves the usual tradeoff
with space.  I use approximately 120K for arrays - space which may not
be available in lesser machines or languages.  Total memory consumption,
including code and display screen, amounts to about 300k.