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.