Hello! My name is Vladimir Sadovsky and I'm a programming enthusiast (weak applause). I work as an instrument developer at Nau Engine, but what's more interesting - I've been playing games since childhood. When I was 8 years old, my parents got me a computer for studying, but the first game that caught my attention was Carmageddon. After that, everything started to blur.

Later on, I discovered Command & Conquer: Generals, Fallout 2, and probably hundreds of other games. My childhood passion eventually turned into a career.

I started exploring procedural content generation (PCG) while studying at ITMO University. Back then, I was fascinated by how PCG helps create open-world games and affects replayability. As a game developer, I noticed that even professionals often confuse procedural generation with generative AI.

Let's discuss GAI in another article (because it's a huge and interesting topic that deserves its own material). Today, we'll dive into what eats procedural content generation and how to use it without choking on the complexity of the game industry. Along the way, we'll explore the history of PCG (which is almost twice as old as I am), review popular tools, and discuss the most promising algorithms.

Let's get started!

In 1984, the first game in the Elite series offered something even more impressive. There were eight galaxies with 256 planets each - and all cosmic expanses fit into 22 KB of magnetic tape! At the first launch, the game stored some initial value of seed and after every start restored galaxies and celestial bodies according to this value.

In 1994, Arena, the first part of The Elder Scrolls series, used PCG to create a whole fantasy continent with thousands of NPCs and hundreds of populated settlements. Its sequel, The Elder Scrolls 2: Daggerfall, still remains one of the largest open-world games: 161,600 km² area, 15,000 cities, and approximately 750,000 NPCs. Yes, the world was empty, quests were monotonous, and characters weren't exactly interesting... But almost unlimited freedom made up for all shortcomings.

In the same 1996, Diablo came out. Of course, it couldn't boast the scale of Daggerfall, but its game levels were completed and met game design metrics. For example, they were all passable, and some objects and fragments of locations, like Butcher's lair or Leoric's tomb, were placed in a strictly determined manner. If the map didn't meet the specified metrics, it was regenerated until all conditions were met.

But even more significant legacy of Diablo is its item generation system. First, the game decided whether an item would drop at all. Then - what type (bow, sword, armor etc.). Next - if it was magical or not. After that - its uniqueness, characteristics, prefix and suffix were determined. And some parameters appeared more often than others, while some could never be combined.

The entire flood of variables influenced the generation process, starting from the character's level to the location (city or dungeon) and source (monster or, say, a chest) where the item was found. As a result, thousands of unique items fell at the feet of heroes. Inspired by Diablo, developers have successfully awakened the instinct of collecting in players, ready to spend hundreds of hours in ARPGs and looter-shooters searching for new randomly generated weapons.

In over 40 years, PCG has come a long way from being a forced measure to overcome platform limitations to becoming an important and necessary tool that frees the game designer from hundreds of hours of routine work. Today, procedural generation is used to create living megacities (Marvel’s Spider-Man), realistic forests (Horizon Zero Dawn) and entire universes (No Man’s Sky). Below I will show specific examples of what is often created with PCG and what tools are used for this purpose.

In Unreal Engine, the PCG framework is designed specifically for procedural generation. To place random objects, you need to create a separate object and program a blueprint that will run within a specified area during generation.

Formally, Unity also has its own tool for placing random objects, but originally it was intended for working with vegetation. I'll discuss this further below.

In dark areas, higher biomes with dense flora (mainly tree) are generated, while in light areas, low-lying areas with sparse vegetation are.

To calculate the density of vegetation, the following method is used. In a selected area, procedural generation is started using a normal distribution. Then, the distance from each object to its neighbors is calculated. If the resulting density matches the specified one, the generation is left unchanged. Otherwise, the process is restarted.

Non-intelligent algorithms for procedurally generating vegetation based on distribution are the most common basis for creating tools for working with flora in game engines. Despite not mathematically modeling real plant growth processes, these algorithms show good results quickly, which is very important for games with procedural generation running in runtime.

This property is especially valuable for tool developers who need to work quickly during user interaction with the engine. For example, a brush that makes it easy to place vegetation on a landscape is usually based on an algorithm calculating density.

Intelligent algorithms for procedurally generating vegetation based on growth models mathematically model real biological processes. Typically, a growth model is combined with one of the competition models between plants, allowing for accurate placement of plants of different heights. For example, small bushes will not affect each other, but if two large trees are nearby, the algorithm will only allow one to survive.

How does an algorithm based on growth modeling work together with competition?

