Looking for a good world map generation algorithm

Question

I'm working on a Civilization-like game and I'm looking for a good algorithm for generating Earth-like world maps. I've experimented with a few alternatives, but haven't hit on a real winner yet.

One option is to generate a heightmap using Perlin noise and add water at a level so that about 30% of the world is land. While Perlin noise (or similar fractal-based techniques) is frequently used for terrain and is reasonably realistic, it doesn't offer much in the way of control over the number, size and position of the resulting continents, which I'd like to have from a gameplay perspective.

A second option is to start with a randomly positioned one-tile seed (I'm working on a grid of tiles), determine the desired size for the continent and each turn add a tile that is horizontally or vertically adjacent to the existing continent until you've reached the desired size. Repeat for the other continents. This technique is part of the algorithm used in Civilization 4. The problem is that after placing the first few continents, it's possible to pick a starting location that's surrounded by other continents, and thus won't fit the new one. Also, it has a tendency to spawn continents too close together, resulting in something that looks more like a river than continents.

Does anyone happen to know a good algorithm for generating realistic continents on a grid-based map while keeping control over their number and relative sizes?

Answer 1

You can take a look at algos that freeciv uses - http://freeciv.wikia.com/wiki/Main_Page

Answer 2

You could take a cue from nature and modify your second idea. Once you generate your continents (which are all about the same size), get them to randomly move and rotate and collide and deform each other and drift apart from each other. (Note: this may not be the easiest thing ever to implement.)

Answer 3

Just thinking off the cuff here:

Pick some starting points, and assign each a randomly drawn (hoped for) size. You can can maintain a separate size draw for planned continents and planned islands if you want.

Loop over the land elements, and where they are not yet at the planned size add one square. But the fun part is weighing the chance that each neighboring element will be the one. Some suggested thing that might factor in:

1. Distance to the nearest "other" land. Further is better generates wide oceanic spaces. Nearer is better makes narrow channels. You have to decide if you're going to let bits merge as well.
2. Distance from the seed. Nearer is better means compact land masses, farther is better means long strung out bits
3. Number of existing land squares adjacent. Weighting in favor of many adjacent squares gives you smooth coast, preferring few gives you lots of inlets and peninsulas.
4. Presence of "resources" squares nearby? Depends on the game rules, when you generate resource square, and if you want to make it easy.
5. Will you allow bits to approach or join with the poles?
6. ??? don't know what else

Continue until all land masses have reached the planned size or can't grow anymore for some reason.

Notice that diddling the parameter to these weighting factors allows you to tune the kind of world generated , which is a feature I liked about some of the Civs.

This way you'll need to do terrain generation on each bit separately.

Answer 4

I would work the other way around. Instead of starting with ocean and adding land, start with land and add ocean.

Here's a link to an atricle that goes into a lot of detail.

Also, for anything terrain-based, there's always vterrain.

Answer 5

I'd suggest you back up and

1. Think about what makes "good" continents.
2. Write an algorithm that can tell a good continental layout from a bad one.
3. Refine the algorithm so that you can quantify how good a good layout is.

Once you have that in place, you can start to implement an algorithm which should be shaped like this:

• Generate crappy continents and then improve them.

For improvement you can try all sorts of standard optimization tricks, whether it's simulated annealing, genetic programming, or something completely ad hoc, like moving a randomly chosen edge square from whereever it is on the continent to the edge opposite the continent's center of mass. But the key is to be able to write a program that can tell good continents from bad ones. Start out with hand-drawn continents as well as your test continents, until you get something you like.

Answer 6

I'd place fractal terrain according to some layout that you know "works" (e.g. 2x2 grid, diamond, etc, with some jitter) but with a Gaussian distribution damping peaks down towards the edges of the continent centers. Place the water level lower so that is mostly land until you get near the edges.

Answer 7

I think you can use "dynamic programming" style approach here.

Solve small problems first and combine solutions smartly to solve bigger problem.

A1= [elliptical rectangular random ... ]// list of continents with area A1 approx. 
A2= [elliptical rectangular random ... ]// list of continents with area A2 approx.
A3= [elliptical rectangular random ... ]// list of continents with area A3 approx.
...
An= [elliptical rectangular random ... ]// list of continents with area An approx.

// note that elliptical is approximately elliptical in shape and same for the other shapes.

Choose one/more randomly from each of the lists (An).

Now you have control over number and area of continents.

You can use genetic algorithm for positioning them 
as you see "fit" ;)

It will be very good to take a look at some "Graph Layout Algorithms"

• Force Based Algorithms
• Genetic Algorithm for Graph Layout

You can modify these to suit your purpose.

Answer 8

I wrote something similar to what you're after for an automated screensaver-style clone of Civilization 1. For the record I wrote this in VB.net but since you don't mention anything about language or platform in your question I'll keep it abstract.

The "map" specifies the number of continents, continent size variance (eg 1.0 would keep all continents with the same approximate land area, down to 0.1 would allow continents to exist with 1/10th the mass of the largest continent), maximum land area (as a percentage) to generate, and the central land bias. A "seed" is distributed randomly around the map for each continent, weighted towards the centre of the map as per the central bias (eg a low bias produces distributed continents more similar to Earth, where as a high central bias will resemble more of a Pangaea). Then for each iteration of growth, the "seeds" assign land tiles according to a distribution algorithm (more on that later) until a maximum land area has been reached.

The land distribution algorithm can be as precise as you want but I found more interesting results applying various genetic algorithms and rolling the dice. Conway's "Game of Life" is a really easy one to start out with. You'll need to add SOME globally aware logic to avoid things like continents growing into each other but for the most part things take care of themselves. The problem I found with more fractal-based approaches (which was my first inclination) was the results either looked too patterned, or lead to too many scenarios requiring hacky-feeling workaround rules to get a result which still didn't feel dynamic enough. Depending on the algorithm you use, you may want to apply a "blurring" pass over the result to eliminate things like abundant single-square ocean tiles and checkered coastlines. In the event something like a continent being spawned surrounded by several others and having nowhere left to grow, relocate the seed to a new point on the map and continue the growth passes. Yes, it can mean you sometimes end up with more continents than planned, but if it's really something you firmly don't want then another way to help avoid it is bias the growth algorithms so they favour growth in the direction with least proximity to other seeds. At worst (in my opinion anyway), you can flag a series as invalid when a seed has nowhere left to grow and generate a new map. Just make sure you set a maximum number of attempts so if anything unrealistic is specified (like fitting 50 even-weighted continents on a 10x10 board) it doesn't spend forever trying to find a valid solution.

I can't vouch for how Civ etc do it, and of course doesn't cover things like climate, land age etc but by playing around with the seed growth algorithm you can get pretty interesting results that resemble continents, archipelagos etc. You can use the same approach to produce 'organic' looking rivers, mountain ranges etc too.

Answer 9

I haven't actually tried this but it was inspired by David Johnstone's answer regarding tectonic plates. I tried implementing it myself in my old Civ project and when it came to handling collisions I had another idea. Instead of generating tiles directly, each continent consists of nodes. Distribute mass to each node then generate a series of "blob" continents using a 2D metaball approach. Tectonics and continental drift would be ridiculously easy to "fake" simply by moving the nodes around. Depending on how complex you want to go, you could even apply things like currents to handle the node movement and generate mountain ranges that correspond to plate boundaries overlapping. Probably wouldn't add that much to the gameplay side of things, but it could make for an interesting map generation from a purely academic perspective :)

A good explanation of metalballs if you haven't worked with them before: http://www.gamedev.net/reference/programming/features/isometa2d/