In the past months I’ve been reading up on procedural generation and emergence. My reasearch led me to develop a scripting language to be able to interactively ‘program’ L-system based fractal animations. It’s meant to be easy to pick up and modify, so it might be a nice sandbox for people that would like to learn to program or just want to engage in a session of creative coding. It’s quite fun once you’ve gotten the hang of it!
I think every programmer has dabbled with Fractals at one point. I remember generating Mandelbrot images on the very first computer my family owned.
Last fall Josh Parnell pitched his project Limit Theory on Kickstarter. His claims sounded way too ambitious for a one-man project, yet he raised more then 350% of the funding goal. So why did people trust him to pull it off? His pitch video was featuring quite some cutting-edge procedural generation technology.
This project rekindled my interest on that topic. I found a pdf copy of the book “Algorithmic Beauty of Plants” and was intrigued. The basic concept of L-System is simple enough. It’s grammar based rewriting system, a theoretical framework for modelling the development of simple multicellular organisms, introduced 1968 by the Hungarian theoretical biologist and botanist Aristid Lindenmayer.
But the above book introduced me to more advanced variants of L-Systems, adding context sensitivity, randomness and parameters. The examples were quite impressive and my urge to experiment with it irresistible.
Usually L-Systems define a bunch of production rules that operate on strings of symbols. When a rule is applied it replaces a sequence of symbols in the string (the predecessor) by a different, typically more complex sequence (the successor). The more iterations you perform the longer and more complex the string of symbols becomes. Symbols are statically defined to do a very specific thing like rotating or moving a cursor to generate a rendering.
Imagine the above string of symbols were generated using L-Systems. F is defined to move forward, + to rotate left and – to rotate right.
This method of programming line based drawings by controlling a cursor through commands that move and rotate it relative to it’s current state is called Turtle Graphics. The programming language Logo designed for educational use first introduced it and it’s quite intuitive to grasp.
My experiments turned into a little scripting language to interactively ‘program’ L-system based fractals, called Grove Script. At first it seems like it does nothing special as it is based on the concept of using turtle graphics in conjunction with L-systems, too.
But, instead of statically defining an alphabet of symbols that the productions operate upon and that have a specific meaning when executed, in Grove Script the symbols refer to executable code. The key idea is that instead of programming everything like in your typical programming language or forfeiting the flexibility of procedural languages completely like in your typical rewriting system Grove Script brings both worlds together. It allows you to use rewriting rules to create complex sequences of procedure calls by applying simple rules to equally simple axioms.
And unlike most other script- or programming languages where writing and running the program are separate steps Grove Script is aiming to allow users to develop fractal renderings and animations in an fun, intuitive process: There’s no compiling or restarting required when you change the code. You get instant feedback on your changes. I let Bret Victor explain why that’s a good thing!
You’re free to use your favorite Text Editor to write Grove Script. But when the script you’re editing is running in the interpreter every changes you make will be instantly incorporated.
The most basic productions just replace a token with a with some replacement whenever it is encountered. Rules need not be simple, though. Grove Script supports:
- Context Sensitivity – Rule can require multiple tokens to be encountered in order.
- Parametric Tokens – Tokens can have a parameters attached.
- Conditions – Production trigger only if the supplied boolean expression evaluates to ‘true’
- Consequences – Rule-specific code can be executed whenever a production triggers. Great to raise some counter variables.
As mentioned before I use the concept of Turtle Graphics in Grove Script. All pixels are drawn by the turtle, controlled by only a handful of straightforward commands. Besides commands to modify the turtles spatial state you can set the size, transparency and color of the line. That’s it.
There are other commands to save and restore the interpreter state on a stack – very important to generate branching structures. There’s an instruction to call subroutines or a list of subroutines. And of course those subroutine-lists are ideal to be generated with L-System-inspired productions. So you got a command to initialize a list with the axiom and one to apply a ruleset. Last but not least you can define variables through commands that can be used in algebraic and boolean expressions.
But all in all there are only a dozen commands you have to familiarize yourself with to unlock the full potential of Grove Script.
I found a way to handle all the usual control flow (conditional branching, loops) with 3 basic instructions that operate on code blocks marked using Tab indentation.
- Repeat – Continue with the first of all previous instructions of the same block depth
- Break – Skip all following instructions of the same or greater block depth
- Gate – When condition evaluates to false, skip all following commands of the same or greater depth, except other Gate instructions op’s of the same depth.
Using these control-flow instructions to the desired effect is a little counter-intuitive though. So to improve the usability I added macros that will unfold to the required operations when the interpreter parses the script. Macros blend well with instructions and improve readability. Being able to write code that uses familiar words like “while, until, repeat, if, else” hopefully appeals to people with and without programming background alike.
Thanks to macros you can write this…
repeat 4 out 'foo
… which unfolds to this…
set _c, 4 gate _c > 0 out 'foo set _c, _c-1 repeat
The interpreter is written in C++ and quite fast. It renders even complex fractals that require thousands of instruction calls in real-time. If it’s possible to render 60 frames per second it would be a waste to never change the output. By using the time() function in expressions you can generate fractals that change over time and render animations. Another important function in that regard is random() which provides you with pseudo random numbers. You can use the time() to calculate the random seed to be used by the PRNG and suddenly the randomness is under your control. It took me a while to figure out how to use these elements in conjunction with productions but once you’ve gotten the hang of it it’s quite easy to script quite impressive looking vector graphics that let you forget that everything you see is rendered with the plain olde Turtle Graphics approach.
Excuse the poor quality. I just captured the interpreter with Hypercam instead of rendering to video directly.
To experience Grove Script the way it’s meant to be you should check out the Github repository. There’s a precompiled interpreter, full source-code, documentation, examples and a half finished tutorial! Feel encouraged to try it for yourself: Start Grove.exe. Drag&Drop some scripts from the example folder to the application. You can edit the script while Grove executes it and it will adapt at run time. If you’ve got questions and can’t find answers in the Docs or from the tutorial just comment below!
There’s no reason this shouldn’t compile on Mac or Linux. If you want to make your own build you need the Cinder Framework – the rest is just plain standard C++.
And if you just want to know how Grove Script looks like without having to download and run executables from the internet here’s the listing that generates the animation from the above video:
//set some basic constant parameters to be used in expressions set speed, 15 set fadetime, 20 set budstep, 5 set maxage, 70 set leafAge, 5 //let the size of the structure adapt with window size set step, 0.5*_height/480 //these variables change every frame because they all depend on the current //value of the time() function. //Thanks to the modulo operate age wraps around at maxage. set age, (speed*time()) % maxage set fade, min(1, (maxage-age) / fadetime) out fade set age, 2.5*age^0.55 set frac, max(0.01, frac(age)) //each structure should look unique. //So we use a different random seed for every new structure out 'rnd seed, floor(time()*speed/(maxage)) shuffle floor(time()*speed/(maxage)) //init the turtle dir random(360) pos 0, step*(5*age-100) //set the axiom of the 'plant' structre seed plant, A(0,0,1) //apply the ruleset 'r1' as often as the plant is old. repeat age grow plant, r1 //fun info: how many buds were generated? out budCnt //render 'plant' twice - mirrored. push rotate -45 run plant pop rotate 135 run plant //Now the Tokens that the L-System operates upon are defined. //light blue tips of the structure #A(age, angle) run shade(leafAge/frac) size frac^0.5 move step*frac^0.5, angle //what becomes of A in the next cycle - a simple curve #B(t, angle) run shade(leafAge/(t+frac)) size (t+frac)^0.5 move step*(t+frac)^0.5, angle //B becomes C when it's old enough to spawn leaves - does the same thing, though #C(t, angle) run B(t, angle) //a growing leaf #L(t, angle) run leaf(t+frac, angle) //a finalized leaf #xL(t, angle) run leaf(t, angle) //a growing bud #Y(t, spread, angle) run bud(0.3*(t+frac), (spread+frac)*budstep, 0.1*angle) //a finalized bud #xY(t, spread, angle) run bud(0.3*(t+frac), (spread+frac)*budstep, 0.1*angle) //render a bud #bud(len, angle, curve) run budshade(1/len) //left side push size 2*len^0.3 rotate angle move len^0.3, angle size len/2 rotate -90 move len, -angle pop //right side push size 2*len^0.3 rotate -angle move len^0.3, -angle size len rotate 90 move len, angle pop //stem rotate curve move 0.55*len^0.7 //render a leaf #leaf(len, ang) size 1 rotate 10*ang*len^0.6 move 0.5*len^0.3 move len^0.6, ang*(60+len*5) rotate 180 - ang*0.4*(60+len*10) move 0.5*len^0.5, -ang*(len*5) move 0.7*len^0.5, ang*(len*10) //color buds #budshade(alpha) visible alpha * fade rgb 1.0-0.8*alpha*alpha, 0.6*alpha+0.2, 0.2*alpha*alpha //color rest #shade(alpha) visible alpha * fade rgb 1.0-0.5*alpha, 0.5*alpha+0.5, 0.3*alpha #[ push #] pop //The rules are evaluated in the order of appearance. //rare rules appear first, if all are skipped the general case is usually to just grow the existing tokens #r1 //BRANCHING //higher c makes a vine less likely to bend or split but increases chance to spawn buds A(i, j, c) : rnd(0, c) > 2+budCnt -> B(1, j) Y(0, 1, j) raise budCnt, 1 //if old enough there's a chance to split into 3 A(i, j, c) : i > c and rnd() < 0.5/c -> B(1, j) [ A(0, rnd(-40,-60), c+2) ] [ A(0, rnd(40,60), c+2) ] A(0, 0, c+1) //...or into 2 A(i, j, c) : i > c and rnd() < 0.5/c -> B(1, j) [ A(0, rnd(-40,-60), c+1) ] A(0, rnd(40,60), c+1) //or just change the direction A(i, j, c) -> B(1, j) A(i+1, j+rnd(-90, 90)/(c+1), c) //LEAVES //based on the curvature leaves spawn on different sides B(i, j) : j < 0 and i = leafAge-1 -> C(i+1, j) [ L(0, 1) ] B(i, j) : j > 0 and i = leafAge-1 -> C(i+1, j) [ L(0, -1) ] //GROWTH //and of course everything needs to grows Y(i, j, k) -> Y(i+1, j+1, k) xY(i, j, k) B(i, j) -> B(i+1, j) C(i, j) -> C(i+1, j) L(i, j) : i > 1+rnd(7) -> xL(i+1, j) L(i, j) -> L(i+1, j)