Iβm not sure what trace1 and trace2 are meant to do in the spec below.
Introduction
An interesting challenge in the games and cinematic effects industries is
that of generating and rendering visually realistic scenes containing organic
structures like plants, bushes and trees.
One approach is to have a database of predefined objects that can be
looked up and placed into a scene on request. However, if the same structure
is used repeatedly then the rendered scene tends to looks very artificial β in
nature not all trees are alike!
An alternative is to use a program to generate artificial plant-like structures from scratch using rules for generating trunks, branches, flowers etc.
as the program executes. With a little additional effort, these rules can be
applied probabilistically so that no two structures end up looking the same.
A popular way of defining plant-like structures is to use Lindenmayer
Systems, or L-Systems for short. L-Systems are named after the biologist
Aristid Lindenmayer who was interested in describing the apparently fractal
nature of plant growth using simple rewriting rules. L-Systems can be used
to define some of the well-known fractals you might have come across already.
In this exercise, we are going to work with very simple deterministic
two-dimensional structures, but it should be easy to see how the process
might be generalised, for example to build probabilistically-generated threedimensional objects.
1
How L-Systems work
L-Systems work by repeatedly replacing the items in a list according to a
fixed set of rewrite rules. Starting from an initial βseedβ list, or axiom, the
list grows in size as the rewrites are repeatedly applied. In this exercise the
items will be characters, so the rewrite problem becomes one of expanding
an axiom string into an output string respresenting the final structure. To
render the structure the characters in the output string are mapped to a
sequence of commands for a turtle - an imaginary device on wheels with a
pen underneath that draws as it moves.
Turtle graphics
A graphics turtle can be thought of as a simple robot which moves around
on a sheet of paper according to a set of basic commands. The robot has a
pen built into it which, in general, can be raised or lowered onto the paper.
If the robot moves whilst the pen is βdownβ the movement will trace a line
on the paper. This exercise uses a simple imaginary robot turtle whose pen
is always in the βdownβ position and which moves around using just three
commands encoded as characters:
βFβ Moves the turtle forward a fixed distance in the direction in which the
turtle is facing.
βLβ Rotates the robot by a given angle anticlockwise (i.e. to the left) on
the spot.
βRβ Rotates the robot by a given angle clockwise (i.e. to the right) on the
spot.
The movement distance will be fixed here arbitrarily at 1 unit; the angle of rotation will be an attribute of the L-System used to generate the
command string.
Rewrite rules
In this exercise each turtle command will be a character (βFβ, βLβ or βRβ)
and a sequence of commands will be a string. An L-System again works with
strings but the characters within the strings can be arbitrary. A rewrite rule
is a mapping from characters to strings and each will be represented as a
(Char, String) pair. A set of rules will be represented as a list of such
pairs (a table), thus:
type Rule = (Char, String)
type Rules = [Rule]
An L-System consists of an axiom string, a list of rewrite rules and an
associated rotation angle used to drive the turtle. In principle any characters
can appear in an axiom string and rewrite rules. However, in order to drive
the turtle the characters in the final output string must be mapped to the
command characters βFβ, βRβ or βLβ in some way (see later).
To help you get started a number of L-Systems have been defined for
you in the skeleton file for this exercise, LSystems.hs. Each is stored as a
triple of the form (angle, axiom, rules):
type LSystem = (Angle, Axiom, Rules)
cross, ..., arrowHead, ... :: LSystem
cross
= (90,
"M-M-M-M",
[(βMβ, "M-M+M+MM-M-M+M"),
(β+β, "+"),
(β-β, "-")
]
)
...
arrowHead
= (60,
"N",
[(βMβ, "N+M+N"),
(βNβ, "M-N-M"),
(β+β, "+"),
(β-β, "-")
]
)
...
As a simple example, suppose we work with the arrowHead L-system.
The axiom is the string βNβ. After the first rewrite the βNβ will be replaced
by the string βM-N-Mβ, using the rewrite rules obtained by calling rules
arrowHead. If the string is rewritten again, each βNβ will be replaced likewise, each βMβ will be replaced by the string βN+M+Nβ and the β+βs and β-βs
will be replaced by themselves. Thus, after a second application of the rules,
the string becomes βN+M+N-M-N-M-N+M+Nβ, and so on.
Notice that there are different rules for rewriting βNβs and βMβs, but
both will be ultimately interpreted as βmoveβ commands for the turtle. The
reason for having multiple move commands is thus not to control the turtle
in more elaborate ways, but to enable more interesting rewrite systems to
be expressed.
If you apply the rules for arrowHead a total of six times the command
string has 1457 characters! If the βMβs and βNβs in this string are both
mapped to turtle command βFβ and β+β and β-β to βLβ and βRβ respectively
the turtle will trace out the picture shown in Figure 1.
Bracketed L-Systems
In the above example the string contains just the characters βMβ, βNβ, β+β,
β-β and the final sequence of turtle commands generated from the final
string defines a continuous linear path, i.e. with no branches. You can
build more elaborate branching structures using bracketed L-Systems, as in
systems bush and tree.
Bracketed systems present an interesting problem because the commands
between a β[β and its matching β]β, corresponds to a branch in the structure. To render this, the turtle will have to draw the bracketed term as if it
were a separate L-System. When we reach the matching β]β we will have to
restore the turtle state to where it was before it hit the β[β. We thus need
a mechanism for βrememberingβ the turtle state throughout the execution
of the bracketed commands, so that we can process the commands after the
β]β starting from the same state. There are two ways to do it; both involve
writing a helper function.
Method 1: By recursion
Think about the problem: when we hit a β[β we have no idea where the
matching β]β is. Therefore, we cannot immediately determine the list of
commands that follow the matching β]β. One way to fix this is to get the
helper function to return not only a list of coloured lines, corresponding to
the trace, but also any remaining commands that have yet to be processed.
When you hit a β]β command you return an empty trace (nothing more to
do) and the list of commands that follow the β]β. When you hit a β[β you
first produce the trace for the commands up to the matching β]β. Then you
process the remaining commands, which you now know as they are returned
along with the trace. The final trace is obtained by appending the two
together.
Note that nested bracketed terms fall out naturally by recursion.
Method 2: Using an explicit stack
The second solution remembers the turtle state explicitly at each β[β command by carrying around a stack of turtle states β an additional argument
to the helper function. When you process a β[β command you push the
current turtle state onto the stack. When you process a β]β command you
need to process the remaining commands (after the β]β) but using the same
turtle state that you had when you hit the matching β[β command. But
this turtle state is precisely what now sits on top of the stack! Therefore,
all you need to do is pop this state from the stack and continue processing
the remaining commands.
Notice again that nested bracketed command sequences present no problems: each time you come across a β[β you push the current turtle state. If
there was already a state on top of the stack that state will now sit one element lower. So, it will take two β]β commands before that state is restored
β exactly what you want.
This solution avoids the need to produce and dismantle pairs (Method
1). However, it requires an extra parameter to be carried with each call to
the helper function.
Note that stacks are easily implemented in Haskell using lists. An item
can be placed on top of the stack (βpushedβ) using the : operator. An item
can be removed from the top of the stack (βpoppedβ) by pattern matching,
e.g. f (top : stack) = β¦
Important: Stacks are arguably the most important data structures in
computer science, precisely because they provide a way of traversing rich
branching structures in a sequential manner. You should implement both
of the above methods as it will help you to understand the role of stacks in
the implementation of recursive functions.
Β Define three functions angle, axiom and rules for extracting the angle, axiom and rules components of an LSystem.
angle :: LSystem -> Float
axiom :: LSystem -> String
rules :: LSystem -> Rules
Β Define a function
lookupChar :: Char -> Rules -> String
that will look up a character in a list of expansion rules, each of which (a
Rule) associates a character with a string. The function should return
the associated string. A precondition is that a binding exists for the
character in the expansion rules. For example:
lookupChar βMβ (rules peanoGosper)
"M+N++N-M--MM-N+"
lookupChar β+β (rules triangle)
"+"
Β Using lookupChar define a function
expandOne :: String -> Rules -> String
that will return the string formed by replacing each character in the given argument string with the string associated with that
character in the given list of expansion rules. For example:
expandOne (axiom triangle) (rules triangle)
"-M+M-M-M+M"
Β Define a function
expand :: String -> Int -> Rules -> String
that will invoke expandOne a specified number of times on a given initial string (axiom) using the given list of expansion rules. For example:
expand (axiom arrowHead) 2 (rules arrowHead)
"N+M+N-M-N-M-N+M+N"
Β Define a function
move :: Command -> Angle -> TurtleState -> TurtleState
that will calculate the new position of a turtle given a
move command (synonymous with [Char]). The move command can
be either to turn left (βLβ) or right (βRβ) or to move forward (βFβ) in
the present direction.
The angle is the one associated with the L-System that was used to
generate the list of commands.
The state of the turtle is given by its current (x, y) co-ordinate and
its orientation, which is measured in degrees, anticlockwise from the
positive x-axis.
The type synonyms referred to above are defined in the template as
follows:
type Vertex = (Float, Float)
type TurtleState = (Vertex, Float)
type Command = Char
type Commands = [Command]
For example:
*LSystems> move βLβ 90 ((100, 100), 90)
((100.0,100.0),180.0)
*LSystems> move βFβ 60 ((50, 50), 60)
((50.5,50.866024),60.0)
*LSystems> move βFβ 45 ((-25, 180), 180)
((-26.0,180.0),180.0)
Β Using move, define two trace functions:
trace1, trace2 :: Commands -> Angle -> Colour -> [ColouredLine]
that implement the two
turtle tracing methods described above. They each take a string of
turtle commands and convert them into a list of lines drawn with
the specified colour that can be subsequently drawn on the screen by
drawLines. The angle is the one associated with the L-System that
was used to generate the list of commands β it is required when invoking move.
The type ColouredLine defines the start and end points of a line in
the Euclidean plane, along with its colour:
type ColouredLine
= (Vertex, Vertex, Colour)
Note: If you are facing angle ΞΈ degrees anticlockwise from 3 oβclock,
then a movement of length 1 would correspond to a displacement of
(cos ΟΞΈ
180 , sin ΟΞΈ
180 ) in (x, y) terms. L means add 90 (degrees) to ΞΈ and R
means subtract 90 from ΞΈ. Initially the turtle is at (0, 0) and has angle
ΞΈ = 90.
In each case you need to keep track of the state of the turtle as it is
moved and rotated; you will therefore need a helper function.
For Method 1 you need to keep track of both the generated trace and
the remaining command sequence. Itβs a little fiddly, as each call to the
helper function now returns a pair of items, so youβll need to pattern
match on the result each time in order to dismantle the pair. If you
get stuck here you might like to get Method 2 working first.
Recall that turtles have a single βmove forwardβ command (βFβ) whilst
the strings generated by the rewrite rules here use two characters βMβ
and βNβ to mean the same thing. Also, the characters β+β and β-β
are used to mean βrotate leftβ and βrotate rightβ respectively whereas
the corresponding turtle commands are βLβ and βRβ. Before a string is
passed to trace, therefore, the characters must be mapped into turtle
commands. Fortunately, you have just built such a function which can
perform such a mapping, i.e. expandOne! To use this to perform the
mapping we need to define a new Rules table that maps characters
to commands, e.g. βMβ and βNβ to βFβ, β+β to βLβ etc., and then call
expandOne accordingly. To save you time, we have provided this in the
skeleton β itβs called commandMap for obvious reasons. For example:
*LSystems> let (a, ax, rs) = arrowHead
*LSystems> let s = expand ax 3 rs
*LSystems> s
"M-N-M+N+M+N+M-N-M-N+M+N-M-N-M-N+M+N-M-N-M+N+M+N+M-N-M"
*LSystems> expandOne s commandMap
"FRFRFLFLFLFLFRFRFRFLFLFRFRFRFRFLFLFRFRFRFLFLFLFLFRFRF"
*LSystems> let (a, ax, rs) = triangle
*LSystems> trace1 (expandOne (expand ax 1 rs) commandMap) a blue
[((0.0,0.0),(1.0,0.0),(0.0,0.0,1.0)),((1.0,0.0),(0.99999994,1.0),
9
(0.0,0.0,1.0)),((0.99999994,1.0),(2.0,1.0),(0.0,0.0,1.0)),
((2.0,1.0),(2.0,0.0),(0.0,0.0,1.0)),((2.0,0.0),(3.0,0.0),
(0.0,0.0,1.0))]
Note the use of a let here to bind identifiers. GHCi remembers these
up until next file (re-)load, or until they are redefined by a subsequent
let. Instead of defining the components of arrowhead and triangle
using a let we could, of course, have used the functions angle, axiom
and rules.
To save typing in long expressions involving expandOne the template
contains the following function:
expandLSystem :: LSystem -> Int -> String
expandLSystem (_, axiom, rs) n
= expandOne (expand axiom n rs) commandMap
This takes the numeric index of a predefined L-System and the number of expansions required and returns the final sequence of turtle
commands. You might find this useful.