Ok, so remember how yesterday I said I tried to draw this curve, but “everything went wrong” and here’s something random? Yes? Great!
What I was trying to get at is that there is more than one way to skin a cat or, if you prefer, to visualize a recursive set. In the last Koch example, the drawing code itself was recursive. We would see if we were at the terminal (bottom-most) depth and if so, draw a little bit of line. Otherwise, we would recursively call the drawCurve(…) function.
Instead of making the drawing code recursive, we can define the curve as a set of rules, evaluate those rules recursively, and use the Turtle from my last post to draw the whole curve!
The especially cool thing about this is that we can change the rules to draw whatever kind of self-similar shape we want, without having to do a bunch of math for each curve we want to draw.
About L-systems
An L-System is defined by a grammar. It has a starting state (sometimes called an axiom) and some rewriting rules. For the Koch curve, you’ll sometimes see the L-System defined like this:
Axiom: F
Rule: F -> F+F-F-F+F
I think people use pluses and minuses to make it look like math. Instead, you should think of each character in the Rule as an instruction for your turtle. F means “go forward”, + means turn left, – means turn right.
I wrote my Koch curve rule like this:
Axiom: f
Rule: f -> f l f r r f l f
For myself, “l” means turn left, and “r” means turn right.
Ok, so that’s all well and good, but how does this translate to a crazy self-similar curve? All I’ve shown you so far is a really simple grammar.
Well, the key is that the rule “f” rewrites itself. I’ll show you in the table below, for up to two iterations:
| Iterations |
Result |
| 0 |
f |
| 1 |
f l f r r f l f |
| 2 |
f l f r r f l f l f l f r r f l f r r f l f r r f l f l f l f r r f l f |
Ok, so for each iteration, you replace ‘f’ with ‘f l f r r f l f’. Once you’ve iterated enough times, you can tell your turtle to follow the instructions in that list.
Trouble is, when you fully expand the list, you see that it gets really big after just a couple of iterations. If you tried to just string replace 10 times, you would run out of memory. And don’t think about trying to get more memory, because if you doubled your memory, you might have enough for just one more iteration.
So, the way to overcome this is to evaluate the rules while we’re drawing. You’ll find the code for that in the function called evalutron, below:
Turtle t;
HashMap rules;
class Turtle {
float x, y, ang;
float default_angle;
boolean down;
Turtle(float _x, float _y, float _ang) {
x = _x;
y = _y;
ang = _ang;
down = false;
}
void penDown() {
down = true;
}
void penUp() {
down = false;
}
void forward(float len) {
float nx = x+cos(radians(ang))*len;
float ny = y+sin(radians(ang))*len;
if (down) {
line(x,y,nx,ny);
}
x = nx;
y = ny;
}
void turnLeft(float _ang) {
ang -= _ang;
}
void turnLeft() {
ang -= default_angle;
}
void turnRight(float _ang) {
ang += _ang;
}
void turnRight() {
ang += default_angle;
}
}
void execute(char chr, float zoom_factor) {
switch (chr) {
case 'l':
t.turnLeft();
break;
case 'r':
t.turnRight();
break;
case 'f':
t.forward(zoom_factor);
break;
}
}
void evalutron(String state, HashMap rules, int depth, float zoom) {
for (int i = 0; i < state.length(); i++) {
char x = state.charAt(i);
String result = (String) rules.get(x);
if (depth > 0 && result != null) {
evalutron(result, rules, depth-1,zoom);
}
else {
execute(x, zoom);
}
}
}
void setup() {
background(10);
stroke(120);
smooth();
size(600,600);
frameRate(30);
/**
* Set up the L-System Rule
*/
rules = new HashMap();
rules.put('f', "flfrrflf");
/**
* Configure our friendly turtle
*/
t = new Turtle(0,300,0);
t.penDown();
t.default_angle = 60;
/*
* Evaluate the rule set, and draw the curve.
* 'f' is the initial rule set. notice that 'f' is the rule in the rules map,
* so it will get rewritten for each iteration.
*/
evalutron("f", rules, 7, .28);
}You see that evalutron just looks at the current token, evaluates the depth at which its evaluating, and decides whether to expand the current token to another ruleset, or to pass the command to the turtle. Easy as pie!
Oh, and if you’re paying very close attention, you’ll see that the turtle has changed a teeny bit: he can now turn a ‘default’ amount by calling turnLeft() and turnRight() with no parameters.
So anyways, this is another way to draw cool recursive sets, but in a way that’s a little more language-y and a little less math-y. Also, you can change the original ‘axiom’ or add new rules to get wildly different results. Try it!
As proof, here’s the applet in action. Sorry, no interaction this time:
