Try my new book!

Algorithms, circle mazes, hex grids, masking, weaving, braiding, 3D and 4D grids, spheres, and more!

The Buckblog

assorted ramblings by Jamis Buck

May 2015

Experimenting with L-Systems

7 May 2015 — An overview of L-system fractals, with a simple implementation in Ruby. An argument is given in favor of exploration, experimentation, and play. — 6-minute read

With my book out of the way, I’ve found myself with a bit more time to experiment, explore, and play. It’s been a long time! I feel like I’ve almost forgotten how.

I’ve tinkered with some algorithms I’d never played with before, like Bridson’s algorithm for Poisson-disc sampling, and the Bowyer-Watson algorithm for Delaunay triangulation. Those were fun—definitely challenging my limits and teaching me things I’d never considered before.

But while those were intriguing, they weren’t necessarily fun. It’s hard to take those algorithms and play “what-if” games with them. There’s only so much you can do with a Delaunay triangulation, for instance, before it’s just another mesh grid.

So while researching and writing an article for the May issue of PragPub Magazine, I stumbled across this thing called a Lindenmeyer system (or “L-system” for short). I’d played with L-systems before, years ago, back when fractals were ubiquitous and the cool thing to do was to zoom Mandelbrots to the limits of your CPU. I’d never tried to implement these L-systems before, though.

It was time.

So I rolled up my sleeves and went to work, and you know what? This stuff is almost as fun as mazes!

I won’t go into the whole background of L-systems (though it’s worth reading about—who knew a study of algae could lead to a grammar for recursively generating fractals?). The gist of it is this: you start with some initial string, and then repeatedly apply transformations to it until the string is some desired length. Then you interpret the string as a series of commands (turtle-style) that draw the final pattern.

Here’s a concrete example. Let’s say you start with the string FX. To transform this string, we’ll replace each instance of X with X+YF+, and (because we’ve introduced a Y there) we’ll replace Y with -FX-Y. The other symbols (F, +, and -) we’ll leave untouched.

So, after a few iterations, our string grows like this. (Parentheses are used to indicate expansions, and aren’t actually part of the grammar, here.)

  1. FX
  2. F(X+YF+)
  3. F(X+YF+)+(-FX-Y)F+
  4. F(X+YF+)+(-FX-Y)F++-F(X+YF+)-(-FX-Y)F+

And so forth. (You can see that the string grows long quite rapidly!)

