Procedural Island Generation UE4

Hi! Today I’m going into details of the procedural island generation I posted on my Twitter 🙂

To start off, a few great resources I’ve personally read that will help your understanding of terms and tools we’re using.

Awesome Blog post on Perlin Noise.
Complete resource on Hexagonal Grids.
Resource on Biome/Elevation.

I strongly suggest reading the above resources to get a good background knowledge of what I’ve used myself.

For the Perlin Noise I use the UnrealFastNoise from Chris Ashworth.

While this is a hexagonal grid, all of the code is easily transformed into square grids, so if you want a natural map that isn’t tied to hexagons you can still follow this guide.

High-Level process

The order in which I generate the island is as following:

• Generate entire flat hexagonal grid
• Mark edge tiles as ocean
• Divide Island and Ocean (Create island shape)
• Smoothen the island
• Flood-fill to differentiate lake and ocean
• Calculate tile distance from shore
• Create elevation (disabled in my preview)
• Assign biomes
• Smoothen the biomes
• Generate Flora (trees)
• Generate Resources

The order of the generation isn’t largely important, however, some are a prerequisite for others such as assigning biomes before generation flora because flora is dependent on biomes. But you can easily first generate resources and then the flora.

Noise

Throughout the post I use a lot of Noise->GetValue2D(x,y), this is how I get the Noise object.

UUFNNoiseGenerator* Noise = UUFNBlueprintFunctionLibrary::CreateNoiseGenerator(this, ENoiseType::Simplex, Euclidean, CellValue, FBM, EInterp::InterpQuintic, SeedValue, 5, FrequencyValue, 2.f, .5f);

Generating the grid

The generation of the grid is entirely done with the Procedural Mesh Component from Unreal Engine.

To start the generation we iterate over the grid x size and grid y size and calculate the position of that tile, then add 7 vertices (one for the center and one per corner). And after that, we add 6 triangles. We store this information in a struct per tile (indexes of the vertices, indexes of the triangles) so we can, later on, use it to assign biomes and elevate the terrain.

The actual calculation of the location of each vertex is neatly explained on this blog post.

for (int x = 0; x < xGridSize; x++)
{
      for (int y = 0; y < yGridSize; y++)
      {
        // Calculate hexagon location and offset by actor location
        int32 UseIndex = x * xGridSize + y;

        //Create TSharedPtr of the tile
        Tiles[UseIndex] = MakeShareable(new FLevelTile(UseIndex, x, y));

        //Actually create the tile
        AddTileToMesh(x, y);
    }
}

void ALevelGenerator::AddTileToMesh(const int32& x, const int32& y)
{
	//Get center of the tile
	FVector Center = FVector::ZeroVector;
	GetCenterForTile(x, y, Center);

	//Always add center first
	AllUVS.Add(FVector2D(0.25, 0));
	int32 CenterIndex = AllVertices.Add(Center);

	//Get locations for each corner
	FVector a = GetCornerForTile(Center, NORTH);
	FVector b = GetCornerForTile(Center, NORTHEAST);
	FVector c = GetCornerForTile(Center, SOUTHEAST);
	FVector d = GetCornerForTile(Center, SOUTH);
	FVector e = GetCornerForTile(Center, SOUTHWEST);
	FVector f = GetCornerForTile(Center, NORTHWEST);

	//Add vertice
	int32 A = AddVertice(a);
	int32 B = AddVertice(b);
	int32 C = AddVertice(c);
	int32 D = AddVertice(d);
	int32 E = AddVertice(e);
	int32 F = AddVertice(f);

	//Create triangles
	int32 AT = AddTriangle(B, A, CenterIndex);
	int32 BT = AddTriangle(C, B, CenterIndex);
	int32 CT = AddTriangle(D, C, CenterIndex);
	int32 DT = AddTriangle(E, D, CenterIndex);
	int32 ET = AddTriangle(F, E, CenterIndex);
	int32 FT = AddTriangle(A, F, CenterIndex);
      
  //Add all A-F and AT-FT data into the tile struct
}

To generate the mesh (after doing biome, resources, and flora) you need to add a ProceduralMeshComponent to your actor and have the following arrays in your class:

TArray<FVector> AllVertices;
TArray<int32> AllTriangles;
TArray<FVector2D> AllUVs;
TArray<FLinearColor> AllColors; //I leave this empty

AllVertices and AllTriangles get filled during the generation of the flat hexagonal grid.

To spawn the generated level use the code below. To be able to do that you need to include “ProceduralMeshComponent.h” and add “ProceduralMeshComponent” to your DependencyModuleNames.

for (int i = 0; i < AllVertices.Num(); i++)
{
    //I want all normals to be up, but you can change this if you want to
    AllNormals.Add(FVector::UpVector);
}

