How does MC generate chunks?

I've been trying to solve this for awhile, and just before I get started explaining this a little more, let me add:
1. yes I've reviewed the FAQ's
2. yes I have googled this and variants of this question.

Let me explain my question a little better. After reviewing perlin simplex noise and other interpolated noise functions, I understand how the general layout of noise is created:

1st, define a domain (we'll use a one dimensional domain right now)
say from 0<=x<= L

2nd, define nodal points x_n this domain where:
n = 3 + 2*(wavenumber - 1);

3rd, define height values at these nodal points according to:
y_n = random number_n.

4th, interpolate these nodes across a finer set of x data points, say 100, where the spacing between the nodes is: ∆x = 100/n . Use your favorite interpolating function for this; cubic, linear, quartic, etc;

If you do this, you'll end up with something like:

5th, repeat steps 2-4 with a different n and/or different type of interpolation.
6th, add all the resulting functions and you get something like:

You can also add different weights to different frequencies to change the 'fuzziness' of the terrain, or set bounds on the max value of your random function to express things such as mountains or plains.

My question is, given that MC uses a similar process to create terrain, how does that translate into chunks? is the entire map one domain and the chunks just access the height profiles at their intervals? or does MC somehow 'stitch' chunks together from different interpolated domains and if so, mathematically how does it do this?

I'm currently developing a real world geology mod for SMP (don't care if its difficult, I like taking on challenging projects), and its important that I know how the terrain is made in MC.

 

I always thought minecraft used value noise with turbulence, and they incorrectly called it perlin noise.

 

i guess thats possible. Id still like to know how the code bridges the world between the noise function and chunk generation

 

I'm not an expert on the subject, but I'm pretty sure Value noise uses a random number generator (that takes the coordinates of the point and the seed as parameters) instead of a permutation table. You can use perlin noise, but value noise is a tremendous amount simpler. It defines a function such that f(x,y,seed) will return a noise value for each point on the map, and when given the same parameters, it will return the same value. It then uses this to generate the chunks by using the noise value of each point in the world to determine how high that part of the world is.

If you would like to learn about value noise: https://code.google.com/p/fractalterraingeneration/wiki/Value_Noise
If you would like to learn more about perlin noise: https://code.google.com/p/fractalterraingeneration/wiki/Perlin_Noise
If you want to make a terrain generator plugin: http://forums.bukkit.org/threads/th...ation-part-one-prerequisites-and-setup.93982/

 

Hey, I've been researching this topic quite considerably, and I have learned quite a lot from it. If you haven't already read this post by notch, then you should definately do so. Due to the fact that I haven't delved into the actual code in Minecraft, I don't know the specifics of how it works, but I do know that it uses either Perlin Noise or Value Noise, both of which are very good for making terrain (I use Value Noise, because the programming concepts behind it make good sense and there are better tutorials for it on the internet. This site is a very good explanation of how it works. Although the site says that the noise function it is describing is called Perlin Noise, it is mislabeled, and is actually an explanation of Value Noise). I'll post an essay for a school project I did on Value Noise and using it to create natural-looking terrain for you, as well as the source code of my one, two, and three dimensional Value Noise functions. Once you have a very solid understanding of Value Noise or whatever noise function you wish to use, you can then use it to understand Minecraft's terrain generation. Bukkit has a very nice way of allowing programmers to create their own terrain generators. To do this in you own plugin, learn a bit about Chunk Generators and Block Populators, as they are the two classes used to implement custom terrain generation.

Cant seem to upload the files, so here is a link to it on dropbox.

EDIT by Moderator: merged posts, please use the edit button instead of double posting.

 

Thanks Guys! I read into your links and this is what I have to say:
jtjj: link 1 was exactly what i described above! neat!
link 2, more stuff about perlin noise, very good
link 3, will be extemely useful later.
However none of the links really show how MC puts in a seed number and coordinates and outputs a height i.e f(x,y,seed) = terrain height. f(x,y,seed)?? You seem to be a pretty competent developer, do you know anyone who might know this?

The Butlah:
Good basic overview of how Notch started using value noise and perlin noise to develop his terrain generation algorithms, but still not explicit enough for me to actually implement somewhere.
Your paper was really awesome! I wish i'd done that for a high school project! :SS

I still need to know though how MC smoothly adds on two of these interpolated maps without the terrain exhibiting discontinuities (chunk errors). Thanks alot though guys!

 

I sent you the third one, that way you could see exactly how mc turns noise into terrain

 

