Fractal Continent Generator

[vither999]

Hey all,

One of my projects this long weekend was to try and generate continental shapes. I didn't succeed, but I figured I'd show it and see if any of you had any helpful criticisms that might point me towards a better algorithm.

---

What I'd like from you!

Hopefully you can help me out with some criticism of the output, or suggestions for places to go to look for ways to improve my process. I can gladly post sample code if you're interested (it's in C++).

---

First, my lovely result images! They aren't that big (maybe 20kb each?) so I advise looking at them full-size.

Image One	Image Two
image_one.png	image_two.png

My thoughts
First of all, these don't really look like continents: there's some basic continental shapes, sure, but the shapes are too 'conservative', if that makes sense. Looking at examples in the real world, most continents have approximately a gazillion random doo-dads that stick out at unusual angles: Italy, Florida, Korea, Japan, Scotland, etc. These shapes are too 'square-ish' or 'conservative' in branching out into the ocean. I'm not happy about that; I mention a couple ideas of what might be able to improve this in the algorithm discussion below.

Second of all, what they DO look like is interesting coastlines. If you zoom in anywhere on the coastline, you'll actually find a fairly good looking random coastline; often there are small islands, tiny peninsulas, and if you grab a chunk of it and scale it with interpolation way up, you get a fairly believable coastline, like this:

image_three.png

Not bad (I might actually use that in my next map).

In all honesty though, I mostly think I've been staring at these kinds of images for way, way too long to give any honest/unbiased opinion on what they do or do not look like. Hence why I'd like your opinion (though I realize that getting an artistic opinion might be better suited to a different forum).

---

The Algorithm As It Stands...
The interesting part!

Similiar to a Koch Snowflake, I start with an initial seed shape, and then union this shape with a number of similar edge child shapes to create a more interesting shape. However, instead of using a regular shape (such as the equilateral triangle in the koch snowflake) I use randomized shapes: random positioning, size, and shape (though only a circle and a square are programmed in right now).

On a more implementation specific level, I use a depth-first draw tree to conserve memory. My initial breadth-first attempt used way too much memory (bottoming out at drawing around 1,000,000 or so shapes) while this depth-first method draws much more (image one has around 16 million shapes, while image two has only 2 million shapes or so).

There are some basic parameters which I can vary as well:

Parameter	Image One	Image Two
Seed Count	5	5
Seed Size	Image Width / 16	Image Width / 32
Iteration Size Factor	70%	70%
Iteration Distance Factor	140%	180%
Random Variance Factor	10%	20%

These factors affect the output shapes, though not the seed locations (which are determined by my random number generator seed), which is why the two images share roughly similar continent locations.

In terms of efficiency, one of my early comments might already reveal that there's still a lot of work to be done; the simpler shape has nearly 8 times as many shapes as the more advanced one. My run time isn't too bad (maybe 4 seconds on this 5 year old laptop), but if I optimize that I could draw more seeds which means I wouldn't have as much clustering (and would get actual continents).

---

Next Steps

• Get some feedback (hopefully you can help with that!)
• Add in more shapes (triangles for example, or have a way to load in vector shapes)
• Play with parameters to try and get more peninsulas and non-conservative coastlines

---

References
Koch Snowflake wiki article
Fractal Terrain wiki article (similar concept)
Paul Bourke's space filling algorithm (inspiration/similar concept)

[vither999]

So, after playing with my code some more, I reached a better set of parameters. Here is my new result (blurred and contrasted to reduce the random dots):
image_three.png

Much better! Note the peninsulas, the coves, the small islands off the coast; altogether, a much better broad view of the coastline.

Now, for what I fixed:

In my previous post, you'll note these two variables: Iteration Size Factor and Random Variance Factor. These defined the following:

1. How big are the children a shape places
2. How random are the children a shape places

All of this based off the size of a parent.