Typically, algorithms that use a growth model with competition function as follows:

• In the beginning, several points are chosen where vegetation starts to spread. These can be placed using a random distribution or noise map.
  
  
  
• The growth stage follows, where each iteration of mathematical modeling allows a tree to grow or age. The age of the tree determines its probability of dying and being removed from the population.
  
  
  
• The reproduction stage occurs when plants reach maturity and start spreading seeds in the surrounding area.
  
  
  
• Finally, the self-thinning stage is added if additional competition models are used. When trees grow close together, they begin to compete for living space, and the weakest one is eliminated.

These steps will be repeated as many times as necessary to simulate a vegetation array of a given age.

Two methods of competition are usually used:

• Symmetric, where competition is divided between two generation objects evenly. This means that if plants have the same size, they present equal threats to each other.
  
  
  
• Asymmetric, where resources are distributed between generation objects unevenly. Depending on the parameters set for evaluation, the dominant competitor will receive more resources and a greater chance of survival compared to its opponents.
  
  

If game engines use algorithms based on growth modeling, symmetrical competition is usually chosen for modeling competition between plants because it is easier to define than asymmetric competition, and results on large maps will be approximately the same.

Algorithms based on growth methods are rarely found in game engines, usually hidden in specialized utilities. Unlike distribution-based algorithms, they show more realistic results in top-down games, but cannot guarantee a specific density of planting in other projects. However, this is not the biggest problem.

Moreover, these are heavy algorithms that take a long time to work. Therefore, they cannot be used in games where vegetation generation is important and should occur quickly. Additionally, the user does not immediately see the final result. You have to wait for the generation results, and if something is wrong, you have to regenerate everything again. That's why growth-based generation is rarely used.

Now a few words about some of the most interesting tools in modern game engines.

Unity. Unity's tree generator uses additional nodes that are responsible for new branches or leaves, as well as their shapes.

Another tool is Mass Place Trees - it allows growing entire virtual forests with one mouse click. The "brush" tool gives you the ability to adjust the weight of each selected game asset, regulate its distribution and choose a texture background.

Another characteristic feature of Unity is the Tree Imposter tool. An imposter is a combination of 2D texture and 3D object (in the form of two perpendicular planes intersecting at their midpoint) that is orthogonal to the camera and is usually used at a sufficient distance from it to optimize computer load when visualizing large arrays of vegetation.

Unreal Engine also has its own tools for working with vegetation. Procedural Foliage Tool allows generating a list of specified entities within a certain area with a high degree of accuracy using spawn frequency settings and randomization modifiers for position. Separate colliders enable the cutting out of areas where tree growth is prohibited.

In addition, Unreal Engine allows you to place vegetation using a brush. This approach is most often used for working with grass. Finally, this purpose is applied by the above-mentioned Procedural Content Generation Framework.

In Unigine, tree placement occurs in the same way as generation of random objects.

Proprietary engines also offer tools for working with vegetation. For example, Dunia Engine, which was used to develop the FarCry series, allows placing trees (as well as other assets) using a brush tool. Their feature is that they usually operate not on some set of homogeneous single objects, but immediately place entire arrays of vegetation: trees with shrubs and grass, which are interconnected with each other.

REDengine, which was used to develop games in the The Witcher and Cyberpunk 2077 series, also contains a powerful tool for working with vegetation. It is similar to Procedural Foliage Tool from Unreal Engine, but allows precisely setting up the distribution of vegetation on the map using physical parameters.

Unreal Engine did not have built-in tools for generating cities until version 5.3, where they became possible to imitate using PCG. Epic Games has been working on this problem for a long time. The generation of New York in the demonstration game The Matrix Awakens occurred in UE5 in several stages. Part of the work was done in Houdini Engine, and there the basic look of the city was set up.

The available space was divided into districts, and districts - into lots. Further on, the height of the district depending on its distance from the center was adjusted to create an effect of skyscrapers. Then, based on the average height of the district and a specific lot, a 3D building contour was created. At the final stage, all this information was passed further into the engine using a special plugin for working with Houdini.

The generation of buildings also occurred in several stages. At the first stage, formal grammars (about which is below) were applied to create the visual style of individual floors. Then, with the help of an Unreal Engine plugin for working with WFC, the geometry of these buildings was refined: objects on rooftops, external engineering systems, etc.

