Enhancing Procedural Tiles-Maps Generation

Many game developers dream of infinitely large worlds for their hero to explore until they meet a terrible truth: asset creation takes time. But the creation of maps (the gaming term for the world to explore) is also a repetitive process. So the first reaction of developers is to generate most of the repetitive work automatically through specialized algorithms and to append the data with more specific regions. In this article I will briefly discuss a technique to increase the realism of generated 2D maps. A result is shown on Figure 1 where I'm using the assets from Zelda: A Link to the Past as illustration.

2D worlds are often created by assembling small square images (the tiles) to ease creation. You may notice 16x16 tiles on Figure 1 as repetitive portions. For example, there is a tile for plain grass, for grass with flowers, for water and for transition between grass and water. Finally, some tree sprites (much larger than the tiles used) are added on top of the map to add some variation. You may do the same with rocks, buildings, cascades and so on. The idea is to create something that breaks the monotony of traditional procedural generation.

Procedural generation consists of assigning which regions of the map should be grass, which should be water, sand... where should the tree/rock/cascades be put and so on. There are many way to achieve this and the easiest one is the Perlin noise algorithm. It is far from being the best algorithm available but is much easier to understand and implement.

In the Perlin technique, we create a map with harmonic noise and use threshold to identify the various regions. The easiest way to create a harmonic noise map is to first create a 1x1 bitmap with a random pixel value (freely chosen from 0 to 1). We then rescale this 1x1 map to the desired map dimensions, say 512x512 using a bilinear or bicubic algorithm for smooth results. Then, we create a 2x2 random map with values from 0 to ½, rescale it to 512x512 and append it to the first bitmap. We continue with a 4x4 random map from 0 to ¼, rescale it and append it as well. At every step, we double the map size and divide by two the random amplitude. We stop when we reach the final map size (512x512 in our example). The final map is then divided by 1+½+¼+... so that every pixel is contained in the [0,1] range. A 128x128 Perlin noise map example is given on Figure 2.

Once you have the noise map (sometimes it is called a height map), all you have to do is to define some threshold values such that all pixel value below t₁ will be sand, those below t₂ (but greater than t₁) will be grass etc. To have reproducible results I use the histogram of the noise map so I know the percentage of sand, grass and water on my map. You may combine several noise maps such as one for terrain type, another for urban/donjon density, another one for trees etc.

So far there is nothing really new and many game developers have been using this for a long time.

The problem is not how we generate the various regions but how we manage the transitions between them. If you look at Figure 1 you will see corners between grass and water (or sand if you look at the post banner). These transitions are harder to get and most developers do not cope with them. They are actually easy to generate once you have the assets.

The idea is to link the tiles selection algorithm not only to the current pixel type but also on its neighbourhood. For example, a grass pixel should not be treated the same if it has only grass pixels around it or other terrain types. The various cases for two terrains (light grey and dark grey) type are represented on Figure 3. The question mark indicates that we don't care about the pixel type.

The idea is to have one asset for each specific case. These various cases translate to the art assets represented on Figure 4.

For two terrain type there are 32 cases but only 17 are strictly necessary. For example, in our previous black/white example, we have 16 cases for the black terrain junctions. But if we add a ";white"; terrain type, we get a complete set for the two terrains. Moreover, if your game is rotational invariant, you can simplify the various assets by rotating them. Our 17 assets are then simplified to a set of 5 different images for the artist. This is only valid is your game is viewed from top, so it won't work for isometric representations.

In the system I have designed I'm using descriptor files to discriminate the various cases through an algebra of operators. For example, here is one of the files:

There is first a description of the case met (?=any, s=sand, g=grass, ...) followed by a list of asset to use. In this case, there is only one asset available but I may list more than one to let the system randomly choose between several alternatives to add some variation and break the monotony of uniform terrains.

Descriptors should always be applied by their order of specificity. So descriptors with more question marks (less specific) should always be applied after the others. That way, you can write system that won't left pixel unassigned. For example, the last resort for grass should always be:

but we should not rely on that descriptor is something more specific is available (such as the former descriptor). During development, I like to use the extremely general "?" descriptor to find errors and show them with big red square tiles.

Finally, you may add more cases using the corners. This may lead to nicer results but at the price of more assets.