Looking for a good world map generation algorithm [closed]

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.)

Edit: Here's another way of doing it, complete with an implementation — Polygonal Map Generation for Games.

I've created something similar to your first image in JavaScript. It's not super sophisticated but it works :

http://jsfiddle.net/AyexeM/zMZ9y/

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>Untitled Document</title>

<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.7.2/jquery.min.js"></script>
<style type="text/css">
    #stage{
        font-family: Courier New, monospace;
    }
    span{
        display: none;
    }
    .tile{
        float:left;
        height:10px;
        width:10px;
    }
    .water{
        background-color: #55F;
    }
    .earth{
        background-color: #273;
    }
</style>
</head>

<body>


<div id="stage">

</div>

<script type="text/javascript">

var tileArray = new Array();
var probabilityModifier = 0;
var mapWidth=135;
var mapheight=65;
var tileSize=10;

var landMassAmount=2; // scale of 1 to 5
var landMassSize=3; // scale of 1 to 5


$('#stage').css('width',(mapWidth*tileSize)+'px');


for (var i = 0; i < mapWidth*mapheight; i++) {

    var probability = 0;
    var probabilityModifier = 0;

    if (i<(mapWidth*2)||i%mapWidth<2||i%mapWidth>(mapWidth-3)||i>(mapWidth*mapheight)-((mapWidth*2)+1)){

        // make the edges of the map water
        probability=0;
    }
    else {

        probability = 15 + landMassAmount;

        if (i>(mapWidth*2)+2){

            // Conform the tile upwards and to the left to its surroundings 
            var conformity =
                (tileArray[i-mapWidth-1]==(tileArray[i-(mapWidth*2)-1]))+
                (tileArray[i-mapWidth-1]==(tileArray[i-mapWidth]))+
                (tileArray[i-mapWidth-1]==(tileArray[i-1]))+
                (tileArray[i-mapWidth-1]==(tileArray[i-mapWidth-2]));

            if (conformity<2)
            {
                tileArray[i-mapWidth-1]=!tileArray[i-mapWidth-1];
            }
        }

        // get the probability of what type of tile this would be based on its surroundings 
        probabilityModifier = (tileArray[i-1]+tileArray[i-mapWidth]+tileArray[i-mapWidth+1])*(19+(landMassSize*1.4));
    }

    rndm=(Math.random()*101);
    tileArray[i]=(rndm<(probability+probabilityModifier));

}

for (var i = 0; i < tileArray.length; i++) {
    if (tileArray[i]){
        $('#stage').append('<div class="tile earth '+i+'"> </div>');
    }
    else{
        $('#stage').append('<div class="tile water '+i+'"> </div>');
    }
}

</script>

</body>
</html>

I'd suggest you back up and

Think about what makes "good" continents.
Write an algorithm that can tell a good continental layout from a bad one.
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.

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.

Polygonal map generation article describe step by step map generation unsing Voronoi polygons.

This guy give also all source codes. It's Flash (ActionScript 3 / ECMAScript) but transposable to any other object oriented language

Or try to use algorithms implemented in some fractal environement softwares like TerraJ

Looking for a good world map generation algorithm [closed]

Related

Recent Posts