Someone commented on a thousand trees, that I'm using Lindenmeyer systems and this was a common approach to generating vegetation. I have never heard of Lindenmeyer Systems, or L-Systems for short, so I wanted to learn about them and see how they relate to my naive approach. The basic idea of Aristid Lindenmeyers invention is that plant growth can be modelled via a string replacement algorithm. Starting from an axiom, each character of the string is replaced according to production rules thereby creating a new string. This procedure can be repeated using the new string as axiom until the desired size is reached. To my understanding, the first application was a model of algae growth with the following axiom and rules:
Axiom: AB
Production Rules:
A -> AB
B -> A
Which resulted in these strings that represent an aspect of the algaes structure.
ABA
ABAAB
ABAABABA
ABAABABAABAAB
ABAABABAABAABABAABABA
ABAABABAABAABABAABABAABAABABAABAAB
ABAABABAABAABABAABABAABAABABAABAABABAABABAABAABABAABABA
ABAABABAABAABABAABABAABAABABAABAABABAABABAABAABABAABABAABAABABAABAABABAABABAABAABABAABAAB
At first I experimented with some complicated designs, but in the end I found a pure function does the job just fine. It takes the axiom and rules in the form of a HashMap<String, String> where strings index their replacement string. I then simply iterate over the axiom and push the replacement strings to the output string.
pub fn produce(axiom: &str, rules: &HashMap<String, String>) -> String {
let mut s = String::new();
for var in axiom.chars() {
match rules.get::<str>(&var.to_string()) {
Some(string) => {
// Variables are subsituted according to their production rules
s.push_str(string)
}
None => {
// Constants are simply kept
s.push_str(&var.to_string())
}
}
};
s
}
The above Algae output was produced by this program:
fn main() {
let axiom = String::from("AB");
let mut production_rules = HashMap::new();
production_rules.insert(String::from("A"), String::from("AB"));
production_rules.insert(String::from("B"), String::from("A"));
let mut production = axiom;
for _i in 0..10 {
production = produce(&production, &production_rules);
println!("{}", production);
}
}
The extension to introduce the all-important randomness into the process, or probabilistic L-Systems, can be achieved by substituting the replacement string from before with a vector of replacement strings with associated probabilities.
pub fn produce_stochastic(axiom: &str, rules: &HashMapString, Vec<(f32, String)>>) -> String {
let mut s = String::new();
let mut rng = rand::thread_rng();
for var in axiom.chars() {
match rules.get::<str>(&var.to_string()) {
Some(choices) => {
// Variables are subsituted according to a production rule
// randomly chosen from the given choices
let random_val: f32 = rng.gen();
let mut total_prob = 0.0;
for (prob, string) in choices {
total_prob += prob;
if total_prob > 1.0 {
// panic
println!("Total probability is greater than 1.0, aborting");
break;
}
if random_val < total_prob {
s.push_str(string);
break;
}
}
}
None => {
// Constants are simply kept
s.push_str(&var.to_string())
}
}
};
s
}
Rendering
The Algae strings are cool, but my goal was to create nice images of plants. In the sources I found, L-Systems were rendered using Turtle graphics. Imagine a turtle with a pen strapped to it's belly so it draws while walking. In its simplest form the turtle can only walk straight and rotate. To achieve branching structures such as trees, the turtle is equipped with a stack of poses (position + rotation). On a given command, for example [, the current pose is pushed on the stack. Another command, for example ], pops a pose off the stack and teleports the turtle to that pose. Pushing a pose to the stack means the turtle "remembers" the current pose as a branching point to which she will come back when she is finished with the current branch by popping the pose off the stack and teleporting.
My turtle implementation simply consists of the Turtle struct which can perform these operations. It has the additional fields thickness and color for more visual interest. While moving forward() the turtle draws a line using the awesome creative coding framework nannou.
pub struct Turtle {
pub position: Vector2,
pub orientation: f32, // 12:00 -> 0 03:00 -> PI/4
pub thickness: f32,
pub color: Rgb8,
pub stack: Vec<(Vector2, f32)>
}
impl Turtle {
pub fn forward(& mut self, draw: &Draw, dist: f32) {
let new_position = self.position + vec2(
dist * self.orientation.sin(),
dist * self.orientation.cos(),
);
draw.line()
.start(self.position)
.end(new_position)
.weight(self.thickness)
.color(self.color);
self.position = new_position;
}
pub fn turn(& mut self, rad: f32) {
self.orientation = self.orientation + rad;
}
pub fn push(&mut self) {
self.stack.push((self.position, self.orientation));
}
pub fn pop(&mut self) {
match self.stack.pop() {
Some(popped) => {
let (position, orientation) = popped;
self.position = position;
self.orientation = orientation;
}
None => println!("Popped off empty stack")
}
}
}
Now that we can produce L-Systems and render them with Turtle Graphics, it's time for some images! To generate different graphics, we need axioms and rules for the L-System and instructions on how the turtle should interpret each character. The fractal plant is a common example. The rules are:
Axiom: X
Rules:
X -> F+[[X]-X]-F[-FX]+X
F -> FF
Here is how I would produce it with my implementation, omitting the nannou boilerplate for brevity.
fn main() {
let mut axiom = String::from("X");
let mut production_rules = HashMap::new();
production_rules.insert(String::from("X"), String::from("F+[[X]-X]-F[-FX]+X"));
production_rules.insert(String::from("F"), String::from("FF"));
for _ in 0..6 {
axiom = produce(&axiom, &production_rules)
}
// This call would actually be inside the view function, which provides a Draw API object
render_turtle(draw, axiom);
}
pub fn render_turtle(draw: &Draw, path: &str) {
let mut turtle = Turtle{
position: vec2(0.0, 0.0),
orientation: 0.0,
thickness: 1.0,
color: FORESTGREEN,
stack: Vec::new(),
};
for c in path.chars() {
match c.to_string().as_str() {
// F means "draw forward"
"F" => {
turtle.forward(draw, 5.0);
}
// − means "turn right 25°"
"-" => {
turtle.turn(to_rad(25.0));
}
// + means "turn left 25°"
"+" => {
turtle.turn(to_rad(-25.0));
}
// X does not correspond to any drawing action and is used to control the evolution of the curve.
"X" => {}
// [ save current values for position and angle
"[" => {
turtle.push();
}
// ]: pop position and angle
"]" => {
turtle.pop();
}
_ => {
println!("unknown command")
}
}
}
}
Summary
I am fascinated by how much variety can be produced from this seemingly simple concept. I have just touched the surface, other people produce amazingly complex and intricate structures with this technique. Check out the Wikipedia page on L-Systems for more examples. However, I personally find it very hard to translate some desired effect or outcome into production and rendering rules that would achieve it. The naive approach of explicitly creating branching structures, while possibly equivalent, seems more intuitive to me.
