Fractal Continent Generator
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! :D They aren't that big (maybe 20kb each?) so I advise looking at them full-size.
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:
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:
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.
||Image Width / 16
||Image Width / 32
|Iteration Size Factor
|Iteration Distance Factor
|Random Variance Factor
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).
- 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
Koch Snowflake wiki article
Fractal Terrain wiki article (similar concept)
Paul Bourke's space filling algorithm (inspiration/similar concept)
Fractal Continent Generator Update
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):
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.