3
\$\begingroup\$

I want to generate a world like minecraft's with an algorithm that treats every block separately. I want the world generator to be a single large function that takes in the x,y,z coordinates and returns what block should be placed in that spot.

It should work without knowledge of what the adjacent blocks are. It should be able to generate terrain with biomes, trees, caves, ore deposits and structures like villages.

Is it possible to make such a world generator and if so, can I get some pointers to how it can be done and what topics to research? If somebody wrote a tutorial about doing that it would be perfect. I hope this isn't a duplicate question because I am specifically interested in generating each block completely independent from its surroundings.

\$\endgroup\$
8
  • \$\begingroup\$ Have you tried researching yourself? This community helps more if you at least attempted at doing this yourself. \$\endgroup\$ Commented Sep 24, 2017 at 23:29
  • 1
    \$\begingroup\$ I have and I know that it's going to be lots of layers of nosie corresponding to different data, but I don't know if generating caves and villages like the ones in minecraft is possible without conditionals based on surrounding blocks. \$\endgroup\$
    – tempfugit
    Commented Sep 24, 2017 at 23:42
  • 1
    \$\begingroup\$ You can definitely not do it without checking for blocks at specific places (especially during structure and tree generation). Also, are you sure you want to make another Minecraft clone" \$\endgroup\$
    – Bálint
    Commented Sep 25, 2017 at 5:55
  • 1
    \$\begingroup\$ @Bálint, are you certain it cant be done? It wont be fast but I think there might be a way to calculate everyblock reversely. Im not quite sure how to pull it off but it makes for a much more interesting I-wonder-if-I-can-make-this-work-project than just another minecraft-clone. \$\endgroup\$
    – Niels
    Commented Sep 25, 2017 at 13:15
  • \$\begingroup\$ Your goals seem contradictory. Biomes are spatially grouped collections of environmentally / thematically similar cells. How do you create such a grouping of a given size or shape without some awareness of its component cells? \$\endgroup\$
    – Pikalek
    Commented Sep 25, 2017 at 16:42

2 Answers 2

10
\$\begingroup\$

