I Need Some Help With Terrain Gen.

[Doc]

Hello,
I asked Ben about terrain generation and he said to come here. I need help understanding the bases of how procedural terrain generation works, so that it can generate more chunks as you explore. Can you help me with this? I have been searching for a long time, but I have not found something I understand. Can you explain how procedural terrain gen works?

 

[Skaldarnar]

As far as I know the terrain generation is based on perlin noise right now, so googling that term will get you on the right way. If you are German/understand German I can recommend the paper "Gradientenbasierte Rauschfunktionen und Perlin Noise" from Wilhelm Burger. It's quite mathematical (due to the context, but good figures and pseudo code), but it gave me a good idea of the principle.

 

[Nym Traveel]

Thanks for the link, will help me, too

Right now it's based on a 3d perlin noise. Imagine this as a 3d version of something like this:

The exact look of this is based on a given seed - same seed, same noise and therefore pseudorandom.
Well, this isn't restricted in any dimension, so you can extend this pattern on all three axis.
What Minecraft or Terasology now does to generate a chunk is the following:
It takes a 3d array with the size of the chunk and for every entry it asks for the noise value on this point.
If this entry is below a threshold the block is set to air, else a solid block.
If you would do this with the above noise you'd get a chunk full with random pieces of solid mass. To get the landscape the noise gets and overlayed gradient from top to bottom so that the upper blocks are more likely to be air. The settings of the noise and the overlaying gradient are the secret to a realistic terrain.

Now this chunk is set. when the player proceeds the corresponding chunks are generated through the same methode. They basically fit just because the underlying noise is the same.

I'm fiddeling with this issue atm in Terasology; i don't see through it 100% but I'm getting there slowly
Eventually I'll hopefully have a nice shiny layout with several biomes and stuff

If you wan't to have a look on it yourself, go grab the source of TS and look into org.terasology.world.generator.core

 

[Doc]

First, thanks for all the help! Second, how does the program align the blocks up if it just asks the code whether a block is solid?

 

[Doc]

I looked through the source of ChunkGeneratorManager.java and it calls ChunkGenerator.java which contains this:

Spoiler: ChunkGenerator.java

/*
* Copyright 2012 Benjamin Glatzel <benjamin.glatzel@me.com>
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package org.terasology.world.generator;
import org.terasology.world.chunks.Chunk;
/**
* @author Immortius
*/
public interface ChunkGenerator extends BaseChunkGenerator {
/**
* Generate the local contents of a chunk. This should be purely deterministic from the chunk contents, chunk
* position and world seed - should not depend on external state or other data.
*
* @param chunk
*/
public void generateChunk(Chunk chunk);
}

(put in spoiler )

Is this correct? It calls nothing and it doesnt process anything.

 

[Skaldarnar]

As you can see the ChunkGenerator is an interface. Therefore, it just specifies how other classes can interact with some kind of ChunkGenerator ('some kind' means an implementing class, such as PerlinTerrainGenerator). In this case it says that all chunk generators have to offer a generate chunk method. For the actual implementation you have to look at the implementing classes.

 

[Doc]

Ok, so which file would you recommend looking at?

 

[Cervator]

Ok, so which file would you recommend looking at?

Are you looking at the code in IntelliJ or another IDE? I'd suggest setting up for that if not, then you've got all sorts of utility like "Find Usages" on an interface like ChunkGenerator that'll tell you all the implementing classes. Makes it a lot easier to travel the code and figure out how it works

 

[Immortius]

First, thanks for all the help! Second, how does the program align the blocks up if it just asks the code whether a block is solid?

I guess the first thing to understand is while perlin noise is useful, you can't just use it directly. It is noise, after all - all you'll get using it naively is swiss cheese. Instead what you have to do is combine multiple layers of perlin noise for different features (and potentially other useful noise like voronoi). So we first determine the general height of the world, and then hollows, and determine temperature and humidity, all from different sources of noise. And all of this information is used, along with a number of rules, to generate the world itself.

The other thing to note is the world is basically a three dimensional grid, so the process of generation is akin to rasterisation. At each cube of the grid the various pieces of information on height, temperature, humidity and so forth are used to populate it with the correct block.

 

[Doc]

Cervator: I use netbeans, which i believe has this function! I'll try downloading the source and loading it into netbeans sometime.

Immortius: So if i want to generate a chunk at a time, but still have it line up with the next chunk, how do I do it? Would I have to store all the arrays and stuff used during gen in that chunk to be used in the next chunk's gen?

Thanks for helping me learn this!

 

[Cervator]

Doc - you just use the same algorithm on the same backing Perlin noise map for all the chunks and they'll magically line up without needing to know anything about their neighbors

 

[mkalb]

Doc We use Gradle as our Build-System. It doesn't support Netbeans yet.
It is possible to work with Netbeans but it will be easier with IntelliJ IDEA or Eclipse.

 

[Doc]

Cervator - I just don't get the process you use for procedural terrain gen. What is the process (ie. generate a heightmap the size of blank chunks, overlay this with heightmap size blank chunks) for generating a single chunk, then what is the process for generating a second chunk where the first one left off?

mkalb That's ok, I just reinstalled my os and I don't want to clutter it with programs again lol.

 

[Immortius]

Cervator - I just don't get the process you use for procedural terrain gen. What is the process (ie. generate a heightmap the size of blank chunks, overlay this with heightmap size blank chunks) for generating a single chunk, then what is the process for generating a second chunk where the first one left off?

Ok, forget about chunks for a moment. You have a perlin noise function. This takes N arguments (typically 2 or 3) and returns a a value (typically around -1 to 1 I think, although from memory it can exceed those values). Perlin noise has the following features:

• If you provide the same arguments, you get the same result. So you can always go back and get the value for noise(0.1, 0.1, 0.1) again.
• The noise function is "smooth". This means that when you vary the arguments, there are no sudden leaps in the returned value. The result for noise(0.1, 0.15, 0.1) will be very similar to noise(0.1, 0.1, 0.1). But not the same generally.

So if the problem is using perlin noise to provide a height-map as you generate blocks and chunks, a natural solution is to use block spatial coordinates on the horizontal axes as the arguments - so noise(posX * s, 0.5, posZ * s) for instance, where s is a scaling factor. It is important to note when using perlin noise to avoid sampling only integer positions like noise (0,0,0) and noise(0,1,0) - integer positions are where the perlin noise will have extreme values of -1 and 1, so you loose the important smoothness if you do. So s may be something like 0.001.

Then the answer to how to chunks will match up is clear - if you are using the same perlin function when generating each chunk, seeded with the same value, and use the absolute block coordinates as arguments into the function, the chunks will naturally align as a result of the smoothness of the noise.

 

[Nym Traveel]

Doc
If you think of terrain, don't think of the single chunks. They are helpers to control all of it memorywise.
Think of one function |R x |R -> |R that gives you the heigh at one point on the plane. So basically all of your terrain is now set in stone. Now chunks come and rasterize the plane to 16x16 pieces. Hence the chunks have to align, because they are just adjacent blocks of the same global (kinda smooth) function.

(I left out that our Noise goes from |R^3 -> |R just because of visualisation issues)

If you want to have another explanation, I recommend you reading through -notch's post- on terrain generation or if you really wanna learn something about Perlin noise read though -this- pdf (requires some mathematical understanding)

 

[Doc]

I don't understand german, and I have read that post from notch. What I don't get is how do you make this noise function? Can you give me a concept and tell me what it does each time it is called, and how it generates the values?

 

[Nym Traveel]

Ok, I'll explain it in 1D, further abstractation is quite simple then.
what you want is a noise function noise(x) giving you the value of the noise at x.
Let grad(x) be a function which returnes fixed but random values between -1 and 1 for x an integer. (visualisation pdf page 2).
We also want all integers to be zeroes of noise(x).
We can now define a polynomial interpolation of third degree which fits the requirements (zeros at the integer values, first derivate equals grad(x) at all integers). (pdf page 4)
In the field you wanna use a polynom of degree 4 to get a more pleasing result.
For a real Perlin noise you overlay multiple noises with different scales. (page 14, second image)

In Terasology The noise is scaled way more up so you can actually see the oscillation. (and to avoid aliasing effects)
Well, thats the basics, I bet you'll find several google entries getting you familiar with the matter

ps: a starting point

 

[Doc]

I just don't understand, how do you use them (do you plug the xyz into noise then into grad or what?), and what is inside those functions. Can you give me some code on how you use them and tell me whats inside them?

 

[Nym Traveel]

No, you want the value of the noise at a point -> put it into the noise function.
The grad function is only necessary to evaluate noise.
You can simply download Terasology and look into it or go to Ken Perlins page, he has a reference implementation there

 

[Doc]

Ok, I looked into terasology some more, starting at:
src / main / java / org / terasology / world / generator / core / PerlinTerrainGenerator.java

I traced it all the way to TeraMath.java and it has this code which I don't understand:
return (d < 0 && d != i) ? i - 1 : i;

Can you explain what this does?