Chaos game

This post is inspired by the Numberphile video I watched recently: https://www.youtube.com/watch?v=kbKtFN71Lfs.
I greatly recommend watching it and subscribing the channel if you haven't yet done so - it's full of all sorts of mathematical goodness for the mathematical geek in you.

I made an interactive JavaScript implementation of the game, which you can check out HERE (see fig. 1).

The code for the demo is available on GitHub: https://github.com/dagothar/chaos-game. Let me know if you spot any bugs!

Fig. 1. Chaos game demonstration.

So, what is the Chaos Game?
 It's a method for creating fractals. You start with a blank page, a set of vertices arranged in a polygon and a randomly selected starting point. Each turn you select one of the vertices of the polygon and travel towards it covering a certain portion of the distance (for example 1/2 - it is also the same each turn). You draw a dot each time you stop to pick another vertex to travel to. The procedure, simple enough as it sounds, yields some surprisingly complex results.
With a starting set of vertices arranged in a triangle, and covering half the distance to the randomly selected vertex each time, a Sierpiński triangle emerges (see fig. 2).

Fig. 2. Sierpiński triangle is made on a triangular grid with the step parameter set to 0.5.

 More complicated setups yield deservedly rewarding fruits (see fig. 3).

Fig. 3. Pentagonal fractal with step=0.67.

A very curious thing happens when a portion of the game board is barred against the intrusion of the randomly wandering point. In that case, the shape of the restricted area is repeated fractalised all over the board in form of the areas untouched by the point iterations (see fig. 4). The figure shows the blog icon repeated within a square setup of control points. Is it possible to do the same inside a triangle or a pentagon? Does the step size parameter has to be changed?

Fig. 4. DeltaStep logo fractalised in a square after 100,000 iterations.

How to use the demo?

Simply click Start. The game will be played automatically between the vertices of the polygon specified by the red dots. You can Pause the game at any time.

Clear removes the dots, but not the vertices. You can also Download the currently generated image yo your computer.

The Step size slider controls the distance which is covered towards the next randomly selected vertex each iteration (0.0 to 1.0).

You can control the speed at which the new dots are generated. By default, the callback is invoked every 1 ms, but that speed is mostly likely limited by your hardware. You can slow the game down up to 1 dot/sec by using the slider.

You can also customize the colors and the dot size.

Controlling the control points. You can move the control points by hovering over them, clicking and dragging them around. To remove the control point, simply drag it outside the board.

You can add new control points by clicking the Add new point button on the left side of the interface. The new point is placed in the middle of the board, from where you can drag it to wherever you like.

You can make any regular polygon setups by using the Make n-gon button. The number on the right of the button controls the number of the regular polygon vertices.

Defining the restricted area. You can paint on the board with your mouse. Simply click and drag around outside the control points. The painted area will be blocked for the game iterations, thus allowing you to create the fractals of custom patterns. (Note: do not block too much of the board - the script may get stuck trying to find a new possible jump target).

There are several unanswered questions the game leaves us with. What happens when the control points are placed on the vertices of a concave polygon? What if the polygon is distorted? What does the step size actually do? How do you achieve the fractalisation effect with more or less points than four?

The chaos game invites.

Literature

[1] Numberphile, Chaos game video, available: https://www.youtube.com/watch?v=kbKtFN71Lfs

[2] Wikipedia,  Chaos game, available online: https://en.wikipedia.org/wiki/Chaos_game

Dragon curve

Fig. 1. A forest...? a whirlpool...? a blaze? of Dragons. What do you think a collective noun for these should be?

You fold a paper strip absent-mindedly and a wondrous creature emerges...

If you read The Jurassic Park by M. Crichton (and I’m sure you did), you sure have noticed how each of the chapters started with a page featuring an interesting drawing. It began at first with a simple set of lines, but as you progressed in the book, it got more and more convoluted. I couldn’t figure out the rule behind it at the time, and I found the explanation only years later.

Fig. 2. Dragon curve animation by 碳酸鈣 (available at  this
 Wiki page under CC license).

The lines form a fractal, which is also called Heighway dragon, the Jurassic Park dragon, or simply a dragon curve (see fig. 2). It’s quite a nice thing to doodle! There are a few ways you can do this and the choice is yours:

1. The paper strip folding method

Take a strip of paper. Start folding it: right over left, and keep repeating: right over left, right over left… You won’t be able to do that more than 4-5 times. Don't worry! You can always make more components and connect them end to end  to get more complicated shapes (more iterations of the fractal).

Unfold  each of the components and crease all the folds so they all form right angles (see fig. 3). Place it on a flat surface, and voila!

Fig. 3. How to make the Dragon Curve by folding the paper strips.

2. The pen-and-paper method
You can very well draw the dragon on the paper, starting with a straight line segment and making proper right or left 90 degree turns. There is a neat method that can be used for the determination of the turns in the sequence. Let's start with an example (R marks a right turn and L - a left turn):

1st iteration:  R,
2nd iteration:  R_R_L,
3rd:            RRL_R_RLL,
4th:            RRLRRLL_R_RRLLRLL,

And so on… As you can see, in each of the iterations you take the previous one, add an R (right 90 degree turn) at the end, and then add the previous iteration again, but this time  both reversing i, and swapping R’s and L’s (see fig. 4).

Fig. 4. Drawing the Dragon Curve.

3. The computer friendly method
You can calculate the n-th turn direction by evaluating the following expression:

if ((n & -n) << 1) & n == 0 then:

  turn ← R;

else:

  turn ← L;

& is a bitwise and operator, << is left shift and you have to remember the -n should be encoded as two-complement. Also, the n-th full iteration is a sequence of 2n-1 turns, so you should probably calculate all of these! :)

