Huge procedurally generated 'wilderness' worlds

Question

I'm sure you all know of games like Dwarf Fortress - massive, procedural generated wilderness and land. Something like this, taken from this very useful article.

However, I was wondering how I could apply this to a much larger scale; the scale of Minecraft comes to mind (isn't that something like 8x the size of the Earth's surface?). Pseudo-infinite, I think the best term would be.

The article talks about fractal perlin noise. I am no way an expert on it, but I get the general idea (it's some kind of randomly generated noise which is semi-coherent, so not just random pixel values).

I could just define regions X by X in size, add some region loading type stuff, and have one bit of noise generating a region. But this would result in just huge amounts of islands.

On the other extreme, I don't think I can really generate a supermassive sheet of perlin noise. And it would just be one big island, I think.

I am pretty sure Perlin noise, or some noise, would be the answer in some way. I mean, the map is really nice looking. And you could replace the ascii with tiles, and get something very nice looking.

Answer 1

I think I better understand what you are asking now.

Noise is not random - it's random-looking but is completely based on a mathematical formula and is repeatable. All the information is encoded in the formula. This means that you can have a formula that potentially covers an infinite area, and just use the formula on the coordinates of the area you need. When you need an adjacent area, you just re-use the formula on the new coordinates, and since the formula yields continuous values, the areas will join seamlessly.

Here's a simplified example, using sine instead of perlin noise for the height generation, and imagining the world is infinite in the X axis but only 1 unit high in the Y and Z axes.

Formula is: height(x,y) = sin(x/20)

The game starts, and we generate heights for the nearby area, ie. (0,0) to (9,0):

[0.0, 0.05, 0.10, 0.15, 0.20, 0.25, 0.30, 0.34, 0.39, 0.43]

We have a hill, rising up towards the right. Let's say we walk to the end of it and need to generate the values from (10,0 to 19,0) now:

[0.48, 0.52, 0.56, 0.61, 0.64, 0.68, 0.72, 0.75, 0.78, 0.81]

Notice how the hill keeps rising steadily, and that the value at (10,0) follows on nicely from the one at (9,0). This is because the sine function is continuous, which basically means that if you feed it 2 adjacent numbers in, you'll get 2 adjacent results out - for a certain definition of adjacent. So if you use your world coordinates as the parameters to the function that defines your world, you will get a continuous landscape that fits together no matter how much or little of it you generate at once. When you generate new parts, they will flow on from the existing parts automatically, because the heights are already pre-determined.

If the world isn't going to change, you don't even need to store anything, since you can calculate exactly what the height is at any given point from the formula. Obviously with something like Minecraft the world is totally deformable so you just save each chunk as you create it. Given that there is a high degree of coherence between adjacent chunks (ie. if 1 block is grass, it's more likely than not that the block next to it will be grass too) you can compress the data very efficiently - run length encoding would work well, but then so would almost any standard compression algorithm.

Whereas I have talked about height as the most obvious value, you can use the same system to generate any characteristic you want. Use a mathematical function with continuous properties and where the inputs are your world coordinates and that can decide the presence of landmarks, mineral deposits, spawn points, whatever you like. (Obviously the values in one formula may affect another - no point placing a coal deposit in mid-air, so you generate the world height map and then only calculate coal possibilities for the blocks that are far enough below ground.)

Answer 2

This tutorial I wrote years ago might give you something like what you want:

If you do the island modification in the last step, it tends towards a single landmass that doesn't reach the edge of the map.

Answer 3

To create a large island you do not need to generate it all at once. I would build regions asynchronously as you visit them.

Instead of using a mask to create the island as the article describes, one thing you can do is play with the perlin noise octave wavelengths to achieve the look you are going for. Usually, the first octave describes the general shape of the terrain. All octaves after it simply add more fine grain detail. Therefore, play with the wavelength of the first octave to control how large your landmasses will be. If you want the landmass to be in the center you can simply reduce the height map by an increasing amount as you move away from the center and then normalize the noise. For instance imagine combining these two to create your island:

This article should help: Perlin Noise.

If you want to learn about infinite 3D worlds and about various tricks you can use to change the appearance of the terrain through playing with the noise input and output, have a look at this article: Generating Complex Procedural Terrains Using the GPU.

It may be a little bit of a difficult read if you are not familiar with the graphics pipeline and shader programming.

Answer 4

Some useful links for you about auto world generation:

http://pcg.wikidot.com/ - Procedural Content Generation

http://www-cs-students.stanford.edu/~amitp/gameprog.html#tiles - Amit's Building Worlds set of algorithms

Answer 5

Perlin noise and friends are a good starting point but you probably want to take it a step further. Most of the popular noise-based generators will give you a fairly uninteresting results. In order to make terrain realistic, you want to take a look at the algorithms emulating erosion effects. One of the most advanced game-ish world simulators out there - Dwarf Fortress - does erosion simulation as one of the world-building steps.

One of the pretty cool solutions I've seen was described in the "Advanced Particle Deposition" article in the Game Programming Gems 7. There are many others available on the Internet so there's a lot of resources to draw from (e.g. 1 or 2).