Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

:D

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.

Anyone have any ideas?

Thanks. :D

share|improve this question
8  
"would result in just huge amounts of islands" - Or it generates land with lakes in it, if you just swap land/water. –  user744 Oct 19 '10 at 16:42
3  
Even so, you would get a large amount of lakes, in a fairly standard pattern. –  The Communist Duck Oct 19 '10 at 16:45
1  
@Kylotan: Mincraft is infinite in size (well not really, but it is really big... total volume = long.MaxValue x 128 x long.MaxValue). Therefore, it does not generate the whole world in one shot nor does it store the entire map in memory. It generates regions of 16x128x16 blocks asynchronously if they have not been visited before otherwise it loads them from disk. –  arriu Oct 19 '10 at 17:37
2  
@The Communist Duck: Yes this is true, a game like minecraft can get away with using about 2 to 4 bytes of data per block but only a byte needs to be saved after it is no longer visible (one byte describes the type of block, the other bytes describe lighting and other data which can be recalculated later). Here is where it gets interesting, you can use RLE to drastically reduce the stored size down to only a few bytes since the blocks are somewhat coherent, as you mentioned. –  arriu Oct 19 '10 at 20:20
4  
'Really big' is not the same as infinite and you can't use the two terms interchangeably. If you grow the map as and when it is discovered, that is a finite size that grows on demand - quite a different proposition from being infinite. Each bit of growth can be generated as needed. The terrain data in Minecraft is very amenable to trivial compression since there is a high degree of coherence among the data. (eg. RLE as mentioned.) –  Kylotan Oct 20 '10 at 10:34
show 2 more comments

5 Answers 5

up vote 25 down vote accepted

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.)

share|improve this answer
    
You've definitely helped clear up things, thanks. :) But something like a noise function wouldn't be continuous. And AFAICS, if it's continuous I wouldn't receive a 'random' world. Or am I missing something here? –  The Communist Duck Oct 21 '10 at 15:51
    
Sorry for the double comment, but I feel the above is separate from this. When you say 'use the world coordinates for the perlin noise', would this be the same kind of effect as generating the 'huge' sheet of noise but in parts? I feel a bit slow on the uptake today. –  The Communist Duck Oct 21 '10 at 16:17
    
Well, your noise generation certainly can be continuous, and usually is, because you smooth it out. To smooth across boundaries you might need to read across the border a little, but the principle remains the same. If the noise in question needs pseudo-random data, then you generate that from known quantities - ie. a hash of your world coordinates. The outputs then are predictable. –  Kylotan Oct 21 '10 at 16:47
1  
As for randomness, each world can have its own seed value which is used in the calculations. eg. sin(x+seed) instead of sin(x), in my example above. Each different seed will generate a different world. And regarding the huge sheet... I'm not sure what relevance that has. It doesn't matter how much or how little you generate or when you do so. The initial state of the world is defined by the mathematical formula, and you just use that formula to discover that state as and when you need it. –  Kylotan Oct 21 '10 at 16:49
add comment

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

alt text

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.

share|improve this answer
6  
Great visualizations! –  arriu Oct 21 '10 at 19:37
2  
I remember using this tutorial when doing my Masters dissertation on the simulation of natural phenomena. I used the "hill" example to create the sky dome over my 3D world. Excellent introduction to the concept of terrain generation. –  C.McAtackney Nov 17 '10 at 10:04
1  
Crazy, that's awesome! I didn't know anyone ever really used it. –  munificent Nov 26 '10 at 5:06
    
OMG !!! I used this too in a previous project ... the simplest way to generate terrain I've ever come across!!! –  Wardy Apr 8 '13 at 19:30
add comment

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:

first octave details

This article should help: http://freespace.virgin.net/hugo.elias/models/m_perlin.htm

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: http://http.developer.nvidia.com/GPUGems3/gpugems3_ch01.html

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

share|improve this answer
    
The sort of effect I want to achieve is something like a 2d top down of Minecraft's map (not game)...if I just used fewer octaves, wouldn't I still need to generate a massive sheet of perlin noise? Or could I somehow generate just a very, very small amount of it? –  The Communist Duck Oct 21 '10 at 16:16
    
I think you might still be a little confused about how perlin noise works. You can generate chunks of 16x16 blocks individual by sending the function the x and y coordinate offsets for the perlin noise. Notice how the PerlinNoise_2D(float x, float y) function takes in the x and y coordinate. In other words it generates noise for some (x,y) position. Also, generating less octaves is not the same as changing the wavelength of the octaves. Less octaves => Less fine grain detail. Longer wavelength => more zoomed in. –  arriu Oct 21 '10 at 19:34
    
Also, here is an article with code that shows you how to implement zoom/longer wavelenghts: dreamincode.net/forums/topic/66480-perlin-noise –  arriu Oct 21 '10 at 19:36
add comment

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

share|improve this answer
add comment

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).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.