I just finally got my copy of Mandelbrot’s book on fractals. In his discussion of curve fractals (that is, fractals formed from an unbroken line, isomorphic to the interval (0,1)), he describes them in terms of shorelines rather than borders. I’ve got to admit
that his metaphor is better than mine, and I’ll adopt it for this post.
In my last post, I discussed the idea of how a border (or, better, a shoreline) has
a kind of fractal structure. It’s jagged, and the jags themselves have jagged edges, and *those* jags have jagged edges, and so on. Today, I’m going to show a bit of how to
generate curve fractals with that kind of structure.
The canonical example of a fractal curve is the Koch curve. To generate the canonical Koch curve,
you take a line segment, divide it into three sections, and replace the middle with
the upper two edges of an equilateral triangle. Then you repeat that process for each of
the straight edges in the resulting figure. Over to the side are illustrations of the Koch
curve after 1, 2, 3, and 4 iterations.
This kind of curve obviously isn’t ideal as a model of something like a coastline. It’s perfectly regular, which natural structures like coastlines aren’t. But it’s a starting point; we can eventually work irregularity and randomness into these kinds of curves. But
for now, we’ll stick with the simple ones.
The Koch curve can be described in terms of a simple grammar, which guides
a recursive rewrite system. (In fact, that’s how I implemented the code to generate
the diagrams for this post: I’ve got a simple rewrite system, and I’m feeding the
results into a turtle drawing program which traces out the curve.)
In a rewrite system for fractal curves, you start with a grammar symbol called
the initiator, and then specify a rule system called the generator. The generator is a set of replacement rules. Each iteration of the algorithm, you scan through the current state of the curve (starting with the initiator on step 0), and
each time that you encounter a symbol which is the left hand side of a rule in the generator, you replace that symbol with the right hand side of the corresponding rule.
For example, the Koch curve is specified by:
- Initiator: line
- Generator: line → line,left(60),line,right(120),line,left(60),line
You can also draw the generator graphically, as the following:
Playing with the rewrite method, you can get some really interesting curves, which
often seem as if they defy the simplicity of their definition. For example,
take the same initiator as the koch curve, but instead of using a triangle, generate
a square: line → line,left(90),line,right(90),line,right(90),line,left(90),line;
visually, the replacement for a line is the segment on the right. Now look at what
you get after 4 and 5 iterations:
Now, did anyone out there actually expect that trivial generator to produce
an intricate cross-lace pattern?
That last one is cheating a bit, because the curve crosses itself; proper curve fractals don’t do that. But it’s cool anyway, so I wanted to show it to you. Even staying
within the non-crossing curves, there are numerous variations on the Koch curve that
are interesting.
For example, look at this generator: “line→line,left(30),line,right(90),line,left(90),line,right(30),line”, shown graphically to the left. Run it for 4 iterations, and you get a curve like below. Now, that’s starting to look rather a lot like a coastline, isn’t it? It’s still
completely regular, but it’s really starting to look quite different, and interestingly
real.
Throw in a little bit of randomness, and the regularity starts to fade out, even though the generation process remains regular. You get bays and inlets, promontories, etc., all of
the features of a real shoreline. The following two graphs are samples from the same generator as above, but randomly varying the length of the straight lines when a segment
is replaced. The segments that replace the straight are always shorter than the segment they replace, but the ratio of segment length to replacement length is randomized.
Thank you for your excellent posts on fractals.
For further exploration of this topic, I strongly suggest that Chaos and Fractals; by Heinz-Otto Peitgen, Hartmut Jürgens, Dietmar Saupe be read.
This work received the American Book Award in 1992. It is easily understood with only a high school mathematics background.
It is available in most university libraries in either the 1st or 2nd editions or through amazon.com.
I guess “Logo” would be a good language for this sort of thing.
I guess “Logo” would be a good language for this sort of thing.
Indeed. This is from over a decade ago, and written for MSWLogo, but should be easy to port to any other logo system:
http://web.archive.org/web/19970514205726/www.mathcs.carleton.edu/students/martind/fractal.lgo.txt
Also, these rewriting systems usually go under the name “Lindenmayer system” or L-system.
For the “square-Koch” shape: it doesn’t really *cross* itself; just touches at the corners. Changing the angles by epsilon would make a shape with no crossings — just change 90 to 90-e.
As a total nerd, I feel duty bound to report that this sort of math is of practical importance to players of fantasy role-playing games. There’s nothing like a fractal generator to develop one’s own worlds!
For the curious, a list of commercial and non-commercial world generators:
http://dmoz.org/Games/Roleplaying/World_Building/Map_Making/Tools/World_Generators/
Mandelbrot’s most recent book as about using fractals in financial markets. It is very interesting. I am hoping to generate a few stock charts using fractals…if I can ever find the time to figure them out. This blog series about fractals, as usual, is great!
to gg:
I recently found out that the only code from Civilization 3 that they didn’t rewrite for Civ 4 was the fractal terrain generation code I wrote.
I wasn’t sure whether to be flattered (because they still thought it was great code), or upset (because it was so incomprehensible that no one dared touch it). 🙂
(Honestly, I think it was just the word “fractal” that scared them off.)
You wrote code for Civ? Awesome, Chris. That’s so cool. ^_^
Ruby Quiz 125 asked people to develop Ruby programs to draw that square cross-lace fractal. If you want to see other similar fractals, some solutions (like mine) allowed alternate rules.
#7: “(Honestly, I think it was just the word “fractal” that scared them off.)”
It’s one of the great ironies of fractal geometry that the topic scares some people off. I’m guessing that lots of people look at the fractal images and assume that the math behind it must be horribly complicated, when in fact the whole point is that you can get complicated structures from relatively simple rules.
“I wasn’t sure whether to be flattered (because they still thought it was great code), or upset (because it was so incomprehensible that no one dared touch it). :)”
Well, having just finished a game of Civ 4 this morning, I would lean towards your first option: the terrain is great! Of course, this doesn’t discount your second option, which may be equally true! 🙂
Whoops, comment #7 was supposed to be signed ‘gg’. Darn Firefox update seems to have wiped some of my autofills…
Double whoops: comment #10 was supposed to be signed ‘gg’. I need to go drink more caffeine…