Saturday, August 4, 2018

Dave Computes With L-Systems

Let's begin with turtle graphics, in which a turtle can move forward (F), turn right 90 degrees (R), or turn left 90 degrees (L). Here is a simple program:
FRFF
For a turtle initially facing north, the program traces out the following path:


Now let's introduce the x operation, which does nothing at all. For example, the program Fx simply moves the turtle forward once. Now consider the following rule:
Replace x with Fx.
If we start with x, and apply the rule, we get Fx. If we apply the rule to Fx, we get FFx. After applying the rule 8 times, we get FFFFFFFFx. Therefore, this replacement rule can be used to draw an arbitrarily long straight line. We'll abbreviate this rule as xFx. It is our first example of a Lindenmayer System, or L-System. Here is another example:
x → FRx
Starting from x, this rule gives us FRx, then FRFRx, then FRFRFRx, then FRFRFRFRx, which will draw a square. Applying the rule any more will simply retrace the original square path. Now it's time for a more interesting rule.
x → xFxR
Starting from x, this rule gives us xFxR, then xFxRFxFxRR, then xFxRFxFxRRFxFxRFxFxRRR. But here's another way to think about it. First, execute FR, resulting in a single line segment followed by a right turn:


Applying the rule means drawing this shape (FR), then moving forward (F), then drawing a second copy of the shape (FR), and then turning right (R). Here is the resulting path (FRFFRR):

Having drawn this shape, we move forward, draw the shape again, and turn right, resulting in level 3:

Level 4:

Level 5:

Level 6:

Level 7: 


Many levels later, we get the following tentacle-like fractal:

x → xFxR


xFxR is the most interesting L-System of length 4. (RxFx, xFxL, and LxFx are all related by symmetry.) The only other interesting and distinct L-System of length 4 is FxxR, which draws a different (uglier) tentacled shape:

x → FxxR


5-character rules allow us to produce new tentacle shapes like this one:

x → xRxRF


We can also produce more complex fractals based on three copies (3 x's):

x → xxFxR

x → xRxxF


More interesting images can emerge from 6-character rules:

x → xFRxLx

x → xxRxxF


And here are some fractals resulting from longer rules (drawn with shorter segments):

x → xxRRFxR

x → xxxRRxFR

x → xRxxFLxR

x → FxxRRxFR

x → xRRxxxFRx

x → xFxLxxRxR

x → xRxxRRxRxF

L-Systems with multiple rules can produce even more complex fractals. Here's an L-system I found for drawing a version of the dragon fractal:

x  xRyF
 FxLy


L-Systems can also use angles other than 90 degrees. This is necessary to produce Fractals like the Sierpinski curve, Koch curve, or even Penrose tilings.

Thursday, August 2, 2018

Dave Computes Fractals

I explored fractals based on an n-by-n pattern like this one:


To make the fractal, I replaced each black square with the entire pattern, and then repeated this process multiple times. The L-shaped pattern above results in this Sierpinski fractal:


That turns out to be the only interesting fractal based on a 2-by-2 pattern. Things got more interesting when I moved onto 3-by-3 patterns like this one, in which only the middle square is empty:


That pattern resulted in this carpet fractal:


I had seen that fractal before, but I found there were many other interesting fractals based on 3-by-3 patterns. Here are a few of my favorites: