Dragon fractal

So I'm diving a little into the world of fractals. You know, the repetitive patterns that can go into infinity and make pretty pictures. No? Mandelbrot, Julia? Still nothing? Then this is not for you. For the rest, keep reading :) Otherwise, you may jump to the pretty demo right now.

I never really got to code a fractal. Well, except for a simple Sierpinski triangle in Mirc script ;) So after searching a little I landed on this page about the Jurassic Park fractal. It shows you a little trick which you can apply to compute the next step in the fractal.

It is actually really simple. You have "folds", which go either Left or Right. The first fold is considered Right. After that, three simple steps are applied to get to the next iteration:

1: the center fold of the next iteration is always a Right
2: the left part of the next iteration is the same as the entire previous iteration
3: the right part of the next iteration is the exact opposite of the left part

So doing this in Javascript had me going in a few different directions.

The first was a very naive version, also very slow and memory consuming.

var s = 'RRL';
while (true) s += 'R'+s.split('').reverse().join('');

This will work. It will work fine. Except for that pesky memory. Oh and it's relatively sluggishness.

Okay, let's try to use arrays instead.

var a = [1,1,0]; // 1=R,0=L
while (true) a.concat([1],a.reverse());

Better, but still slow and of course there's the ever lasting memory inefficiency. Can't we do better? Yes we can!

var s = [1,1,0];
while (true) {
var n = s.length;
s.push(1);
while (n--) s.push(+!s[n]);
}