For example, the direction of 42nd turn is:

((00101010 & 11010110) << 1) & 00101010 =
= 00000100 & 00101010 = 0,

so the 42nd turn is R.

The figure 1 comes from an old program I wrote in C to explore the possibilities offered by the Dragon curves. You can find this program here.

If you ever want to summon a dragon, just use your imagination! 

Sources:
http://en.wikipedia.org/wiki/Dragon_curve
http://math.rice.edu/~lanius/frac/jurra.html

Note. This was originally posted on my Tumblr blog: http://dagothar.tumblr.com/post/26697353061/the-jurassic-park-fractal-if-you-read-the. I think this is a much better place for it though, and I'm pretty sure you haven't seen it yet anyway!

Growing lichen

It was supposed to be a quick effect, and a trip to the past. It was one of the first things I ever coded in C, years ago. I found a description of it (was it a course?) in some old gaming magazine and decided to give it a try.

And now I've found the chapter about it in an old book I ordered for a couple of bucks from an American second-hand bookshop. The book is "The Magic Machine - A Handbook of Computer Sorcery" by A. K. Dewdney (see Fig. 1).

Fig. 1. "The Magic Machine" - can you feel the 90s?

Slo-Gro (slow growth) is a model of a particulate growth process, which happens for example during the aggregation of zinc particles in a two-dimensional film. The ions wander around until they meet the previously settled particles and thus form tree-like structures. DLA stands for diffusion-limited aggregation. The particles settle to form complex, fractal tree-like structures, which remind me of moss, or the Tree of Life - with branches that thrive and branches that wither out (see Fig. 2).

The analogy (well, one of the analogies) for the DLA process presented in the book is simply too precious to pass [1]:

The most colorful (albeit the least realistic) model for a DLA process involves a succesion of drunks wandering about in the dark until they stumble on a crowd of insensate comrades; lulled by the sounds of peaceful snoring, they instantly lie down to sleep. An aerial view of the slumbering crowd by morning light might well reveal the same fractal shape found in a zinc cluster or a soot patch.

On more serious note, the process can be described as follows. The particles (pixels, ions, ...) are initially placed randomly on the circumference of the circle. Each of the particles then wanders randomly (up, left, right, down) until it finds itself in the neighbourhood of some other particle, which is now stationary. The wandering particle then settles down and a now one is launched. The wandering process is stopped when the particles wanders out too far (outside the circle), or if it made too many steps (10 000) without any contact. New particle is generated to replace the strayed one. The process is repeated in a loop. At some point the arena will fill completely, and no new particles will find any more place to join.

In order to make the process quicker, you can influence the Brownian motion of the particles a little. I added a small displacement for the particles at each step, that slowly drags them towards the center, regardless of their random motion. This is controlled by the attraction parameter.

I made a small interactive simulator of the SLO-GRO effect: SLO-GRO Simulator

The code is available here: https://github.com/dagothar/slo-gro (beware: at some points it's one hack upon another!).

In the simulator you can launch your own slow growth process. You can draw on the board to create your own seeds, even during the simulation. You can tweak and mix the colors on the go. The process produces quite interesting graphical results (see figs. 3-9). Make sure to try different values of parameters, as well as different colors.

Fig. 3. The field overgrown.

Fig. 4. Dappled grass.

Fig. 5. Waves of grass.

Fig. 6. Creative palette.

Fig. 7. Delta step overgrown!

Fig. 8. Moon grass.

Fig. 9. Acid eye.

The moss grows quite quickly in the beginning, but it loses its pace abruptly: at some point the growing tree seems almost static. Even though the particles now have smaller distance to travel, more of them is necessary to fill the rings of increasing area (which grows as the square of the distance!). It will take several minutes to fill our Petri dish.

It is interesting to see what is the dimension of the structure generated by the slow growth process. For such a fractal, we can expect its fractal dimension to be somewhere between 1 and 2. Isn't it exciting that there are figures that dwell somewhere between being linear and planar? If you want to learn more about fractals and fractals dimension, I recommend watching an excellent video by 2Blue1Brown.

The fractal dimensions is basically the exponent by which the area of the object increases in response to scaling. For example, the "area" (length) of the line is linearly dependent on its scaling and thus the line is 1-dimensional. The area of a planar figure (e.g. a triangle) raises with the second power of the scaling, and thus the triangle is 2-dimensional. Similarly, a cube is 3-dimensional. The notion of dimension gets complicated with fractals. They tend to have fractional dimensions.

There's an easy way of calculating the fractal dimension of our structure. Simply measure the area (the number of settled points) for several different values of the radius. I did it by letting the moss grow, pausing at certain intervals, and measuring what the radius of the circle containing the sediment is. The data is presented in the plot below (fig. 10).

Fig. 10. Area of the structure vs. the total area.

The fractal dimension is calculated as the slope of the line of the structure area vs the scale plot.  My result is ~1.9. The fractal dimensions cited for Slo-Gro in [1] is 1.58. The discrepancy here is probably due to the attraction parameter; without it the tendrils of the tree tend to be considerably less dense (but then it takes massive amounts of time to generate the data! - see fig. 12). Feel free to experiment.

Fig. 11. Structure area (blue) and the total area (red) in log-log scale. The blue line has slightly smaller slope.

Fig. 12. Sparser structure with the attraction parameter set to 0.1 instead of 0.5.

Literature

[1] A. K. Dewdney, "The Magic Machine. A Handbook of Computer Sorcery", W. H. Freeman and Company, New York, 1990, ISBN: 0-7167-2149-2.