Increasing the probability for similar tiles to generate next to each other

Question

I'm working on a tile map system, which insofar looks like this (green is grass, air is white, stone is grey, and blue is water):

It uses a simple random number generator so that there's a 45% chance of the tile being grass, 30% chance of it being water, and a 25% chance of it being stone.

Is there anyway I can increase the tendency for grass/stone blocks to clump together to form land masses, and make water blocks form oceans (sort of like what could be seen in a game like Minecraft)?

Answer 1

You could use an algorithm that checks near blocks, and varies the probability depending on what is there - but I think it's largely the wrong approach.

What you want to be looking at is fractal noise types - in this case, perlin or simplex noise. If you generate noise, you'll get values from -1 to 1.

http://en.wikipedia.org/wiki/Perlin_noise

You can then adjust your water level by setting the threshhold of what makes water. For the other blocks you can run a second set of noise to switch between rock and grass. (this way you can have large patches of water, but smaller clumps of stone).

getTerrain(x,y) {
if(perlin_noise(x,y) > 0) {
    if(perlin_noise(x * scale,y * scale) > 0) {
        return rock
    } else {
        return dirt
    }
} else {
    return water
}

As I think the scan and toss method is overly complicated and not overly robustly scaleable, I'll suggest another method that I enjoyed:

Lay a grid across your map, breaking the map into large squares.

Generate a random number at each intersection (between 0 and 1 will work for your percentages)

Subdivide by cutting each square into 4 even squares - follow the old lines, and where you find the subdivision lines, generate a random number between the 2 adjacent points, similarly, for the center of the cross, generate a point that lies between the highest and lowest values.

Rinse, and repeat. You will get the initial randomness from the first pass, but the latter passes will give some uniformity Sorry for the psuedo-random numbers:

0-------5  0---3---5 0-1-3-4-5 011233455
|       |  |   |   | | | | | | 012344555
|       |  |   |   | 0-2-4-6-5 002445665
|       |  |   |   | | | | | | 123445666
|       |  2---5---7 2-4-5-7-7 234455777
|       |  |   |   | | | | | | 233455688
|       |  |   |   | 2-3-5-5-9 223455589
|       |  |   |   | | | | | | 233455589
2-------9  2---4---9 2-4-4-5-9 234445579

This works even better for triangles, because you don't have the lost cross-bar when you sub-divide.

Of course, the absolute best result will come from combining these methods - layer upon layer, some techniques will give you great land-masses, others will give you awesome caves, others work for hills, and more will work for water-systems.

Answer 2

Noise is one good solution, as has already been mentioned. Another option is to take a second pass at the data to nudge it toward the layout you want. Gaussian Blur is one of many ways you could achieve this. Doing a pass with that should get you nice "round" blobs of each type.

No matter what method you go with though, one important thing to keep in mind is to store the results of the process in a new location. If you modify the map in place, the portions you have already processed will start to affect the algorithm and you'll end up with some strange patterns.

Answer 3

A relatively simple way of doing this would be to create a number of nuclei at random positions. Draw the Voronoi diagram of these points. Assign an element to each region of the result.

This results in something rather ugly and mechanical looking. Muddy up the borders a bit and you'll be in decent shape.

If you are generating for a large map, you could do this on two levels. Create your initial Voronoi diagram using, say, 20 nuclei, and call each resulting region a nation. Create another diagram using 400 nuclei and call each resulting region a vicarage.

All vicarages totally contained within a nation will have the nation's element. Vicarages partially contained in two or more nations will take one of their enclosing nations' elements at random.

This post deserves a picture, but I am too lazy to provide one.

Answer 4

Polygonal Map Generator would be a good read into creating map with different 'zones' which would give you a better formed maps as well. It's based on voronoi diagrams but I guess this would be a good start into it.

Answer 5

you can do it using this method:

• put all the tiles in unspecified list
• while there is a tile in unspecified list
• begin
• pick one tile from that list
• check neighbors of that tile, and select a type depending on it's neighbors
• remove that tile from unspecified list
• end