Diffusion Limited Aggregation (DLA) for Atari 8-bit =================================================== Diffusion-limited aggregation (DLA) is the process whereby particles undergoing a random walk due to Brownian motion cluster together to form aggregates of such particles. For a good description of DLA, see: https://en.wikipedia.org/wiki/Diffusion_limited_aggregation This Atari 8-bit implementation is written in 6502 assembly, using the ca65 assembler from the cc65 suite: https://cc65.github.io/ Building -------- You need a Unix/GNU like system (which might even be modern Windows), with GNU (or possibly BSD) make, Perl 5, and the CC65 tools installed. Provided you have all that, simply type "make" to assemble the source. If you have trouble building on Linux, ask me for help. If you have trouble on other OSes, ask someone who actually knows about your OS (not me, I don't do Windows or Mac). Running ------- The executable is called "dla.xex", and is a standard Atari binary load file. It can be run in the same way you run any other .xex files, e.g. in an emulator or with an SIO2PC cable on real hardware. At startup, you're asked "How many particles?". The more particles you enter here, the longer it will take to generate the image. The default (if you just press Return) is 1000, which generally takes about 3 to 3.5 minutes. For a quick test just to see what the result will look like, try 300, which should take less than 20 seconds. The maximum is 65535, which takes around 6-7 minutes to run... but more than about 2000 is too much anyway: The result starts to have a "ring" around it, which means it outgrew the limited size of the Atari screen. After you enter the number of particles, you'll be asked for the "Seed type". The default is the standard DLA seed: a single pixel in the center of the screen. Other seeds generate different types of image, and run faster than the dot; try them all. After you enter the seed type, the screen will clear and go solid black, while the image is generated. The ANTIC chip's DMA is disabled, to speed things up. However, you can "peek" at the progress of the generator by holding down the Start key. This will show the work in progress, but it will slow things down noticeably. After the image is finished generating, the screen DMA will be turned back on, so you can see it. The bottom line shows a menu, from which you can choose to: - Save: Save the image to disk. You'll be prompted for a filename, which must be a complete filespec (examples: D:TEST.DLA, D2:THING.DLA). The file will be the raw pixels, 8 per byte, 256 pixels (32 bytes) per line, 170 lines. Size will be 5440 bytes, or 44 sectors on a single-density disk. If an error happens while saving, you'll get the chance to retry the save. - Redo: Run the generation process again, with the current particle count and seed type settings. - New: Start the program over, so you can enter different settings. The only way to exit the program (for now) is to press Reset or power cycle the Atari. Algorithm --------- The algorithm works like this: 1. The initial "seed" pixels are drawn. 2. Each particle starts on the edge of a circle whose center is the center of the screen. The circle's radius depends on the number of particles that have been rendered so far: radius is 15 for particles 1 to 100, 30 for particles 101 to 300, 45 for particles 301 to 600, and 75 for particles 601 and up. 3. Walk the particle around randomly. For each step, pick a random one of the 4 cardinal directions (no diagonals). 4. If the particle goes "out of bounds" (see below), respawn it and try again (without incrementing the particle counter). 5. If the particle is ever adjacent to a set pixel, it gets stuck there, the particle counter is incremented, and we go back to step 2. When the particle counter reaches the max (the number the user entered), the process is complete. Notes ----- It should be possible to optimize this a bit further, maybe shave another 5% to 10% off the run time. There might be a quick way to limit the particles' movement outside the initial circle's radius. Right now, it's limited to a square area; width and height are the diameter of the circle plus 10 pixels. The corners of this square waste a lot of time; it'd be better to come up with a way to do an octagon (the square with the corners cut off), which shouldn't slow down the inner loop too much... I actually did implement this, but it was too slow (the time spent in calculations was longer than the time saved by doing them). Tech stuff: rather than calculate points on a circle in asm code, the tables of points for the 4 circle sizes are pre-calculated by a perl script and included in the executable verbatim. The tables bloat the code some (2KB), but the speed boost is well worth it. Also, the graphics mode used is "graphics 8", but in ANTIC narrow playfield mode, so the X resolution is 256... meaning I don't need two bytes for the X cursor position (which saves a good bit of time). The code that plots pixels doesn't use CIO to do so (it writes directly to the screen memory), which also saves time. There's no floating point math in the generation process: if there were, the asm version wouldn't be all that much faster than the BASIC one... Author ------ The original version of this was in Atari BASIC, by ChrisTOS. It can be found at https://github.com/ctzio/DLA/ This assembly version is by B. Watson (urchlay@slackware.com, Urchlay on libera.chat IRC). The code is licensed under the WTFPL: do WTF you want with it.