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

; by Heinz-Otto Peitgen, Hartmut Jürgens, Dietmar Saupe be read.Chaos and FractalsThis 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

mustbe 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

#10was supposed to be signed 'gg'. I need to go drink more caffeine...