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
|
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 takes approximately half
an hour.
After you enter the number of particles, 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.
Notes
-----
The algorithm works like this:
1. 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.
2. Walk the particle around randomly. For each step, pick a random one
of the 4 cardinal directions (no diagonals).
3. If the particle goes "out of bounds" (see below), respawn it and
try again (without incrementing the particle counter).
4. 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 1.
When the particle counter reaches the max (the number the user
entered), the process is complete, and DMA is enabled so you can see
the result. TODO: at some point, there will be a way to save the image
and/or generate a new image. For now, all you can do is look.
It should be possible to optimize this further. The Atari will never
be a speed demon, but I'd be happy to get execution time for 1000
particles down to 10 or 15 minutes.
It might be nice to include several built-in seeds, besides the single
dot in the middle of the screen. Possibilites: line, plus, 4 dots in a
square pattern...
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.
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
here: 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.
|