What you are looking for is Fractal Noise generation algorithms, the most popular of which being Perlin noise with successive octave noise generation (in addition to simplex noise, which is patented by Nokia, however the patent expires in a 2021 and if you want to take the risk, technically doesn't apply to terrain generation (only that which "generates an image")).

I'm not going too in-depth into perlin noise here, but I'll give a rough overview to how it is really the closest thing that solves your problem.

Perlin noise is a type of Gradient Noise algorithm, which smooths out visual artifacts compared to Value Noise. Both of these types of fractal noise generation techniques work via pseudo random hashing of grid coordinates which then create a pseudo random value at that grid point implicitly, which can be independently accessed and repeatedly generated with the same value regardless of the existence of values around the point. All these techniques need to know is the index you are trying to generate, and how many octaves you want to generate on top of it. Values at each point are interpolated between each value that corresponds to grid intersections, this creates noise.

Octaves are what create the fractal, correlated patterns you see in the wiki articles (the cloudy images). Octaves are successive application of the same algorithm but summed up with some weight applied to each level. You start out with a very high frequency octave (which is to say, high resolution grid, acting as if the discrete points you generate are actually several sub points within that grid, higher resolution means the less points correspond to a single cell of the grid) and succesively sum up lower frequency versions of that grid until you get what would look like the images above.

These values end up just being numbers, so they can map to anything you like, people often use this to generate terrain quickly.

Value noise just means at each octave, or run of the algorithm, you act like the corner point number you've generated with a hash is just a value (integer, float or otherwise). In Gradient noise, this value becomes a direction, you will end up generating hills which give you values based on their height, interpolating where you are on the hill based on the directions at each point. This creates a Gaussian smoothing effect of features, in addition to creating less directional artifacts visible by people on successive octave generations.

These techniques are not limited to 2D or even 3D, this type of generation can be used to create moving 3D clouds by using 4D noise generation, where the 4th dimension is the time location instead of a spacial index location. These techniques can work on Ndimensional data (but are obviously slower at higher dimensions)

Again, you can generate any point independently from any other with these methods, there is no interdependence on adjacent values.

Now how would you use this to generate like you say?:

terrain with biomes, trees, caves, ore deposits and structures like villages.

I am unsure of the specifics on minecraft, but I do know Notch says that the game uses perlin noise generation.

For 3D height maps this is easy. You can easily generate hills and mountains with this using the output value from summed octaves as the height you want, and this can all be done with 2D perlin noise.

If you want different physical characteristics of the noise (like sharp spine ridges or more bubbly appearances) you can modify your output, or change your indexing formula to warp space and create such characterstics. See here for visual examples of what gradient noise is capable of

Caves on the other hand are a bit tricky. Have you even wondered why minecraft has floating islands? Well part of the reason it exists is likely how horizontal concave terrain generation is handled, for example what is required to create caves and cliffs.

One way to handle this is to use 3D noise generation and the 2D surface generation together, and only fill in blocks that exist within the 2D initial surface and pass the "empty" threshold value that you will use to interpret the 3D noise output with. The issue with this approach is that, in some instances, this will produce the artifacts you see in minecraft. Floating islands can happen in part because the "floating" part may have passed the threshold, and despite the empty part being inside the initial 2D surface, it didn't pass the threshold and was left empty.

This can be partially mitigated with out block interdependence via using the height map value you are generating at to also determine the empty threshold (making it harder to be an empty block the further up you are generating at). However, with out some block dependent post processing fix up this is usually not completely fixable.

The good news is that from this point, if you understood how to do the previous stuff, the rest is pretty easy. For deposits, like combining 3D and 2D to create caves with height maps, we can simply apply another perlin noise function to figure out whether or not to place a deposit and what type of deposit it should be. Biomes can be handled similarly, either with a single noise function, or multiple functions that produce different biomes based on overlapping values, in addition to incorporating elevation. Trees can be handled similarly, with another noise function which simply places the tree on the surface generated as the height map is generated and biome calculated. Villages will be a bit harder, but in general you can at least place the spawn place of a village in a similar way. You may have to move away from block independence to create a logical structure, something like cellular automata may work. Village place is spawned, and then generated outwards from that location later. But of course you may be able to find a way to independently generate it with via perlin noise like everything else, the issue is how to generate the structures themselves, one compromise is using predefined structures, and connecting them online, or even having entire predefined villages.

For an additional resource awesome redblog article goes over tree and biome generation in this style but in 2D and with actual code.

\$\endgroup\$
2
\$\begingroup\$

I would highly recommend you to watch Sam Hogan's I Made Minecraft in 24 Hours. He has talked about how to procedurally generate trees and water, and also different terrain.

And if you want to know more about Procedural Landmass Generation check out Sebastian Lague's playlist on Procedural Terrain Generation

This is a part of the description from Sam's video which I think would be of help. It is like an overview of the video.

I started off with basic terrain generation, using cube game objects arranged in a grid, whose heights are varied by a Perlin noise function. This, however, led to not great performance, but luckily I knew of a way to significantly optimize things.

This was using terrain chunks - which is what the actual Minecraft does as far as I can tell. This meant using voxel data to only build faces of blocks that are facing air blocks. And because the voxel data is 3D, it's possible to have much more interesting procedural terrain generation, like caves, overhangs, trees, etc.

It's super fun to play around with the different noise functions and see what type of terrain is generated. I ended up doing some simple stuff which looks pretty good: A base layer of simplex noise at a large scale + another layer at a smaller scale that is multiplied by yet another layer for terrain variety. This is the heightmap. Then 3D simplex noise cuts pieces out to create cave systems.

Procedurally generating trees and water were both a little tricky. For trees, I used a Perlin noise value at each chunk coordinate to determine how many trees would be in each chunk. Then, a random number generator seeded with the chunk's coordinates was used to build the specific trees. This way, the exact same random numbers are produced each time for a specific chunk, and the same trees are generated.

Water had to form around the terrain, so you don't have weird stuff like finding water when you did straight down. What I ended up doing was creating a separate mesh for the water. To build it up, just loop through each xz coordinate in the chunk, for each starting at the max y position and move down through the voxel data, checking if land exists. If the water level is reached before the first land block, build a square at the water level.

There's some boring stuff cut out of the video, like optimization. I did things like adding an object pool for reusing terrain chunks and add a timer to load chunks one at a time instead of all at once. The performance is still not great, which is mostly due to all the noise function calculations. This could probably be fixed with multithreading, but there's no way I could figure that out without internet help.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .