Wednesday, September 1, 2010

Exploring L-Systems

Another day, another dog. Another month, another piece of dangerous productivity avoided. This month I am avoided furthering my life goals by starting to read Godel, Escher, Bach", which is an awesome book. It deals with a remarkable amount of things, including formal logical systems. This got me delving into string manipulation systems again and somehow got me onto L-Systems.

L-Systems were developed by this theoretical botanist (yes such a thing exists) to codify plant growth. Later they were taken up by mathematicians to visualise and generate a variety of interesting recursive geometric patterns. Lately they have been used extensively to generate artificial life in computer science, especially tree like entities.

L-Systems are a string rewriting system. basically they take a string of characters, and then create a new string by replacing each old character with a new string, according to some rules. This continues and iterates creating increasingly more complicated and intricate strings of characters. These characters can then be interpreted by drawing program to make beautiful patterns. You can read more about L-Systems at the Wikipedia Article, I don't want to get bogged down in the details, I want to look at some cool patterns.

Below is an L-System generator I built. You can explore the different possibilities of L Systems. The string grammar is as follows:

  • Capital Letter: Draw a line forward
  • Small Letter: Do nothing
  • +: Turn right
  • -: Turn left
  • [:Save position to stack
  • ]:load previously saved position from stack
The rules are defined in a simple way, for example "x->y" means replace every "x" with a "y". You can change a whole bunch of settings about how the drawing system interprets the strings in the settings below. This is a bit of a rushed explanation, but you can find lots of info online that should help you out. There is also a list of interesting presets at the bottom of this post, check them out, play around, leave any interesting rules you find in the comments.

Axiom:
Rule:
Number of Generations:
Starting Point: (, )
Starting Angle:
Turn Angle:
Movement Size:

Interesting Examples

8 comments:

taliesin said...

Very, very cool. You should consider posting it on HackerNews, I'm sure they'd love it there...

Rosie said...

Ooh, L-systems. I did my final year project on these at university. I highly recommend the book 'The Algorithmic Beauty of Plants' particularly if you want to start drawing trees

cageface said...

We seem to have independently built almost the same thing:

http://www.burgerkone.com/elsy/

hyeend said...

This is really good! You've inspired me to try to write a version for the http://js1k.com contest

taliesin said...

cageface: your one is slicker, but I like how James's draws it live..

cageface said...

Yeah I agree I like that feature. We should pool our resources!

James said...

Yeah, cageface, yours is pretty cool. If you have a cool idea you'd like to collaborate on one day drop me a message.

cageface said...

Agreed. There are a couple things I'd like to try that would benefit from a partner.