Unigine - one of the few engines with a separate tool for generating buildings. Here you can generate 3D buildings by specified attributes in the form of a shape mask and coordinates, as well as use geodata from open sources, such as GeoJSON or OSM. In addition, Unigine allows you to generate urban development based on several parameters, choosing materials used, adjusting height, roof shapes, etc.

In Unreal Engine, the Sky Atmosphere Component physically models light scattering by skybox and penetration of rays according to atmosphere settings and fog. Unigine, on the other hand, stands out for its wide range of customization options for volumetric clouds and numerous realistic types.

To make the world look even more dynamic, NPCs will start building relationships with each other, forming alliances or fighting. As a result, no two passes will be similar to each other.

Another way to make the game's world interesting and believable is to model its chronology. For example, at the beginning of a Dwarf Fortress party, we don't get an empty map. Before starting the game, the program generates 100 years of history: the founding of cities, wars, the rise and fall of entire empires. As a result, the player has access to a unique living world that is just inviting them to leave their own mark on history.

If we consider procedural generation of history in a more general sense, not tied to developing a specialized tool for the game engine, it turns out that this is quite common.

Generation of character names or backstory appears in many RPGs. No less are generators of typical quests, such as, for example, in Fallout 4 ("General, another settlement needs your help!") or in Sea of Thieves (treasure hunt quests). Such algorithms usually do not develop specialized tools. They simply complement existing game mechanics.

Unreal Engine has taken a big step forward in this regard: it has several different systems for working with complex generation rules. Within PCG, there is a wide range of rule settings through blueprints, the ability to determine the type of surface, slope, and size for spawning objects.

WFC is related to spreading restrictions. Each subsequent step reduces entropy, i.e., the number of possible choices for that particular step. The algorithm's effect ends at the moment when out of all options there remains only one. If initial restrictions are not set, then instead of a resolver for a specific situation, you can get a generator of certain content.

Thanks to the fact that this algorithm is somehow similar to neural networks (able to create a set of rules based on an example), it is spreading widely in the game industry.

So, in The Matrix Awakens, a special plugin was used for working with WFC (its extension to the 3D space), which refined the geometry of buildings: added small details, air conditioners, fire stairs, pipes and ventilation systems on rooftops.

The main advantage of WFC is also its weak point. Without a set of data that can be presented as an example for WFC, problems arise in writing generation rules (and there may be many) and creating assets that the generator will use. Oscar Stålberg, creator of games Bad North and Townscaper, said that the latter uses several thousand assets and several hundred generation rules. In this case, WFC is applied to refine building geometry on an irregular grid, where the user's input is the initial restriction.

Another promising approach to PCG is formal grammar. This is a way to describe a formal language, an algorithm for extracting some subset from a set of all words of a finite alphabet.

Words of the language are called all sequences of symbols generated from the initial state by rules of derivation.

Two types of grammars are distinguished:

• Generative;
• Analytical.

Generative grammars are most interesting in the context of generating game content. I would like to tell you about them.

To set up a generative grammar, you need to define an alphabet of terminal and non-terminal symbols, derivation rules, as well as the initial set of non-terminals.

By terminals, we mean some symbol that represents, for example, a game asset. By a non-terminal symbol, we understand some entity of the language that does not have a specific physical representation, such as a formula, arithmetic expression, or command.

Thus, from an initial set of non-terminal symbols and derivation rules, you can obtain a specific (terminal) word that will correspond to the generation parameters. This word can be used later as the initial state for another generator.

Formal grammars were used, in particular, in The Matrix Awakens mentioned earlier. There, they were used to set up the initial visual style of buildings. Depending on input restrictions (such as wall length) from a certain set, a word was generated. Each terminal symbol of the word corresponded to an asset that replaced this terminal when generating a 3D object building.

Another good example of using formal grammars is the normal algorithms Markov (NAM).

The normal Markov algorithm represents a system for rewriting strings that uses certain rules to work with sequences of characters. It has been proven that NAM (unlike an abstract formal grammar) are Turing complete, which means they can be used for general computations and even to model mathematical expressions.

Markov algorithms have long been known and have shown their effectiveness for modeling random events.

PCG algorithms (Procedural Content Generation) are particularly well-suited to tasks where you need to place pre-created content according to a certain set of rules.

In contrast to generative artificial intelligence, which I would like to consider in another material, PCG algorithms always provide a deterministic result from run to run under the condition of unchanged input data. This allows them to be used, including in runtime.

PCG allows you to create entire virtual worlds using minimal resources. Which means that despite more than 40 years of history and active competition with AI, procedural generation is still far from losing relevance.