Turtle Graphics and L-systems with F# and WPF

• Download source - 2.56 KB

Introduction

This is a turtle graphics program which I wrote to improve my knowledge of F#. The turtle, shown as a cursor, draws lines on a canvas when given simple commands relative to its own position such as left, right and forward. These simple commands can provide building blocks for the drawing of complex shapes such as spirals and fractals. F#'s interactive prompt provides a useful means of controlling the turtle. This article will explain how to use the turtle graphics program, and show the F# and WPF code which was used to implement it, and provide some example code for generating fractal shapes using L-system grammars.

How to Use the Turtle

Install and Run F#

These instructions assume that you are using F# interactive with Visual Studio, either Visual Studio 2010 or the free shell. Information about installing F# can be found at the Microsoft F# Development Center. Open the file FSharpTurtle.fsx, select all using Ctrl-A, then press Alt-Enter to load the script into F# Interactive. A canvas with the turtle will appear.

Turtle Commands

The turtle responds to the commands left, right, forward and move or their abbreviations lt, rt, fd and mv. Each of these commands is followed by a float and two semicolons (e.g. left 90.0;;). The left and right commands turn the turtle a given angle, forward draws a line and move moves the turtle without drawing a line. Typing clear();; clears the canvas and returns the turtle to its original position. The default colours (white background, black line, red arrow) can be changed using the settings variable. F# uses the <- operator to change the values of variables.

settings.BackgroundColour <- Brushes.Black;;
settings.ArrowColour <- Brushes.Green;;
settings.LineColour <- Brushes.Red;;

Example: Drawing a Square

Typing the command below in F# Interactive draws a square on the canvas.

for i = 1 to 4 do
       forward 200.0
       left 90.0;;

The turtle draws a line and turns left until it returns to its original position.

Example: Drawing Spirals

let rec polyspi (angle:float)(inc:float)(side:float)(times:int) =
   if times > 0 then
      forward side
      right angle 
      polyspi angle inc (side + inc)(times - 1)
   else None |> ignore 

I adapted the spiral pattern drawing function above from Turtle Geometry (p 18-19). In F#, the let keyword is used to declare functions and variables while rec indicates that the function is recursive. Calling this function with different parameters creates differently shaped spirals, so more specialised versions of the polyspi function can be created using partial function application, also known as currying. The functions declared below have their first 3 polyspi parameters pre-filled and take only the final parameter (times:int) as an argument.

let polyspi90 = polyspi 90. 5. length

let polyspi95 = polyspi 95. 1. length

let polyspi117 = polyspi 117. 3. length

Turtle Graphics Implementation

Type Definitions

The type definitions below, which are called records, are used to store the state of the turtle. The turtle has an x y point on the canvas and an angle, represented by the record labels P of type Point and Angle of type float. The keyword mutable is used to specify that the value of the variables can be changed.

type Point =  {  mutable X : float
           mutable Y : float}
               
type Turtle = {   mutable P : Point
           mutable Angle : float }

The code below constructs the turtle record and puts it in the middle of the window. The type Turtle can be inferred from the record labels so it does not need to be specified.

let turtle = {P = {X = w.ActualWidth/2.;Y = w.ActualHeight/2.}; Angle = 0.}

Turtle Coordinates

Turtle commands use direction and distance from a starting point to draw lines. The program uses trigonometry to find the xy coordinates of the end point of the line. The nextPoint function defined below takes the distance given to forward and treats it as the hypotenuse of a right-angled triangle. This, combined with the turtle angle is used to find the lengths of the adjacent (x) and opposite (y) sides of the triangle and add them to starting point to give an endpoint for the line.

let nextPoint hypotenuse =
     let newX = turtle.P.X + hypotenuse * Math.Cos(degreesRadians(turtle.Angle))
     let newY = turtle.P.Y + hypotenuse * Math.Sin(degreesRadians(turtle.Angle))
     let newPoint = {X = newX;Y = newY}
     newPoint

WPF Canvas and Turtle Arrow Polygon

The turtle graphics are drawn on a WPF canvas. WPF canvases are not usually scrollable, but I found some C# code for a scrollable subclass of Canvas here and rewrote it in F#. The code below creates a window, scrollable canvas, scrollviewer, and an arrow to represent the turtle.

