bzdww

Get answers and suggestions for various questions from here

Procedual Generation in Minecraft - Structure Generation

cms

Summary


When it comes to the open world, the sandbox, the first technology point that comes to mind is Procedual Generation. Post a definition on a wiki

The term "proceduralization" refers to the process of computing a particular function , such as fractals . Procedural generation is often used to generate textures, polygon meshes, sound effects, speech synthesis, and music production. The benefit of procedural generation is that with very small functions and source data, you can create many new data that are related or similar to the source data but that are different. With it, video games can have many (nearly unlimited) levels. This can reduce development time and reduce the file size of the software.

Many games have the technology to use the Professional Generation, more or less, but for the best combination of the Procedual Generation and GamePlay, of course, Minecraft.

All code is from forge, ver10.2 (plus some human flesh decompilation). Some images are from the minecraft wiki.

All code usage is subject to the open source agreement!

github.com/MinecraftFor

Linear congruence random number generator

Why do the same seeds produce completely consistent terrain, using pseudo-random numbers.

The LCG algorithm is mathematically based on the formula:

X(n+1) = (a * X(n) + c) % m

Among them, the coefficients are:

Mm m , m > 0

Coefficient a , 0 < a < m

Increment c , 0 <= c < m

Original value (seed) 0 <= X(0) < m

The parameters c, m, a are sensitive, or directly affect the quality of the pseudo-random number.

Suppose a = 2, c = 3, m = 10, initial value Xo = 5, write the code

int lcgRandom(int seed)
{
    return (2 * seed + 3) % 10;
}

void Start() {
    int seed = 5;
    for (int i = 0; i < 10; i++)
    {
        seed = lcgRandom(seed);
        Debug.Log(seed);
    }
}

The result is

5 3 9 1 5 3 9 1 5 3...

It can be found that there will be a cycle, which is caused by the modulo operation. In the theory of random numbers, this cycle is called

Period of the sequence . For random number generation, the larger the cycle, of course, the better, so that the randomness of randomness is higher. Generally, the larger m is, the larger the cycle is. At the same time, a and c also have a certain influence on the cycle. Some parameters can generate the numbers in m. At this time, the generator is Full-Cycle Linear Congruential Generator.

Some random number generation algorithms directly set c to 0 because c is just a constant

Xn = aXn-1 mod m

Such a generator is called a pure multiplicative generator . One problem with such a generator is that it cannot generate 0.

There is a minimum standard for the values ​​of and m and a. Proposed by Park and Miller, m = 2,147,483,647 and a = 16,807. If you want to propose a better algorithm, you can't be worse than this combination.

In general, m of high LCG is the exponential power of 2 (generally 2^32 or 2^64), because this modulo operation truncates the rightmost 32 or 64 bits. This theory is used in most compiler libraries to implement its pseudo-random number generator rand().

Take a look at the random number generator in Minecraft:

void GenLayer::initChunkSeed(int x, int z)
{
	m_ChunkSeed = m_WorldGenSeed;
	m_ChunkSeed *= m_ChunkSeed * 6364136223846793005L + 1442695040888963407L;
	m_ChunkSeed += x;
	m_ChunkSeed *= m_ChunkSeed * 6364136223846793005L + 1442695040888963407L;
	m_ChunkSeed += z;
	m_ChunkSeed *= m_ChunkSeed * 6364136223846793005L + 1442695040888963407L;
	m_ChunkSeed += x;
	m_ChunkSeed *= m_ChunkSeed * 6364136223846793005L + 1442695040888963407L;
	m_ChunkSeed += z;
}

int GenLayer::nextInt(unsigned int range)
{
	unsigned int r = (unsigned int)(m_ChunkSeed >> 24) % range;

	m_ChunkSeed *= m_ChunkSeed * 6364136223846793005L + 1442695040888963407L;
	m_ChunkSeed += m_WorldGenSeed;
	return r;
}

m_ChunkSeed is stored in 64 bits. There is no modulo operation. For unsigned integer overflow, the C specification is defined. "The number after overflow will be modulo 2^(8*sizeof(type)).

Program generation pipeline

Similar to the iphone assembly line of Fu Kang, Minecraft has its own generation pipeline from a random number seed to the terrain displayed in the game.

The overall generation pipeline is as follows

The introduction of the simple process can refer to this Minecraft terrain generation algorithm is what?


Mine formation

The generation of structural classes in Minecraft occurs after the formation of the cave canyon, and the resulting structures mainly include abandoned pits, villages, fortresses, and dungeons.


Structure generation process



Related structure UML diagram


Simple description

  1. Detect whether it is suitable to generate the current structure when generating the Chunk;
  2. To build a central building, the mine pit is a Room, and the village is a well;
  3. Detect whether the four directions of the center building can randomly generate new structures and buildings;
  4. If it can be generated, it is detected whether it is possible to generate a new Component that can be connected based on this Component.
  5. Repeat 4
  6. In the Populate stage, each component is filled with squares, as well as brush monsters, treasure chests, villagers, and so on.

Let me talk about an algorithm that randomly generates dungeons .

If we want to generate a dungeon, we first define some basic components in the dungeon, they have:

Room : It has one or more exits;
Corridor : It is a very narrow and long area with two exits, it may also be a slope; the
connection : is a small space with more than three exits;

Here are a few simple component models, each with a bounding box to prevent the components from interspersing at the time of generation. At the exit of each component, there is a mark that marks the position and rotation for the component. match.

Now you can generate dungeons by splicing them together according to certain rules. These rules are:

  1. The room can only link to the corridor;
  2. Corridor linking rooms or connections;
  3. The connection can only be connected to the corridor;
  4. There should be no interspersed between components (using the Bounding Box).


Next is a detailed description of the generation algorithm.

  1. Initialize a revelation module (you can choose the module with the most number of exits);
  2. Generate an eligible module for each unconnected exit;
  3. Re-establish a list of currently unconnected exits;
  4. Repeat steps 2 and 3.

The following figures are the initial state, three iterations and six iterations.


The above random algorithm only generates the dungeon framework, and also needs to generate many other dungeon elements, such as the cans that can be broken on the ground, the torch that flickers on the wall, and the slime that suddenly pops out from behind. The method of generating these elements is similar to the previous one. Simply put, some mark points are marked on the ground or wall of the component. Randomly generate some matching features on these mark points. The following are two program generation. An example of a room.

According to the above algorithm, the basic components of the abandoned pit are Room, Corridor, Stair, and Cross. In the constructor of StructureMineshaftStart, the starting component is a Room, and the Room object contains a list of BoundingBoxes connected to its own components.

Take a look at Room's buildComponent function.


Code everyone can build some forge environment to run some, here is not explained in detail.


summary

Structure generation is just a very simple part of MC's generation pipeline. Interested friends can also refer to forge to learn more generation algorithms, such as generating cave canyons, generating various ecological terrains, etc., and generating some code in minecraft. They are fairly clear, so students interested in the program generation algorithm are very recommended to take a look.


reference

Generating terrain in Cuberite Biome - Official Minecraft Wiki Perlin noise - Wikipedia Simplex noise - Wikipedia How does Minecraft generate structures? (Especially rivers) • r/gamedev Minecraft's world generation process (six) villages - El Psy Congruu - Blog Channel - CSDN. NET Bake Your Own 3D Dungeons With Procedural Recipes