1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
|
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 6.5 to 8
minutes. For a quick test just to see what the result will look like,
try 300, which should take less than a minute. The maximum is 65535,
which takes around 18 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;
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, 192 lines. Size will be 6144 bytes,
or 50 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.
|
