You are to write a program that generates fractals using
what are known as Lindenmayer systems, or L-systems. The concept
of an L-system was introduced in the 1960's by Aristid Lindenmayer
as a simple model of the growth of plants. It is based on the idea
of a formal grammar, as used by linguists to analyze the
structure of natural languages (and by computer scientists to specify
the structure of programming languages). For more details on
the theory behind L-systems, consult
http://en.wikipedia.org/wiki/L-system
.
The best way to understand the version of L-system we will be using is to consider a simple example (this is essentially Lindenmayer's original model for the growth of algae, although we will cast it in more familiar terms). Let the symbol B represent a baby bunny, and let the symbol A stand for an adult rabbit. If we assume that an adult rabbit produces one baby bunny each month, and that it takes a baby one month to mature into an adult, then we could model the growth of a population of rabbits with the following rules:
- A --> AB
- B --> A
The arrow (-->) is read as "produces" or "develops into" (after one month), so the first rule says that an adult rabbit develops into an adult (itself) and a baby after one month, while a baby bunny develops into an adult after one month. We are also assuming that these (idealized) rabbits are immortal; as you can see in the interpretation of the rules, each rabbit present in one month will continue into the next (accompanied by an ever-increasing crowd of relatives...).
In addition to a set of symbols and a list of rules, an L-system needs a starting point, known as the "axiom". For our rabbits, suppose we start with a single baby bunny, B, as our axiom. Given a starting point, an L-system develops in a series of stages (months, in our case). At each stage, every member in the current population (represented as a string of symbols) is replaced by the right-hand-side of the rule for that symbol; if there is no rule for a given symbol, it remains unchanged. For example, here are the first few stages of the growth of our rabbit population:
| Month | Population |
| 0 | B |
| 1 | A |
| 2 | AB |
| 3 | ABA |
| 4 | ABAAB |
| 5 | ABAABABA |
| 6 | ABAABABAABAAB |
Looking at the size of the rabbit population in each month reveals a familiar sequence: 1, 1, 2, 3, 5, 8, 13, .... Indeed, we have reproduced the original model of rabbit population growth studied by Leonardo of Pisa (son of Bonacci, hence "Fibonacci") about 800 years ago, although of course he didn't phrase it in terms of L-systems.
To summarize, an L-system is specified by giving a list of rules describing how the symbols develop in each stage, plus an axiom which serves as the starting string of symbols. We will only consider deterministic L-systems, where there is at most one rule for each symbol, although the generalization to stochastic L-systems (where one of several rules is chosen at random for each symbol) is also very interesting.
To use an L-system to generate fractals, we will apply a graphical
interpretation to some of the generated symbols. The graphics will be in
the form of commands to a "turtle" -- an imaginary animal that crawls
around leaving trails on the screen. Our turtle will be provided by the
Turtle class, which has the following methods:
- init(): resets the turtle on a blank screen, heading to the right (in the positive x direction)
- drawForward(): moves the turtle one unit forward and leaves a trail
- moveForward(): moves the turtle one unit forward but does not leave a trail
- left(): turns the turtle counter-clockwise by the angle delta (see below)
- right(): turns the turtle clockwise by the angle delta (see below)
- setDelta(float delta): sets the turtle's basic turning angle to delta, measured in degrees; the default value for a newly-constructed turtle is 90 degrees -- usually you will want to call setDelta immediately after constructing the turtle
- display(): shows a window with a visual representation of the trail left by the turtle; it will be scaled and centered to fit in the window
You will need to write a function called interpret that
takes a sequence of symbols (as generated by running the L-system to a given
stage) and gives the appropriate sequence of commands to the turtle. You
should follow the conventions of the program FRACTINT
(http://spanky.triumf.ca/www/fractint/fractint.html)
which interprets F as drawForward, G as
moveForward, + as right, and - as
left; any other character is ignored. For example, if the
sequence of symbols were stored in a String, you could write the following:
public void interpret(String sequence, delta)
{
Turtle t = new Turtle();
t.setDelta(delta);
t.init();
for (int i = 0; i < sequence.length(); i++) {
switch(sequence.charAt(i)) {
case 'F':
t.drawForward();
break;
case 'G':
t.moveForward();
break;
case '+':
t.right();
break;
case '-':
t.left();
break;
default:
// Do nothing
break;
}
}
t.display();
}
Given this function, calling interpret("F-F++F-F", 60)
results in the following display:
This is the first stage of part of the Koch snowflake curve. The entire curve may be generated using the axiom F++F++F and the single rule F --> F-F++F-F; here is the result of applying this rule for 3 stages:
As a final example, the axiom FX together with the rules F --> (nothing), X --> -FX++FY-, and Y --> +FX--FY+ produce the "dragon curve". Here it is, generated to 15 stages (resulting in about 200,000 symbols) and interpreted with an angle of 45 degrees:
Of course, since this project deals with linked lists, you won't have the sequence of symbols stored in a String, so you can't use the above version of interpret without modification. Why don't we want to use a String? Because many L-systems produce sequences that grow exponentially in the number of stages, so we may well be generating sequences of millions of symbols. Although it isn't a problem just to store millions of characters in a Java String, it is a problem to replace one of those characters by the several that might take its place when generating the next stage of a sequence -- besides the fact that Java String objects are immutable, so you have to make a copy of the entire String to change any part of it, there is the simple problem for any data structure using contiguous storage that to insert several things in place of one you have to shift everything else to make room! These problems are solved if we switch to a linked-list representation of the sequence of symbols: it is an easy matter to splice in a replacement set of nodes each time a symbol needs to be substituted by the right-hand-side of its corresponding rule.
Input file format: The input to the program will be a text file giving the following information on successive lines:
- The axiom of the L-system
- The number of rules in the L-system
- The rules of the L-system, each on two lines: the first line will give the symbol on the left-hand-side of the rule, and the second line will give the (possibly empty) sequence of replacement symbols on the right-hand-side of the rule
- The number of stages to generate
- The angle delta to assign to the turtle
All of the symbols used in rules will be from the ASCII character set, so you can rely on their code values being less than 128 (in case you want to use them as array indices, for example).
For example, here is a file describing the dragon curve shown above
(this is the file dragon.txt in the folder
I:\CSC122x\public\LSystem):
FX
3
F
X
-FX++FY-
Y
+FX--FY+
15
45
You should use the Infile class from the previous
projects to read the lines of the file. To convert a string s to an
int, use the static method Integer.parseInt(s); there
are similar methods for the other primitive types (for example,
Float.parseFloat(s)).
The LSystem project:
- The project should consist of at least four classes – Driver, LSystem, Turtle, and Infile.
- Driver (client) – Creates an instance of LSystem and invokes appropriate methods from it.
- LSystem (server and client) – Provides methods to read a system description from an Infile, generate the appropriate number of stages of the system, and interpret the result by giving a sequence of Turtle commands. The sequences of symbols should be stored using the Java LinkedList class.
- Turtle (server) - This class will be given to you in the LSystem folder, and is described above.
- Infile (server) – This class will be given to you in the LSystem folder, and is the same as in previous projects.
- The provided files can be copied from I:\csc122x\public\LSystem
- Implement the project using the test-driven implementation strategy: first build a test system and stubbed implementation of each class.
Standards:
Your project should be well-written, neatly-formatted, modular, and well-documented.
Grading:
- Reading the L-system description (20 pts)
- Generating the stages of the L-system (40 points)
- Interpreting the resulting sequence of symbols (20 points)
- Documentation and style (20 points)
