Random Placement of Objects on a Tilemap

Question

I have read many topics on random world generation on this site and others, and I roughly understand most of it. What I can't see is how to randomly place objects on the generated tile map I get. Say I want to generate a forest. How would I go about doing this? I have tried studying other people's code. I delved into Notch's Minicraft to look at how it generates its random worlds.

I have identified this part of the code that generates trees for example.

for (int i = 0; i < w * h / 400; i++) {
        int x = random.nextInt(w);
        int y = random.nextInt(h);
        for (int j = 0; j < 200; j++) {
            int xx = x + random.nextInt(15) - random.nextInt(15);
            int yy = y + random.nextInt(15) - random.nextInt(15);
            if (xx >= 0 && yy >= 0 && xx < w && yy < h) {
                if (map[xx + yy * w] == Tile.grass.id) {
                    map[xx + yy * w] = Tile.tree.id;
                }
            }
        }
    }

However, this just confuses me. I need to be able to see how this code translates into spread out trees. There is also code for generating the desert.

for (int i = 0; i < w * h / 2800; i++) {
        int xs = random.nextInt(w);
        int ys = random.nextInt(h);
        for (int k = 0; k < 10; k++) {
            int x = xs + random.nextInt(21) - 10;
            int y = ys + random.nextInt(21) - 10;
            for (int j = 0; j < 100; j++) {
                int xo = x + random.nextInt(5) - random.nextInt(5);
                int yo = y + random.nextInt(5) - random.nextInt(5);
                for (int yy = yo - 1; yy <= yo + 1; yy++)
                    for (int xx = xo - 1; xx <= xo + 1; xx++)
                        if (xx >= 0 && yy >= 0 && xx < w && yy < h) {
                            if (map[xx + yy * w] == Tile.grass.id) {
                                map[xx + yy * w] = Tile.sand.id;
                            }
                        }
            }
        }
    }

Is this just way over my head or is there some kind of algorithm that I'm missing here?

Answer 1

Both of those pieces of code appear to pick a random location (xx,yy in the first example and x,y in the second), then try to change grass to something else near that location.

There are lots of other algorithms, although most are more complicated than the ones you posted. I can't answer whether they're over your head; I don't know what's in your head ;-)

I usually like to use noise functions. I have written a tutorial on noise functions. I also like to start with the simplest possible thing, and change it only if it's not satisfactory.

Pink Noise

The first question you have is about placing forests, deserts, grasslands, etc.

You can use some sort of random noise to generate attributes that determine whether some land is grass, forest, desert, etc.

For example, you could use Perlin Noise to generate a value from 0.0 to 1.0, and then decide that the range 0.0–0.3 is desert, 0.3–0.7 is grass, and 0.7–1.0 is forest. That's fairly simple, once you have a Perlin Noise library.

A more involved approach would be to generate "realistic" attributes such as temperature and moisture using a noise function, and then use those attributes to decide whether something is a forest. You might decide that forests occur when moisture is between 0.2 and 0.8, and temperature is between 15°C and 30°C. See Whittaker Diagrams for more on this; it gives you different types of forests and other areas.

Another approach would be to generate those attributes using something other than a noise function. For example, in this project I used “distance from coast” to generate elevation, which then turned into temperature. I used “distance from river” to generate moisture. I then used temperature and moisture to look up the biomes on the Whittaker diagram.

These systems typically follow “pink noise”. There are large areas with one type of biome or another. There's a small amount of variation within these areas.

Blue Noise

The second question you may have is to place objects such as trees in a forest zone, or rocks in a desert zone. “Blue noise” is used when you want semi-even spacing of objects.

The simplest approach is to go through each tile in the forest zone and place a tree with some probability. Something like: if random() < 0.3 then place tree. It's really simple, and it's worth starting with this. However, it often yields clumps of trees that you may not want.

To fix clumping, you can pick a random point and place your tree if it's in a forest zone and there are no other trees within a certain radius. See this article for an explanation and sample code.

There are more complicated approaches, using things like Wang Tiles. I liked the video from this project. However, I haven't tried implementing it.