2D tile map generation with biomes

Question

I would like to generate a 2D tile map with biomes (let's say : Desert, Grass, Snow). I had a few ideas of algorithms, like putting a few random tiles and then trying to expand, but I have absolutely no idea on how to determine when to expand and when not to. (the tries I've made always end with an infinite recursion)

The result I'm looking for is something like that : (with less biomes)

Is there a simple way to do that?

Answer 1

I tested your problem with a real simple algorithm:

1. randomly set points with a biome type on your field
2. walk over the complete field and set the biome type to the nearest point

example result (X marks the biome point from step 1):

% % % % % % % % % % % % % % % % % % I I I I I I I I I I I I I I 
% % % % % % % % % % % % % % % % % I I I I I I I I I I I I I I I 
% % % % % % % % % % % % % % % % I I I I I I I I I I I I I I I I 
% % % % % % % % % % % % % % % % I I I I I I I I I I I I I I I I 
% % % % % % % % % % % % % % % I I I I I I I I I I I I I I I I I 
% % % % % X % % % % % % % % I I I I I I I I I I I I I I I I I I 
% % % % % % % % % % % % % % I I I I I I I I I I I I I I I I I I 
% % % % % % % % % % % % % I I I I I I I I I I I I I I I I I I I 
O O O O O O O O O O O O O I I I I I I I I I I I I I I I I I I I 
O O O O O O O O O O O O O I I I I I I I I I I I I I I I I I I I 
O O O O O X O O O O O O I I I I I I I I I I I I I I I I I I I I 
O O O O O O O O O O O O I I I I I I I I I I I I I I I I I I I I 
O O O O O O O O O O O O I I I I I I I I I I I I I I I I I I I I 
O O O O O O O O O O O O I I I I I I X I I I I I I I I I I I I I 
O O O O O O O O O O O I I I I I I I I I I I I I I I I I I I I + 
O O O O O O O O O O O I I I I I I I I I I I I I I I I I I I + + 
O O O O O O O O O O O I I I I I I I I I I I I I I I I I + + + + 
O O O O O O O O O O O I I I I I I I I I I I I I I I I + + + + + 
O O O O O O O O O O O I I I I I I I I I I I I I I + + + + + + + 
O O O O O O O O O O I I I I I I I I I I I I I + + + + + + + + + 
O O O O O O O O O O I I I I I I I I I I I I + + + + + + + + + + 
O O O O O O O O O O I I I I I I I I I I + + + + + + + + + + + + 
O O O O O O O O O O I I I I I I I I + + + + + + + + + + + + + + 
O O O O O O O O O I I I I I I I I + + + + + + + + + + + + + + + 
O O O O O O O O O I I I I I I + + + + + + + + + + + + + + + + + 
O O O O O O O O O I I I I I + + + + + + + + + + + + + + + + + + 
O O O O O O O O O I I I + + + + + + + + + + + + + + X + + + + + 
O O O O O O O O I I + + + + + + + + + + + + + + + + + + + + + + 
O O O O O O O O I + + + + + + + + + + + + + + + + + + + + + + + 
O O O O O O O O + + + + + + + + + + + + + + + + + + + + + + + + 
O O O O O O O + + + + + + + + + + + + + + + + + + + + + + + + + 
O O O O O O + + + + + + + + + + + + + + + + + + + + + + + + + + 

I used Java for the solution but it shouldn't be to hard to convert it to C/C++

// a simple 'struct' to hold some vars
class BiomeInfo {
    char type;
    int x;
    int y;
}

next we set up some points. You can add random to this task and also add any type multiple times

    char[][] field = new field[32][32];

    biomeInfo[0].type = '#';
    biomeInfo[0].x = 5;
    biomeInfo[0].y = 5;

    biomeInfo[1].type = 'O';
    biomeInfo[1].x = 10;
    biomeInfo[1].y = 5;

    biomeInfo[2].type = 'I';
    biomeInfo[2].x = 13;
    biomeInfo[2].y = 18;

    biomeInfo[3].type = '+';
    biomeInfo[3].x = 26;
    biomeInfo[3].y = 26;

next: walk over the field

    for (int i = 0; i < field.length; i++) {
        for (int j = 0; j < field[0].length; j++) {
            char nearest = '.'; // value here doesn't matter
            int dist = Integer.MAX_VALUE; // select a big number

            // walk over each biomeInfo
            for (int z = 0; z < biomeInfo.length; z++) {

                // calculate the difference in x and y direction
                int xdiff = biomeInfo[z].x - i;
                int ydiff = biomeInfo[z].y - j;

                // calculate euclidean distance, sqrt is not needed
                // because we only compare and do not need the real value
                int cdist = xdiff*xdiff + ydiff*ydiff;

                // is the current distance smaller than the old distance?
                // if yes, take this biome
                if (cdist < dist) {
                    nearest = biomeInfo[z].type;
                    dist = cdist;
                }
            }

            // set the field to the nearest biome       
            field[i][j] = nearest;

            // you can mark the biome point with this code
            // if (dist == 0) {
            //    field[i][j] = 'X';
            // }
        }
    }

and finally print field:

    for (int i = 0; i < field.length; i++) {
        for (int j = 0; j < field[0].length; j++) {
            System.out.printf("%c ", field[i][j]);
        }
        System.out.printf("%n"); // %n means newline
    }
    System.out.printf("%n");

Answer 2

The lines on your picture go under the name of Voronoi diagram. Wikipedia page mentions a few algorithms for finding that, or the dual Delaunay triangulation. A simple way would be the following: for each control point, draw median lines between that point and each other control point, order these lines by the angle to Ox axis, and then traverse them in that order to construct a polygon around the control point.

After you have that, assigning the types to tiles should be easy. You can just look at the centers of the tiles and find which face of the diagram it belongs to. If you need better precision, for each tile, you can calculate the area of intersection with each face, and pick the one with the largest area.