Overview of modern algorithms for world procedural generation in computer games

Abstract

This article analyzes the most common algorithms and approaches of worlds' procedural generation that are used today, and considers real use cases of these methods in order to obtain the best understanding of the use of these algorithms in specific situations. There are also the estimations of algorithms' time complexities to determine whether they are justified with high-quality output virtual environment. Among such algorithms are graph grammar, Fortune's algorithm, Perlin noise construction, cellular automaton construction, genetic algorithm and others.

Keywords

• eol>Graph grammar
• Voronyi diagram
• Fortune's algorithm
• Minkowski metric
• Perlin noise
• cellular automaton
• genetic algorithm

1. Introduction

2. Generative grammar

Generative grammar was originally used to create phrases by specifying rules to select a lexeme (term) from a set of logically correct options [ 1 ]. Therefore, it is possible to form a given number of grammatically correct constructions. Based on this, other grammars were developed such as graph rewriting1 and form grammar.

2.1. Graph grammar

Graph grammar is commonly used for world-building of diferent types of dungeons, castles, and other structures for role-playing (RPGs) or strategy games. It considers the world to be represented as a graph [ 2 ]. Firstly, an initial graph (randomly selected from a template) is defined, and then rules for subgraph transitions from one to another are sequentially applied. Typically, rewriting rules are specified manually to ensure logical transitions.

The most popular approach to graph rewriting is the algebraic approach, in which the double pushout and the single pushout methods are defined. The double pushout method involves using rules of three graphs: a left-hand , a right-hand , and a context (often called the interface). The graphs and specify a transition using the context : ⊇ ⊆ . There is a homomorphic subgraph to in the graph and all elements that are present in but not in are removed from . After that, the elements of that are not in are glued to (figure 1). This method is strict, which allows to avoid cases where conflicting changes are applied to the same subgraph. The single pushout method is simplified and operates only with graphs and . Elements of that do not correspond to graph are removed, and new elements from are added to (figure 2). This method is more flexible, but can cause issues with compatibility of changes.

The time complexity of graph rewriting mostly depends on the sizes of an input graph and a left-hand graph , since finding subgraph homomorphism is an NP-complete problem, that can lead to exponential complexity. Therefore, the time complexity of searching for a mapping position in a graph by a graph is ( * ) in simple cases, and ( ) in the worst case, where is the number of vertices in and is the number of vertices in . The time of applying a rule is (), however, it is usually a constant value. Considering that rewriting a graph processes rewriting rules, the time complexity is ( * * ) in the simple case and ( * ) in the worst case. The space complexity depends on the size of the graph and all rewriting rules – ( * (|| + || + ||)), where is the number of rules, ||, ||, || are the sizes of graphs , , and respectively. When applying the single pushout, the context size will be absent in the space complexity.

Generating graph rewriting rules can be a challenge, as all rules must modify the graph in a way that can actually be generated. Paul Merrell proposes a new method for generating graph rewriting rules [ 3 ] (figure 3-4).

The first step is to select graphs that will serve as examples for generation. It is required that the result must be locally similar to the examples. This means that every part of the generated graph should be similar to the example at small scales, but its large-scale structure can be completely diferent. The examples are broken down into the primitives and glued together by all possible ways. The primitives and all glued graphs are organized into a hierarchy of subgraphs. If the new subgraph can be simplified to the one higher in the hierarchy, then a rewrite rule can be formed (new subgraph ↔ simpler subgraph) (figure 5).

Graphs and are mutually gluable if they have the same boundary string: = . The graph boundary string is described by positive ∧ and negative ∨ turns of the subgraph and also its half-edges (figure 6). If the positive and negative turns are consecutive, they can be reduced: ∧ ∧ ∨ = ∧ . If the numbers of half-edges, positive and negative turns are the same, then the boundary strings of the subgraphs are also the same. Due to the reason that all our graphs are planar, they can be glued in linear time. There are two operations to directly glue subgraphs: loop glue and branch glue. They can be considered more in Paul Merrell’s publications.

After applying a rewriting rule, there is a process of randomly defining the edge lengths of the graph. If the lengths are organized so that the graph is planar, then the decision is made, otherwise, the edge lengths are redefined.

