Original Link: https://forum.cocos.org/t/topic/157116
Author: GreenPack
About Noise Generation Algorithm
Big is strong, and big is beautiful! Who doesn’t like big things?
The first time I encountered the concept of procedurally generating an infinitely large world was through an article titled “how-does-no-mans-sky-generate-the-universe”.
The article mentioned using an irrational number that exists in nature and contains infinite information to construct the world. Yes, that figure is π!
At that time, I was still a novice, only vaguely understanding that procedural world generation uses π, but had no idea how it actually worked until I later studied shaders and read the classic book: thebookofshaders.
This e-book contains a lot of content, which I won’t elaborate on here. In short, it explains how to procedurally generate noise. Here, I will simply tell you the core points of procedural noise generation in three steps:
1. Random Numbers with One-Step Calculation
First, setting aside complex concepts, to generate random content, the first step is to generate a random number. No, wait, in the process of procedurally generating a world, we need a large number of random numbers, and these random numbers must be uniquely determined by their coordinates.
The book thebookofshaders describes the calculation of random number generation and presents it in a way that can be viewed in real-time using web elements, which is very high-end. However, regarding the first step of random numbers, perhaps due to translation issues, I personally feel that the book does not explain it very well. Below, I will combine images to explain my understanding. First, look at the image in the noise chapter:
Looking at the code, the input value x undergoes a fract operation, which means taking the fractional part. We can understand this as dividing the curve into infinite blocks with a period of 1.
Then, looking back at the image in the random chapter:
Here, the input x value undergoes a sin operation.
Alright, tell me loudly, what is the period of sin?
This is the core operation. A curve with a period of 2π, where we take a value every unit 1, forms a sequence of values. Mathematically, this guarantees that the sequence has no periodicity. So, it is a random sequence.
2. Smooth Transition, One-Dimensional to Two-Dimensional
In the first step, we obtain some discrete random numbers, but in reality, the values between two very close coordinates are also very close. In other words, noise is continuous.
Transforming a discrete sequence into a continuous curve is simple, just smooth the transition between two points:
Usually, the common smoothstep algorithm is used for smooth transitions. The book thebookofshader also mentions the quartic Hermite function used in simplexNoise.
I haven’t researched much in this area, but I have a small personal experience: the smoothstep function has a slope of 0 at the endpoints. This means that the curve above will have a “flat” every unit 1.
After the smooth transition, upgrade the one-dimensional curve to a two-dimensional noise map. There are many tutorials online about this, so I won’t elaborate here.
3. Iteration and Fractals
Among the technologies related to noise generation, there is something that sounds very impressive: Fractal Brownian Motion (FBM). Don’t be intimidated by it. In simple terms, it just uses a for loop to superimpose the waves obtained in the previous steps.
Brownian motion refers to the continuous and irregular motion of particles suspended in a liquid or gas. A fractal is a mathematical concept. You might have forgotten, but a quick example: snowflake crystals! A fractal means that when magnified, the small parts resemble the large shape.
How to create Fractal Brownian Motion? Simple, just reduce the amplitude and increase the frequency of the curve obtained in the previous steps, and iterate multiple times.
This introduces another term: octaves. This is a musical concept. Here, the number of iterations in FBM is referred to as the number of octaves.
Cocos Creator Code to Generate Mesh
1. Code Interface
Cocos Creator provides an interface for code to generate meshes. Refer to the official documentation for details. Here is a simple code example.
let mesh: Mesh = utils.MeshUtils.createMesh({
colors: [1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1],
positions: [0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1],
indices: [0, 3, 2, 0, 2, 1],
minPos: v3(0, 0, 0),
maxPos: v3(1, 1, 1),
// attributes: [
// new gfx.Attribute(gfx.AttributeName.ATTR_POSITION, gfx.Format.RGB32F),
// ],
});
Parameter Explanation:
- positions: Vertex coordinate array. The length must be a multiple of 3, with every three values representing the x, y, z of one vertex.
- colors: Vertex color array. The length must be a multiple of 4, with every four values representing the rgba of one vertex (color values are normalized).
- indices: Indices array for reusing vertex data. Each three values form a triangle face.
- minPos & maxPos: The start and end points of the bounding box. Can be omitted and let the mesh calculate itself, but this will be computationally intensive.
Note: When procedurally generating meshes, ensure all triangle faces are in clockwise order when viewed from the camera. This is because most 3D engines differentiate between the front and back of faces and usually have backface culling enabled by default. The differentiation is based on the clockwise or counterclockwise order of the vertices.
- attributes: Vertex data format. Can modify the default vertex data format. The default vertex data format for procedural meshes is defined in create-mesh.ts:
const _defAttrs: Attribute[] = [
new Attribute(AttributeName.ATTR_POSITION, Format.RGB32F),
new Attribute(AttributeName.ATTR_NORMAL, Format.RGB32F),
new Attribute(AttributeName.ATTR_TEX_COORD, Format.RG32F),
new Attribute(AttributeName.ATTR_TANGENT, Format.RGBA32F),
new Attribute(AttributeName.ATTR_COLOR, Format.RGBA32F),
];
The five default vertex data types are all rgba32f. If the precision requirement for a value is not high, you can change it to reduce bandwidth (e.g., changing the color value).
2.View Mesh
We use the executeInEditMode decorator to decorate the script class, allowing the script to run in the editor, making it easier to observe the generated mesh.
To handle the issue of repeatedly creating meshes after modifying the code, we generate a child node and place the mesh on the child node, performing a removeAllChildren operation before generating.
@ccclass('procedural1')
@executeInEditMode(true)
export class procedural1 extends Component {
start() {
this.node.removeAllChildren()
let node = new Node()
this.node.addChild(node)
let meshRenderer:MeshRenderer = node.addComponent(MeshRenderer);
let mesh:Mesh = utils.MeshUtils.createMesh({
colors:[1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1],
positions:[0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1],
indices:[0, 3, 2, 0, 2, 1],
minPos:v3(0, 0, 0),
maxPos:v3(1,1,1),
// attributes: [
// new gfx.Attribute(gfx.AttributeName.ATTR_POSITION, gfx.Format.RGB32F),
// ],
});
meshRenderer.mesh = mesh;
meshRenderer.onGeometryChanged();
}
}
Now, we can see our mesh in the editor. Selecting it will show a square box frame, which is the bounding box we defined.
Move the camera below to look up, and the mesh disappears because the view is now from the back of the mesh. Interested users can try changing the vertex index order or, after adding materials later, modify front and back culling to deepen understanding of the front and back culling mechanism.
3. Hexagonal Mesh Structure
Constructing a mesh using two triangles to form a square is the simplest, but such a mesh is inefficient. To maximize the area with the same number of vertices, using equilateral triangles is the best choice. When equilateral triangles are put together, they form countless regular hexagons. Naturally, I used a hexagonal mesh structure.
For hexagonal meshes, you can refer to this article, which contains a wealth of information and almost every image is interactive: “Hexagonal Grid Reference”.
Article link: 六角网格大观 | indienova 独立游戏
The content in the article is extensive, so I won’t elaborate here. I’ll just briefly mention one key point about the calculations related to hexagonal grids: cubic coordinates.
Cubic coordinates, as the name suggests, have three axes: x, y, and z. To see how three axes can be used in a plane, just look at this screenshot.
Imagine we have many cubic blocks stacked in space. Now, look at them from an angled perspective and make a cross-sectional cut:
Hexagonal grids and cubic coordinates become clear.
4. Normalizing Hexagonal Vertices to Center Points
The article above includes almost all the methods related to hexagonal grid calculations, but I encountered a problem when constructing hexagonal grids: calculating the coordinates of hexagonal vertices (relative to the center point, the six corners around a hexagon) is easy, but handling reusability and de-duplication is not straightforward.
After some thought and drawing, I figured out a way to normalize vertices to center points:
As shown, the vertices of a large hexagon can be considered as the center points of smaller hexagons with a size of 1/3.
We use a two-level map to store the index values corresponding to the vertices, using the x and y of the cubic coordinates as keys (in cubic coordinates, x + y + z = 0, so only xy values are needed; details can be found in the hexagonal grid reference).
To show the shape of hexagonal grids, we color all the center vertices black and the corner vertices white.
addPoint(aid: Vec3, a: number, isCenter: boolean = false) {
let map = this.idxMap.get(aid.x);
if (!map) {
map = new Map();
this.idxMap.set(aid.x, map);
}
if (map.has(aid.y)) {
return map.get(aid.y);
}
let pos = HexUtils.getCellPositionWithAxisID(aid, a);
this.positions.push(pos.x);
this.positions.push(0);
this.positions.push(pos.y);
if (isCenter) {
this.colors.push(0);
this.colors.push(0);
this.colors.push(0);
this.colors.push(0);
} else {
this.colors.push(1);
this.colors.push(1);
this.colors.push(1);
this.colors.push(1);
}
let idx = this.positions.length / 3 - 1;
map.set(aid.y, idx);
return idx;
}
5.Expansion
Define a boundary value N and loop to construct the hexagonal grid:
let N = 5;
let a = 1;
for (let cx = -N; cx <= N; cx++) {
for (let cy = Math.max(-N - cx, -N); cy <= Math.min(N, -cx + N); cy++) {
let cz = -cx - cy
let center = v3(cx * 3, cy * 3, cz * 3)
let idx0 = this.addPoint(center, a / 3, true)
let offset = v3(1, 1, -2)
let v1 = v3()
Vec3.add(v1, center, offset)
let idx1 = this.addPoint(v1, a / 3)
let v2 = v3()
for (let i = 0; i < 6; i++) {
// rotate 60 degrees
offset.set(-offset.z, -offset.x, -offset.y)
Vec3.add(v2, center, offset)
let idx2 = this.addPoint(v2, a / 3)
this.indices.push(idx0)
this.indices.push(idx1)
this.indices.push(idx2)
v1.set(v2)
idx1 = idx2
}
}
}
6.Rotation
Normalizing the center points of hexagons to smaller hexagons is simply done by multiplying the coordinates by 3. For corner vertices, we find one point (offset (1, 1, -1) from the center point), and then use a very useful trick mentioned in the hexagonal grid reference to get the cubic coordinates of the cell rotated by 60 degrees:
Apply a material and shader, multiplying the output in the shader by the vertex color, and the effect appears:
Alright, you’ve learned about noise and procedural meshes. Now, just add some details, and you can construct procedural terrain, provided your machine has theoretically infinite performance.
More Details
1.LOD
LOD (Level of Detail) is a common technique in 3D rendering. Typically, we see this term in two places: one is model LOD. It involves creating high, medium, and low poly models (or more), and dynamically replacing models of different precision based on the distance from the camera to ensure high visual quality up close and low performance cost at a distance.
Another common place is in certain shaders, where a LOD value is defined to use different shaders on different performance devices to accommodate performance differences.
Here, we use a rough LOD concept. Since this demo is viewed from a first-person perspective, using high-precision meshes near the character and low-precision meshes farther away suffices.
We use the terminology from FBM, representing levels with octaves. Each level’s hexagonal edge length is twice that of the previous level. This way, we can construct a very large map with a relatively small number of meshes.
let octaves = 5
let N = 5;
let n = N / 2
let a = 1;
for (let oct = 0; oct < octaves; oct++) {
let mul = Math.pow(2, oct)
for (let dx = -N; dx <= N; dx++) {
for (let dy = Math.max(-N - dx, -N); dy <= Math.min(N, -dx + N); dy++) {
let dz = -dx - dy;
if (oct > 0 && Math.abs(dx) < n && Math.abs(dy) < n && Math.abs(dz) < n) {
continue;
}
}
}
}
2.Static Meshes & Dynamic Meshes
In the process of attempting procedural terrain, I tried using Cocos Creator’s dynamic meshes, with an official example to reference.
For a procedurally generated boundless map, constant terrain updates are inevitable, so theoretically, dynamic meshes would be more efficient. However, when increasing the mesh quantity, I encountered an error:
I suspect it’s due to reaching the upper limit of mesh data.
Furthermore, even disregarding the mesh limit, updating a very large mesh with many vertices involves significant computational overhead.
After several attempts, I tried:
Mehthod 1：Using Shaders for Coordinate Offset
Set the entire mesh’s y-coordinates to 0, and compute the actual height in the shader. The benefit is no need to update the mesh; you just move a flat mesh, and the shader will display the height accordingly.
Disadvantage 1: This method is only suitable for displaying terrain. When we need units to move on the terrain, we need to obtain the terrain height, which requires height calculations on the CPU side. After testing, I found that the height calculated in real-time in the shader can significantly deviate from the value calculated on the CPU side due to precision issues. This deviation becomes critical on a very large map.
Disadvantage 2: Calculating the entire height in the shader means that the FBM octaves need to be very high for an extremely large map, resulting in a huge computational load.
Method Two: Using Tiles for Construction
Referring to 2D tile maps, we can use numerous tiles to piece together a large map. Tiles can be batched rendered using GPU instancing. We calculate the height of each tile on the CPU side, then add vertex offset corrections in the shader.
Issue with Tiling: I used hexagons as tile units, calculating each hexagon’s coordinates and using the noise value of the hexagon’s center to determine its height. Then I calculated the height and normals of the six corner vertices and passed these to the GPU using GPU instancing attributes for offset alignment in the shader. However, I encountered an error after trying several times, concluding that the upper limit for GPU instancing attribute data is four vec4s (i.e., a mat4 matrix).
Therefore, I had to split all hexagons into three quadrilaterals (only constructing one mesh and rotating it three times to form a hexagon).
3. Using Noise Maps
Replace the FBM calculation in the shader with noise map sampling to reduce the computational load.
Combine vertex normals with the sampled FBM normals, using a simple half-Lambert model to calculate lighting.
4. Shading
There are generally two ways to shade procedural terrain: tri-planar texture sampling and color gradients. Tri-planar sampling involves sampling textures from the x, y, and z directions and blending the three samples based on the current point’s normal.
Without tri-planar sampling, using a single direction (e.g., sampling textures using the xz vector from an overhead view) will result in noticeable stretching on steep slopes.
Another simple method is to use pure colors. However, to show different terrains, we should use a color gradient rather than a single color.
Here is a commonly used function from Shadertoy authors:
vec3 palette(in float t, in vec3 a, in vec3 b, in vec3 c, in vec3 d) {
return a + b * cos(6.28318 * (c * t + d));
}
6.28318 is 2π; t is a parameter between 0 and 1 (it’s fine if it exceeds this range as cos will handle it); the abcd parameters control the rgb color curves. You can use this webpage to adjust the gradient you want and then use the parameters.
Article link: http://dev.thi.ng/gradients/
After shading, add some snow to higher elevations. Snow accumulation can be handled by calculating the angle between the normals and the vertical direction; the flatter the area, the more snow it accumulates.
Define a snow line based on height; snow only appears above a certain altitude.
Add some randomness to the snow line using our noise map.
float snowHeightValue = smoothstep(40.0, 50.0, v_position.y + texture(mainTexture, p * 0.1).r * 10.0);
float s1 = clamp(1.0 - snowHeightValue, 0.0, 1.0);
float snowValue = smoothstep(s1, s1 + 0.002 / (s1 + 0.1), dot(vec3(0.0, 1.0, 0.0), n)) * 0.5 + 0.5;
5.Moveing Updates
We need to update the terrain within our view as the character moves. Because the terrain is large, we need to achieve this with minimal changes.
Using the concept of LOD, we can update the mesh only when necessary.
Here’s a simple example to illustrate:
As the character moves, constantly determine the character’s street;
When the character’s street changes, update the street mesh;
When updating the street mesh, if the city changes, update the city mesh;
When updating the city mesh, if the province changes, update the province mesh;
When updating the province mesh, if the country changes, update the country mesh.
We update the mesh according to our hierarchical octaves.
onCenterChanged() {
for (let i = 0; i < HexConfig.octaves; i++) {
if (!this.checkCellChange(i)) {
break;
}
}
}
Add a simple direction control UI to move the character; these basic codes are omitted.
At this point, we can happily stroll through our procedural world. After completing this step, I also implemented an important optimization feature.
6.Shared Nodes
Although we use LOD, each hexagon has 3 nodes, resulting in a significant number of meshes on the map. This causes a noticeable delay during initialization. I recalled a forum post about shared nodes:
Article link: 【性能优化】共享节点-动效复用方案 - Creator 2.x - Cocos中文社区
In summary, shared nodes do not create actual nodes but create one node plus n-1 self-defined objects. These objects contain all the rendering differences.
Using this method, we can reduce the time consumption when creating a large number of nodes. However, that article is based on 2.x, and there’s no direct relation to our 3.x model sharing.
I spent three days and nights reading the source code and finally came up with a roughly working shared node solution for 3.x. The code isn’t particularly special and is not well encapsulated, but the basic principle is that Cocos Creator’s MeshRenderer automatically creates a model after assigning a mesh. This model is the rendering target.
The model has node and transform variables pointing to the current node, which will be used for the node’s matrix information during rendering.
I did an experimental scene, constructing 10,000 nodes and using shared nodes, significantly reducing the time spent in the editor.
There’s also some improvement on the PC web:
Unexplored Concepts
Due to space and time constraints, this article ends here. However, there are still many things to explore in procedural terrain generation. Finally, I list some ideas and clues I haven’t had the time or energy to explore further. Feel free to try these out:
-
Using height + humidity to define area types: Details can be found in the following article:
Article link: 多边形游戏地图的生成 #2 | indienova 独立游戏 -
Reducing at least half the mesh based on the character’s viewpoint
This is quite doable, but I haven’t had the time. Writing this article has taken two to three weeks. -
Procedural Sky
This is a huge topic. Done well, it can create incredibly dreamy effects. Check out the effects of various celestial bodies and starry skies on Shadertoy. Integrating these into a procedural world’s sky should be quite stunning. -
Map Creatures and Items
Using noise maps to get a random value for the current point, then determining what creature or item exists at that point. Technically simple and very practical for actual games. -
Time Changes
Thebookofshaders mentions using FBM to distort FBM, creating a dreamlike, twisting fog effect. Similarly, we can add a time parameter to the terrain, making it change slowly over time. An ever-changing infinite world! -
Better Noise Maps
I spent two days reading IQ’s articles. I always wanted to take a closer look, but never had the time (definitely not afraid of reading English). I’ve gained a bit, but no practical results yet. Hopefully, one day I can achieve terrain rendering at the level of the masters:
- Stylization
The terrain rendering in this example is realistic, but due to limited technical ability, it lacks realism. Often, procedural terrain generation can avoid those difficulties and not always strive for physical realism, resulting in more visually appealing effects. Here is an example of procedural terrain with a stylized approach that I found while researching:
Conclusion
Finally, I wish Cocos all the best and hope that all developers can create games they are satisfied with! In a few days, I plan to organize the demo and upload it to the Cocos Store, hoping it will help those who are interested.