Mountain meets procedural content generation

Made by: Terrence Wemer

Introduction

Mountains within games, people might be able to name a few such as the Death mountain in Zelda Breath of the wild, mount Chiliad in Grand Theft Auto 5, The Throat of the world in Skyrim or the entire game of Celeste which takes place on mount Celeste. All of the mountains mentioned above have a predefined shape of the terain and placement of structures within the environment. In this post I will be exploring how I can implement PCG(procedural content generation) within meshes. The goal is to create an environment that adapts to the terain instead of the norm where everything is pre defined.

Table of content

• Introduction
• Plan of action
  – My original plan
  – Actual proces
• Meshes
  – Perlin noise
• Path finding (A*)
• Environment
  – Trees
  – Textures
  – A path to the top
• Optimization
• Sources

Plan of action

My original plan:
Within the past weeks we have had a total of 6 workshops. 3D meshes, shaders, multiplayer, performance, Game design and PCG. I instantly gravitated towards PCG because I thought this was the most interesting subject. After thinking for a while I had 3 ideas left:
– A game which takes place inside a maze that a player can complete with the use of a surround sound system.
– A custom created world map with villages and obstacles.
– A realistic looking mountain that would generate at random after given some basic input on shape and looks.

After some debating I decided to go with the mountain idea. My plan was to start by making a mesh, implement something called Perlin Noise to add random levels of height and after that make a path finding algorithm to make a path leading to the top of the mountain.

Actual process:
I started out making a basic terrain using techniques I learned from the Mesh workshop we had earlier. After creating a basic mesh i implemented Perlin noise. When implemented it didn’t look up to standard so extra features from Perlin noise including Frequency, Octaves and Amplitude were introduced. After this proces I did research on path finding methods and landed with A*. When path finding was finished I made spawn-able trees which shouldn’t be walk able. After that was finished I added textures for the mountain to make it realistic and finally added a path from a chosen point to the top of the mountain.
During and after the individual parts I invested some time in optimizing for performance. There will be mentions of this along the way and at the end.

Meshes

With the workshop knowledge fresh in memory I started out by creating a mesh. Meshes exist out of vertices and triangles. By giving the grid a size for the amount of vertices we can give a triangle 3 vertices as its shape and a quad 2 triangles. Giving 1 quad a total of 6 vertices.
Example of how vertices are assigned.

int v = 0;
for (int x = 0; x <= gridsizeX; X++)
{
   for (int Y = 0; Y <= gridsizeY; Y++)
{
     newVertices[v] = new Vector3((x), map[X,Y] + (mapheight * -Vector2.Distance(middleGrid, currentVertex)), (Y));
     v++;
     }
}

The user has input in how large the mesh should be. Therefor gridsizeX and gridsizeY will be public variables.

Perlin Noise
With the basics of a mesh done I could start shaping it the way i wanted to. the best method I could find was by use of Perlin Noise. Perlin noise is a common method where a 2d map is made and filled with values between 0 and 1 where 0 is black and 1 is white with everything in between being a mix of them. This value will be one of the bigger impacts on the height of the vertices.

Now that a Noise map had been implemented I wanted to give it a bit more of a mountain feeling. By calculating how far a vertex is from the middle point and lowering a vertex the further it is we get quite the interesting results.

Although this doesn’t look too bad a lot can still be done to make the shape way better. You see Perlin noise can easily be manipulated within code. some of such manipulations are Amplitude, Frequency and Octaves.
Amplitude is used to asign the basic height of the terain. Whenever the amplitude value is raised all the height values will be multiplied by that amount.
Frequency is used to determine how much noise you want in a certain area. When the Frequency value is low there wil be a smaller density of Noise within your noise map and vice versa.

Lastly Octaves, to put it simply Octaves are the amount of layers of Perlin noise stacked on top of each other. The reason you stack them ontop of each other is so you can have different frequency’s and Amplitudes stacked on top of each other with different levels of how much it will be implied. The higher the value of Octaves the more small influence there will be within a Noise map.
All these functions together with a random offset on the noise map wil give a nice basic shape of a random generated mountain each time when booted.

When all implemented together the code looks like the following:

perlinHeight = Mathf.PerlinNoise(frequency * (X + vertexOffset),
                                 frequency * (Y + vertexOffset));
