Lab 20: The Dragon Fractal
Implement this lab with the Intermediate Student Language with Lambda.
Make sure you follow The Style we use for the {B,I,A}SL{,+} languages in this class.
Choose the initial Head and Hands, and get started!
A Bit Different
Almost every function we’ve written to-date follows some template based on the structure of the input data. Today we’re going to design a program that is structured based on the generated output.
Today you will design functions to draw the iterations of an interesting fractal curve known as the Dragon. The shape was featured in the headings of chapters in the book Jurassic Park.
We’ll start off by building a simple line drawing program. Then we’ll combine pieces into the fractal’s generative recursion.
Lines
; A Dir is one of "left", "right", "up", or "down". ; Interp: A direction in which a line may be drawn.
Ex 1: Design the function rotate-dir that returns the 90° counter-clockwise rotatation of the given Dir.
Ex 2: Design the function rotate-dirs that rotates all the Dirs in a given [Listof Dir]
Ex 3: Design the function move-posn : Number Number Dir Number -> Posn that returns a Posn that is the result of moving the given x and y in the given direction, by the given amount.
Ex 4: Design the function draw-dirs that adds lines to the given image in the given list of directions (in order), starting at the given x and y onto the given image.
; draw-dirs : [Listof Dir] Number Number Image -> Image ; Draw lines of any color on the given image, following the given directions ; starting at (x, y).
Hint: Use structural recursion over the directions here, and choose some constant amount for move-posn (say 5).
Here’s a small set of definitions to help you test your functions. Use the arrow keys to create a path (a [Listof Dir]). You can hit r to rotate all the points to the left.
; Screen Size... (define W 400) (define H 400) ; Draw wrapper (define (draw w) (local [(define lst (reverse w))] (draw-dirs lst (/ W 2) (/ H 2) (empty-scene W H)))) ; Key handler (define (key w ke) (cond [(ormap (λ (d) (key=? ke d)) '("up" "down" "left" "right")) (cons ke w)] [(key=? ke "r") (rotate-dirs w)] [else w])) (big-bang '() (to-draw draw) (on-key key))
Drawing the Fractal
Swap Head and Hands!
Now we need to generate our fractal! The function dragon takes a [Listof Dir] and a Natural iters, which counts the number of remaining iterations. The number iters will count down to 0; the list of directions will double in size after each iteration.
Ex 5: Based on the information in the last pararaph, why must we give a non-empty list of directions as the initial directions given to dragon?
; dragon : [Listof Dir] Number -> [Listof Dir] ; Compute the next iteration of the Dragon Fractal. (define (dragon lod iters) '()) ; <- stub (check-expect (dragon '("down") 0) '("down")) (check-expect (dragon '("down") 1) '("down" "right")) (check-expect (dragon '("down") 2) '("down" "right" "up" "right")) (check-expect (dragon '("down") 3) '("down" "right" "up" "right" "up" "left" "up" "right"))
Ex 6: Design the function dragon. If there are no iterations remaining return the given list of directions. Otherwise, return a new list of directions such that
all of the directions in the given list are rotated counter-clockwise,
that rotated list of directions is reversed,
that rotated/reversed list of directions is appended to the end of the given directions, and then
recur on the whole list of directions with one fewer remaining iters.
Now we can remove (or comment out) our old big-bang code and replace it with this:
; draw : Natural -> Image (define (draw w) (local [(define lst (dragon '("down") w))] (draw-dirs lst (/ W 2) (/ H 2) (empty-scene W H)))) ; key : Natural KeyEvent -> Natural (define (key w ke) (cond [(key=? ke "up") (add1 w)] [(and (key=? ke "down") (> w 1)) (sub1 w)] [else w])) ; Let's make this fractal! (big-bang 0 (to-draw draw) (on-key key))
You can hit the up or down arrows to increase or decrease the number of iterations of the generated fractal.