3. Space distribution

The space distribution methods refer to the algorithms that divide the entire game space among individual generation elements (e.g., rooms). Such algorithms were originally used in computer graphics for texture generation, and later found wider application.

3.1. Voronyi diagram

The Voronyi tessellation2 [ 4 ] describes the entire territory, dividing it so that any point inside a separated element is the closest to the corresponding partition point : (, ) < (, ), if and are partition points of the diagram. This can be achieved, if we draw perpendicular bisectors of the lines connecting each pair of randomly given points and choose the part of the bisector that does not intersect with others (figure 7): () =

ℎ(, ) ⋂︁ 1≤ ≤

̸= where is partition point, ℎ(, ) is half-plane formed by drawing a perpendicular bisector and containing and not containing . However, there are better algorithms for constructing a Voronyi diagram that do not require a pairwise search of all points. (1)

Fortune’s algorithm [ 4 ] suggests using a line that sequentially “sweeps” all points of the diagram (figure 8). If the line passes the partition point, then the site event is triggered. During this event, a new arc (parabola) is created, which is a representation of this partition point. The intersection of the arcs gradually grows and outlines a new edge of the Voronyi diagram. If the middle arc at the place of three arcs shortens and compresses to one point of the circle, then the circle event is triggered. At this moment, the middle arc is removed and the vertex of the diagram is formed. Since the number of events processed by the algorithm is , and the complexity of operations with data structures (priority queue of events and arc tree) of each event takes (log ) time, then this algorithm has a time complexity ( log ), where is the number of partition points. Due to the storage of the previously mentioned data structures, the space complexity of the algorithm is ().

Using various distance metrics, it is possible to achieve versatile partitions of the Voronyi tessellation. The Manhattan (figure 9) or Euclidean (figure 10) distance are the most common metrics, but they lead to straight edges of the diagram. An interesting approach is to use the Minkowski metric [ 5 ], which will make the edges curvilinear. To calculate the distance between points = (1, 2, . . . , ) and = (1, 2, . . . , ) the formula can be used: (, , ) = ︃( ∑︁ | − | =1 )︃ 1 (2) If = 1, this is the Manhattan distance, = 2 is the Euclidean distance. When > 2 (but not too big), the edges of the Voronyi diagram become curvilinear (figure 11). This can be used, for example, to generate biomes – diferent areas in the game world, which are defined by climate, terrain, vegetation, fauna, etc. It is possible to determine the belonging of each group of Voronyi cells to a specific biome 2More popular name ’Voronoi diagram’ is replaced with ukrainian correct transliteration option. Also names ‘Voronyi tessellation’, ‘Voronyi decomposition’ or ‘Dirichlet tessellation’ are commonly used. using algorithms to combine the cells in a shared entity. Muzzin [ 6 ] describes generating biomes for a two-dimensional strategy game with rectangular or hexagonal cells in his paper “How to Use Voronoi Cells for Strategy Game Maps”. Another approach to generate biomes with indirect edges is to use gradient noise.

Since the Voronyi diagram generation algorithm is used only to distribute the game space, it is not universal for various world generation and does not provide a wide range of input parameters: 1. The number of partition points; 2. Algorithm for random placement of the partition points (for example, each point in a separate square cell); 3. Parameter according to the Minkowski metric.

To summarize the Voronyi diagram’s usability, it can be helpful for developing the real-time strategies (RTS), simulation, survival, and exploration games.

3.2. Gradient noises

The idea of gradient noises is to create a field divided into cells and distribute randomly specified gradients, where the value in the intermediate cells is found by interpolation of dot products of cells.

