Procedural Generation with L-Systems (very simple example)
While working on a new project, I found myself needing to use procedural generation. This wasn’t just a “this would be something cool to add” type of thing, it was absolutely necessary (like any other feature that eventually leads to feature creep, and the project not getting completed).
So, like any reasonable person, I went down the 10-hour YouTube rabbit hole on how I would go about implementing this on my use case. To my surprise, building something like this turns out to be relatively simple. I introduce to you the L-system.
So, how do we code this algorithm? Well first, let’s get a simplified overview of what a L-system is.
In a nutshell, this algorithm requires a formal alphabet (constraints), rules to apply to those constraints, and a starting state (axiom). Remember grammars from your complier class? Neither do I. So let’s go over them at a high level.
A grammar is just a set of rules to apply to an alphabet. For example:
F -> “FF+F-[+-F]”
All this means is that where ever you see “F” in an axiom, you will replace it with the string “FF+F-[+-F]”. For those that have done a calculus class think of this as a function composition.
So with this grammar (rule) and the axiom (starting state) of “FXF” we would get the derivation:
grammar: F -> “FF+F-[+-F]”
axiom: FXF -> “FF+F-[+-F]XFF+F-[+-F]”
(where “->” symbol means our derivation.)
Simple enough right? So now what do we do with these strings? Let’s apply an action to each of these characters.
F = draw forward
X = no geometric meaning
+ = 60% right
— = 60% left
[] = Start/end of branch
With these simple rules we can then draw our tree over iterations of our state.
iteration 1:
grammar: F -> “FF+F-[+-F]”
axiom: FXF -> “FF+F-[+-F]XFF+F-[+-F]”
iteration 2:
iteration1 as axiom: FF+F-[+-F]XFF+F-[+-F] -> FF+F-[+-F]XFF+F-[+-F]FF+F-[+-F]XFF+F-[+-F]+FF+F-[+-F]XFF+F-[+-F]-[+-FF+F-[+-F]XFF+F-[+-F]]XFF+F-[+-F]XFF+F-[+-F]FF+F-[+-F]XFF+F-[+-F]+FF+F-[+-F]XFF+F-[+-F]-[+-FF+F-[+-F]XFF+F-[+-F]]
Now I’m sure you have a good understanding of how these can grow and become arbitrarily complex. If I went through this too fast or if you’re a visual-audio learner like me, checkout Simon Dev’s youtube video on the subject. He does a fantastic job explaining it. The code I’m using for this tutorial is his, the only thing I did was add an express server so you can clone my git repo and run it on your local machine.
Now, let’s get this project up and running so you can play with the beauty of this simple and elegant algorithm.
The server is serving files in a /static directory, handle this as necessary for your use case.
Lastly, the javascript file that performs this algorithm:
Again, if you want a more in-depth explanation about the code, please visit Simon Dev’s youtube video as he goes into the implementation details and makes everything very easy to understand.
As for running the code, make sure to have Node installed on your computer and run npm init && npm install express in your root directory where the main.js file is. After that, just run node main.js from your command line and visit https://localhost:3000/simple.html and enjoy the work of Aristid Lindenmayer.
Circling back around to my project, this side exercise didn’t solve my project’s use case, but it is a step in the right direction. This did help me hypothetically solve what I need to do to get this project done. Check back for an implementation of this code using Swift and Metal (as our graphics library) on IOS.
Sources:
SimonDev. “Procedural Plant Generation with L-Systems.” YouTube, uploaded by SimonDev, https://www.youtube.com/watch?v=feNVBEPXAcE&t=361s.
Compton, Kate. “Practical Procedural Generation for Everyone.” YouTube, uploaded by GDC, https://www.youtube.com/watch?v=WumyfLEa6bU.
Department Ecoinformatics, Biometrics and Forest Growth, Georg-August University of Göttingen. “L-Systems.” grogra.de, http://wwwuser.gwdg.de/~groimp/grogra.de/grammars/lsystems.html.
