For a fledgling pro­ject idea, I’ve recently needed to work out how to draw plants pro­ced­ur­ally, and of course Python is my lan­guage of choice for some rapid pro­to­typ­ing. Whilst some richly-featured pro­fes­sional applic­a­tions exist for gen­er­at­ing flora in a pro­ced­ural fash­ion for high-end ren­der­ing, there are pre­cious few sys­tems avail­able for the kind of bulk task that I require.

At first the task of gen­er­at­ing plants might seem like a massive endeav­our. The vari­ous per­muta­tions of stem widths, lengths, branch fre­quency, col­our vari­ation, leaf size, shape, fre­quency and mind-boggling. And that’s not even con­sid­er­ing the prob­lem space rep­res­en­ted by flowers.

Fortunately, the prob­lem of rep­res­ent­ing self-similar bio­lo­gical devel­op­ment is one that attrac­ted Aristid Lindenmayer, who in 1968 intro­duced L-Systems:

… as a the­or­et­ical frame­work for study­ing the devel­op­ment of simple mul­ti­cel­lu­lar organ­isms, and sub­sequently applied to invest­ig­ate higher plants and plant organs. After the incor­por­a­tion of geo­met­ric fea­tures, plant mod­els expressed using L-systems became detailed enough to allow the use of com­puter graph­ics for real­istic visu­al­iz­a­tion of plant struc­tures and devel­op­mental processes.

(Lindenmayer’s book The Algorithmic Beauty of Plants is no longer in print, but is avail­able for free in PDF.)

L-Systems are remark­ably power­ful, simple sys­tems that express the devel­op­ment of a formal gram­mar through a par­al­lel rewrit­ing pro­cess. In effect, you start with a string that rep­res­ents cer­tain graph­ical oper­a­tions, and a set of rules for rewrit­ing the string. You iter­ate over the string a cer­tain num­ber of times, and are left with a final product.

For example in a 2D sys­tem, the sym­bol F rep­res­ents draw­ing a straight line in a for­ward dir­ec­tion, the sym­bol + rep­res­ents rotat­ing left, and — rep­res­ents rotat­ing right. If you start with the string “F”, and a rule that says “(F → F+F−F−F+F)”, then you’d see the fol­low­ing iterations:

  1. F+F-F-F+F
  2. F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F
  3. F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F+ F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F– F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F– F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F+ F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F

If you then plot those rules using a unit vec­tor length and an angle of 90 degrees, you end up with the fol­low­ing iterations:

  1. Single iteration of a Koch Square
  2. Second iteration of a Koch Square
  3. Third iteration of a Koch Square

There are sev­eral more sym­bols that can be applied to the graph­ical oper­a­tions, includ­ing push­ing the cur­rent pos­i­tion and ori­ent­a­tion onto a stack and pop­ping it off again, rota­tions in 3D, and oper­a­tions to define closed poly­gons and mov­ing through col­our and size lookup tables.

The most basic type of L-System is the determ­in­istic context-less sys­tem, D0L, where each oper­a­tion is inde­pend­ent and will always pro­duce the same out­put. The Koch Square above is one of the most simplistic examples, but with a couple of vari­ations much more com­plex pat­terns arise:

  • Start: “X”
  • Rule 1: “(X → F-[[X]+X]+F[+FX]-X)”
  • Rule 2: “(F → FF)”
  • Angle: 25 degrees
  • Iterations: 5
  • Sample 1

In Part 2 we’ll look at a first approach to imple­ment­ing L-Systems in Python, and a rudi­ment­ary ren­derer for 2D sys­tems using PyCairo.