perlinHeight += (1 / octaveInfluence) * Mathf.PerlinNoise(frequency * octaveInfluence * (X + vertexOffset),
frequency * octaveInfluence * (Y + vertexOffset));
map[X, Y] = (float)Math.Pow(perlinHeight * amplitude, 1.00);

Now that we have a random shape can move into the next step: Pathfinding

Pathfinding

The next part in the proces is creating a pathfinding algorithm. The reason for this is because within nature there is almost no mountain where there is not at least a path. The path may vary from some difference in the floor to an entire road being build. I first had to start looking into which path finding algorithms there were and why were they used. One of the options I found was the Dijkstra algorithm. The Dijkstra algorithm would look into a grid of nodes and check the neighbor. This proces would repeat until it would find the end goal. Even though this was probably the most used algorithm and a very solid one. An slightly different algorithm which looks like Dijkstra is what caught my eye. A* (A star), is an algorithm which first determines where the start and end goals are. From there it will see which general direction the end goal is and instead of searching every direction it will focus that specific direction to find the shortest path possible.

After deciding what algorithm I wanted to use I got to work. a* uses a path finding cost system with the basic being
fCost(total cost) = gCost(cost from start point to node) + hCost(cost from node to end goal).
As reference I used a pseudo code I found to help me along the way:

OPEN //the set of nodes to be evaluated 
CLOSED //the set of nodes already evaluated add the start node to OPEN 
loop 
  current = node in OPEN with the lowest f_cost
  remove current from OPEN 
  add current to CLOSED 
if current is the target node //path has been found 
  return 
foreach neighbour of the current node 
  if neighbour is not traversable or neighbour is in CLOSED skip to the next neighbour 
  if new path to neighbour is shorter OR neighbour is not in OPEN 
    set f_cost of neighbour 
    set parent of neighbour to current 
    if neighbour is not in OPEN
      add neighbour to OPEN 

This pseudocode is meant for a 2D node grid where the A* finds the path with only the horizontal, vertical and diagonal in a 2D space. for my mountain to use it i’d have to ad the slope of the mountain so it wouldn’t just straight run up the mountain but also wouldn’t completely go around either. Now that I added the inclines i still wanted to mess around with heuristics a bit. Heuristics within pathfinding is a technique designed for solving a problem more quickly or in my case finding an approximate solution when classic methods fail to find an exact solution the user is looking for. I want the algorithm to be able to be adjusted acoording to the user. for this to happen I gave a lesser incline a decreased travel cost and a higher incline an increased cost. After a while of tweaking I found a pattern I was happy with for the time being.

Something noted in the picture is the cube with a yellow outline. This was done because I needed the path to adjust its course if there was an obstacle in the way. this was necessary in case I wanted to add environment which will be the next step. The route can be changed by moving the startpoint to a desired location.

Environment

Trees
The next thing I wanted to do was to add trees. After doing some research almost every mountain has either trees or a forest at the bottom of the mountain. During the research I also found out that trees don’t grow past a certain height which is called the Timberline. this is where the natural living conditions are not met anymore such as temperature, air pressure or ground quality. when I went to program the trees I made it so they randomly spawn within the borders of under the Timberline and above ground. if they do fall outside these borders or there is already a tree on the desired vertex another one will be chosen.

In the picture above the trees are shown. A notable thing is that the path goes around the trees. within this picture the yellow cubes are indicating that the vertices are in contact with the tree and so the path is unwalkable.
One problem i ran into after the trees were added was a major drop in performance. After some looking around i found the cause for this problem. The trees all loaded with a 2048 by 2048 texture on it. This causes the scene to load a lot of unnecessary textures, after all the camera most of the time wont come close enough to see actual details. In the end I turned down the size of the textures to 512 by 512 for a much better performance.

