Archive | August 2015

Simple Terrain Generation Using Perlin Noise

Perlin noise is a very useful algorithm that can be used for the construction of textures, random worlds in games, and other more graphical applications. I myself am more interested in terrain generation. To start with, the result of a Perlin Noise algorithm execution may look like this:

Perlin Noise

The image, taken from Wikipedia, kind of looks like clouds, in fact, Perlin Noise may be used in the construction of cloud textures. But how does this relate with terrain generation like this?

pygame

Lets first define what we need with terrain generation by looking at a vary famous example.

Basics

In an early blog post, Minecraft’s creator, Notch, described how he used Perlin Noise for terrain generation. This was before the worlds generated in Minecraft were as complex as they are now, without the various biomes, objects, villages, temples, etc. Terrains were just simple hills generated at random.

So we need some way of generating random hill. Some hills may be bigger than others, higher than others, have bigger sloops, etc. The point is that they are different among themselves. The hills are generated using Perlin Noise. If you look at the clouds above as hills, you can see how this algorithm may be used for the objective at hand.

In the image, we clearly see hills, where darker areas are actually valleys, and brighter areas are the hill tops, or vice-versa. Basically, the output is a 2D grid, in which each cell has some value between 0 and some maximum limit. The transition from cell to cell is smooth enough so as to give the sensation of hills without edges.

Simple 3 Level Terrain

Suppose you want to use Perlin Noise to generate terrains. We can have something like hills like it was shown. But If the objective is to have a 2D map, something different may be done. The map should have three height levels. The middle level is interpreted has being ground, where a player or a NPC could walk. The high level could be interpreted has mountains which can’t be access, and the low level can be interpreted as being water, like a lake, river, sea, etc.

To do this a Perlin Noise grid is generated. The values of the grid may range from 0 to 9, for example. It is now asserted that where the grid has a value bellow 3, then that is water. Where there is a value above 7, that’s mountains. Everything else is just ground level.

This may sound like a very duct tape way of generating terrains, but it has pretty good results for generating a simple terrain. This file shows one of the results. The cell with X are mountains, with . are water, and the empty cells are ground level.

You might be wondering, why not just make the range of the values in the grid something from 0 to 2? Like that there is Perlin Noise with three levels.

Well, yes, but using this kind of division will yield terrains where the ground level is bigger then the water and mountain levels. And it looks good.

More Complex Terrains

Obviously, the solution above is too simple and better methods may exist. One immediate concert is that Perlin Noise alone doesn’t generate terrain features such as rivers. We also only see hills and valleys. We don’t see big plains or big mountain ranges. The sizes and slopes of the hills are also never too different.

Perlin Noise alone doesn’t even begin to consider things like animals and vegetation. Or objects such as resources, villages, and other locations.

All these addition must be developed for a specific goal in mind, but Perlin Noise may be used as a primitive for generation.

Plotting using Python and MatplotLib

I’ve put together a small project that generates Perlin Noise grids and displays them on a heat map. The algorithm is implemented in C. It generates a file with some binary information. Then a Python script uses Numpy and Matplotlib to make the heatmap. There is a link here.

The results of one of these execution is something like this:

perlin_hm

So, this is a plot of a Perlin Noise grid, without the three level rules I talked about earlier. To execute this script just run the run.sh command. You can also edit three settings in perlin_gen/settings.h, run make in the perlin_gen directory, and do run.sh again for different grid configurations. The settings state both SIZE_X and SIZE_Y for the actual size of the grid. DEPTH is how deep the grid will be, meaning that if depth is 5, the grid will have values from 0 to 4, if it is 10, it will have values from 0 to 9, and so on.

Fell free to try different settings for different results.

Just another note. The Perlin Noise algorithm implementation in C was not developed by me, but I have no idea where I got the code. I have had it in my drive for a few years and I don’t know the origin anymore. I have tried googling it and found many implementations of Perlin Noise, but not this one. If you know the original author, please tell me.

More

I just want to end with an image of an implementation done with Pygame, the Python library for 2D games. The image, shown bellow and at the top, is a map with a few tiles. The map was created using the three levels method described above. That implementation actually allows some bigger things, like efficient scrolling. I have been wanting to write about that for some time, but never got around to doing it. Also, I am no longer working on anything with Pygame, but it is still a cool thing to show. My next blog post will be about that.

pygame