Perlin noise [ 7, 8, 9 ] is one of the simplest gradient noises. Firstly, the entire space is divided into a grid, each vertex of which is represented of a random gradient→{−1 →,−2 , . . . , →−2 }, where is the number of dimensions. Then for every single point we calculate the vectors from four nearest vertices of the grid to the point :→{−1→,−2, . . . , →−2 }. Next step is finding dot products of →{−1 →,−2 , . . . , →−2 } and →{−1→,−2, . . . , →−2 } and these values are interpolated. For example, considering a two-dimensional space, this process consists of interpolating the upper left and the lower left products 1 = →(−1 →*−1 →,−2 →*−2 ) and the upper right and the lower left products 2 = →(−3 →*−3 →,−4 →*−4 ), and after that finding the interpolation of 1 and 2 (figure 12). Therefore, we obtain a value from 0 to 1, which can be graphically interpreted at point and all other points (figure 13).

The time complexity of Perlin noise depends on the number of points and dimensions . We have already seen that if = 2, then the number of operations for one point is 4. Therefore, the time complexity of Perlin noise is ( * 2).

Fractional Brownian noise (FBN) [ 9 ] extends the idea of classical Brownian motion, which describes the random movement of a particle. In general, FBN works by layering ordinary noise (e.g. Perlin noise) with varying amplitude and frequency parameters. One such layer is called an octave of Brownian noise. The amplitude controls the pitch of the noise, so with each next octave, this coeficient decreases so that each layer becomes smoother and less contrasting. The frequency increases with the transition to the next octave and adds rough small details. FBN has the fractal property of self-similarity: a change in scale partially repeats the original appearance of space.

Gradient noise is often used to define a height map of open world. The game Minecraft uses such algorithms for world procedural generation [ 10 ]. To do this, congruent generators are firstly used to create Perlin noise, which serve as octaves of the FBN. After that, the map is processed in a multilayer stack of operators similar to cellular automaton to define biomes (figure 14). Each layer takes the biome map from the previous one, adds some details and passes it to the next one. Also, each biome has the parameters of the average depth and its average deviation (figure 15). Minecraft procedural generation is a good example of open world PCG, developed over the years.

As it is seen, gradient noises are frequently used in 3D adventure, exploration, or survival games but generating randomized and smooth 2D terrains and obstacles for platformer games is also a common way of its exploitation.

4. Simulative algorithms

Simulative algorithms generate the world based on the reproduction of the change of a real object over time. In such algorithms, time is expressed in the number of iterations and plays a key role in the shape and distribution of the game space.

4.1. Cellular automaton

