Hacker News new | past | comments | ask | show | jobs | submit login
Lindenmayer systems (vsekar.me)
163 points by vsekar on Nov 19, 2023 | hide | past | favorite | 22 comments



There are IFS-like fractals that can be generated using small iterative functions. Here are examples in JavaScript that can be remixed (and they are very short, only 140 characters or less). E.g.: https://www.dwitter.net/h/fractal and https://www.dwitter.net/h/fern

Dwitter is a cool social network where JavaScript programmers can share demos, fractals, art algorithms and interactive code viewed on <canvas>.


i'd say these are still ifses, just not linear ones

dwitter looks pretty cool. like twitter if it was designed for creativity and beauty instead of trolling

i did a golfed emoji ifs the other day in python but it's 288 characters, not 140 or even 280: http://canonical.org/~kragen/sw/dev3/hilbert.py

i feel like the three levels of representation needed to draw l-systems on a raster display (strings, turtle commands, and cartesian coordinates) sort of disfavor golfing. i managed to get an ascii-art ifs down to 259 strokes by using complex numbers instead of vectors: http://canonical.org/~kragen/sw/dev3/cifs.py


That's great, thanks for sharing!


Related. Others?

Lindenmayer Systems - https://news.ycombinator.com/item?id=38024405 - Oct 2023 (34 comments)

Evolving Lindenmayer Systems - https://news.ycombinator.com/item?id=20588039 - Aug 2019 (15 comments)

Lindenmayer systems - https://news.ycombinator.com/item?id=16002532 - Dec 2017 (9 comments)

Four L-system fractals in LaTeX - https://news.ycombinator.com/item?id=9716780 - June 2015 (5 comments)


If you value learning about the strengths and weaknesses of different algorithms then I recommend reading this counter-argument against one species of heavily extended L-Systems used for city road network generation: http://nothings.org/gamedev/l_systems.html


I did my university graphics project with L Systems and made a video that explains em decently I think. You can use the "bud" character to draw leaves at the end of the iteration steps and it works pretty well. I got a poor grade in this class!

https://youtu.be/pZ8NLfUJ7p0?si=RXtX4lcfGTXosWK-


I still use the old Blender LSys py scripts for quick vines and hasty greebles. There's better ways to generate this stuff now - first Sverchok , but now you got geo nodes and all sorts of parametric stuff- but sometimes, I guess, the handsaw that you know is sometimes, occasionally better than the fancy CNC that you don't.


I made one in vanilla JS on canvas and was focused on making trees while keeping it fast as possible. If you add probability for each rule, you can get very close to real like trees. To handle probability faster, I simply added the rules with higher chance more number of times in the set. Then I started following The Book (ABOP). And what I stopped at was having the need to write a compiler for custom syntax and things that come with it.

If I don't dive into functions etc I got far enough with a loop iterating on ops, but it was getting tedious adding more functionality while following abop. Might sit and give another try, some day.


i feel like js is flexible enough that you can probably use an embedded dsl instead of writing a parser; maybe something like

    {
        a: '-bff+affa+ffb-',
        b: '+aff-bffb-ffa+',
        c: ['a', {p: .1}, 'b', {p: .9}],
    }


It's similar to this already. But this isn't flexible enough to implement methods etc which abop expands towards. My goal was to do almost everything all other browser based lsystems are doing while keeping it fast which most tools are not.


you'll probably be pleasantly surprised by how easy it is to write a parser using a parser generator; unfortunately i don't know which one to recommend for js (i've used yacc, ocamlyacc, hammer, and a few i've written myself, but i don't recommend using the js one i wrote)

if you aren't pleasantly surprised, maybe try a different parser generator


A nice overview for generating in JS. Building on ideas I had writing some systems for https://anvaka.github.io/lsystem/, I used supercollider to write some raga like compositions that are executed as L-systems. https://poetaster.de/sc-ls/


I like that you show L systems for many of the fractals in Benoit Mandelbrot’s 1982 book The Fractal Nature of Geometry. It’s a beautiful book and worth checking out.


It seems Lindenmayer systems are formal grammars[1] combined with some geometric output instead of text.

1 https://en.wikipedia.org/wiki/Formal_grammar


they're a particular way to apply a cfg, yeah


Lindemayer's book (The Algorithmic Beauty of Plants) claims L-systems are not CFGs because all expansions to a non-terminal are applied simultaneously, rather than sequentially. Having played around with simple l-systems, the claim holds some water. No time to go into details now but I can give some examples later if requested.


you get the same result if you apply them sequentially, don't you? to me the crucial difference is that you stop after a certain number of iterations, a number which is uniform across the whole string, so for interesting l-systems your final string has nonterminals in it, while usually with a cfg your terminals and nonterminals are disjoint and so you can't stop expanding until you run out of nonterminals

i'd love to see your examples!


Ugh, sorry. Too much work. Maybe I'll write about it somewhere (don't have a blog or anything) in which case I'll post it here. Sorry!


sorry! you don't owe me any work but if you have some notes somewhere I'd be delighted to read them. maybe email?


that's not even a fern, much less barnsley's fern, which is canonically an ifs

this is barnsley's fern https://en.wikipedia.org/wiki/Iterated_function_system#Const...

you can clearly generate barnsley's fern with an l-system but i've never seen it done

otherwise this seems like a nice explanation of l-systems

— ⁂ —

i'm a bit dubious about the implementation strategy because even though i'm not a rustacean this looks like accidentally quadratic code to me

                sequence.remove(insert_index);
                sequence.insert_str(insert_index, rule);
https://web.mit.edu/rust-lang_v1.25/arch/amd64_ubuntu1404/sh... says:

> Inserts a string slice into this String at a byte position. This is an O(n) operation as it requires copying every element in the buffer.

you can probably draw an l-system graphic of more than a million drawing commands on your screen, let alone a laser cutter or something (in http://canonical.org/~kragen/sw/laserboot/cut-6/ for example i laser-cut a sierpiński triangle with an l-system implemented in postscript) so the problem size starts to get into the range where being accidentally quadratic matters

if i'm not just mistaken, which is possible since i haven't tested it, but i thought it was a likely enough problem to be worth mentioning

— ⁂ —

also where the article says

> The function above can also be written recursively but for larger iterations, you would run out of stack depth way before running out of heap memory.

it is exactly backwards, at least with the straightforward recursive approach; 40 generations would require 40 stack frames occupying perhaps 4096 or 8192 bytes of stack, but for the non-barnsley non-fern given as the first example, produces something more than 18 × 3⁴⁰ = 218837978263024718418 bytes of output, which is sufficiently larger than 8192 that the heap runs out first

(you can of course maintain an explicit stack and write an iterative loop)

— ⁂ —

i hope these corrections and other comments are helpful and not discouraging. keep creating beauty! keep hacking!


I think that it's actually P. Bourke's Tree : http://www.paulbourke.net/fractals/lsys/


it's a lovely tree, and it does appear on paul bourke's page, but he doesn't seem to be claiming that it is original to him; on the contrary, he says

> This program implements some of the L-Systems discussed in "Lecture Notes in Biomathematics" by Przemyslaw Prusinkiewcz and James Hanan

he merely introduces it as 'example' with no notes on its provenance

i haven't seen the lecture notes, and i don't remember if this l-system is in abop, which is from the year before (and cited on bourke's page)




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: