[CSDb] - User Forums - Dragon Curve

You are not logged in - nap

CSDb User Forums

Forums > C64 Coding > Dragon Curve

2006-01-25 10:55

Monte Carlos

Registered: Jun 2004
Posts: 359

Dragon Curve

I wrote an experimental routine, which displays a dragon curve.
When i read about how to do it i came across the iteration formula S(0)=R ; S_(n+1)=S_(n)R S*_(n), where R stands for right turn and S* is reverse S with exchanged L(left) and R.
T(n,m) be the letters of S(n).
The first three iterations give
R T(1,1)
RRL T(2,1)..T(2,3)
RRL R RLL T(3,1)..T(3,7)
RRLRRLL R RRLLRLL etc...
As i want to draw the lines and calculate the turns simultaneously, T(n,m) has to be build up from low to high m.

Now the code for the first 256 turns, which can be expanded straightforward to more turns:

dragon:
ldx #0

l1:
txa
ldy #7

l0:
lsr
bcc l2
dey
bpl l0

l2:
lsr
bcc right
jsr lineforwardandleftturn
jmp next

right:
jsr lineforwardandrightturn
next:
inx
bne l1
rts

Try it out with Logo.
Is there any way to improve the inner loop, so you dont
have 8 repeats for x = 2^(n)-1?

Monte

2006-01-26 14:26

j0x

Registered: Mar 2004
Posts: 215

One way of doing this would be to keep a 256-entry table of "lefts" or "rights", and "unknown1" and "unknown2".

0: right
1: right
2: left
3: right
4: right
...
126: left
127: unknown1
128: right
...
254: left
255: unknown2

If you encounter an "unknown2", process the next more-significant byte.
If you encounter an "unknown1", process the next more-significant byte multiplied by two (or handle it as a special case)

Pseudobasic (x is turn number)

loop:
i = x and 255
x = x / 256
if (table=="left") then goto left
if (table=="right") then goto right
if (table=="unknown2") then goto loop
## table must be "unknown1" if we end up here
if ((x and 1) == 0) then goto right
else goto left

Several speedups are possible, but this should get you started.

Standard disclaimers apply :)

/Stefan

2006-01-26 19:18

Monte Carlos

Registered: Jun 2004
Posts: 359

i did want to get around a table like this.
i should have written a little bit more information about
my approach.
if you look at the letters T(n,m) of S(n) you recognize, that every second byte alternates between L and R.
so the half of the steps can very easyly be generated.
but what about the other half?
cut out the alternating L/R's and you see, that again every second letter alternates between L and R an so on.
so, if you start with m=0 and end with m=255, you test first bit 0. if this is zero, bit 1 holds the information about the direction(0 for left, 1 for right).
if bit 0 is 1, test bit 1. if this is zero, bit 2 contains the direction information and so on.
the problem with this approach is, that you have to do average
4.5 shifts per step to decide over the direction(min. 1 and max. 8) for m < 256.
you could ofcourse use recursion, but with the c64 its only fun with very simple fractals(i tried that with other ones).

so the question is, how to make a nonrecursive and non precalculated dragon curve the fastest way.
additionally it would be nice to know before, which x and y size the finished fractal will have after m steps.

its not the first time someone does dragon curves on the c64, so feel free to add something to this topic.
imagine 20 mega ora dragoncurves wobbling around your screen;)

2006-01-27 14:11

_V_
Account closed

Registered: Jan 2002
Posts: 124

Well (if I remember correctly), if you use half a square in a V shape as the primitive (initial dimensions: X0 = 2Y * Y0 = Y), then I believe that every 2nd iteration (when new diagonals are spawned), the dragon curve will expand with half the previous expanded length (with Y as a seed value).

So after two steps,

X2 = 2Y + Y/2
Y2 = Y + Y/2

after four steps,

X4 = 2Y + Y/2 + Y/4
Y4 = Y + Y/2 + Y/4

etc.

So the limit resolution of the dragon curve would be XinF = 3Y and YinF = 2Y. If the resolution of the V primitive is 200 * 100, say, then the dragon curve shouldn't exceed 300 * 200 pixels.

At any finite iteration, you'd get a partial sum, which can be calculated explicitly:

X2k = X2k-1 = Y + Y * ( 1 + 1/2 + 1/4 + ... + (1/2)^k )
Y2k = Y2k-1 = Y * ( 1 + 1/2 + 1/4 + ... + (1/2)^k )

or

X2k = X2k-1 = Y + Y * sum(0 -> k) (1/2)^k
Y2k = Y2k-1 = Y * sum (0 -> k) (1/2)^k

or

X2k = X2k-1 = Y + Y * ( 2 - (1/2)^k ) = Y * ( 3 - (1/2)^k )
Y2k = Y2k-1 = Y * ( 2 - (1/2)^k )

k being any positive integer.

2006-01-29 15:36

Monte Carlos

Registered: Jun 2004
Posts: 359

Thank you, i have to think about it.
Greetz

Refresh

Subscribe to this thread:

You need to be logged in to post in the forum.

Search the forum:
Search for in
All times are CET.

Search CSDb

Advanced

Users Online

Sychamis
DanPhillips
Guests online: 87

Top Demos

1 Next Level  (9.7)
2 13:37  (9.7)
3 Mojo  (9.7)
4 Coma Light 13  (9.6)
5 Edge of Disgrace  (9.6)
6 What Is The Matrix 2  (9.6)
7 The Demo Coder  (9.6)
8 Uncensored  (9.6)
9 Comaland 100%  (9.6)
10 Wonderland XIV  (9.6)

Top onefile Demos

1 No Listen  (9.6)
2 Layers  (9.6)
3 Cubic Dream  (9.6)
4 Party Elk 2  (9.6)
5 Copper Booze  (9.6)
6 X-Mas Demo 2024  (9.5)
7 Dawnfall V1.1  (9.5)
8 Rainbow Connection  (9.5)
9 Onscreen 5k  (9.5)
10 Morph  (9.5)

Top Groups

1 Performers  (9.3)
2 Booze Design  (9.3)
3 Oxyron  (9.3)
4 Censor Design  (9.3)
5 Triad  (9.3)

Top NTSC-Fixers

1 Pudwerx  (10)
2 Booze  (9.7)
3 Stormbringer  (9.7)
4 Fungus  (9.6)
5 Grim Reaper  (9.3)

Page generated in: 0.047 sec.