Oh well duh, why call reverse and add the overhead of two additional arrays (in code that's very memory consuming as is) when you can do it manually. Note that doing the loops yourself can be slower than using the internally optimized functions (doing a loop in C or ASM is faster than doing it in JS).

Ok so we probably reached the end of our game here. At least using the rules we have. However, this leaves us at a max of about 23 iterations, amounting up to 32M values to remember. If you take into account that one value is not one byte for Javascript, you can probably do the math on the type of memory this will take. (On a side note: it's interesting to see after which amounts browsers will immediately start to sputter.)

Okay so I can generate full patterns like this. But do I need all of them? Isn't there some kind of pattern to the code that allows me to create a generator for a single path? Yes, there is. But it's not that obvious. And to be honest, I found it on my first attempt but that's probably sheer luck.

If you take the folds of first 10 iterations this is what you'll get. Note that the iterations are encoded in 0 and 1, being L and R respectfully.

110
1101100
110110011100100
1101100111001001110110001100100
110110011100100111011000110010011101100111001000110110001100100
1101100111001001110110001100100111011001110010001101100011001001110110011100100111011000110010001101100111001000110110001100100
110110011100100111011000110010011101100111001000110110001100100111011001110010011101100011001000110110011100100011011000110010011101100111001001110110001100100111011001110010001101100011001000110110011100100111011000110010001101100111001000110110001100100
1101100111001001110110001100100111011001110010001101100011001001110110011100100111011000110010001101100111001000110110001100100111011001110010011101100011001001110110011100100011011000110010001101100111001001110110001100100011011001110010001101100011001001110110011100100111011000110010011101100111001000110110001100100111011001110010011101100011001000110110011100100011011000110010001101100111001001110110001100100111011001110010001101100011001000110110011100100111011000110010001101100111001000110110001100100
110110011100100111011000110010011101100111001000110110001100100111011001110010011101100011001000110110011100100011011000110010011101100111001001110110001100100111011001110010001101100011001000110110011100100111011000110010001101100111001000110110001100100111011001110010011101100011001001110110011100100011011000110010011101100111001001110110001100100011011001110010001101100011001000110110011100100111011000110010011101100111001000110110001100100011011001110010011101100011001000110110011100100011011000110010011101100111001001110110001100100111011001110010001101100011001001110110011100100111011000110010001101100111001000110110001100100111011001110010011101100011001001110110011100100011011000110010001101100111001001110110001100100011011001110010001101100011001000110110011100100111011000110010011101100111001000110110001100100111011001110010011101100011001000110110011100100011011000110010001101100111001001110110001100100111011001110010001101100011001000110110011100100111011000110010001101100111001000110110001100100
1101100111001001110110001100100111011001110010001101100011001001110110011100100111011000110010001101100111001000110110001100100111011001110010011101100011001001110110011100100011011000110010001101100111001001110110001100100011011001110010001101100011001001110110011100100111011000110010011101100111001000110110001100100111011001110010011101100011001000110110011100100011011000110010001101100111001001110110001100100111011001110010001101100011001000110110011100100111011000110010001101100111001000110110001100100111011001110010011101100011001001110110011100100011011000110010011101100111001001110110001100100011011001110010001101100011001001110110011100100111011000110010011101100111001000110110001100100011011001110010011101100011001000110110011100100011011000110010001101100111001001110110001100100111011001110010001101100011001001110110011100100111011000110010001101100111001000110110001100100011011001110010011101100011001001110110011100100011011000110010001101100111001001110110001100100011011001110010001101100011001001110110011100100111011000110010011101100111001000110110001100100111011001110010011101100011001000110110011100100011011000110010011101100111001001110110001100100111011001110010001101100011001000110110011100100111011000110010001101100111001000110110001100100111011001110010011101100011001001110110011100100011011000110010011101100111001001110110001100100011011001110010001101100011001000110110011100100111011000110010011101100111001000110110001100100011011001110010011101100011001000110110011100100011011000110010001101100111001001110110001100100111011001110010001101100011001001110110011100100111011000110010001101100111001000110110001100100111011001110010011101100011001001110110011100100011011000110010001101100111001001110110001100100011011001110010001101100011001000110110011100100111011000110010011101100111001000110110001100100111011001110010011101100011001000110110011100100011011000110010001101100111001001110110001100100111011001110010001101100011001000110110011100100111011000110010001101100111001000110110001100100
110110011100100111011000110010011101100111001000110110001100100111011001110010011101100011001000110110011100100011011000110010011101100111001001110110001100100111011001110010001101100011001000110110011100100111011000110010001101100111001000110110001100100111011001110010011101100011001001110110011100100011011000110010011101100111001001110110001100100011011001110010001101100011001000110110011100100111011000110010011101100111001000110110001100100011011001110010011101100011001000110110011100100011011000110010011101100111001001110110001100100111011001110010001101100011001001110110011100100111011000110010001101100111001000110110001100100111011001110010011101100011001001110110011100100011011000110010001101100111001001110110001100100011011001110010001101100011001000110110011100100111011000110010011101100111001000110110001100100111011001110010011101100011001000110110011100100011011000110010001101100111001001110110001100100111011001110010001101100011001000110110011100100111011000110010001101100111001000110110001100100111011001110010011101100011001001110110011100100011011000110010011101100111001001110110001100100011011001110010001101100011001001110110011100100111011000110010011101100111001000110110001100100011011001110010011101100011001000110110011100100011011000110010011101100111001001110110001100100111011001110010001101100011001001110110011100100111011000110010001101100111001000110110001100100011011001110010011101100011001001110110011100100011011000110010001101100111001001110110001100100011011001110010001101100011001000110110011100100111011000110010011101100111001000110110001100100111011001110010011101100011001000110110011100100011011000110010011101100111001001110110001100100111011001110010001101100011001000110110011100100111011000110010001101100111001000110110001100100011011001110010011101100011001001110110011100100011011000110010011101100111001001110110001100100011011001110010001101100011001000110110011100100111011000110010011101100111001000110110001100100011011001110010011101100011001000110110011100100011011000110010011101100111001001110110001100100111011001110010001101100011001001110110011100100111011000110010001101100111001000110110001100100111011001110010011101100011001001110110011100100011011000110010001101100111001001110110001100100011011001110010001101100011001001110110011100100111011000110010011101100111001000110110001100100111011001110010011101100011001000110110011100100011011000110010001101100111001001110110001100100111011001110010001101100011001000110110011100100111011000110010001101100111001000110110001100100111011001110010011101100011001001110110011100100011011000110010011101100111001001110110001100100011011001110010001101100011001001110110011100100111011000110010011101100111001000110110001100100011011001110010011101100011001000110110011100100011011000110010001101100111001001110110001100100111011001110010001101100011001001110110011100100111011000110010001101100111001000110110001100100011011001110010011101100011001001110110011100100011011000110010001101100111001001110110001100100011011001110010001101100011001000110110011100100111011000110010011101100111001000110110001100100111011001110010011101100011001000110110011100100011011000110010011101100111001001110110001100100111011001110010001101100011001000110110011100100111011000110010001101100111001000110110001100100111011001110010011101100011001001110110011100100011011000110010011101100111001001110110001100100011011001110010001101100011001000110110011100100111011000110010011101100111001000110110001100100011011001110010011101100011001000110110011100100011011000110010001101100111001001110110001100100111011001110010001101100011001001110110011100100111011000110010001101100111001000110110001100100111011001110010011101100011001001110110011100100011011000110010001101100111001001110110001100100011011001110010001101100011001000110110011100100111011000110010011101100111001000110110001100100111011001110010011101100011001000110110011100100011011000110010001101100111001001110110001100100111011001110010001101100011001000110110011100100111011000110010001101100111001000110110001100100

So, can you tell the pattern here? Because there is one.

To make the pattern more obvious, we need to break the iteration up. Let's take the first 160 characters of the tenth iteration and see what that would look like in chunks of eight:

11011001
11001001
11011000
11001001
11011001
11001000
11011000
11001001
11011001
11001001
11011000
11001000
11011001
11001000
11011000
11001001
11011001
11001001
11011000
11001001

Now can you see a pattern? There are two characters to pay attention to, with one minor and one major changing part. Let me explain how it works.

The first three characters are always the same, 110. The fourth character is alternating between 0 and 1. The fifth through nine are again always the same (opposite and mirrored of the first three...), 100. Then the last one. What's the pattern here? Well, because the fractal nature can be found right here. It's such a beauty... Take the last character of each chunk and put them after each other...

1101100111001001

Now look up. This is EXACTLY the same pattern as the tenth iteration starts with. And it will remain to follow that recursive pattern.

Okay, so that's interesting. How do we use this to create a generator (or Turing Machine)?

We'll create two "dynamic" arrays and one "fixed" (Javascript arrays are always dynamic). The static array is [1,1,0,2,1,0,0,3] and indicates the value for each position of the chunk. We use dynamic arrays because we need to track data on each recursive level. And since Javascript has variable arrays and we don't know how many iterations we'll see, this is perfect. One array tracks which character of the chunk we are generating right now. All except the fourth and the eighth character have fixed values. For the fourth value we use another array, which simply ensures that the character will be alternating. The last character is the one that causes a recursion step. The second array tracks which character of the chunk of that index we want the next time a character is required for that chunk. Since only one character is returned on every step, the character of the deepest recursion is returned (since that's the character that should be in the eighth position of all the other levels).

In the static array, the 2 and 3 will help us to determine what to do. This will leave us with the next snippet:

var pattern = [1,1,0,2,1,0,0,3];
var position = [0];
var toggle = [0];

var getNext = function(n) {
if (position[n] == 7) {
var r = getNext(n+1);
position[n] = 0;
} else {
switch (pattern[position[n]||0]) {
case 0:
var r = '0';
break;
case 1:
var r = '1';
break;
case 2:
if (!toggle[n]) var r = '1';
else var r = '0';
toggle[n] = !toggle[n];
break;
default:
debug('impossible');
}
position[n] = (position[n]+1)||1;
}
return r;
}

And every call to getNext(0) will return us the direction of the next fold (0 for Left, 1 for Right). And this works and it will help us in creating the fractal. Because that's what we were working on, a fractal. Remember? ;p

Okay so we have the function above. That's the hardest part. Now we'll simply use canvas to do the drawing. We draw in predetermined (but variable) steps, allowing the browser to take a deep breath (and keep responding). Some trickery was used to keep the image centered (for as far as that's possible), which gave some problems because I used paths. Interestingly enough drawing very small paths is still visible in the long run (when zooming, the distance drawn gets far below one pixel).

So that's basically it. Maybe you want to see the Dragon / Jurassic Park demo now? No, not the movie.

Note that my fractal is actually only half of it. Because I use a generator, the code never actually reaches the middle fold and therefore never converges to an end point. It's not very difficult to give the program a limit and converge after that many folds.

I've left this code run for about a day and was still able to see progress (albeit very very tiny). Kind of surprising.



Hope you enjoy it. I'll probably create some others as well, soon. No promises though ;)