LevelMesh->CreateMeshSection_LinearColor(0, AllVertices, AllTriangles, AllNormals, AllUVS, AllColors, TArray<FProcMeshTangent>(), false);

Creating the island shape

To create the island shape I create a simple Perlin Noise and apply a radial alpha on top of it. This will lerp out the edges of the noise to a darker tone and if we then use a MinAlpha then this will effectively create an island-like shape. Here’s the end result of an island noise map.

The dark spots in the center of the noise map become oceans tiles as well and later on we flood-fill to determine if it’s a lake. (A lake is defined as no connection with the border without crossing land)

//Map X index to 0 -1 
float UseX = (float)x/ (float)xGridSize; 

//Map Y index to 0 -1 
float UseY = (float)y/ (float)yGridSize; 

//Get Noise at X and Y
float NoiseValue = Noise->GetNoise2D(UseX , UseY); 

//In our case the noise returns -1 to 1, we want to map it to 0 to 1
float Value = MapRangeClamped(NoiseValue, -1.f, 1.f, 0.f, 1.f);

//Get our distance from the center rounded to nearest whole
int Distance = Round((CenterLocation - FVector2D(x, y)).Size());

//The further away from center the less likely it is to be island
float RadialAlpha = MapRangeClamped(Distance, 0, MaxDistanceFromCenter, 1.f, 0.f);

//Apply this value to our mapped NoiseValue(Value) which will fake a radial alpha 
const float FinalValue = Value * RadialAlpha;

if (value > IslandMinAlpha)
{
  MarkTileAsType(GRASSLAND, TileIndex);
}
else
{
  MarkTileAsType(OCEAN, TileIndex);
}

Generating Biomes

To generate biomes I use 3 noise maps (One for Tundra, one for Woodland and one for Snowland).

We take the value we get from the noise map (0 to 1) and round it to nearest whole number(0.0-0.49 = 0, and 0.50-1.0 = 1), this will create very hard edged shapes which is useful for biomes.

For Tundra and Woodland we create an RGB value (Red = Tundra, Green = Woodland, Blue = nothing).

Based on the frequency of the Perlin noise per biome and different weight of the biome it can create different shapes and sizes.

With the RGB value we can determine if this tile is either black(Grassland), green(Woodland) or red(Tundra), and overlap of both colors is still woodland. Example of a biome noise map below.

For our purposes we want the Snowland biome to always be in the center of the map and always a minimum radius so to do that we get distance from center and if that distance from center is smaller than SnowRadius then it will always be snow, if distance is larger than SnowRadius but smaller than SnowRadius*2 then it will use a radial alpha on the snow noise map to create a non-round falloff around the snow biome.

if (Tile->GetGroundType() == GRASSLAND || Tile->GetGroundType() == WATER)
{

//Get tundra noise
float fTundraNoise = TundraNoise->GetNoise2D(x / xGridSize, y / yGridSize);
//Get woodland noise
float fWoodlandNoise = WoodlandNoise->GetNoise2D(x / xGridSize, y / yGridSize);
//Get snowland noise
float fSnowlandNoise = SnowlandNoise->GetNoise2D(x / xGridSize, y / yGridSize);

//Tundra final value
float R = MapRangeClamped(TundraNoise , -1.f, 1.f, 0.f, 1.f) * TundraWeight; 
//Woodland final value
float G = MapRangeClamped(fWoodlandNoise , -1.f, 1.f, 0.f, 1.f) * WoodlandWeight; 
//Snowland final value
float A = MapRangeClamped(fSnowlandNoise , -1.f, 1.f, 0.f, 1.f);  

//Round R and G to nearest whole number
R = RoundToInt(R);
G = RoundToInt(G);

//Get Distance from center of the map in tile distance
int Distance = RoundToInt((CenterLocation - FVector2D(x, y)).Size());

//Get radial addition for snowland
float RadialAddition= MapRangeClamped(Distance, SnowRadius, SnowRadius * 2, 1.f, 0.f);

//Get radial alpha for snowland
float RadialAlpha = MapRangeClamped(Distance, SnowRadius, SnowRadius*2, 1.f, 0.f);

//Get ground type from color(Red = Tundra, Green = Forestland, Black = Grassland)
Type = GetBiomeFromColor(FVector(R, G, 0));

//Check if tile is within snow radius and if not if tile has MinSnowAlpha
if ((A+ RadialAddition)*RadialAlpha > MinSnowAlpha)
{
  //If so we want this to be Snowland (override the previous biome)
  Type = SNOWLAND;
}

//If we are snowland
if (Type == SNOWLAND)
{
  //And we are water then this water(lake) should become ice water
  if (Tile->GetGroundType() == WATER)
  {
      Type = ICEWATER;
   }
}

//If the tile type is already water and not ice water then we want to keep it water
if (Tile->GetGroundType() == WATER && Type != ICEWATER)
{
  Type = WATER;
}
//At the end mark this tile as the type
MarkTileAsType(Type, TileIndex);
}

