Atari Fractal Dragons

Dennis E. Hamilton

Few programs have spawned as much reader interest in recent months as Paul Carlson's fractal graphics routines, published in the March 1986 issue of COMPUTE!. These translations for eight-bit Atari computers provide valuable insight into how well-written BASIC programs can achieve good performance without the need for machine language routines.

Here are two Atari BASIC programs that draw fascinating images based on fractal curves. The subject of fractals has been discussed in two previous articles: "IBM Fractal Graphics," by Paul Carlson (COMPUTE!, March, 1986), and "MODified Shapes For Atari ST," by Robert Geiger (COMPUTE!, August, 1986). This article allows owners of eight-bit Atari computers to explore fractal graphics as well. Programs 1 and 2 are written entirely in BASIC, so they're both easy to modify. Type in and save both programs.

Both programs draw the same shape, but at very different speeds (Program 2 is faster). The result in both cases is a complex pattern which resembles an abstract, Oriental dragon (see photo). You can enjoy the designs without understanding the math involved. However, by examining the programs you can learn something about efficient BASIC programming as well as the mathematical principles that underlie the code.

Program 1 shows, in lines 200–410, the simplicity of the edge-drawing procedure. The behavior of the dragon curve is related to the patterns of binary bits that arise as a counter is advanced from all 0's, in single increments, up to all l's. The way that the curve contains nested, miniature versions of itself is directly related to the way the lowestorder bits repeat cyclically while we step a binary counter through its entire range. A dragon curve is generally created in one of two ways: either by breaking up existing segments to fill up space, or by keeping a counter to pace off the course.

The speed of Program 1 is governed by how fast we increment the binary counter in the SN() array. Lines 400–410 provide a very quick solution. Note that it's not necessary to inspect the entire counter to establish the direction of the next move. The change in direction is determined by the binary bit just beyond where the highest carry lands. Line 410 makes that adjustment too; lines 210–220 keep the transformed direction value in the correct range.

These improvements, along with efficient use of tables and FOR-NEXT control, produce curves at a rate that is almost pleasant to watch, down to a mesh interval of two pixels. Program 1 draws each finer curve on top of its predecessor so that you can observe the nesting of patterns. Program 2 works differently, plotting only the endpoints of segments, instead.

Brains Over Muscle

Program 1 performs reasonably well, but is still quite slow at maximum resolution. Program 2 draws exactly the same pattern, but at much higher speed. Both programs use the same line-numbering scheme so that you can identify the program changes precisely.

The second program takes advantage of a technique known as loop unwinding. Instead of counting by ones, as in the first program, Program 2 advances the counter in steps of eight. For each eight-step counter increment, the eight required one-moves are performed immediately, one after the other. This approach works well because of the dragon curve's relationship to counting. Each time the three lowest bits of the dragon curve "odometer" step through the eight binary values from 000 to 111, the program performs the same fundamental pattern of relative direction changes. Lines 300–370 play out that pattern, including certain other simplifications made possible because we now know precisely what the three lowest counter bits would have been at each step.

Although it uses no machine language routines, Program 2 shows a dramatic increase in efficiency over Program 1. Not every fractal-tracing problem can be solved so easily, but these programs demonstrate one case where brains, in the form of careful logic, can achieve nearly as much as the muscle of machine language.

For instructions on entering these listings, please refer to "COMPUTE!'s Guide to Typing In Programs" in this issue of COMPUTE!.

Program 1. Fractals As Counting

NG 30 GRAPHICS 8 : COLOR 1
EM 40 DIM SN (14), SX (3), SY (3)
MP 50 FOR I = 0 TO 3: READ D: SX (I) = D : READ D : SY (I) = D : NEXT I
DK 60 DATA 128, 0, 0, 128, -128, 0, 0, -128
OC 100 N2 = 0 : POKE 752, 1
LF 110 SETCOLOR 2, N2, 2 : SETCOLOR 1, 0, 12 : N2 = N2 + 1 : NC = 2*N2 : NP = NC - 1
LN 120 IF NC>12 THEN POKE 752, 0 : END
ON 125 POKE 77, 0 : REM Defer Attract Mode
IP 130 FOR I = 0 TO 3 : SX (I) = SX (I)/2 : SY (I) = SY (I)/2 : NEXT I
KH 140 POKE 656, 0 : POKE 657, 5 : PRINT "ATARI Fractal Dragons Mesh "; SX (0) ; " "
FB 150 X = 100 : Y = 96 : PLOT X, Y
PK 160 FOR C = 0 TO NC : SN (C) = 0 : NEXT C
AP 200 FOR D = 4 - N2 TO 100
CM 210 IF D>3 THEN D = D - 4
CG 220 IF D<0 THEN D = D + 4
GI 300 X = X + SX (D) : Y = Y + SY (D) : DRAWTO X, Y
GK 400 FOR C = 0 TO NP : IF SN (C)>0 THEN SN (C) = 0: NEXT C: GOTO 110
AD 410 SN (C) = 1 : D = D - 2*SN (C + 1) : NEXT D

Program 2. Counting In Blocks

NG 30 Graphics 8 : COLOR 1
KM 40 DIM SN (14), SX (12), SY (12)
PP 50 FOR I = 0 TO 12 : READ D : SX (I) = D : READ D : SY (I) = D : NEXT I
GC 60 DATA 32, 0, 0, 32, -32, 0, 0, -32
GD 70 DATA 32, 0, 0, 32, -32, 0, 0, -32
GE 80 DATA 32, 0, 0, 32, -32, 0, 0, -32
EE 90 DATA 32, 0
OE 100 N2 = 2 : POKE 752, 1
BD 110 SETCOLOR 2, N2-1, 2 : SETCOLOR 1, 0, 12 : N2 = N2 + 1 : NC = 2*N2: NP = NC - 1
LP 120 IF NC>14 THEN POKE 752, 0 : END
ON 125 POKE 77, 0 : REM Defer Attract Mode
LP 130 FOR I = 0 TO 12 : SX (I) = SX (I)/2 : SY(I) = SY(I)/2 : NEXT I
KH 140 POKE 656, 0 : POKE 657, 5 : PRINT "ATARI Fractal Dragones {3 SPACES} Mesh "; SX(0) ; " "
FB 150 X = 100 : Y = 96 : PLOT X, Y
PK 160 FOR C = 0 TO NC : SN (C) = 0 : NEXT C
BD 200 FOR D = 8-N2 TO 100
DA 210 IF D>7 THEN D = D - 4
CK 220 IF D<4 THEN D = D + 4
NG 300 X = X + SX (D): Y = Y + SY(D): PLOT X, Y
LJ 305 D = D + 1
NH 310 X = X + SX (D) : Y = Y + SY (D) : PLOT X, Y
JA 320 X = X + SX (D + 1) : Y = Y + SY (D + 1) : PLOT X, Y
NJ 330 X = X + SX (D) : Y = Y + SY (D) : PLOT X, Y
GK 335 D = D + 1 - 2*SN (3)
NK 340 X = X + SX (D) : Y = Y + SY (D) : PLOT X, Y
JD 350 X = X + SX (D + 1) : Y = Y + SY (D + 1) : PLOT X, Y
NM 360 X = X + SX (D) : Y = Y + SY (D) : PLOT X, Y
MB 365 D = D - 1
MN 370 X = X + SX (D) : Y = Y + SY (D) : PLOT X, Y
GN 400 FOR C = 3 TO NP : IF SN (C)>0 THEN SN(C) = 0 : NEXT C: GOTO 110
AO 410 SN(C) = 1 : D = D - 2*SN (C + 1) : NEXT D