While playing with extensions in Inkscape, I ran into Tavmjong Bah's detailed breakdown of the Render Extensions. It got me really interested in Lindenmayer systems, which are formal grammars based on string rewriting. An L-system begins with an initial state called the axiom. Its terms (characters in a string) are iteratively replaced using a set of rules. There are two types of terms: constants which replace themselves (identity function) and variables which are replaced by a sequence of one or more terms. The system is run for a set number of iterations and can grow quite quickly.
Consider a system with the axiom "A" and the replacement rules 'A' => "AB", 'B' => "A". After one iteration, the state of the system is "AB". Then "ABA", then "ABAAB", and so on. As a quick snippet of pseudocode:
iterations = 4 axiom = "A" state = axiom while i < iterations newstate = "" for c in state if c is 'A' newstate += "AB" else if c is 'B' newstate += "A" state = newstate print state
Aristid Lindenmayer, the name sake of L-systems, originally developed the above system to model the growth of algae. L-systems, when used with ]turtle graphics](https://en.wikipedia.org/wiki/Turtle_graphics), can actually draw fractals and other interesting patterns found in nature.
Some terms have special meaning for the purpose of the turtle graphics. Note that the use of '[' or ']' makes the system a bracketed OL-system, a refinement on L-systems.
F = move forward 1 unit + = increment current angle by angle - = decrement current angle by angle [ = save current position and angle (stack) ] = restore last saved position and angle (stack)
And now for some examples!
The well-known Sierpinski triangle, as an L-system:
axiom: "F-G-G" rules: 'F' => "F-G+F+G-F" 'G' => "GG" angle: 60 iterations: 6
A realstic plant generated by an L-system:
axiom: "X" rules: 'X' => "F-[[X]+X]+F[+FX]-X" 'F' => "FF" angle: 25 iterations: 5
Stochastic L-systems, where rules are probabilistically applied, can be used to create convincing models of nature in both 2D and 3D.
User:Solkoll [Public domain], via Wikimedia Commons
All L-systems that don't use '[' or ']' from the turtle graphics noted above can be drawn with a single line on paper. These would be really fun to try out with a pen plotter I've been working on for a group project, which I should be posting about in the near future.