[HN Gopher] Lindenmayer systems
___________________________________________________________________
Lindenmayer systems
Author : vsekar
Score : 140 points
Date : 2023-11-19 11:47 UTC (11 hours ago)
(HTM) web link (vsekar.me)
(TXT) w3m dump (vsekar.me)
| smusamashah wrote:
| 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.
| kragen wrote:
| 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}], }
| smusamashah wrote:
| 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.
| kragen wrote:
| 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
| nightowl_games wrote:
| 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-
| MilStdJunkie wrote:
| 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.
| zeitgeistcowboy wrote:
| 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.
| flipgimble wrote:
| 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
| poetaster wrote:
| 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/
| rsiqueira wrote:
| 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>.
| kragen wrote:
| 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
| Rochus wrote:
| That's great, thanks for sharing!
| kragen wrote:
| 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 sierpinski 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 x 340 = 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!
| poetaster wrote:
| I think that it's actually P. Bourke's Tree :
| http://www.paulbourke.net/fractals/lsys/
| cubefox wrote:
| It seems Lindenmayer systems are formal grammars[1] combined with
| some geometric output instead of text.
|
| 1 https://en.wikipedia.org/wiki/Formal_grammar
| kragen wrote:
| they're a particular way to apply a cfg, yeah
| YeGoblynQueenne wrote:
| 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.
| kragen wrote:
| 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!
| dang wrote:
| 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)
___________________________________________________________________
(page generated 2023-11-19 23:00 UTC)