Generating Flora

To create trees we again create one noise map per biome, this case 4 noise maps (Tundra, Woodland, Grassland and Snowland), each biome has different density and frequency for its trees.

For example, Woodland has dense clusters of trees while grassland has more single standing trees and tundra barely has trees.

For trees, we want to get the noise at the tile index and if it’s larger than a minimum alpha then that tile should become the tree for that tile.

Values I used for a 150 x 150 grid for the biomes:

• Tundra -> 0.2 Frequency and 0.3 minimum alpha
• Woodland -> 0.2 Frequency and 0.5 minimum alpha
• Grassland -> 0.5 Frequency and 0.5 minimum alpha
• Snowland -> 0.2 Frequency and 0.4 minimum alpha

The lower the frequency the larger the maximum size of a single cluster of trees, the higher the minimum alpha the fewer trees a single tree cluster will be.

Below an example of various woodland settings:

0.2 Frequency and 0.5 minimum alpha
0.1 Frequency and 0.5 minimum alpha
0.2 Frequency and 0.15 minimum alpha

• 

• 

• 

Generating Resources

Creating resources is done with one noise map per resource, we have 3 (Stone, Iron, Gold). For every tile, we get the noise value per resource type and if the value is lower than the minimum alpha for that resource type we set it to 0 so it doesn’t spawn at that tile.

After that, we again use the 3 noise values as RGB data, and we select which is the strongest on that tile by selecting the highest value. If no value is larger than 0 then none of the noise maps has the required minimum alpha.

After it passed the minimum alpha check we do one other check with a weight value, if a random roll between 0-1 is larger than the weight for that resource it wins and can add itself to the level.

Resources are quite rare and would rarely spawn in clusters so we use very high frequency values and high minimum alphas. For our purpose, we have different weights per biome but the same minimum alpha globally (Gold can never spawn in grassland for example).

Values I used for the resources in Snowland biome:

• Iron -> 50 Frequency and 0.8 weight
• Stone -> 50 Frequency and 0.9 weight
• Gold -> 50 Frequency and 0.7 weight

Here’s an example of a resource noise map. (R= Stone, G = Iron, B = Gold)

//Get Stone noise
const float fStoneNoise = StoneNoise->GetNoise2D(x / xGridSize, y / GridSize);
//Get Iron noise
const float fIronNoise = IronNoise->GetNoise2D(x / xGridSize, y / GridSize);
//Get Gold noise
const float fGoldNoise = GoldNoise->GetNoise2D(x / xGridSize, y / GridSize);

//Stone final value
float R = MapRangeClamped(fStoneNoise, -1.f, 1.f, 0.f, 1.f); 
 //Iron final value
float G = MapRangeClamped(fIronNoise, -1.f, 1.f, 0.f, 1.f);
//Gold  final value
float B = MapRangeClamped(fGoldNoise, -1.f, 1.f, 0.f, 1.f);                

if (R < StoneWeight) //Lower than weight, never pick
{
  R = 0.f;
}
if (G < IronWeight) //Lower than weight, never pick
{
  G = 0.f;
}
if (B < GoldWeight) //Lower than weight, never pick
{
  B = 0.f;
}

NewResourceType = NONE;

if (R > G && R > B) //Pick stone
{
  NewResourceType = STONE;
}
else if (G > R && G > B) //Pick iron
{
   NewResourceType = IRON;
}
else if (B > R && B > G) //Pick Gold
{
  NewResourceType = GOLD;
}

//Did we select a resource?
if (NewResourceType != ESGGridResourceType::GRT_NONE)
{
 if(RandomBoolWithWeightFromStream(GetBiomeResourceWeight(Biome,NewResourceType))
 {
    //Spawn the resource and set tile resource type to NewResourceType
    Tile->SetResourceType(NewResourceType);
  }
}

UVS and Materials

Obviously, after you generate the shape and setup all your biomes you need to be able to color your island. Based on the biome for every tile I select a different UV space per biome. I create a triangle shape in the UV per triangle located where the mask for that biome goes. Below is a picture of the UVs per biome.

To actually color/materialize the mesh I created a mask per location of a triangle and apply a different world aligned texture per mask and then combine everything into a single material end result. This is probably not optimal and can be improved but then again I’m not a material artist 🙂

Here’s an image of the material I created.

Tags

• c++
• cpp
• Island Generation
• Level Generation
• Perlin Noise
• Procedural Mesh Component
• UE4
• Unreal Engine
• Unreal Engine 4