I wrote an L-systems implementation in Common Lisp as part of a thesis around 2002. The software, thesis and some raytraced images are still available at my old university home page: http://www.ii.uib.no/~knute/lsystems/llisp.html
If anyone plans to test the software: I haven't run it in ages, and I suspect that the OpenGL bindings will be tricky to get working today. The rest of the code hopefully still works.
Aristid Lindenmayer used it originally as a model to study the growth of algae, so it has some scientific applications. While computer graphics is the most common use case, L-systems have also been used for generating music.
People interested in this might also be interested in the release notes for The Grove (a Blender tree gen plugin), as they describe a number of modelled behaviours of trees in nature: phototropism, gravitropism, forking, behaviour of sapwood and heartwood, etc.: https://www.thegrove3d.com/releases/the-grove-release-8/
I love that Blender is so programmable. As far as I'm aware, every action in Blender can be expressed in Python. The Grove in an absolutely beautiful representation of the power that comes with that.
A recall a undergrad project where I was helping write a C wrapper around an old FORTRAN library or potential energy calculations to make them accessible in Mathematica (and yes, I am aware of how wild that sentence is). We used Mathematica to generate some potential energy surfaces (they looked like the first picture here https://sav.blogs.unr.edu/3d/ ) and for an interesting visuals I exported the models to Blender. An interesting property of these graphs is that modeling a reaction is taking a point on that graph with some amount of energy and combining it with the gradient at that point. This is essentially the same as simulating a ball rolling around within the surface. So I simulated a ball in Blender, tracked it's motion, and compared it to real life data and "actual" simulations, and found them impressively similar.
I ended up winning some aware for presenting it, it was quite a lot of fun, and now I have a publication and conversation starter of an entry on my CV.
It'd be interesting to see more information about L-systems that aren't strictly branching structures! I played around with them for procedural level generation on a dead prototype.
That image shows 9 generations of the following system:
Symbols:
* Rect(Corner, Dimensions) [black]
* Room(Corner, Dimensions) [green]
* Hall(Corner, Dimensions) [blue]
Rules:
* Rect(Corner, Dimensions) => Room(Corner, Dimensions) if Dimensions matches the size of a predefined room (so I could easily place preconstructed rooms)
* Rect(Corner, Dimensions) => Hall(Corner, Dimensions) if either X or Y dimensions are 100 (1 meter width)
* Rect(Corner, Dimensions) => split at a random distance along either X or Y axis to replace with two Rects()
I'd love to see any examples that are more elegant :) One of the few posts I found was about dungeon generation[0] although I've been assured they're used all over game dev for things other than plants!
I first played with L-systems using Fractint https://en.wikipedia.org/wiki/Fractint & also learned to code by writing Mandlebrots, Julias, a Sierpinski Gasket, and lots of other things in Pascal. Fun times, and a great fun way to learn.
Ah I have good memories of this, but I don't think it was exactly Fractint who did L-systems but a companion system
(Maybe they unified later?)
And even later when reimplementing the Mandelbrot algo I figured out that Fractint had a lot of tricks up its sleeve to be that fast (especially in "the lake")
So NOW, finally, I get why Discworld multiverse's L-space is like it is...
Yes, it's also Library-space, but it's also this, complex organically growing and readjusting system where it's hard to not get lost...
Yep, it was also known to eastern mystics. And there is also a parallel in Sefer Yetzira about "stones" (letters) building "houses" (permutations), which also refers to such generative grammars.
The first section of Godel Escher Bach has a very intuitive description of L-systems with exercises. Can't remember if that's what he called them in the book though.
When playing with a workshop for this [0], I found it hard to make real-looking trees. Especially when trying to color them, as the recursiveness doesn't really care if you want it to be a branch or a trunk. I have experimented with checking the depth of the stack for the turtle, and using that to draw with a different color/strokweight. But still not sure how to make it look more like a real tree. [1] It's fun to experiment with, though!
They're visually nice, but misleading from an interaction design perspective. A hover state should mean that clicking the mouse will perform an action. Here, the hover region is larger than the active region. The mouse cursor is the only way to tell whether you're really in the active region or not.
That's interesting. I was aware of formal grammars and was toying with using stochastic parametric grammars to make generative programs, unknowingly a form of L-system.
I did one thing that goes beyond the grammars mentioned in the article and in wikipedia. You can assign an address to each leaf symbols. If you have binary rules of the form Ax->AxAx, this is easy as you are generating a binary tree and a path to that tree is just a binary number. If you are generating a programming language and each leaf node is a program statement, the return value of that statement can be assigned to that address. Then it is not difficult for each parameters in a parametric grammar to have a reference or reference offset back to these address. These address offsets can be stocastic parameters in the grammar.
To me it's more like generating a full programming language since each statement has a return value and later statements can reference these value by address, a bit like putting the value in a variable and accessing it later.
I then have a scheme to try to learn the stochastic parameters from output examples to try to produce programs that learn to generate specific output (I have had very limited success). The learning scheme includes trying to cluster together rules that generate similar subprograms.
I’ve seen it suggested before, when I was looking into the bijectivity of parsing, that generating lexical-program L-systems (i.e. ASTs where the leaf symbols are a compiler’s lexemes) is a good way of turning a compiler’s BNF-grammar spec into a fuzzer for said compiler’s parser, and possibly, through it, the rest of the compiler.
I expect you could get pretty far by teaching AFL (http://lcamtuf.coredump.cx/afl/) to generate inputs “through” a BNF-grammar L-system—since AFL already has the ability to explore the execution-path-space of the program-under-test.
Personally, I’m intrigued about whether L-systems can be generalized into generators for Directed Acyclic Graphs, rather than just trees. Then you could directly generate (branch-and-label-containing) machine-code, and—hooked up to a tool like AFL—fuzz processors/emulators with it.
I've had this same idea before and used this process successfully for fuzzing interpreters, though it was partly manual, partly a hodge podge of shell scripts.
> Space-filling curves can be formalized via L-systems, resulting in a recursive, fractal-like pattern. More specifically, FASS curves, defined as space-filling, self-avoiding, simple, and self-similar. That is, a single, non-overlapping, recursive, continuous curve.
I guess this can't be combined with space-filling curves that form closed cycles, right? (example of such a curve: the H-curve[0])
If you need a closed cycle, start with a closed cycle and use substitution rules that preserve this property. There is a variant of the Hilbert curve that works this way.
Wrote an LSystem app as part of a larger math suite hobby project. Select 'examples' in the menu and click draw to get going. The lsystems are expressed in my own little math-like scripting language. https://mathblocks.net/workspace/#lsystem_0;
I use Firefox on Android as my main driver (former Mozilla eng) and I haven't had a crash, but have noticed sometimes videos don't load. On Chrome too sometimes, but usually the issue is with the lazy loading of images (Firefox lazy loading TBD https://bugzil.la/1542784).
I've been avoiding adding any JS, but interaction observers may be necessary since I haven't been happy with how any browsers handle 5 or so muted webm videos.
If anyone plans to test the software: I haven't run it in ages, and I suspect that the OpenGL bindings will be tricky to get working today. The rest of the code hopefully still works.