Now, the size of a child is equal to the iteration size factor by the size of the parent plus a gaussian distribution around zero with a standard deviation of the variance by the size of the parent. For those of you familiar with a gaussian distribution, you'll know that 96% of the random variables it produces will be within the two standard deviation of the mean, and roughly 70% within one.

Next, looking at each iteration. If we had an iteration size factor of 1, it would mean that (all things being equally) the program would run forever. Slightly less than equal, for a long time, etc. Variance has no effect on how long it'll run (on average) since it will just as often shrink a child as it will grow a child.

As such, instead of having a high ISF and a low RVF, reverse the two; a small ISF (so the program terminates quickly and doesn't overfill) and a large RVF so the coastline varies dramatically. Hence the fairly neat result up there.

Next step towards making it more realistic: increase the size, and switch from using positions in x and y to using latitude and longitude and put a mercator projection on the whole thing.

[adampjr]

wow. I really like the last output there. Are you going to make the program available when you finish?

[waldronate]

One thing that you might try is to use an ellipse and rectangle rather than circle or square. These shapes give you an additional degree of freedom (aspect ratio), which might well get you more interesting shapes with fewer primitives.

As far as the shapes themselves, they don't seem statistically different than the output of a slice through a fractional Brownian motion (fBm) surface or a simple wavelet noise surface. I suppose that's not surprising because the basic process is the same (add progressively smaller details to a basic shape).

If I understand correctly, you're generating an abstract shape tree and then rasterizing it, which would mean that performance would break down the generation phase and the rendering phase. Are you limited on the placement end or on the rendering end?

[vither999]

wow. I really like the last output there. Are you going to make the program available when you finish?

Yes? I'd make both the source and the program avaliable. I'd want to do a quick UI on top of it (right now it's just a single command in the terminal), but I'd like to release.

One thing that you might try is to use an ellipse and rectangle rather than circle or square. These shapes give you an additional degree of freedom (aspect ratio), which might well get you more interesting shapes with fewer primitives.

Yeah, I think I'll probably do that. My other option was to read in vector shapes and use those, so I could theoretically have a "C" shape or something, but it might be that ellipses and rectangles are enough. Oh, and of course I'd need to have a random rotation of the ellipse and rectangle.

As far as the shapes themselves, they don't seem statistically different than the output of a slice through a fractional Brownian motion (fBm) surface or a simple wavelet noise surface. I suppose that's not surprising because the basic process is the same (add progressively smaller details to a basic shape).

Ehhhhh.... kind of. I'd love to see some kind of mathematical analysis to see if they were similarish, but I suspect the reason they look similar is because the third one was blurred and then thresholded, which removed most of the noise around the edges. If you go back and look at the first two I posted (the unblurred and thresholded ones) you'll see the noise I'm talking about, which doesn't seem like either of those you mentioned.

Now, are these existing methods better? Very good question...

If I understand correctly, you're generating an abstract shape tree and then rasterizing it, which would mean that performance would break down the generation phase and the rendering phase. Are you limited on the placement end or on the rendering end?

Ah, that was my first approach, yes; that approach quickly became too slow to be usable. A faster approach is instead to tie the generation in with the rendering: this means I don't have to save that massive tree, and am instead only looking at a part of it at a time.

i.e.:

DrawFractal( size, location )
   DrawRandomShape( size, location )
   GenerateRandomChildren()
   ForEach Child
      DrawFractal ( Child.size, Child.location )

Similar in concept to a depth-first search tree rather than a breadth-first search tree. In terms of memory use, this means I'm only keeping the size and the location on the stack (three doubles), and at each iteration of draw fractal I create a new shape on the heap, draw it, then delete it, so I don't consume as much memory.

[waldronate]

If you go back and look at the first two I posted (the unblurred and thresholded ones) you'll see the noise I'm talking about, which doesn't seem like either of those you mentioned.

As an example of an fBm surface with similar characteristics to the ones that you posted, consider the attached image. All that blurring and thresholding should have done is effectively reduce the image resolution, not change the characteristics of the surface.

Adding different types of shapes at different levels is a good algorithm. It should be possible to allow arbitrary images as the starting point, as long as the initial image meets the basic requirements for the shapes at that scale. I would expect that using a distance field in the areas to be placed and using that distance field as the guide would be a helpful optimization.

Untitled-1.gif

[vither999]

Ah, yes, that does have a similar noise pattern on the edges. My mistake; I'm still working on understanding the different noise algorithms I've seen.

I'm not sure what you mean by blurring not changing the characteristics of the surface. If we were to take two any two different surfaces and blur/smooth them a large amount, wouldn't they end up looking similar to each other? Or am I not thinking about the characteristics of a surface correctly?

[waldronate]

For a point-sampled image, blurring and thresholding it is roughly equivalent to downsampling the image and then upsampling it to the same resolution. Similarly, a fractal synthesis algorithm that works on the scale/add principle can be stopped at fewer levels of scaling and adding to get an image that's very approximately equal to a lower-resolution image that's upscaled (if that makes any sense).

For something like a basic fBm, the number of octaves of noise required to generate an image without aliasing (that is, that just exactly fills the surface with maximum detail) is approximately log2(imageresolution). That is, for a function with 1/(2^n) scaling, having more than the above number of octaves won't generate meaningful new information, while having a lesser number of octaves will generate versions of the surface that have the same information content as lower-resolution images. The above information is subject to the basic function, of course; the classic cubic-spline-based Perlin function gives nice a smooth lower-resolution images that look an awful lot like a Gaussian-blurred and thresholded image.

[vither999]

Oooh, I understand where you're coming from now. ~head-desk~

---

(TL;DR) Summary:
If I understand correctly, what you're saying holds true for a random fractal such as brownian motion or fractal terrain, but I'm unsure if it holds true for an L-system, which is what (I think) my algorithm actually is.

Most of my knowledge about this comes from wikipedia and you seem to know more on the subject; I don't suppose you've got some good links/books to read on the subject to try and learn more?

Also, after bouncing this around, I can abstract the entire method into a more universal and faster method. Awesome! Exactly what I came here looking for. Thank you.

---

The Long Path to Conclusion:

What you're saying is that a fractal synthesis algorithm that works on scale/add can be stopped at an octave n to produce an image of n^sqrt(k) resolution without aliasing, where k is the number of children that occur at each octave (in the trivial case where we divide into four quadrants, two; if it were instead dividing into nine equal children it'd be different). Understood and agreed. And what you're saying about blurring and thresholding does hold in this case and makes sense (although I'm still trying to wrap my head around if it's true in all cases...).

The crucial difference is that this fractal generation isn't based on scale/add (I think, if I understand you correctly). It's closer related to an L-system; using the terminology on the wiki page, the algorithm is a non-deterministic L-system with a stochastic and context-sensitive grammar. Fractal in a completely different sense, but still fractal.

Although, most of my knowledge about this comes from wikipedia and you seem to know more on the subject; I don't suppose you've got some good links/books to read on the subject to try and learn more?

The system in L-system terminology:

Variables	Squaresize, Circlesize
Constants	Size Factor F; Variance Factor V; Random Gaussian with mean 0, stddev 1, g
Start	Square (0.5), Circle (0.5)
Rules	Squaresize = s (0.5)-> SquareF * s + V * s * g Squaresize = s (0.5) -> CircleF * s + V * s * g Circlesize = s (0.5) -> SquareF * s + V * s * g Circlesize = s (0.5) -> CircleF * s + V * s * g

Also, after formalizing that, I just realized I could abstract the entire method into a more universal method that I could re-use later on that is also probably faster. Awesome! Exactly what I came here looking for.

[waldronate]

You might also want to take a look at GeoControl. Its original version claimed to be L-system based.