Textures
Now that the trees are added the last thing to do to make this mountain look realistic is to add Textures. I don’t just want to add a normal texture because I want te mountain to be dynamic when it is generated at random. The way I am going to texture the mountain is through shaders. Seeming that I had trouble with shaders during the workshop my goal is to find one that I can use and then manipulate variables according to my own requirements. I managed to find one in a Unity Forum which helped me understand the principles and made me able to manipulate the ones I found(Unity Forum, 2018).

 _BaseHeight = ((minYValue - endLocation) - floorHeight);
 Mountainshader.SetFloat("_BaseHeight", _BaseHeight);
 _Layer1Height = timberLine - _BaseHeight;
 Mountainshader.SetFloat("_Layer1Height", _Layer1Height);
 _Layer2Height = timberLine - minYValue - highestVertice;
 Mountainshader.SetFloat("_Layer2Height", _Layer2Height);
 _Layer3Height = 0;
 Mountainshader.SetFloat("_Layer3Height", _Layer3Height);

After editing the values and finding some good textures to go along with the structure of the mountain. To improve performance a bit I also tiled the textures which I used and lowered the texture size quality. Tiling makes it so the texture gets used multiple times and not stretched. The texture size was set to 8k by 8k which i reduced to 512 by 512. The result gives a very realistic feel to the mountain while keeping the performance in check.

A path to the top

The last thing I wanted to implement is a path. I created the pathfinding for this specific reason because I personally think it would look good and gives me a lot of options later in the future if I want to continue with spawning houses or campsites. When I tried to spawn path objects on the points of the path finding algorithm I found a problem. For coding a path I needed to figure out the exact order of which the path nodes were given into my algorithm. my algorithm although it found out the fastest route would still give me the order in which the grid was created row by row.

One of the big reasons I found out that the order was so wrong is the way the objects are facing. In order to fix this I had to tweak the heuristics within the path finding algorithm some more. after doing this I could make it so the objects would be ordered in a list by the gCost of the nodes.

Now that the ordering was finished I could work on making the objects the right sizes and having them faced the right way. The answer for making them face the right way was solved in 2 steps. Set the pivot point for the object in the beginning of the object instead of the center which was easily done. The second was changing the quaternion angles of the object which was a bit more difficult. After some research and some hours of testing ways I found the solution.

Vector3 direction = nextPathPointPosition - currentPathPointPosition;
Quaternion.LookRotation(direction, Vector3.up);

With the path finished I can add everything together to see how the final result ends up looking.

Optimization

Performance started to become a pretty big issue at one point. The textures as mentioned before had been making a small difference, but there stil was a bigger problem. To make sure everything worked correctly I kept all my functions inside the Update method. This caused a huge drop in performance due to the placement of every vertex, tree and path obstacle constantly updating. It also gave me a problem where instantiating objects and path objects had to have a first rotation bool inside the function so it wouldn’t keep instantiating infinitely. This also then made it so an unused function kept getting called. Whenever i tried to put all the function into the start method to only run it once some requirements for functions weren’t met.

The solutions to these problems came in the form of a onInspectorGUI button. When i was talking with some classmates I noticed a feature within their projects. I asked about it and it turned out to be a onInspecterGUI button. When pressed this activates a method on the chosen class.
I looked into when to call functions so that I could make sure there would be no lacking requirement if I were to put them into the start method. I did this by putting them in a notepad and order them on what they need to function and where they would go afterwards.

XXXXX > meshdata > createmesh
meshdata > createmesh > XXXXX
meshdata > flagpoles > pathfinding
meshdata > trees > XXXXXX
flagpoles + trees > pathfinding > pathway
pathfinding > pathway > XXXXX

After shifting around the functions to my start method and others to designated places to not cause any errors I finally had the button working. I now needed to call all functions once instead of constantly to create the mountain and only once to create a new one. This had increased my frame rate from 10-15 to about 160-190.

public override void OnInspectorGUI(){
base.OnInspectorGUI();
TerainMesh terainmesh = (TerainMesh)target;
if (GUILayout.Button("Create new mountain")){
        terainmesh.Start();
    }
}

Sources

Redblobgames, July 2015, Making maps with noise functions
https://www.redblobgames.com/maps/terrain-from-noise/
Sebastian lague, December 2014, A* Pathfinding
https://www.youtube.com/watch?v=-L-WgKMFuhE
Unity forum, march 2018, Invertex
https://forum.unity.com/threads/blend-between-textures-based-on-height.210221/#post-3422178
Github:
https://github.com/terrence229/Gameplay-engineering-R-D/tree/environment