How to create endless worlds in games using procedural generation
Almost all of us have played a game that automatically generates a landscape at least once. Games like this really strongly stimulate the user to continue playing, constantly throwing new situations at him.
If you are a developer and like to pay attention to detail, then you probably wondered how such endless worlds are generated. Despite all their complex structure, all such generation comes down to a carefully tuned random component.
What is procedural world generation?
Procedural generation Is a method of creating data using an algorithm, not manually. In the case of computer games, this method is used to generate worlds and their details without the obligatory intervention of the developer. This technique is widely used in games such as Minecraft, Terraria or No man’s skybased on open worlds… The user can explore such worlds as he pleases and interact with them.
Procedural world generation is fundamentally superior to manual generation – because development requires less time and costs. The size of the downloadable files can usually be significantly reduced, since the game does not ship with huge pre-built maps. Moreover, they are usually implemented without difficulty, as soon as the development of the engine responsible for generating worlds is completed.
Now let’s move on to the technical part, let’s see how this process actually works. I will show you how to generate a 2D world.
I decided to write the code for the examples using Processing Is a graphics library and IDE based on the Java language. I chose Processing for simplicity reasons, but you can use whatever technology you like. At the end of the article, I will leave a link to the GitHub repository, where all the source code is posted.
Note: in the examples, I use the .java filename extension to colorize the code well. In fact, all of these files have a .pde extension.
What is noise and why is it so important?
We are all familiar with the concept of “noise” – which is commonly referred to as random, annoying sounds. Now let’s get to know numerical noise… It consists of many points, the values of which are influenced by the values of the surrounding points.
The fact that these values are interconnected with each other is a key aspect of world generation, since it is logical to expect that areas located nearby will look similar, not different. For example, do not assume that in the middle of the sky you can meet a river.
Of all types of noise, noise Perlina, named after its creator, Ken Perlin. Perlin noise allows you to generate pseudo-random organic patterns for any number of dimensions.
I won’t go into the details of the math behind this algorithm, since many programming languages provide built-in functions for this purpose. Anyway, if you want to take a closer look at this topic, here full explanation…
Noise maps and how they are used
Noise maps are graphical representations of noise in a given n-dimensional region of space, usually in 2D or 3D games. In the case of procedural generation, they represent a specific characteristic of the world, such as altitude, temperature, humidity, etc.
Each point on the map defines a specific value in the final piece. Let’s see how you can generate a noise map – in this case for the terrain heights – in Processing:
// масштаб определяет, насколько детализирована будет сгенерированная карта
float scale = 0.005f;
// Максимальная высота, которая может быть на ландшафте. В Minecraft она равна 255.
static final int MAX_HEIGHT = 255;
// xPos и yPos – это актуальные координаты мира
int xPos = 0;
int yPos = 0;
final int[][] generateHeight()
{
// создаем 2D-массив, в котором будет содержаться карта шумов для высот мира.
// "width" и "height" – это встроенные переменные, представляющие, соответственно, ширину и высоту окна
int heightMap[][] = new int[width][height];
for (int x = 0; x != width; x++)
{
for (int y = 0; y != height; y++)
{
// сгенерировать шум Перлина на основе координат x,y
// умножение координат на масштаб влияет на детализацию сгенерированной карты
// функция noise() возвращает число в диапазоне от 0 до 1
float value = noise((x + xPos) * scale, (y + yPos) * scale);
// выразить на карте сгенерированный шум между 0 и MAX_HEIGTH, затем округлить
int h = round(map(value, 0f, 1f, 0, MAX_HEIGHT));
// наконец, установить высоту актуальной точки на карте
heightMap[x][y] = h;
}
}
return heightMap;
}Code for generating a two-dimensional noise map in height.
As you probably already guessed, it is also possible to generate many noise maps at once for each characteristic that our world should have. Previous image of noise was generated using this particular function.
So what other characteristics should the world have? I decided to focus on temperature and humidity. The process for generating these maps is similar to the one we have already discussed above.
The only difference is that the humidity at a particular point also depends on the temperature at that point, and the height of the landscape also affects the temperature – all this is completely logical. For example, in the real world, temperatures at 3000 m are usually lower than at sea level.
// TEMPERATURE_SCALE определяет, насколько детализирована должна быть карта температур.
float TEMPERTURE_SCALE = 0.001f;
int DEFAULT_TEMPERATURE = 20;
// TEMPERATURE_INCREMENT определяет, насколько температура меняется в зависимости от высоты.
float TEMPERATURE_INCREMENT = 0.3f
// Функция принимает карту высот в качестве параметра, поскольку температура связана с ней.
final float[][] generateTemperatureMap(int[][] heightMap)
{
// Сначала создадим 2d-массив, в котором будем хранить карту температур
float temperatureMap[][] = new float[width][height];
for (int x = 0; x != width; x++)
{
for (int y = 0; y != height; y++)
{
// Получим шум Перлина в заданной точке с координатами x,y.
// Умножим координаты на масштаб, чтобы определить, насколько детализированной должна быть карта.
// Наконец, умножим на 100 и вычтем 50, чтобы подогнать температуру под конкретный диапазон.
// Второй шаг полностью специфичен для данной реализации и не является общим правилом.
float temperatureNoise = noise(x * TEMPERATURE_SCALE, y * TEMPERATURE_SCALE) * 100 - 50;
// Вычислить изменение температуры на основе того, какова высота точки
// Как видите, степень влияния высоты на температуру зависит от константы TEMPERATURE_INCREMENT.
float temperatureFromAltitude = DEFAULT_TEMPERATURE - abs(heightMap[x][y] - MAX_TEMPERATURE_HEIGHT) * TEMPERATURE_INCREMENTe;
// Вычислить финальную температуру и сохранить ее на карте.
temperatureMap[x][y] = temperatureNoise + temperatureFromAltitude;
}
}
return temperatureMap;
}
// HUMIDITY_SCALE определяет, насколько детализирована должна быть карта влажности.
float HUMIDITY_SCALE = 0.003f;
// HUMIDITY_TEMPERATURE определяет, насколько температура влияет на влажность.
float HUMIDITY_TEMPERATURE = 1.3f;
// Константы, зависящие от реализации.
float HUMIDITY_HIGH_TEMP = 23f;
float HUMIDITY_LOW_TEMP = 2f;
// Функция принимает карту температур в качестве параметра, поскольку влажность связана с ней.
final float[][] generateHumidityMap(float[][] temperatureMap)
{
// создадим 2d-массив, в котором будем хранить карту влажности.
float humidityMap[][] = new float[width][height];
for (int x = 0; x != width; x++)
{
for (int y = 0; y != height; y++)
{
// Как и в случае с картой температур, сгенерируем шум Перлина в заданной точке при заданном масштабе.
float humidityNoise = noise(x * HUMIDITY_SCALE, y * HUMIDITY_SCALE) * 100 - 50;
// Корректировки, зависящие от реализации и определяющие, как температура будет влиять на влажность в заданной точке.
float humidityFromTemperature = 0f;
if (temperatureMap[x][y] > HUMIDTY_HIGH_TEMP)
humidityFromTemperature = temperatureMap[x][y] * 2 - HUMIDITY_HIGH_TEMP;
else if (temperatureMap[x][y] < HUMIDITY_LOW_TEMP)
humidityFromTemperature = HUMIDITY_LOW_TEMP;
else
humidityFromTemperature = temperatureMap[x][y]
// Вычисляем окончательную влажность.
// Константа HUMIDITY_TEMPERATURE определяет, насколько температура влияет на влажность.
humidityMap[x][y] = humidityNoise + humidityFromTemperature * HUMIDITY_TEMPERATURE;
}
}
return humidityMap;
}Code for generating 2D noise maps describing temperature and humidity.
About biomes and how they are defined
First, let’s find out what a biome is? According to National Geographic, A biome is a vast area characterized by specific flora, soil, climate and fauna. As this definition implies, a biome is characterized by a specific set of characteristics that can be generated from noise maps. It remains to correlate these values with different biomes, depending on what characteristics they should have.
To clarify this process, consider a specific example: the savannah. It is a relatively low plain. Tall grass grows in the savannah, so this landscape should not be arid, and also should not freeze through.
Setting these values is the responsibility of the programmer and is entirely implementation dependent. The process of finding the best values is associated with the generation of different worlds with slightly different parameters, after which you choose the results that you like the most.
In my example, I am assuming that the height range in the savannah should be between 135 and 169 – these are the values I arrived at by trial and error. In addition, I believe that the temperature should be in the range from 0 to 50, humidity should also be in the range from 0 to 50.
Note: these values are not expressed in meters, degrees, or percentages. They are simply numbers that represent specific coordinates on the corresponding map.
For convenience, let’s create classes in Processing Range and Biome:
// Класс, представляющий диапазон чисел (напр. от 0 до 50)
class Range
{
public final float min;
public final float max;
public Range(float min, float max)
{
this.min = min;
this.max = max;
}
// Возвращает, входит ли заданное значение в диапазон
public boolean fits(float value)
{
return min <= value && value <= max;
}
};
// Класс, представляющий биом в мире
class Biome
{
public final String name;
public final Range heightRange;
public final Range tempRange;
public final Range humidityRange;
// col – это цвет, в котором представлен биом
public final color col;
public Biome(String name, Range heightRange, Range tempRange, Range humidityRange, color col)
{
this.name = name;
this.heightRange = heightRange;
this.tempRange = tempRange;
this.humidityRange = humidityRange;
this.col = col;
}
};Range and Biome classes.
We can now represent savannahs as an object (and the same goes for other biomes) and store them in an array that will become our list of biomes:
final Biome[] biomes = new Biome[]
{
// имя высота температура влажность цвет
new Biome("Abyss", new Range(0, 39), new Range(-10, 50), new Range(-10, Float.MAX_VALUE), #090140),
new Biome("Ocean", new Range(40, 129), new Range(-10, 50), new Range(-10, Float.MAX_VALUE), #2107D8),
new Biome("IceLands", new Range(0, 170), new Range(-Float.MAX_VALUE, 0), new Range(-Float.MAX_VALUE, Float.MAX_VALUE), #75FCF2),
new Biome("Shore", new Range(130, 135), new Range(0, 50), new Range(-Float.MAX_VALUE, 50), #C7CE00),
new Biome("SnowyShore", new Range(130, 135), new Range(-Float.MAX_VALUE, 0), new Range(-Float.MAX_VALUE, Float.MAX_VALUE), #EDFCA8),
new Biome("Plains", new Range(135, 169), new Range(0, 50), new Range(0, 50), #40D115),
new Biome("FireLands", new Range(135, 169), new Range(50, Float.MAX_VALUE), new Range(-Float.MAX_VALUE, 30), #E57307),
new Biome("Forest", new Range(140, 169), new Range(0, 25), new Range(5, 30), #128B03),
new Biome("Tundra", new Range(140, 169), new Range(-10, 0), new Range(5, Float.MAX_VALUE), #745F4E),
new Biome("Desert", new Range(135, 169), new Range(30, Float.MAX_VALUE), new Range(-Float.MAX_VALUE, 5), #CBB848),
new Biome("GrassyHills", new Range(160, 189), new Range(5, 25), new Range(5, 30), #2E7612),
new Biome("ForestyHills", new Range(160, 189), new Range(5, 30), new Range(0, 30), #1B5504),
new Biome("MuddyHills", new Range(170, 189), new Range(0, 40), new Range(0, 50), #984319),
new Biome("DryHills", new Range(140, 189), new Range(10, 40), new Range(-Float.MAX_VALUE, 0), #C6950A),
new Biome("SnowyHills", new Range(170, 189), new Range(-Float.MAX_VALUE, 0), new Range(-Float.MAX_VALUE, Float.MAX_VALUE), #1FA27C),
new Biome("DesertDunes", new Range(170, 189), new Range(30, Float.MAX_VALUE), new Range(-Float.MAX_VALUE, 0), #7E7109),
new Biome("Volcano", new Range(170, MAX_HEIGHT), new Range(30, Float.MAX_VALUE), new Range(-Float.MAX_VALUE, 35), #AF1109),
new Biome("RockyMountains", new Range(180, MAX_HEIGHT), new Range(-Float.MAX_VALUE, 30), new Range(-Float.MAX_VALUE, 40), #43100D),
new Biome("IceMountains", new Range(180, MAX_HEIGHT), new Range(-Float.MAX_VALUE, 0), new Range(5, Float.MAX_VALUE), #5B6A63),
new Biome("Swamp", new Range(130, 170), new Range(0, 35), new Range(40, Float.MAX_VALUE), #052403),
new Biome("RainForest", new Range(140, 180), new Range(30, 40), new Range(40, Float.MAX_VALUE), #324B28),
new Biome("DryLands", new Range(0, 150), new Range(0, 40), new Range(-Float.MAX_VALUE, 0), #834C10),
new Biome("Savannah", new Range(135, 169), new Range(20, 50), new Range(-10, 10), #767618),
new Biome("GeyserLand", new Range(130, 170), new Range(40, Float.MAX_VALUE), new Range(40, Float.MAX_VALUE), #3A3B55),
// If none of the previous biomes is represented by the point's values, a special "None" biome is assigned to it
new Biome("None", new Range(0, MAX_HEIGHT), new Range(-Float.MAX_VALUE, Float.MAX_VALUE), new Range(-Float.MAX_VALUE, Float.MAX_VALUE), #E513C3),
};An array of biomes with their properties.
Once the list of biomes for the world is defined, it is time to create a biome map.
A biome map, like the maps we talked about above, is a set of points, each of which is assigned specific values. In this case, the x, y coordinate value is the biome that best matches the parameters for that point on the noise maps.
Consider another example for clarification. For example, in x, y coordinates, the elevation, temperature and humidity maps have values of 140, 25, and 25, respectively. Since all these values fit into the specified for the savannah elevation range 135-169 and the range 0-50 corresponding to temperature and humidity, the biome with such coordinates should be related to the savannah.
Now, in order not to manually check which set of values corresponds to which biome, let’s write the following function for this:
// Сгенерировать 2d-карту объекта Biome
final Biome[][] generateBiomes(int[][] heightMap, float[][] temperatureMap, float[][] humidityMap)
{
// 2d-массив, содержащий карту биома
Biome[][] biomeMap = new Biome[width][height];
// Перебрать все точки на карте
for (int x = 0; x != width; ++)
{
for (int y = 0; y != height; y++)
{
// Перебрать биомы и посмотреть, какой из них соответствует значениям для
for (Biome biome : biomes)
{
if (biome.heightRange.fits(h))
{
if (biome.tempRange.fits(temp))
{
if (biome.humidityRange.fits(humidity))
{
biomeMap[x][y] = biome;
}
}
}
}
}
}
return biomeMap;
}Of course, this is not the most efficient way to define the biome, but I tried to keep the code as simple as possible.
Once each of the points is assigned the desired biome, proceed to creating a graphical representation. This is what the property is used for color class Biome…
Let’s write a function in Processing that draws a finished map on the screen:
// Функция, отрисовывающая карту биома на экране
final void drawMap()
{
// Перебираем экранные координаты x,y
for (int x = 0; x != width; x++)
{
for (int y = 0; y != height; y++)
{
// Получаем на основании карты цвет биома
color col = biomeMap[x][y].col;
// Устанавливаем цвет штриха
stroke(col);
// Ставим на экране точку заданного цвета в координатах x,y
point(x, y);
}
}
}This is the result:
Random seed values
Random seed values Are just numbers used to initialize a pseudo-random value generator. The first pseudo-random value is generated from the initial one, and all subsequent values in a random sequence depend on it.
Initial values are useful when predictable results are needed. In fact, all generated pseudo-random number sequences deduced from the same seed are guaranteed to be equal.
Thus, if you find a truly beautiful world that you want to save and use for the game, you can simply save it with a random initial value. Moreover, if you wanted to transfer this world to someone, then you would not need a wide data transmission bandwidth; it would be enough to send the seed.
In Processing, you can specifically specify a random seed for a function noise() using the built-in function noiseSeed()… It takes a number (random seed) as its value and returns nothing.
int mySeed = 54;
noiseSeed(mySeed);All maps generated from this initial value will look exactly the same, provided the world generation code remains the same.
Further tips for generating worlds
To implement procedural world generation in your game, try splitting the world into chunks so that you only load the resources you need.
To move around the world, you need to move the x, y coordinates in the direction of movement. The noise functions will generate noise values (and therefore maps) according to the new position.
Here is a snapshot of the project that this article is based on. You can see how the terrain is generated as you move around the world.
Demo version of procedural generation of worlds with changing coordinates.
If you are interested, take a look at the repository at Github for this project. I warn you in advance that the code is not of the highest quality, since here I wanted to create only a prototype of a Minecraft-like game that I am currently developing.
I hope you enjoyed the article and learned something new about how worlds are generated in games.
