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
Click image for larger version. 

Name:	image_one.png 
Views:	262 
Size:	13.5 KB 
ID:	54942 Click image for larger version. 

Name:	image_two.png 
Views:	204 
Size:	17.6 KB 
ID:	54943

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:

Click image for larger version. 

Name:	image_three.png 
Views:	596 
Size:	13.3 KB 
ID:	54945

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)