But so what? Well, look: treat those symbols in the string as turtle graphic commands, right? Let F mean “move forward”, + mean “turn right 90 degrees”, and `-‘ mean “turn left 90 degrees” (and ignore all the other symbols). Those strings become descriptions of curves! In this case, if you let the string get long enough, it becomes a fractal known as the Dragon curve. The following was created by applying the transformation 14 times in succession:

Well, this totally tickles my inner geek. (And I’ll be the first to admit, my inner geek is not buried very deeply at all.) I mean, heck, not only does this have the word fractal in it, it also has grammar, curve, and transformation, and suggests things like parser and interpreter. I gotta say—I kind of love those things.

And look at all the ways you can experiment with this! I mean, you can start just by fiddling with the transformation rules, right? What if you switch a - for a +, or go whole-hog and replace an entire substitution rule? You can get all kinds of interesting effects. But you can go even further! Who’s to say that a turn needs to be 90 degrees? Or that left and right turns need to be symmetrical? What if you add more operations, like push and pop to save and restore the turtle’s position?

Well, you wind up with beautiful fractals like this one:

This is a seaweed pattern I grabbed off the Internet, which uses an initial starting string of F, and a substitution rule that changes every F into FF-[-F+F+F]+[+F-F-F]. (Those square brackets represent “push” and “pop” operations.)

But you know what really makes me giggle? This whole thing is ridiculously easy to implement. The computer scientist in me had to try and abstract things all out, but here’s a bare bones implementation that illustrates the basic idea.

require 'chunky_png'

WHITE = ChunkyPNG::Color::WHITE
BLACK = ChunkyPNG::Color::BLACK

# Expand the given string, using the given rules. Any
# character in the string that does not match a rule
# is preserved, verbatim.
def expand(string, rules)
  string.
    each_char.
    map { |char| rules[char] || char }.
    join
end

# [face_x, face_y] describe a vector. Turn that vector
# through some angle theta, and return the resulting
# vector.
def turn(theta, face_x, face_y)
  [ face_x * Math.cos(theta) - face_y * Math.sin(theta),
    face_y * Math.cos(theta) + face_x * Math.sin(theta) ]
end

# Draw the given L-system:
# * canvas is a ChunkyPNG::Image instance
# * x and y are the position to begin drawing from
# * string is the starting state of the L-system
# * order is how many times the string should be
#   transformed
# * rules is a hash of substitutions, where each key
#   expands to its corresponding value.
# * step is the distance a single move spans
# * angle is the magnitude (in degrees) of a turn
def draw(canvas, x, y, string, order, rules, step, angle)
  order.times { string = expand(string, rules) }

  stack = []
  face_x, face_y = 0, -1
  radians = angle * Math::PI / 180.0

  string.each_char do |char|
    case char
      when "F"
        new_x = x + face_x * step
        new_y = y + face_y * step

        canvas.line(x.round, y.round,
          new_x.round, new_y.round,
          BLACK)

        x, y = new_x, new_y

      when "+"
        face_x, face_y = turn(radians, face_x, face_y)

      when "-"
        face_x, face_y = turn(-radians, face_x, face_y)

      when "["
        stack.push [x, y, face_x, face_y]

      when "]"
        x, y, face_x, face_y = stack.pop
    end
  end
end

# Dragon curve
start = "FX"
rules = { "X" => "X+YF+", "Y" => "-FX-Y" }

canvas = ChunkyPNG::Image.new(600, 450, WHITE)
draw(canvas, 460, 150, start, 14, rules, 3, 90)

canvas.save("fractal.png")

I’ll be playing with this stuff for a while, I’m sure, discovering and rediscovering things that others probably stumbled across years and years ago, and enjoying every minute of it. The entire premise of “what if I change this one small thing” is just so compelling!

If you’re interested in tinkering, too, I’d encourage you to try your hand at implementing an L-system processor. Or, if you’re impatient to just jump in and start playing with fractals, you can grab what I’ve done so far, a simple library I’m calling “Lindy”, at https://github.com/jamis/lindy.

Happy exploring!

Mar 2015

Playing with Constants, Methods, and Superclasses

24 March 2015 — A few curious Rubyisms of dubious use, which may yet be worth knowing about — 3-minute read

Task Tracking for Neurochemical Brains

17 March 2015 — Presenting a simple (and perhaps very unoriginal) technique for keeping track of a list of tasks in the face of interruption and exploration — 4-minute read
Feb 2015

Mazes for Programmers: Beta!

4 February 2015 — The author announces the beta availability of his new book, "Mazes for Programmers", and invites the reader to participate in its completion by offering feedback, corrections, and suggestions — 2-minute read
Jan 2015

Lessons from the Kitchen

30 January 2015 — A retrospective on a personal journey, wherein the author's experiences of growing as a cook are compared with learning how to write software — 5-minute read

Hanging Out a Shingle

26 January 2015 — 1-minute read

Getting Back in the Pool

20 January 2015 — 2-minute read

A Better Recursive Division Algorithm

15 January 2015 — 5-minute read

Winding Back Up

13 January 2015 — 3-minute read

Sep 2011

Winding down...

1 September 2011 — 1-minute read

Jun 2011

Sharing the Inheritance Hierarchy

7 June 2011 — 3-minute read

Mar 2011

Maze Generation: More weave mazes

17 March 2011 — 8-minute read

Maze Generation: Weave mazes

4 March 2011 — 11-minute read

Feb 2011

Weave Mazes: Your Take?

28 February 2011 — 1-minute read

Programming Language Survey Results

22 February 2011 — 3-minute read

Kaleidoscope

19 February 2011 — 2-minute read

Mazes in CoffeeScript

9 February 2011 — 2-minute read

Maze Generation: Algorithm Recap

7 February 2011 — 5-minute read

Maze Generation: Sidewinder algorithm

3 February 2011 — 12-minute read

Maze Generation: Binary Tree algorithm

1 February 2011 — 7-minute read

Jan 2011

Maze Generation: Growing Tree algorithm

27 January 2011 — 9-minute read

Maze Generation: Hunt-and-Kill algorithm

24 January 2011 — 15-minute read

Maze Generation: Wilson's algorithm

20 January 2011 — 16-minute read

Maze Generation: Aldous-Broder algorithm

17 January 2011 — 11-minute read

Maze Generation: Recursive Division

12 January 2011 — 11-minute read

Maze Generation: Prim's Algorithm

10 January 2011 — 10-minute read

Maze Generation: Kruskal's Algorithm

3 January 2011 — 7-minute read

Dec 2010

Maze Generation: Eller's Algorithm

29 December 2010 — 11-minute read

Maze Generation: Recursive Backtracking

27 December 2010 — 5-minute read

Theseus 1.0

20 December 2010 — 3-minute read

Way Back

The Buckblog Archives

Dating to 2004 — Hundreds more articles