Unity dynamic Grid map generation: Terrain creation based on Perlin Noise

Preface:

In the previous article, I wrote a simple grid map generation script, but it was done in two dimensions. In order to further expand the script and learn more about loading large world maps, we will do a series of articles on open-world terrain loading like Minecraft

In this process, I hope that beginners in the industry can understand the basic principles and implementation methods of some common algorithms in a simple way through my introduction, and at the same time know or understand what the rudiment of some mature industry codes is. Simply speaking, it is a zero-based but relatively in-depth series of articles

This article, the first in the series, will complete the initial creation of the world’s terrain, and the result will be roughly shown below:

Map creation logic

I. Create regional grid map:

Similar to my world, when entering the game for the first time, the map will be initialized first, and then the initialized data will be saved, so that you can continue to store and read in the subsequent game

Regional grid map creation logic:

The first stage in this process is the initialization of the map scene. If the whole scene is loaded at one time, it is obviously impossible, no matter the data loading, data storage and calculation, or scene rendering are difficult to achieve.

So we need to have a dynamic loading strategy that, like Minecraft, only computes and renders the terrain data around the player. This ensures that the terrain is displayed correctly without undue performance pressure.

The next step is to think about dynamic loading. Obviously, to generate a map around the character, regardless of the Y-axis, the circle is the best choice, because the player rotates around a circle and the player’s field of view forms a circle. As shown in the picture, the circular area saves more space than the rectangular area:

Of course this is the ideal situation, but imagine the problems of using circles in a practical logical design:

