L-systems | Hacker News Reader

L-systems

jsantell.com

268 pointssigna1143 comments

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.

Talking about OpenGL, there was something else released in 2002 that a resourceful fan [1] has modified to use OpenGL [2] and it works pretty well.

[1] https://verokster.blogspot.com/2019/03/disciples-i-ii-gl-wra...

[2] https://github.com/Verokster/DisciplesGL

Very nice renders!

Since you are an expert, could you share whether L-systems have any practical applications?

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.

http://algorithmicbotany.org/papers/ has a list of papers and other related texts, including the classic book The Algorithmic Beauty of Plants.

Also see https://github.com/krljg/lsystem, a neat way to play with L-systems in Blender in 3D.

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.

HN added the bracket to your link. Should be https://sav.blogs.unr.edu/3d/

Whoops. Fixed, thanks.

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.

https://imgur.com/a/dtmQcHt

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!

[0]: https://www.gamasutra.com/blogs/OsamaAlsalman/20180827/32531...

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")

I played with Fractint around 1997 on my 286, and it already had L-systems. Is your memory of it older than that?

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...

Ook -> Ook ook.

Interestingly, some of the early sources¹ on such recursive string rewriting methods are from Baal haRokeach².

1. https://www.academia.edu/38490274/Symbolic_computation_and_d...

2. https://en.wikipedia.org/wiki/Eleazar_of_Worms

Some people trace the first exposition of recursive production rules for grammars back to Pāṇini (around 5th century BCE) [1]

[1] https://www.jstor.org/stable/23497283?seq=1

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.

Huh, I’m surprised some allusion to this didn’t come up in http://unsongbook.com/. Or maybe I just missed it!

See also "The Algorithmic Beauty of Plants" https://news.ycombinator.com/item?id=8723728

And "Evolving Lindenmayer Systems" https://news.ycombinator.com/item?id=20588039

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.

There is a nice language

#lang lindenmayer, a language for L-Systems

https://docs.racket-lang.org/lindenmayer/index.html

Was not aware of #lang lindenmayer, very cool.

Some of the other, older language environments I've found are the C-based CPFG, C++-based LPFG, L-Py for python

http://algorithmicbotany.org/lstudio/CPFGman.pdf http://algorithmicbotany.org/lstudio/LPFGman.pdf http://algorithmicbotany.org/papers/lpy.fps2012.pdf

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!

The image is produced by

    F: "FF",
    X: "F+[[X]-FX]-F[F-FX]+X"

[0]: https://github.com/FredrikMeyer/lsystems-workshop edit index.js#L102

[1]: https://imgur.com/a/1flZ2b8

That's where the context-sensitive part comes in, I believe.

You can also do these in 3D. See pics at the bottom of this post: http://blog.rabidgremlin.com/2014/12/09/procedural-content-g...

There’s a 3D Hilbert curve in this one too.

The mouse-over effects on the "Projects Notes Speaking About" links at the top right of the page (on desktop) are nice.

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.

university-of-calgary's site: http://algorithmicbotany.org/, also is a treasure trove of articles based on L-Systems...

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 have a longer description here: https://www.quora.com/What-deep-learning-ideas-have-you-trie...

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.

There are already fuzzers based on this idea, for instance tavor (https://github.com/zimmski/tavor). On the purely generative side (no execution), there's blab (https://github.com/aoh/blab).

What these lack is probability parameters for each rule so that the probability distribution isn't necessarily uniform.

> 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])

[0] http://www.akt.tu-berlin.de/fileadmin/fg34/publications-akt/...

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.

It is fun to play with these systems using a software called context free art: https://www.contextfreeart.org

Why aren't there more recent books on L-systems? I was very surprised at the scarcity of them considering the popularity of the topic.

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 always thought L-systems were cool. I even made an animated one: http://jsfiddle.net/victorqribeiro/L3vy97py/

I've been slowing learning webgl, as soon as I have a more robust grasp of it, I'll do one 3D.

LParser: http://laurenslapre.nl/lapre_004.htm

Along with Cthugha, Fractint and Form3D - this was my early PC graphics happy place.

I already implemented it in SDL (C++): https://github.com/MarceloMPJ/LSystemTreeSDL

The page seems to crash Firefox on Android

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.

This is an excellent write-up.

Reply on news.ycombinator.com