This lab builds on last week's Generating Fractal Curves using L-systems. There are three parts to this lab, adding three new features to the L-system productions. For full credit, you must complete the first part (Bracketed) and one of the two remaining parts:
You will need your code to interpret L-systems from last week's lab. If you didn't keep your code, you can use mine from Chalk. From each set of examples, implement only two of them and then go to the next part. You can return and do more if you finish all the parts, just be sure to add test cases for every example you do.
How do we represent a branching structure (such as trees) using a linear sequence of strings? We will add a pair of matched symbols to the production rules: '< and '> (these will always occur paired.) '< indicates that we are beginning a new branch, so we will have to remember the current position and direction of our turtle so we can return to this position and direction when we finish the branch. The matching '> indicates that the branch is finished and we must re-position the turtle to its original position and direction when we first encountered the branch.
Example:
This example creates a line (the first 'F), then creates a new branch ('<), remembering its current position and direction, turns left ('+) on this new branch and draws a line ('F). When the branch finishes ('>) the turtle is repositioned at its original position and direction just before it began the branch (when it encountered '<), and continues by drawing a line (the third 'F).
There are two problems you must handle when trying to interpret a sequence of symbols with branchings:
Solving 1: The easiest way to determine how to return to your starting starting position is to record the sequence of steps you need to REVERSE your travels in the current branch. To do this, you will need to think about what it means to reverse each symbol. You will find it useful to create a new symbol:
Solving 2: You will use a stack data structure to record which branch you are on. Since brackets are nested, when you encounter a '> its pairing '< is the last left-bracket you encountered.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;; Name: Simple Branching Structure ;;;; Description ;;;; ;;;; Alphabet: 'F, 'G, '+, '- ;;;; Axiom: '(F) ;;;; Production Rule: ;;;; 'F -> '(F < + F > F) ;;;; Interpretation: ;;;; Angle: 36 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;; Name: Weed I ;;;; Description ;;;; ;;;; Alphabet: 'F, 'G, '+, '- ;;;; Axiom: '(F) ;;;; Production Rule: ;;;; 'F -> '(F < + F > F < - F > F) ;;;; Interpretation: ;;;; Angle: 25
Now, we will replace the simple symbols, like 'F and '+ with more complex entities which must carry some information. This extra information will be the length of the step or the angle to rotate (although the direction remains the same.) We no longer insist every step is the same length, or every rotation is by the same angle.
Example:
the rule says (in our old syntax):
but now we decrease the step length on each iteration by 65% (0.65) on each iteration of the rule for B. All angles along a branch (B) remain 45 degrees, but in the axiom, there is a rotation of 180 degrees (-[4a], where a=45 degrees).
The easiest way to implement Parametric L-systems, is to replace the simple symbols, with structures which contain a record of the step length or angle rotation. (In this lab these are the only pieces of information we will record, but you could also have color and line thickness or other attributes as well.)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;; Name: Big-H ;;;; Description ;;;; ;;;; Alphabet: F[x], G[x], B[x], +[y], -[y] ;;;; Axiom: ( < B[s] > -[2a] B[s] ) ;;;; Production Rule: ;;;; B[x] -> ( F[(0.65)x] < +[a] B[(0.65)x] > < -[a] B[(0.65)x] > ) ;;;; Interpretation: ;;;; Angle (a): 90 ;;;; Step (s): you supply ;;;; B[x] : Like F[x], draw line of length x ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;; Name: Tree III ;;;; Description ;;;; ;;;; Alphabet: F[x], G[x], B[x], +[y], -[y] ;;;; Axiom: ( B[s] ) ;;;; Production Rule: ;;;; B[x] -> ( F[x] < +[5a] B[(0.5)x] > < -[7a] B[(0.5)x] > -[a] F[x] ;;;; < +[4a] B[(0.5)x] > < -[7a] B[(0.5)x] > -[a] F[x] ;;;; < +[3a] B[(0.5)x) > < -[5a] B[(0.5)x] > -[a] F[x] B[(0.5)x] ;;;; Interpretation: ;;;; Angle (a): 8 ;;;; Step (s): you supply ;;;; B[x] : Like F[x], draw line of length x
In these L-systems we will add some NOISE to our L-system--allowing some chance determine the fractal. There are two ways we can do this: by having multiple production rules for some of our tokens, which we must choose with some probability, or by allowing the step length or angle rotation to be determined with some randomness. For example, by allowing branch angle to vary a few degrees. The examples below are of multiple rules, each of which is equally likely, and you must randomly choose which rule to apply.
For ease of presentation, these examples use the older notation. You may assume all steps and angle are identical. If you have time experiment with stochastic treatment of step length and angle of rotation.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;; Name: Random Koch Island ;;;; Description ;;;; ;;;; Alphabet: 'F, 'G, '+, '- ;;;; Axiom: '(F - - F - - F) ;;;; Production Rule: ;;;; 'F -> '(F + F - - F + F) (probability 0.5) ;;;; -> '(F - F + + F - F) (probability 0.5) ;;;; Interpretation: ;;;; Angle: 60 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;; Name: Stochastic Weed III ;;;; Description ;;;; ;;;; Alphabet: 'F, 'G, '+, '- ;;;; Axiom: '(F) ;;;; Production Rule: ;;;; 'F -> '(F < + F > F < - F > F) (probability 0.33) ;;;; -> '(F < + F > F ) (probability 0.33) ;;;; -> '(F < - F > F ) (probability 0.33) ;;;; Interpretation: ;;;; Angle: 25.7
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;; Name: Bush I ;;;; Description: Gets complex quickly ;;;; ;;;; Alphabet: 'F, 'G, '+, '- ;;;; Axiom: '(F) ;;;; Production Rule: ;;;; 'F -> '(F F + < + F - F - F > - < - F + F + F > ) ;;;; Interpretation: ;;;; Angle: 22 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;; Name: Tree I ;;;; Description: Note how few lines are produced ;;;; ;;;; Alphabet: 'F, 'G, '+, '-, 'B ;;;; Axiom: '(B) ;;;; Production Rule: ;;;; 'F -> '(F F) ;;;; 'B -> '(F < - - B > < + B > - B ) ;;;; Interpretation: ;;;; Angle: 20 ;;;; Symbols: 'B : Draw line (like 'F) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;; Name: Plant ;;;; Description: Found on wikipedia's l-system page ;;;; ;;;; Alphabet: 'F, 'X, '+, '- ;;;; Axiom: '(X) ;;;; Production Rule: ;;;; 'F -> '(F F) ;;;; 'X -> '(F - < < X > + X > + F < + F X > - X) ;;;; Interpretation: ;;;; Angle: 25 ;;;; Symbols: 'X : Do nothing ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;; Name: Sierpinski Rug ;;;; Description ;;;; ;;;; Alphabet: 'F, 'G, '+, '- ;;;; Axiom: '(F - F - F - F) ;;;; Production Rule: ;;;; 'F -> '(F < - F - F > F F) ;;;; Interpretation: ;;;; Angle: 90 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;; Name: Sierpinski Carpet ;;;; Description ;;;; ;;;; Alphabet: 'F, 'G, '+, '- ;;;; Axiom: '(F - F - F - F) ;;;; Production Rule: ;;;; 'F -> '(F < - F - F > F < - F - F - F > F) ;;;; Interpretation: ;;;; Angle: 90 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;; Name: Sierpinski Maze ;;;; Description ;;;; ;;;; Alphabet: 'F, 'G, '+, '- ;;;; Axiom: '(F) ;;;; Production Rule: ;;;; 'F -> '(< G F > < + G - - - F > < G + G + F >) ;;;; 'G -> '(G G) ;;;; Interpretation: ;;;; Angle: 60
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;; Name: Two-Y's ;;;; Description: Broccoli ;;;; ;;;; Alphabet: F[x], G[x], B[x], +[y], -[y] ;;;; Axiom: ( < B[s] > -[4a] B[s] ) ;;;; Production Rule: ;;;; B[x] -> ( F[(0.65)x] < +[a] B[(0.65)x] > < -[a] B[(0.65)x] > ) ;;;; Interpretation: ;;;; Angle (a): 45 ;;;; Step (s): you supply ;;;; B[x] : Like F[x], draw line of length x ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;; Name: Tree II ;;;; Description ;;;; ;;;; Alphabet: F[x], G[x], B[x], +[y], -[y] ;;;; Axiom: ( B[s] ) ;;;; Production Rule: ;;;; B[x] -> ( F[x] < -[3a] B[(0.5)x] > < +[3a] B[(0.5)x] > ;;;; < -[2a] B[(0.5)x]> < +[2a] B[(0.5)x] > F[x] B[(0.5)x] ) ;;;; Interpretation: ;;;; Angle (a): 20 ;;;; Step (s): you supply ;;;; B[x] : Like F[x], draw line of length x ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;; Name: Weed II ;;;; Description ;;;; ;;;; Alphabet: F[x], G[x], A[x], B[x], +[y], -[y] ;;;; Axiom: ( +[9a] A[s] ) ;;;; Production Rule: ;;;; A[x] -> ( F[x] < +[9a] A[(0.5)x] > -[a] F[x] < -[9a] B[(0.4)x] > A[(0.6)x] ) ;;;; B[x] -> ( F[x] < -[9a] B[(0.5)x] > +[a] F[x] < +[9a] A[(0.4)x] > B[(0.6)x] ) ;;;; Interpretation: ;;;; Angle (a): 10 ;;;; Step (s): you supply ;;;; A[x], B[x] : Like F[x], draw line of length x ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;; Name: Parametric Koch Island ;;;; Description ;;;; ;;;; Alphabet: F[x], G[x], +[y], -[y] ;;;; Axiom: ( F[s] -[a] F[s] -[a] F[s] ) ;;;; Production Rule: Let p=0.3 q=0.7 k = (sqrt (* p q)) ;;;; F[x] -> ( F[px] +[a] F[kx] -[2a] F[kx] +[a] F[qx] ) ;;;; Interpretation: ;;;; Angle (a): 85 ;;;; Step (s): you supply ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;; Name: Alien Life ;;;; Description ;;;; ;;;; Alphabet: F[x], G[x], B[x], +[y], -[y] ;;;; Axiom: ( B[s] ) ;;;; Production Rule: Let k = (/ (sqrt 2) 2) ;;;; B[x] -> ( < -[a] F[kx] B[kx] > G[x] < -[3a] F[kx] B[kx] > ) ;;;; Interpretation: ;;;; Angle (a): 35 ;;;; Step (s): you supply ;;;; B[x] : Like F[x], draw line of length x
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;; Name: Stochastic Bush ;;;; Description ;;;; ;;;; Alphabet: 'F, 'G, 'B, '+, '- ;;;; Axiom: '(F B) ;;;; Production Rule: ;;;; 'B -> '( < + F B > < - F B >) (probability 0.33) ;;;; -> '( < + + F B > < - - F B >) (probability 0.33) ;;;; -> '( < + + + F B > < - - - F B >) (probability 0.33) ;;;; Interpretation: ;;;; Angle: 10 ;;;; 'B : Same as 'F
Add the appropriate test cases to the end of your definitions window so I can see some examples, such as:
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; Test Cases ;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;(simple-branch 4) ;(sierpinski-rug 4) ;(sierpinski-carpet 4) ;(sierpinski-maze 6) ;(weed-I 4) ;(bush-I 4) ;(tree-I 6) ;(two-y 6) ;(big-h 5) ;(tree-II 5) ;(weed-II 6) ;(tree-III 4) ;(param-koch-island 5) ;(alien-life 7) ;(random-koch-island 4) ;(weed-III 5) ;(bush-II 8)
Save the definitions window as (your_cnet_id)-Lab05.scm and submit it via the chalk lab assignment. So for example I would save my file as aterrel-Lab05.scm. Do yourself a favor and keep your work somewhere you can access it.