The most fun I have in programming is generating content for games using procedural generation algorithms. It is the art of crafting recipes for generating a dungeon for a game or an entire galaxy for simulation. These algorithms take a small amount of input or noise and generate flowers, buildings, cities, planets, creatures, music… pretty much anything your imagination can come up with.
This post is a follow-up from a talk I gave at a local coder camp earlier this year. By the end you will learn one of the easier algorithms, L-Systems, to begin generating your own content from. It is meant for people who are comfortable with programming and are curious about procedural content generation, games, or creative coding.
L-Systems
Aristid Lindenmayer, a Hungarian biologist, invented a formal language called L-Systems in 1968. This formal language was used to model the behaviour of simple cells. He expanded upon the system later to model plants and he wrote about it in a book called, The Algorithmic Beauty of Plants.
Formal languages are, if you are not aware, fun things to play with. In strict terms they are a set of finite strings of symbols and a set of rules for generating or modifying them. I find it more practical to explain them in terms of a game.
You start with a string of characters, FGF. Using the following rules your goal is to transform the string of characters into, GFG. The rules are:
- You may transform an F into a GF
- You may transform a sequence FG into F
- You must transform the string once using one of the above rules to form a new string. Repeat this process on the new string until you reach the goal.
An example sequence might look like:
FGF
GFGF
GFF
GFGF
GFGFG
GFFGI didn’t check to see whether the goal is reachable or anything like that. Just try a few rounds to see how the game works. Then try the MU puzzle for more.
This is the basis for L-Systems and everything else you’ll learn in this article.
In formal terms, an L-System can be thought of as a context-free formal grammar. It takes an alphabet, an initial string, and a set of production rules. One feeds the string through the production rules applying each rule to produce the new string which becomes the new input for the next iteration. It is defined as:
$$ G = (V, \\omega, P) $$
Where
- \( V \) is the alphabet
- \( \omega \) is the seed
- \( P \) is the set of production rules
The production rules map one symbol in the input string to another sequence of one or more symbols. There is an implicit rule that returns the symbol if there is no production rule for it.
This is what we’ll implement in this article. If you choose to dive deeper into the subject you’ll come across other grammar modes that give even more interesting results and possibilies. There are also a number of open problems in formal languages that are really fun to try and take a stab at.
In order to implement our L-System we start with a function expand which takes a string sequence and a list of rules which it applies to each gene in the sequence to produce a new sequence. It looks like this:
function expand(sequence, rules) {
return [].map.call(sequence, function (gene) {
return rules[gene] || gene;
}).join('');
}Note that this code is purely for demonstration purposes. I leave it to the reader to write this function for very large inputs should they so desire. Caveat emptor.
If we try it out we get:
expand('F-G-F', {'F': 'xxx'});
/*
xxx-G-xxx
*/The next function we need calls expand successively from a given input string. I call it grow and it takes three parameters: seed, rules, and numGenerations:
function grow(seed, rules, numGenerations) {
var sequence = seed;
for (var i=0; i<numGenerations; i++) {
sequence = expand(sequence, rules);
}
return sequence;
}
grow('F-G', {'F': 'G-F-G', 'G': 'F-G-F'}, 2);
/*
F-G-F-G-F-G-F-G-F-G-F-G-F-G-F-G-F-G
*/And we’re done! This is the basis we need for generating larger output from some small, initial input. Depending on how we interpret the sequence of symbols we can draw geometric patterns, trees, flowers, creatures, buildings, cities… whatever suits your intentions and imagination.
Drawing
We’ll use a system of graphics some of you may remember called, Turtle Graphics. It’s a method of drawing vector graphics using a stateful cursor object and a series of commands such as pen up, pen down, and move forward ten units. The specific library I’m using is turtlewax for Javascript and HTML5 canvas.
The easiest method of using L-Systems to draw procedural graphics is to map symbols to the turtle graphics methods I mentioned. In our first example we will map the symbol F to the turtle command, “forward.” G will do the same. We’ll use two symbols: - and + to map to the commands, “left” and “right” respectively.
We’ll use the following helper function that will take our mappings and draw our figures:
function drawLSystem(turtle, seed, rules, numGenerations, drawFunctions) {
var sequence = grow(seed, rules, numGenerations);
for (var i=0; i<sequence.length; i++) {
var draw = drawFunctions[sequence[i]] || function (x) {};
draw(turtle);
}
}We can then write something like this:
function drawSierpinski(turtle, numGenerations) {
var rules = {'F': 'G-F-G',
'G': 'F+G+F'};
var geom = {'F': function (t) { t.go(10); },
'G': function (t) { t.go(10); },
'-': function (t) { t.turn(-60); },
'+': function (t) { t.turn(60); }};
drawLSystem(turtle, 'F-G-F', rules, numGenerations, geom);
}And get something that should look like this:
If you’ve never seen the above figure before it’s a Sierpinski Triangle. We approximated it from an L-System. That’s because, in part, L-Systems are great at generating self-similar fractals. Play with the above code and try different distances, angles, and see what you get.
Lindenmayer later used L-Systems to model plants. In order to do the same we need to add a couple of more symbols and the notion of backtracking. We’ll use [ to push the current position and heading of the turtle onto a stack. We’ll use ] to backtrack the the last state on the stack.
Our function will look like this:
function drawBranching(turtle, numGenerations) {
var states = [{'position': [turtle.x, turtle.y],
'dir': turtle.dir}];
function rememberState(t) {
states.push({'position': [t.x, t.y],
'dir': t.dir});
}
function recallState(t) {
var state = states.pop();
t.penup();
t.goto(state['position'][0], state['position'][1]);
t.dir = state['dir'];
t.pendown();
}
var rules = {'F': 'F[+F]F[-F]'}
var geom = {'F': function(t) { t.go(6) },
'[': rememberState,
']': recallState,
'-': function(t) { t.turn(-20); },
'+': function(t) { t.turn(20); }};
turtle.pendown();
drawLSystem(turtle, 'F[+F]F[-F][F]', rules, 4, geom);
turtle.penup();
}And then we should see something that looks like a branching tree:
Conclusion
L-Systems are one of my favorite introductory algorithms to teach people interested in procedural graphics. From a simple foundation in formal languages we can generate long and complex chains of symbols. Depending on how we interpret those symbols we can draw interesting fractical figures or plants right away.
Understanding L-Systems also provides a strong foundation that you can build upon. It doesn’t have to stop with plants and fractals. Other people have published systems to model city buildings and I’ve heard of people using these concepts to build creatures and cities.
If you want to take the concept further be sure to investigate contextual, stochastic, and parametric grammars. These allow you to build rules that depend on other rules or parameters and allow you to build even more complex structures. There are also a number of open problems in this space to investigate!
If you liked this article follow me on twitter and let me know. It helps motivate me to write more articles if I know they’re helping people out there. Happy hacking!