In a cellular automaton [ 11 ], the game space is divided into cells with their coordinates – , for two-dimensional space. Each cell is defined by one of at least two states: {path, wall}. In the initial step, the state of each cell is randomly selected, after which an iterative process begins: the state of the cell of the next generation ,+ 1 is determined by the state of this , and the neighbor (, ) cells in this generation. This can be written as ,+ 1 = (︀ , , (︀ , )︀ , , ∈ {ℎ, } (3)

There are two commonly used approaches to define neighbor cells: the von Neumann neighborhood and the Moore neighborhood. The von Neumann neighborhood (figure 16) defines neighbor cells as all those that have a common side with the current cell or the distance to which according to the Manhattan metric is equal to one (for the range of one, = 1). The number of cells depends on the range and can be calculated as 2 + ( + 1)2. In contrast, the Moore neighborhood (figure 17) defines that neighbor cells are those to which the Euclidean distance is equal to one (for the range of one, = 1). Similarly, the number of neighbor cells is (2 + 1)2 depending on the range .

From this we can conclude that regardless of which neighborhood is used, the time complexity of one iteration of a cellular automaton in a two-dimensional space is (2), where is the number of cells, is the range of neighbor cells. Since in the last iteration the whole space is remembered to form a game space of the next iteration, the space complexity of a cellular automaton is ().

Cellular automaton approaches are widely used to generate open worlds and simulate the change in the position of fluids over time [ 11 ] (figure 18). In Noita, the environment responds dynamically to player actions. For example, if a player casts a fire spell, it can ignite nearby flammable objects, spread through adjacent combustible pixels, and potentially create chain reactions. Cellular automaton rules dictate how these efects propagate, often resulting in unpredictable and emergent behaviors that enhance the game’s chaos and complexity.

It is worth noting that generation a world with such algorithms does not necessarily guarantee the presence of a single connected path, but when given a well-chosen cell transition function from one state to another, there is a growing tendency for paths and walls to be less distributed, which makes the game space more clustered. In addition, there are relatively few parameters that can be changed to control the generation process: 1. A percentage of inaccessible space (walls); 2. The number of iterations (generations); 3. Definition of neighbor cells; 4. The function of transition from one state to another.

Therefore, cellular automata do not provide suficient control over world PCG, leading to a long process of trial and error to ensure specific gameplay features. However, they are perfect for procedural maze or dungeon generation in roguelike, survival, and puzzle games.

4.2. Genetic algorithms

Evolutionary genetic algorithms [ 13 ] are used to find the optimal solution to optimization problems. Each solution of such problem is expressed in the form of information encoded in a string – a gene (chromosome). The set of all possible solutions is a population. The quality of a chromosome is calculated using a fitness function , which takes into account values that are important for the population. The transition to the next population occurs using the operations of crossing, mutation and selection, which leads to the fact that the average value of the fitness function gradually increases in the next iteration.

When interpreting this approach to world PCG, the ideas of generative grammar are used: a generator graph (figure 19), which determines the generation dependency of certain elements on each other, and a derivation tree (figure 20), which describes an individual in the current population. Each vertex in such a tree is a gene. A population is all possible generated worlds with specified dependencies.

Mutation, which changes an individual independently of the others, and crossover, which relies on two “parents” to create an individual, are used to obtain new members of the population. These operations are applied with a certain probability: mutation only, crossover only, or both mutation and crossover.

There are three types of mutation: grow, cut and alter. Grow adds a random gene to a gene that has not reached the maximum number of children. Cut removes a random gene and the entire subtree that corresponds to it. Alter is characterized by rewriting the parameters of a particular gene to random ones.

During crossover, a random gene (along with the entire subtree) from one parent and a compatible gene from the other parent are selected. After exchanging the subtrees of these individuals, two new representatives of the population are formed (figure 22).

The selection of the next population can be performed with one of several methods to randomly choose the best individuals. Using roulette wheel selection algorithm, we choose an individual with a , where is the value of the fitness function for this individual and ∑︀ is the probability = ∑︀

sum of all individuals fitness function values of current generation. The k-tournament selection method randomly selects individuals from the population and keeps only those with the best fitness function values. In practice, this algorithm is implemented more often than the roulette wheel selection, since it lacks stochastic noise.

After a genetic algorithm processed, the graph should be virtually represented (figure 21). The graph representation algorithm can difer depending on game space type (e.g., building or open world) and they also use similar to a generator graph structure.

The time complexity estimation of genetic algorithms is often dificult because the overall complexity depends on the complexity of the genetic operations [ 14 ]. In general case, we can estimate it as ( * * * ( ) * () * (() + ())), where is the number of generations, is the number of an individual’s genes, is the size of a population, ( ) is the time complexity of the iftness function, (), () and () are the time complexities of crossover, mutation and selection operations respectively. If we assume that genetic operations have constant execution time, then the complexity of the genetic algorithm reduces to ( ). It should be noted that the genetic algorithm is a general approach. For example, sequential Monte Carlo methods and their modifications are used for many problems.

Genetic algorithms provide a wide range of parameters for controlling a generation process. If we consider the problem of generating sequentially connected rooms and rely on the given generator graph in figure 19, then the following parameters can be specified: 1. The area of the game space; 2. The number of rooms; 3. The size of rooms; 4. The number of treasures; 5. Rewards from treasures; 6. The position of treasures; 7. The position of the finish; 8. The distance from the start to the finish.

The number of parameters will grow rapidly as the complexity of the game mechanics increases. Therefore, a genetic algorithm is a universal approach that provides the ability to clearly specify the features for generation. Genetic algorithms are quite generic but the most popular its use cases cover simulation, strategy, combat (tower defense) games.

4.3. Physics simulation

If a generated world is abstractly represented by a graph, then physics simulation can be used to transition to an actual physical representation of the game map. Usually, this approach is helpful in action, adventure, and survival games, where player can interact with environment and cause world terrain changes.

By writing each vertex of the graph into a collider that describes its geometric volumes (a circle in 2D), you can simulate the use of a certain force on this graph with randomly given parameters, which will lead to diferent isomorphic options of generating one world (figure 23). Each vertex is completely incapable of deformation rigid body, but can be characterized, for example, by mass and velocity, which will allow to use momentum between bodies. For edges, a stifness coeficient is specified, which allows to describe how much the final distance between vertices can difer from the initial one.

5. Conclusions

Considered algorithms and approaches are computationally complex, since their growth varies from linearithmic to exponential. This is due to the fact that today’s computers are quite powerful, so developers neglect optimization measures for such algorithms in order to ensure more correct and predictable world generation. Table 1 shows the generalized results of the analysis, which do not World PCG method

Graph grammar Voronyi diagram Perlin noise

Cellular automaton

Genetic algorithms compare the algorithms with each other. These methods are not interchangeable: usually a combination of diferent algorithms and approaches is used, as discussed in this article.

References

[1] J. McCollum , Generative grammars as a form of procedural content generation , The Shaggy Dev , 2022 . URL: https://shaggydev.com/ 2022 /03/16/generative-grammars/.

[2] J. McCollum , An introduction to graph rewriting for procedural content generation , The Shaggy Dev , 2022 . URL: https://shaggydev.com/ 2022 /11/20/graph-rewriting/.

[3] P. Merrell , Example-Based Procedural Modeling Using Graph Grammars , ACM Transactions on Graphics 42 ( 2023 ) 1 - 16 . doi: 10 .1145/3592119.

[4] D. Mount , CMSC 754: Lecture 11 Voronoi Diagrams and Fortune's Algorithm , University of Maryland, 2020 . URL: https://www.cs.umd.edu/class/spring2020/cmsc754/Lects/lect11-vor.pdf.

[5] V. Chugani , Minkowski Distance: A Comprehensive Guide , DataCamp, 2024 . URL: https://www. datacamp.com/tutorial/minkowski-distance.

[6] J. F. Muzzin , How To Use Voronoi Cells for Strategy Game Maps , Medium, 2023 . URL: https: //medium.com/@jaemuzzin/how-to -use-voronoi-cells-for-strategy-game-maps-1deaee9a4b34.

[7] R. MacWha , Generating Digital Worlds Using Perlin Noise, Medium, 2021 . URL: https://medium. com /nerd-for-tech/generating-digital-worlds-using-perlin-noise-5d11237c29e9.

[8] Suboptimal Engineer , What is Perlin Noise?, YouTube , 2023 . URL: https://www.youtube.com/ watch?v= 7fd331zsie0 .

[9] E. Dalefield , Distributed Architecture for Procedural Terrain Generation in Video Games, Master's thesis , Victoria university of Wellington, Wellington, 2024 . URL: https://openaccess.wgtn.ac.nz/articles/thesis/Distributed_Architecture_for_Procedural_ Terrain_Generation_in_Video_Games/25658514?file= 45770220 .

[10] A. Zucconi , The World Generation of Minecraft , 2022 . URL: https://www.alanzucconi.com/ 2022 / 06/05/minecraft-world-generation/.

[11] T. Pagáč , Simulating Game Worlds Using Cellular Automata, Master's thesis , Masaryk University, Brno, 2022 . URL: https://is.muni.cz/th/w12aw/SimulatingWorldsCA.pdf.

[12] P. Purho , Noita: a Game Based on Falling Sand Simulation , 2019 . URL: https://80.lv/articles/ noita -a-game-based-on-falling-sand-simulation/.

[13] V. Kraner , I. Fister , L. Brezočnik, Procedural content generation of custom tower defense game using genetic algorithms , in: I. Karabegović (Ed.), New Technologies, Development and Application IV , volume 233 of Lecture Notes in Networks and Systems , Springer International Publishing, Cham, 2021 , pp. 493 - 503 . doi: 10 .1007/978-3- 030 -75275-0_ 54 .

[14] Y. Pyrih , Computational complexity evaluation of a genetic algorithm, Information and Communication Technologies , Electronic Engineering 4 ( 2024 ) 52 - 60 . URL: https://doi.org/10.23939/ ictee2024. 01 .052.