The first is the edge calculation problem. Compared with the simple addition and subtraction method for rectangles, the calculation of circles needs to be completed by multiplying floating point numbers. In this way, the calculation data is large and the result is not accurate enough
And because the basic unit of the whole grid map is square (inXShaft withYIn simple terms, only part of the square with circular edge will be covered. In this way, it needs to judge and process it, which greatly improves the logic complexity

For the above reasons, the square is chosen as the loading unit of the second dimension of the grid map

Once the shape of the basic map loading blocks is determined, a map can be generated by calculating the player’s initial position. At the beginning of the design, we did not consider the setting of the map block size, and realized the creation of the map first

Basic block unit construction:

Create a script named Item and add some basic attributes first. Later, we can extend them if necessary. Here are some attribute methods we need to implement by default:

gridID: used to represent each square on a map
Enumeration of lattice types: similar to my world stone and earth
Grid material: through the grid type to give different materials, get different display effect
Mouse click event: through the delegation to complete, convenient follow-up click damage effect
Encapsulate a change material method: easy to call later

Simply write some methods that may be used in the later period, of course, it doesn’t matter if you don’t write them now, and then add them when you use them later. The specific code structure is as follows:

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using System;


public class Item : MonoBehaviour
{
    //public Material material;
    public MeshRenderer render;


    public Action clickEvent;
    [HideInInspector]
    public ITEM_TYPE type;
    [HideInInspector]
    public Vector3Int itemID;
    public void Register()
    {
        ChangeMaterial();
    }
    void ChangeMaterial()
    {
        render.sharedMaterial = GameTools.Instance.materials[(int)type];
    }

    public void OnMouseDown()
    {
        clickEvent?.Invoke();
    }

}

Copy the code

In the above script we call an enumeration object called ITEM_TYPE. This enumeration object is created to identify the block type. We can simply fill in one or two values at the beginning:

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public enum ITEM_TYPE 
{
    Bedrock=0,
    Ston=1,
    Cold=2

}
Copy the code

After writing the above two scripts, create oneCubeAnd put theItemDrag the script to create a prefab:

Local mesh creation logic:

Next, create a script named MeshMapCreate. In order to get some properties that can be adjusted for later debugging, choose to inherit from MonoBehaviour as the mount script and define some properties:

Size range of grid map
Create the center location of the grid map
Block template for easy instantiation
Instantiate the parent object of the object

Note that in the above attributes, we only consider the plane composed of Z axis and X axis for the center position of the grid map, because the terrain of Y axis is complex and the terrain change is positively correlated with the direction of Y axis, so it is not a good choice to calculate the center position

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using System;

public class MeshMapCreate : MonoBehaviour{[Header("Map size range:")]
    public Vector3Int mapRange;
    [Header("Map central location:")]
    public Vector3Int startPos;
    [Header("Block template:")]
    public Item item;
    [Header(Instantiate object parent object:)]
    public Transform parentTran;
}

Copy the code

In the script above, a Vector3Int is used as the ID. The purpose of this is to use the ID of the square directly as the position coordinate of the square, and to ensure that any two squares fit closely, the position calculation is globally used as an integer type to avoid the accuracy deviation of floating-point numbers

Why floating-point numbers are prone to skewness: Unity’s handling strategy for floating point numbers is to discard them when they exceed 7 decimal places. While this usually has little impact, it can cause visible skewness after a large number of calculations

Then we need to create a simple map method in this script, which consists of squares forming a plane and instantiating a series of squares by traversing the given map range. However, there is a problem. If we normally use a cumulative way to traverse the map from one corner, This will cause the problem that the starting coordinate point is located in the starting corner of the map generation instead of the center of the map (the center here only considers the plane composed of X and Z axes), as shown in the figure:

But how do you ensure that the character is in the center of the rectangular grid you create in your programming implementation

First of all, we need to understand that the creation of the entire THREE-DIMENSIONAL grid map is the traversal of the number of grids occupied by the length, width and height of the three-dimensional grid. Since the Cube template we use is exactly 1 in length, width and height, we only need to traverse the previously defined attribute mapRange on x, Y and Z axes to obtain Item at all positions. The specific code structure is shown as follows:

	for (int j = 0; j < range.y; j++)
        {
            for (int i = 0; i < range.x; i++)
            {
                for (int k = 0; k < range.z; k++)
                {

                    
                }
            }
                
        }
Copy the code

In the above, I first has carried on the traversal for Y, because they know the terrain structure is often a hierarchical structure, and different depth of geology, the diagram below (in order to avoid infringement, I had to draw a myself, some abstract, but is easy to understand, even if you don’t understand this picture, should also know that my world tend to be the top of the soil, The bottom layer is rock, the bottom layer is bedrock, and the same is true here:

After understanding the creation, we need to calculate the location of the current block according to the unique I, j, K and the center position startPos, and at the same time take this position as the unique ID of the current block, write a method to obtain coordinates:

	public Vector3Int GetItemID(int i, int j, int k)
    {
        int x = i - (mapRange.x + 1) / 2 + startPos.x;
        int y = j + startPos.y;
        int z = k - (mapRange.z + 1) / 2 + startPos.z;
        return new Vector3Int(x, y, z);
    }
    
Copy the code

The implementation method is very simple, that is, encapsulates a remapping method, which can be simply understood as mapping the number from 0 to 2n to -n to N, and the coordinate position of the mapping is generated in Vector3Int (0, 0, 0) relative to the center coordinate. In order to obtain the square coordinate position relative to the center coordinate, You need to add the central location startPos

To illustrate the process, use a coroutine to create the terrain. Define two properties:

A dictionary to cache map grid information, recording keys unique to each squareID, and the value is a block logic scriptitem
A delegate: a method used to perform block creation, this is mainly for the purpose of performing different creation logic when there are different terrain behind

	// Cache map block information
    public Dictionary<Vector3Int.Item> items=new Dictionary<Vector3Int, Item>();
	// Write a delegate to the Item creation time
    private Action<Item> ItemCreateEvent;

	// Create the terrain method, pass in the parameter to create the map center coordinates point
    IEnumerator CreateMap(Vector3Int range)
    {
        for (int j = 0; j < range.y; j++)
        {
            for (int i = 0; i < range.x; i++)
            {
                for (int k = 0; k < range.z; k++)
                {
                	Vector3Int v3i = GetItemID(i, j, k);
                    CreateGrid(v3i);                   
                    yield return new WaitForSeconds(0.0002 f); }}}}// The method to be executed to create a block
	public void CreateGrid(Vector3Int v3i){ Item itemCo = Instantiate(item, parentTran); itemCo.transform.position = v3i; ItemCreateEvent? .Invoke(itemCo); items.Add(v3i, itemCo); }Copy the code

In the above code, I need to define the delegate method for creating the block before I can execute the entire grid map creation method. Create a method named CreateItemEvent, which is equivalent to setting up an interface and adding the required content later, and add a Register method as the program entry:

    public void Register()
    {
        GetPerlinNoise(mapRange);
        ItemCreateEvent = CreateItemEvent;
        StartCoroutine(CreateMap(mapRange));
    }  
    
    public void CreateItemEvent(Item item,Vector3Int v3i)
    {
		//T0: data is initialized when the block is created
    }

Copy the code

Create a script named MainRun that will be used as the entry script to execute the program:

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class MainRun : MonoBehaviour
{
    public MeshMapCreate mapCreate;

    void Update()
    {
        if(Input.GetKeyDown(KeyCode.Space)) { mapCreate.Register(); }}}Copy the code

Let’s see what happens:

As you can see, the map was successfully created based on the red initial points, but now it is a simple terrain block because there is no terrain fluctuation. The next layer is to implement terrain fluctuation

2. Create undulating terrain

In my world, in order to achieve an undulating terrain, it is necessary to have some randomness and continuity at the same time (the following picture is a map without continuity). Randomness is relatively easy to achieve, so how to solve the continuity of the map

1. Failed Scheme:

This scheme was designed and implemented according to my own ideas. The final display effect was poor, and there was no way to expand the subsequent scenes. So just to give you a quick overview, if you’re interested, take a look and get a sense of how other people think

The map loading strategy of the scheme is calculated layer by layer. When the program goes to a certain block to instantiate the creation logic, it judges whether the block around it exists or not. Since the whole grid map block is updated in a corner, there are at most three blocks around it when it is updated to a certain position, as shown in the following figure:

When updating the square where the red ball is located, the position of three squares around it has been logically processed, so its status is determined: it has or does not have squares. My plan is judged according to such a state:

If there are no squares in the position below the current refresh position, the position is directly treated as empty, that is, no squares are allowed to exist, to avoid the situation of floating squares in the air.

If there are squares below, the probability of the existence of squares is given according to the number of surrounding squares. The specific giving logic is as follows:

None: there is a large probability that there is no square
There is a square: there is a square concept of moderation
There are two squares: then the probability that there are squares is very high

After completing the above creation logic design, the result achieved through programming code is shown as follows:

Through the terrain distribution in the above picture, the problems of the scheme can be clearly seen:

Overall, it’s going from one Angle to the other
It’s not smooth enough, it’s still a little bit random
The resulting landscape is small in scope and cannot be lifted
Edges can’t be mixed and subsequent scalability is equivalent to nothing

In general, I personally thought it was a wrong idea at the beginning of development, but then I suddenly saw an article about building caves based on Cellular automaton. It turns out that my idea is basically the same as Cellular Automaton. In essence, there is a problem with the code logic of my idea, so the effect is poor.

aboutCellular automatonHere I directly intercept the content of the big guy’s article:

His explanation of the creation process of a two-dimensional terrain is (picture taken from zhihu big guy)ShaVenZzFor learning use only) :

Cellular automaton generated random terrain has the same idea as my landform creation scheme. It affects the state of the current block by the state of the surrounding block, but the implementation is quite different (if I hadn’t known about Berlin noise, I would have created the map based on his scheme). Briefly analyze the problems of my plan:

There are no random seeds, and the terrain spreads out from one corner
The timing of the terrain creation is not right, so the terrain creation logic should be performed independently, so that the terrain instantiation is not limited to one side and can be judged more based on the number of squares around it
Performing traversal logic only once for terrain results in survivor bias in cases where logic processing blocks have not yet been performed around a block

A quick explanation for the last question. To take an extreme example, when you create the first square, all of the surrounding squares will definitely not exist, which will obviously cause a lot of errors. When we iterate again, there are already some squares in the scene, which reduces the error. Repeat this step gradually to correct the error until the right effect is achieved

If you want more details about Cellular Automaton, here’s ShaVenZz’s original post:

Random cave generation based on Cellular Automaton (1)– Simple map generation

2. Create terrain based on Perlin Noise

After my own attempts failed, I asked for a solution through Baidu, and what I saw most was that Perlin Noise was used to solve the problem. The basic realization principle can be understood as sampling in a noise map, and the results obtained will be different according to the coordinate position of sampling. The simple understanding is that the map is created by taking data from the pre-prepared sample library (which is actually calculated by algorithms). Compared with creating the map through code logic, the amount of calculated data is much less, and the sampling effect is relatively smoother

On Berlin noise:

First paste a paragraph about Baidu Encyclopedia:

Perlin Noise refers to the natural noise generation algorithm invented by Ken Perlin. A noise function is basically a seed randomizer. It takes an integer as a parameter and returns a random number based on that parameter. If you pass in the same argument twice, it produces the same number twice. This rule is very important, otherwise perlin just generates garbage

However, baidu Baike does not have more information about the concrete realization process of Berlin noise, while Wikipedia introduces the general steps of Berlin noise generation:

The whole process is briefly divided into three parts:

Pick a random point and give it a random value
Gradient at a given point (denoted by interpolation function)
The value of the assignment position is calculated from the random point value and gradient

In this process, Perlin Noise uses some special processing strategies to ensure that the generated data is pseudo random and continuous

Simple interpretation of one-dimensional Perlin noise:

Follow the steps described in Wikipedia to deduce the creation of a one-dimensional Berlin noise:

The first step is to create a coordinate system, with the X axis as a one-dimensional reference point and the Y axis as the reference value of the other coordinate, thus creating a basic coordinate system

First, select some positions in a one-dimensional array and assign values to them randomly. In the middle of these positions, some interpolation algorithm is required to obtain values, and finally obtain a continuous curve

In the above process, there are several key points:

How do I choose the location of the assignment
How do I assign it
Which interpolation method is used to obtain the value of non-integer points

In the case of one-dimensional noise generation, we can obtain these points by interval rounding according to the X-axis, and then assign values to these integer points by random method. Then, the corresponding value can be calculated at non-integer points through the numerical interpolation of two adjacent integers, so that a continuous curve can be obtained, namely the one-dimensional Perlin noise graph. Simply write a code to draw a coordinate axis, and draw the one-dimensional Perlin noise based on Line Renderer:

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class PerlinNoise : MonoBehaviour
{
    public int lineWight;

    //public List<Vector3> points;
    public GameObject posPre;
    public Dictionary<int.Vector3> points = new Dictionary<int, Vector3>();
    public LineRenderer line;

    public int interIndexMax = 100;

    private void Awake()
    {
        CreatePos();
        CreateLine();
    }
    // Draw the integer points corresponding to the numeric points
    void CreatePos()
    {
        for (int i = 0; i < lineWight; i++)
        {
            float num = Random.Range(0f.4f);

            Vector3 pointPos = new Vector3(i, num, 0);
            GameObject go = Instantiate(posPre, this.transform); go.transform.position = pointPos; points.Add(i, pointPos); }}// Interpolate between two adjacent integer points to get other positions
    void CreateLine()
    {
        int posIndex = 0;
        int interIndex;
        line.positionCount= interIndexMax * (points.Count - 1);
       	for (int i = 1; i < points.Count; i++)
        {
            interIndex = 0;
            while (interIndex< interIndexMax)
            {
                interIndex++;
                float posY = points[i - 1].y + (points[i].y - points[i - 1].y) * (interIndex / (float)interIndexMax);
                Vector3 pos = new Vector3(i - 1 + interIndex / (float)interIndexMax, posY, 0); line.SetPosition(posIndex, pos); posIndex++; }}}Copy the code

In the above code, we can see that a linear interpolation is performed between two adjacent integer points to find the specific curve between the two points. After running the code, we can see the following effect:

In the above one-dimensional Perlin noise generation, we obtained a continuous broken line based on linear interpolation, because the program will perform linear interpolation between two adjacent integer points to obtain the coordinates of the intermediate point. As a result, a straight line is obtained, and different interpolation intervals are used on the left and right sides of an integer point. As a result, the slopes of the curves on the two sides are different at the integer point, which finally causes the discontinuity of the one-dimensional curve generated by Perlin Noise at the integer point

To avoid the above situation and make the resulting Perlin Noise smoother and more natural, Ken Perlin recommends using: 3T2 −2t3{\ displayStyle 3t^{2}-2t^{3}} 3T2 −2t3 as an interpolation function of Perline Noise, In the latest version of the algorithm, the interpolation function is changed to 6T5 − 15T4 + 10T3 {\ displayStyle 6T ^{5} -15T ^{4}+ 10T ^{3}} 6T5 − 15T4 + 10T3

3T2 − 2T3 {\ displayStyle 3t^{2}-2t^{3}} 3T2 − 2T3 interpolation function display effect, we simply modify the interpolation method, update the line interpolation code:

 	// Interpolate between two adjacent integer points to get other positions
    void CreateLine()
    {
        int posIndex = 0;
        int interIndex;
        line.positionCount = interIndexMax * (points.Count - 1);
        for (int i = 1; i < points.Count; i++)
        {
            interIndex = 0;
            while (interIndex< interIndexMax)
            {
            	interIndex++;
                float posY = Mathf.Lerp(points[i - 1].y, points[i].y, InterpolationCalculation(interIndex / (float)interIndexMax));
                Vector3 pos = new Vector3(i - 1 + interIndex / (float)interIndexMax, posY, 0); line.SetPosition(posIndex, pos); posIndex++; }}}// Calculate the interpolation function
    float InterpolationCalculation(float num)
    {
        return 3*Mathf.Pow(num, 2)2 -*Mathf.Pow(num,3);
    }
Copy the code

In the above code, we simply encapsulate a function calculation formula, and then do a linear interpolation from the interval of two integer points to0,1.And the final curve is:

Compared with linear interpolation, the whole curve is significantly smoother, and since the interpolation function 3T2 −2t3{\displaystyle 3t^{2}-2t^{3}} 3T2 −2t3 has a slope of 0 at the corresponding coordinate point when x is 0 and 1, So the resulting interpolation curve is continuous at integer points, but still sharp at integer points, Therefore, in the latest Perlin Noise generation algorithm, the interpolation function is replaced with 6T5 − 15T4 + 10T3 {\ displayStyle 6T ^{5} -15T ^{4}+ 10T ^{3}} 6T5 − 15T4 + 10T3. The following figure shows the comparison of Noise curves obtained by the two curvilinear interpolation functions:

Blue curve: represents the noise curve obtained by 6T5 − 15T4 + 10T3 {\ displayStyle 6T ^{5} -15T ^{4}+ 10T ^{3}} 6T5 − 15T4 + 10T3
Red curve: represents the noise curve obtained by 3T2 −2t3{\ displayStyle 3T ^{2} -2T ^{3}} 3T2 −2t3

Because it’s so small, it’s not so obvious, so if WE zoom in on the X-axis, it’s pretty obvious, The slope of the curve obtained by interpolation 6T5 − 15T4 +10t3{\displaystyle 6T ^{5} -15T ^{4}+ 10T ^{3}} 6T5 − 15T4 + 10T3 is significantly less than 3T2 −2t3{\displaystyle 3T ^{2} -2T ^{3}} 3T2 − 2T3 interpolation function, as shown below:

Deduction of two-dimensional Perlin noise

Based on one-dimensional Perlin Noise, the generation of two-dimensional Perlin Noise is considered. Similarly, we need to select integer points of coordinates to give random values, and then adopt corresponding interpolation strategies according to the values of these integer points to obtain the values of those non-integer values. The whole process is divided into three parts:

Similar to one-dimensional Perlin Noise, two-dimensional Perlin Noise takes integer points for X-axis and Y-axis respectively

Create a three-dimensional coordinate system in the scene, with the plane composed of X axis and Z axis as the two-dimensional Berlin noise coordinate point, and the Y axis represents the value of each coordinate:

 public int posNumber;

    public GameObject posPre;

    public LineRenderer line1;
    public LineRenderer line2;
    public LineRenderer line3;
    private void Awake()
    {
        Coordinate();
    }

    void Coordinate()
    {

        line1.positionCount=posNumber;
        line2.positionCount=posNumber;
        line3.positionCount = posNumber;
        for (int i = 0; i < posNumber; i++)
        {
            GameObject goX = Instantiate(posPre, this.transform);
            goX.transform.position = new Vector3(i, 0.0);
            line1.SetPosition(i, new Vector3(i, 0.0));

            GameObject goY = Instantiate(posPre, this.transform);
            goY.transform.position = new Vector3(0, i, 0);
            line2.SetPosition(i, new Vector3(0, i, 0));

            GameObject goZ = Instantiate(posPre, this.transform);
            goZ.transform.position = new Vector3(0.0, i);
            line3.SetPosition(i, new Vector3(0.0, i)); }}Copy the code

After executing the code, it will look like the following:

After the establishment of a coordinate system, the basic point of Perlin Noise was selected from the integer points of the X and Y axes of the coordinate system. In order to avoid overlapping with the coordinate system, the coordinate points of X =0 and z=0 were avoided

After the selection of integer points is completed, Y value can be obtained by random function, so that the unique position can be determined in the three-dimensional coordinate system:

 // Gets the value of an integer point and instantiates an object at that position
    void CreatePoints()
    {
        for (int i = 0; i < v2.x; i++)
        {
            for (int j = 0; j < v2.y; j++)
            {
                float nub = UnityEngine.Random.Range(0, MaxNoise);
                GameObject go = Instantiate(itemPre, parent);
                go.transform.position = new Vector3(i+1, nub, j+1); items[i, j] = nub; }}}Copy the code

By executing the code above, we can generate integer points in the scene that can be used as reference points for later interpolation operations:

Free Angle:

Overlooking Angle:

After the above preparation, we come to the focus of two-dimensional Perlin Noise. How to obtain the y value of non-integer points by interpolation

Different from one-dimensional Berlin noise, which only needs one interpolation operation to get the corresponding number, two-dimensional Berlin noise needs to get the final result according to the numbers of the four nearest integer points around it, so we need to adopt some interpolation strategy to connect the four numbers

Similar to bilinear interpolation, Perlin Noise uses cubic interpolation to get the final result, as described in the aforementioned Wikipedia:

Simple said is, for A point in the last four of the rectangular coordinates, in the following figure, for E, need according to A, B, C, D four points of value to the interpolation, the interpolation of logic is the first point by point A and D of the value calculated by interpolation function F point value, and then point by point B and C value, the value of the g-spot is calculated, Finally, the final value is obtained by interpolation of G and F.

Compared with the calculation of the median value by one-dimensional Perlin Noise, two-dimensional Perlin Noise only performs two more interpolation operations, and the core code is simply changed:

    // Compute the interpolation of four adjacent integer points in a matrix
 	public void CreateGrid(int x,int y)
    {
        for (int i = 0; i < 11; i++)
        {
            for (int j = 0; j < 11; j++)
            {
                float interX = Mathf.Lerp(items[x, y], items[x + 1, y], InterpolationCalculation1(i/10f));
                float interY = Mathf.Lerp(items[x, y+1], items[x + 1,y+1], InterpolationCalculation1(i / 10f));
                float inter = Mathf.Lerp(interX, interY, InterpolationCalculation1(j/ 10f));
                GameObject go = Instantiate(itemPre, parent);
                go.transform.position = new Vector3(x+ i /10f+1, inter, y+ j/10f+1); }}}// Calculate the interpolation function
    float InterpolationCalculation1(float num)
    {
        return 6 * Mathf.Pow(num, 5) - 15 * Mathf.Pow(num, 4) + 10 * Mathf.Pow(num, 3);
    }
Copy the code

Execute the code to see a visualization of two-dimensional Perlin noise:

It can be seen from the above picture that the graphics created based on 2d Perlin Noise are very close to the natural terrain, which is why it can be applied to the terrain creation

Perfect Berlin noise

As mentioned earlier, Perlin noise is a pseudo-random algorithm, and every time the terrain is created, it should behave the same at the same coordinate point. However, in the above demonstration, the value of every integer point is generated by a random function, that is, every time the terrain is created, it is completely random

In front of the demonstration, completely random factors that affect the terrain only integer point corresponding numerical, if we have a kind of method, can be given the same value in a certain condition, then finally computed topography also should be the same in order to avoid such problems, Perlin Noise is put forward a solution, the initial value of a given integer point you can:

Although has given the array, but not to use the numerical directly, but after a certain rules of transformation eventually mapped to a set of range smaller gradient, this part is more complex to understand about gradient, so the above is not introduced to, just to simplify ideas to the interpretation of the specific algorithm ideas behind have introduced, the process is very interesting, Have a look if you are interested

In my world, a unique terrain data can be obtained from a simple string of seed data, and the lowest part of the logic is similar to the preset value processing of Berlin noise

Perlin noise algorithm thought

In the above demonstration, to avoid arcane mathematics, only the application level of the processing. For a theoretical understanding of the process, see the Java version of the source code provided by Ken Perlin:

public final class ImprovedNoise
{
    static public double noise(double x, double y, double z)
    {
        int X = (int)Math.floor(x) & 255.// FIND UNIT CUBE THAT
            Y = (int)Math.floor(y) & 255.// CONTAINS POINT.
            Z = (int)Math.floor(z) & 255;
        x -= Math.floor(x);                                // FIND RELATIVE X,Y,Z
        y -= Math.floor(y);                                // OF POINT IN CUBE.
        z -= Math.floor(z);
        double u = fade(x),                                // COMPUTE FADE CURVES
               v = fade(y),                                // FOR EACH OF X,Y,Z.
                w = fade(z);
        int A = p[X] + Y, AA = p[A] + Z, AB = p[A + 1] + Z,      // HASH COORDINATES OF
            B = p[X + 1] + Y, BA = p[B] + Z, BB = p[B + 1] + Z;      // THE 8 CUBE CORNERS,

        return lerp(w, lerp(v, lerp(u, grad(p[AA], x, y, z),  // AND ADD
                                     grad(p[BA], x - 1, y, z)), // BLENDED
                             lerp(u, grad(p[AB], x, y - 1, z),  // RESULTS
                                     grad(p[BB], x - 1, y - 1, z))),// FROM 8
                     lerp(v, lerp(u, grad(p[AA + 1], x, y, z - 1),  // CORNERS
                                     grad(p[BA + 1], x - 1, y, z - 1)), // OF CUBE
                             lerp(u, grad(p[AB + 1], x, y - 1, z - 1),
                                     grad(p[BB + 1], x - 1, y - 1, z - 1))));
    }
    static double fade(double t) { return t * t * t * (t * (t * 6 - 15) + 10); }
    static double lerp(double t, double a, double b) { return a + t * (b - a); }
    static double grad(int hash, double x, double y, double z)
    {
        int h = hash & 15;                      // CONVERT LO 4 BITS OF HASH CODE
        double u = h < 8 ? x : y,                 // INTO 12 GRADIENT DIRECTIONS.
               v = h < 4 ? y : h == 12 || h == 14 ? x : z;
        return ((h & 1) = =0 ? u : -u) + ((h & 2) = =0 ? v : -v);
    }
    static final int p[] = new int[512], permutation[] = { 151.160.137.91.90.15.131.13.201.95.96.53.194.233.7.225.140.36.103.30.69.142.8.99.37.240.21.10.23.190.6.148.247.120.234.75.0.26.197.62.94.252.219.203.117.35.11.32.57.177.33.88.237.149.56.87.174.20.125.136.171.168.68.175.74.165.71.134.139.48.27.166.77.146.158.231.83.111.229.122.60.211.133.230.220.105.92.41.55.46.245.40.244.102.143.54.65.25.63.161.1.216.80.73.209.76.132.187.208.89.18.169.200.196.135.130.116.188.159.86.164.100.109.198.173.186.3.64.52.217.226.250.124.123.5.202.38.147.118.126.255.82.85.212.207.206.59.227.47.16.58.17.182.189.28.42.223.183.170.213.119.248.152.2.44.154.163.70.221.153.101.155.167.43.172.9.129.22.39.253.19.98.108.110.79.113.224.232.178.185.112.104.218.246.97.228.251.34.242.193.238.210.144.12.191.179.162.241.81.51.145.235.249.14.239.107.49.192.214.31.181.199.106.157.184.84.204.176.115.121.50.45.127.4.150.254.138.236.205.93.222.114.67.29.24.72.243.141.128.195.78.66.215.61.156.180
   };
    static { for (int i=0; i< 256 ; i++) p[256+ i] = p[i] = permutation[i]; }}Copy the code

The whole process is similar to the above visual demonstration, but some knowledge is omitted in the understanding of the principle. It is added here for readers to learn and understand. Starting from the code, it is mainly divided into the following steps:

Processing transformations for coordinates
Gets the hash value of an integer point based on the given array
Gets the gradient from the hash value of the integer points around it
The corresponding value of the current point is obtained by interpolation

First of all, the coordinate point processing is to get the coordinate value of the integer points around it according to the integer part of the current passed coordinate, and the decimal is used as the parameter value of interpolation positioning in a basic unit:

		int X = (int)Math.floor(x) & 255.// FIND UNIT CUBE THAT
            Y = (int)Math.floor(y) & 255.// CONTAINS POINT.
            Z = (int)Math.floor(z) & 255;
        x -= Math.floor(x);                                // FIND RELATIVE X,Y,Z
        y -= Math.floor(y);                                // OF POINT IN CUBE.
        z -= Math.floor(z);
Copy the code

The code above retrieves two sets of data using the floor method (rounded down) and a bit operation:

(X.Y.Z) : Mod 256 is used to obtain the hash value of integer points
(x.y.z) : Subtracts itself rounded down, which is simply the mapping from 0 to 1 of the nearest square unit

Here is a brief introduction to bit operation, which is essentially converted to binary for bit operation. The bit operation of & in Perlin Noise is essentially for remainder. Since it is an operation between bits, the operation efficiency is very high.

& represents and operation, and its calculation rules are as follows:

1&1=1 1&0 =0 0&1 =0 0&0 =0Copy the code

So in this case, an integerxwith255for&Operation, assuming the integers are257, the calculation process is:

In the above procedure, the bits beyond 255 are returned to zero by the sum operation, while the bits less than or equal to 255 are equal to themselves after the sum operation to achieve the effect of remainder

The purpose of this step is to make a monomial arrangement of coordinate points in two dimensions or higher, so that the rectangular units of coordinate points can correspond to monomial arrays:

        int A = p[X] + Y, AA = p[A] + Z, AB = p[A + 1] + Z,      // HASH COORDINATES OF
            B = p[X + 1] + Y, BA = p[B] + Z, BB = p[B + 1] + Z;      // THE 8 CUBE CORNERS,


    static final int p[] = new int[512], permutation[] = { 151.160.137.91.90.15.131.13.201.95.96.53.194.233.7.225.140.36.103.30.69.142.8.99.37.240.21.10.23.190.6.148.247.120.234.75.0.26.197.62.94.252.219.203.117.35.11.32.57.177.33.88.237.149.56.87.174.20.125.136.171.168.68.175.74.165.71.134.139.48.27.166.77.146.158.231.83.111.229.122.60.211.133.230.220.105.92.41.55.46.245.40.244.102.143.54.65.25.63.161.1.216.80.73.209.76.132.187.208.89.18.169.200.196.135.130.116.188.159.86.164.100.109.198.173.186.3.64.52.217.226.250.124.123.5.202.38.147.118.126.255.82.85.212.207.206.59.227.47.16.58.17.182.189.28.42.223.183.170.213.119.248.152.2.44.154.163.70.221.153.101.155.167.43.172.9.129.22.39.253.19.98.108.110.79.113.224.232.178.185.112.104.218.246.97.228.251.34.242.193.238.210.144.12.191.179.162.241.81.51.145.235.249.14.239.107.49.192.214.31.181.199.106.157.184.84.204.176.115.121.50.45.127.4.150.254.138.236.205.93.222.114.67.29.24.72.243.141.128.195.78.66.215.61.156.180
   };
    static { for (int i=0; i< 256 ; i++) p[256 + i] = p[i] = permutation[i]; }
Copy the code

In the code, the four points in the three-dimensional case are listed, and at the same time, the following four points are converted in the subsequent calculation. Through the code, it can be seen that the array value corresponding to an integer point is hashed through the three axes of coordinates

Suppose there is A coordinate point A whose coordinates are (x,y,z), then the code structure of the data obtained from the array through hash transformation is as follows:

int posA=p[p[p[x]+y]+z];
Copy the code

And since the array is 0 to 255 numbers, adding subscripts in this way will obviously cause the array to be out of bounds. So Ken Perlin chose to double the array size to avoid this problem

After getting the values from the array, we need to get the dot product of the gradient corresponding to the integer points and the distance vector. In this process, we need to understand that the gradient corresponding to the integer points is not calculated, but based on the number of the array to select the corresponding gradient from some given gradient

So how to get the unique gradient corresponding to a given number? Ken Perline used bit-flipping operation in the algorithm to get the final gradient. In the code case:

static double grad(int hash, double x, double y, double z)
    {
        int h = hash & 15;                      // CONVERT LO 4 BITS OF HASH CODE
        double u = h < 8 ? x : y,                 // INTO 12 GRADIENT DIRECTIONS.
               v = h < 4 ? y : h == 12 || h == 14 ? x : z;
        return ((h & 1) = =0 ? u : -u) + ((h & 2) = =0 ? v : -v);
    }
Copy the code

By converting the value obtained by the previous hash transformation and the decimal coordinates of the desired point, the weight of the desired integer point at the current gradient point is obtained

There is a mathematical concept in this section: gradient

A gradient means that the directional derivative of a function at that point maximizes along that direction. To put it simply, a two-dimensional function can be used to represent a surface in three-dimensional space. If y is specified to remain constant, a curve that changes as x changes can be obtained. The function of this curve is the partial derivative of the two-dimensional function, and the slope at any point on this curve can be represented by a vector, where the direction is positive or negative, and the length is magnitude. Based on this idea, we can also have the vector of the slope of the partial derivative at that point with respect to y, and the sum of the two vectors is the gradient at that point:

For more details on gradient vectors, check out this video: Go

The last step is to interpolate all integer point gradients around the current point using a continuous monotone function of 1 at 0, 0 at 1 and 0.5 at 0.5, This is also why 6T5 − 15T4 + 10T3 {\ displayStyle 6T ^{5} -15T ^{4}+ 10T ^{3}} 6T5 − 15T4 + 10T3 and 3T2 −2t3{\displaystyle 3t^{2}-2t^{3}} 3T2 −2t3 is used as an interpolation function, as shown in the figure:

The curves between 0 and 1 are basically the same, but 6T5 − 15T4 + 10T3 {\ displayStyle 6T ^{5} -15T ^{4}+10t^{3}} 6T5 − 15T4 + 10T3 are more flat near the end points

Terrain create logic code

After the extensive introduction to Perlin Noise’s fundamentals and code structure, it’s easy to see how it can be used for terrain creation.

And forUnityIn terms of, it’s even easier to encapsulate a two-dimensionalPerlin NoiseGenerate method, we only need to call when using, of course, this is not as flexible as their own to write, but for beginners can be faster to use:

As shown in the figure, you only need to pass in the coordinate value to get the corresponding value. However, it should be noted that the circular range of this method is very small. If large coordinates are directly passed in, it is easy to cause the repetition of terrain. Therefore, we try to make an expanded mapping of the range when using the method.

// Get height data set from terrain range
    public void GetPerlinNoise(Vector3Int range)
    {
        
        for (int i = 0; i < range.x; i++)
        {
            for (int k = 0; k < range.z; k++)
            {
                Vector3Int v3i = GetItemID(i, 0, k);
                float sizle = Mathf.PerlinNoise(v3i.x * perlinSizle, v3i.z * perlinSizle)* terrainCom;
                int height = startPos.y+(int)(range.y * sizle);
                terrainLimitNums.Add(newVector2Int(v3i.x, v3i.z), height); }}}Copy the code

With the height data in hand, you can perform a simple create logic to generate a rough terrain structure based on the height data, and modify the CreateMap and CreateGrid methods:

	public void CreateMap(Vector3Int range)
    {
        for (int j = 0; j < range.y; j++)
        {
            for (int i = 0; i < range.x; i++)
            {
                for (int k = 0; k < range.z; k++) { Vector3Int v3i = GetItemID(i, j, k); CreateGrid(v3i); }}}}public void CreateGrid(Vector3Int v3i)
    {             
        if (v3i.y <= terrainLimitNums[new Vector2Int(v3i.x,v3i.z)])
        {
                GridInst(v3i,false);             
        }
        else{ GridInst(v3i); }}Copy the code

In the code above, the first can be carried to the entire area of the lattice traversal, then for each grid coordinates Y value compared with the height data, if less than the height of that point, the incoming parameters false execute judgment, and if is greater than the height of that point, the will that point in the air, not instantiate objects, the processing logic behind as follows:

    public void GridInst(Vector3Int v3i,bool isNull=true)
    {       
        if (isNull)
        {
            items.Add(v3i, null);
            return; } Item itemCo = Instantiate(item, parentTran); itemCo.transform.position = v3i; ItemCreateEvent? .Invoke(itemCo,v3i); items.Add(v3i, itemCo); }Copy the code

ItemCreateEvent is a delegate event that initializes the state of the grid. The script for creating the grid can be written before the map is created.

    // Write a logic based on the incoming height data set to create a simple layered terrain structure
    public void CreateItemEvent(Item item,Vector3Int v3i)
    {
        item.itemID = v3i;

        if (v3i.y == startPos.y)
        {
            item.type = ITEM_TYPE.Bedrock;
        }
        else if (v3i.y == terrainLimitNums[new Vector2Int(v3i.x, v3i.z)])
        {
            item.type = ITEM_TYPE.Cold;
        }
        else
        {
            item.type = ITEM_TYPE.Ston;

        }
        item.Register();
    }
Copy the code

In this way, a simple version of the map generation script is completed, which is executed in the editor after the compilation of the execution call part of the code. You can see the general shape of the generated terrain, as shown in the figure:

A side view of a single terrain:

Free Angle terrain shape:

At the same time, the flatness of the terrain can be controlled by controlling the size of perlinSizle. For example, when perlinSizle is reduced, the shape of the terrain is:

conclusion

In this article, the Perlin Noise algorithm is used to make a simple terrain effect. The whole code structure is very simple, mainly to help beginners understand the basic principle of learning Perlin Noise, I will try to update later, hope to make a complete dynamic map loading case

If you happen to be interested in learning, I’ll cover localized storage and query of map data in my next article

Unity dynamic Grid map generation: Terrain creation based on Perlin Noise

Preface:

Map creation logic

I. Create regional grid map:

2. Create undulating terrain

1. Failed Scheme:

2. Create terrain based on Perlin Noise

conclusion

Related Posts

Box-sizing property for CSS3

The route directly entered in the VUE address bar is invalid

JavaScript basic data types