'Tis Chrimble again, and staying at my parent's place with nothing in particular to do inspires me to start writing programs to draw pretty crystal shapes. Despite the title of this article, I'm not convinced they qualify as ‘fractals’, but I have a hunch that a really big one would show some of the ‘self similar’ character which is the signature of a fractal form—crystals within crystals…
They're not really ‘crystals’ either, because crystals have a regular structure. But hey, whatever.
I remembered reading about this thing called diffusion limited aggregation (DLA) in The New Scientist Guide to Chaos years ago (although I had to look up the term). This is a simple way to model the growth of crystals, or the shape that lightning grows into, by shuffling random particles around. Imagine you have a solution with particles of some solid buzzing around in it at random, and an electrode which can attract particles close to it. When the particles touch the electrode they stick to it, and themselves become part of the electrode, attracting more particles. As they extend the electrode, the ‘free’ particles are more likely to stick to the most exposed parts, before they can find they're way through to the center of the growing structure, so the electrode grows outwards in randomly wibblying spines.
A DLA models this kind of growth by simulating random ‘particles’, which move around at random until they hit the electrode or a particle which has already stuck. That's easy to do in a program using a bitmap image as the solution, and a single pixel colored differently in the middle as the electrode. The particles can be started off on the edge of the image, one at a time, and move up, down, left or right at random until they find themselves next to a ‘fixed’ particle, at which point they themselves become fixed, and a new particle is started off.
First attempt: a little C program (crystal_bitmap_mono.c) which outputs an image in the simple PBM format (here shrunk to half size):
That was generated at 600 pixels square with 20,000 particles.
Second version: a few small modifications make this a bit more colorful (crystal_bitmap_color.c). All I've done is varied the color from blue to yellow as more particles are added to the structure. The colors are arbitrary, but the result is a bit more interesting:
Third version: it's fairly boring waiting for these programs to finish, so I did a bit of always-unpleasant X coding to open a window and show the image as it's being grown (crystal_with_x.c). Note that while the other programs are pure (hopefully) standards compliant C, this one needs the X libraries to compile.
Fourth and (for now) final version: I thought I'd try a slightly different tack. This time I don't use a bitmapped image with discrete particle positions, but keep a linked list of particles which have ‘stuck’ and output them as a PostScript image (crystal_postscript.c). Particles latch on to the structure when they get close enough to one of the other particles, and are shown as a line between the new particle and the one it attached to. Instead of varying the color, I gradually decrease the distance at which particles stick (to make the outer parts finer than the center) and show the later particles with thinner lines than the first ones.
Here's a sample output (crystal_postscript.eps):
This image has 1523 lines. The odd number is due to the fact that I got
fed up waiting for it to finish, so I attached gdb to its process and
tweaked the counter to make it finish early. I couldn't just leave it going,
because my laptop insists on crashing when it goes into suspend mode, and
I haven't worked out how to turn that off, so I have to be using it, or at
least egging it on with the occaisional key-press, to keep it alive.
By the way, I've got a Makefile for building these programs.