Magic.

 

I don't really understand your question. What is the problem, exactly?

 

jtjj, I started your tutorial series, and it seems very helpful so far. I'm keeping tabs on any new tutorials you release.
TheButlah, okay... imagine I'm minecrafts code, and I create the following terrain:

(side note, I created an erosion program in matlab to generate this heightmap D . too slow to ever work on minecraft, but neat nonetheless ) . Further suppose that its is 10 x 10 chunks wide.. that is, 160 by 160 chunks. When I first load the world, I can create random values inside this 10x10 chunk wide space, interpolate, and presto! when I need to actually make the chunks, I just look into this function and find the height values. Now suppose I want to travel off this pregenerated map, so do I need to make a completely new value noise map? and if I do, its very likely this new value noise map will be discontinuous and not smooth at the boundary with the old map. If this is the case (and we obviously don't observe huge discontinuities in the terrain that often) how is MC smoothing it out??

 

Don't make a pregenerated map; Instead, compute the values for each position individually. Use a hash function or seeded pseudo-random number that will always return the same value when presented with the same location for the random feature points. Then, just interpolate away!
This has the effect of making an infinite (as far as the computer can handle) noise map, with no discontinuities.

 

Jtjj is correct. The only reason value noise and Perlin noise is continuous at all is because each octave of the value/perlin noise is made by interpolating between points returned from a seeded pseudo-random number generator. This means that as long as the seed stays the same for a value/perlin noise function, the outputted heightmap will remain the same, no matter how many times the function is called. Therefore, the best, if not only, solution to generating "infinite" terrain on the fly, such as Minecraft's , is to compute the terrain as the terrain comes into rendering distance. Minecraft does this by taking each chunk and first determining if it has already been visited by the player (and therefore it's terrain has already been calculated and stored in the player's world file). If it has been visited already, then to save on CPU resources, it is loaded from the world file; otherwise each coordinate in the 16x16 block chunk is iterated through, and the hight of the highest block in the collumn of blocks at (x,z) is equal to ValueNoise(x,z, world seed). Because all the chunks are generated using the same seed and using the same function, then the terrain will have no discontinuities.

So, in summary:
As long as you use the same noise function consistently,with the same seed, then the terrain will have no discontinuities.

 

soo the random numbers used by the interpolating noise function span the entire possible world??

 

Exactly. Well, as long as the java int type can store the co-ordinates without type errors
AFAIK, that is what caused the 'far lands'.

 

Yep . Did we answer your question?

 

Possibly? So to put it into context of my original post, the domain is basically the size of the java int type? and all the random numbers and lagrange interpolating polynomials are decided before the world even starts? if so, then yes you answered that! although it seems like its a little unbelievable, i can rest easy.

 

Um, no. I think you are under the misconception that in order for a value noise function to work, you need to pre-compute all of the values. This is not necessary. Upon doing ValueNoise(x,z, octaves, seed), the only values it computes are the integers immediately surrounding the point (x,z). Therefore, NOTHING NEEDS TO BE PRECOMPUTED. In other words, the domain is infinite (or as large as the computer can handle)

 

In reality, that is it. Theoretically, it could have an infinite domain, but due to the limitations, it is as far as the game can keep track of with 32 bits. The great part about it though, is that due to the pseudo-randomenss of it, there is no need to pre-compute any values!

 

well.. by virtue of it being a lagrange polynomial predetermined by random values, there is quite a bit of predetermining to do, just not of the heightmap. specifically (assuming one octave only) the game has to compute a polynomial of degree n-1 where n is the number of random points determined by the seed. Assuming 1 random number ever 4 chunks and a max int size of 2,147,483,647, (adding a plus and minus makes twice this), this means an interpolating polynomial of degree 33554430.. thats a ridiculously large polynomial, so i guess thats why im having trouble believing that. But if thats the case then okay, thanks guys

 

That isn't how it works. It does not use perlin noise. There are equally distributed random values (heights). To generate the value for a point (x,z,seed), we use a hash function to determine the values of the nearest random values, and interpolate ebtween them.

 

interpolating polynomials are also used for value noise, not just perlin noise.
Okay, so then it isnt just value noise, its modified value noise. Pure value noise interpolates between a set of points then creates the entire map.
So this hash function must then take into account a certain number of random values already used in the generated terrain to make the new interpolation continuous. That sounds much better!

 

No, that isnt the case. read my post

 

ah... that makes more sense. I should read posts more lol. k thanks.

 

You are welcome