let w = new Window(Topmost=true)
w.Show()
let c = new ScrollableCanvas()
c.Background <- Brushes.White
let scrollViewer = new ScrollViewer()
scrollViewer.HorizontalScrollBarVisibility <- ScrollBarVisibility.Auto
scrollViewer.VerticalScrollBarVisibility <- ScrollBarVisibility.Auto
w.Content <- scrollViewer
scrollViewer.Content <- c
let makeArrow() = 
   let arrow = new Polygon()
   arrow.Fill <- Brushes.Red
   let p1 = new System.Windows.Point(0.,20.)
   let p2 = new System.Windows.Point(25.,10.)
   let p3 = new System.Windows.Point(0.,0.)
   let centrePoint = new System.Windows.Point(0.5,0.5)
   let pCollection = new PointCollection()
   pCollection.Add p1
   pCollection.Add p2
   pCollection.Add p3
   arrow.RenderTransformOrigin <- centrePoint
   arrow.Points <- pCollection
   arrow
  
let mutable arrow = makeArrow()
  
c.Children.Add(arrow)

The left and right functions defined below change the angle of the turtle, then use it to rotate the arrow polygon.

let left deg = turtle.Angle <- turtle.Angle - deg
            arrow.RenderTransform <- new RotateTransform(Angle = turtle.Angle)
let right deg = turtle.Angle <- turtle.Angle + deg
            arrow.RenderTransform <- new RotateTransform(Angle = turtle.Angle)

The moveTo function moves the arrow to the given xy coordinates on the WPF canvas.

let moveTo x y = turtle.P.X <- x
              turtle.P.Y <- y
              Canvas.SetLeft(arrow, turtle.P.X - 12.5)
              Canvas.SetTop(arrow, turtle.P.Y  - 10.0)

The forward function uses nextPoint to get the endpoint of the line, draws the line, then moves the arrow cursor to the endpoint.

let forward distance = 
   let next = nextPoint distance
   let l = new Line()
   l.X1 <- turtle.P.X
   l.Y1 <- turtle.P.Y
   l.X2 <- next.X
   l.Y2 <- next.Y
   l.Stroke <- settings.LineColour
   c.Children.Add(l) |> ignore
   moveTo next.X next.Y

Using L-systems to Draw Fractal Shapes

Fractals and L-systems

Fractals are geometric shapes which are composed of self-similar parts. The growth of fractal shapes, including complex, organic-looking structures can be modelled using L-system grammars and turtle graphics. An L-system grammar has a set of symbols, a starting string of symbols and production rules describing how symbols are replaced with other symbols. Symbols can be variables or constants; constants remain the same each generation and variables are replaced with other symbols. Some of the symbols represent turtle drawing commands.

DOL-systems

This turtle program includes code which can be used to draw the simplest L-systems called DOL-systems, which are deterministic (there is only one production rule per symbol) and context-free (a production rule only depends on a symbol, not its neighbouring symbols).

L-system Implementation

The data type defined below can be used to describe a simple L-system. It has a string of starting symbols Start, a Dictionary of production rules Rules where the char key is a symbol and the string value is the resulting string of symbols. The turtle turns a certain Angle left or right when the shape is drawn.

type LSystem = { Start     : string
                         Rules     : Dictionary<char,string< /> />
                         Angle     : float}

The plant like image above can be drawn using the l-system defined below.

    let branching =
    let rules = new Dictionary<char, />()
    rules.Add('F',"FF")
    rules.Add('X',"F-[[X]+X]+F[+FX]-X")
    rules.Add('+',"+")
    rules.Add('-',"-")
    rules.Add('[',"[")
    rules.Add(']',"]")
    {Start = "X";Rules = rules;Angle=22.5}

The symbols in this l-system grammar (apart from X) match drawing commands in the function defined below. The pushTurtle and popTurtle functions add and remove the current state of the turtle from a stack, allowing a branching shape to be drawn.

let drawCommand (lsys:LSystem)(symbol:char) =
    match symbol with
    | 'F' -> forward length 
    | 'G' -> forward length
    | 'f' -> move length
    | '+' -> left (lsys.Angle)
    | '-' -> right (lsys.Angle)
    | '[' -> pushTurtle()
    | ']' -> popTurtle()
    | _   -> None |> ignore

The function drawLSystem draws an L-system lsys after generating a string of instructions for n iterations.

let drawLSystem (lsys:LSystem) (n:int) =
   let instructions = generateString lsys n in
      for command in instructions do
         drawCommand lsys command

Other L-system examples are provided in the file FSharpTurtle.fsx.

References

F#

• Expert F#
• Microsoft F# Development Center

Turtle Graphics

• Turtle Geometry - Harold Abelson and Andrea diSessa

L-systems

• L-system Wikipedia
• The Algorithmic Beauty of Plants

WPF

• Shapes and Basic Drawing in WPF Overview

History

• 10^th October, 2010: Initial post