Level Generation in Unexplored 2

We are very proud of the Unexplored 2 game level generator, this is a program that meets all modern requirements. In a post I will talk about how game levels are created.

We did not have to reinvent the wheel. In Unexplored 1, we already created techniques that greatly influenced the success of the first game. Unexplored 2 just continued what was started. The foundation of our technology consists of two parts: we use multi-stage generation, which almost simulates a process very similar to the work of a living level designer. On top of it we use a technique called " cyclic dungeon generation", which is much better at generating natural-looking levels than most standard generative content creation applications. In this post I’ll talk about the first aspect. Adapting cyclic dungeon generation to Unexplored 2 will be the topic of a future post.

Imitation of “human” level design

The level generator breaks down the process of level generation into a whole set of controlled stages. It goes from high-level planning to a low-level detailed level map. In fact, he first creates a sketch of the level, and then begins to add details until the level is completed and filled.

At each individual stage of this process, we use generative grammars to transform the level generated in the previous stages. In particular, we use tile grammars and graph grammars, which are varieties of more general string grammars that simply search for and replace parts of strings with other strings, much like regular expressions do. If you are not familiar with the concepts of generative grammars and regular expressions, then I recommend that you search for examples on the Internet (or just continue reading - you will not need in-depth knowledge to understand the meaning of this post).

The first stage of the level is relatively simple. We use a low resolution bitmap to locate the very basics of the level. In the example below, the level is initially very simple: it consists only of the entrance (e) on the left, the entrance on the right and connecting the direct path. Most other tiles are either undefined (u) or blocked (B) because they are on the edges of the level.


Figure 1: A simple sketch of the level

At the next stage, the details are added: a group of rooms appears, connected by a gate, which are designed to pass in a certain direction:


Figure 2: Added structure

Tile maps are great for creating level geometry, but it’s more practical to work with graphs to generate structures and gameplay logic. This is what the generator does next:


Figure 3: Base graph

In the graph, some nodes contain subnodes, in our case most of the gates are marked as dangerous (H), and some are marked as open (O).

Based on a fairly simple analysis and generative rules, new elements are added to the graph. For example, the end point (G) is located at a location that is far enough from the entrances. In addition, small dangers are added to the graph to make the level more threatening.


Figure 4: New items added to the graph.

In the meantime, a low-resolution tile map is converted using several noise functions into a high-resolution tile map to give it a more natural look:


Figure 5: High resolution

tile map. Then the information from the graph is used to decorate the tile map and add new elements:


Figure 6: Decorated tile card.

The map as it is is generated solely for presentation in the gameplay. White tiles indicate open spaces, and almost all other tiles indicate very specific gameplay elements, for example, a secret passage through the bushes (green circles), “gates in the thickets” (green squares and lilac stripes) or spawn places for tying trees (red circles with letter s). The main part of the level is still undefined, and at this stage the generator assumes that these areas should be filled so as to block the player’s movement.

He performs this task on several layers: the lower layer indicates the level of height and type of surface, the second adds water in certain locations, and the third layer adds vegetation and other decorations.


Figure 7: Earth surface types (grass, mud, and stones)


Figure 8: Water


Figure 9: Vegetation and other decorations

These layers are then added to the final level data file, to which some more details are added. The game uses this data to place assets and build the level as you see it. There are many tricks at this stage. For example, you may notice that the land tiles in the figure above have strange shapes. These forms are used to create ground “tiles” in such a way that the player does not notice that the source data was a tile map. I will talk about this in the second part of the article.


Figure 10: Ready Level

Adding Gameplay

There are many benefits to this level generation method. The stage of converting a level into a graph is especially important in order to simplify the “reasoning” about the gameplay to the generator. In the example shown above, we did nothing with it except to verify that level targets are created at some distance from the inputs. But for other levels at these stages more tasks are performed.

Take for example a cave map in a more classic dungeon style (compared to the forest level from the example above). The base graph of this level has only one entrance and a couple of new gate types. A pair of them is closed (L): one gate traps the player on one side of the trap (T), and dark green I call the “valve”: this type of gate allows the player to go in only one direction.


Figure 11: Base Cave Count

The structure of this level allows the generator to create a much more complex mission. For example, the only way to get to this level is through a “valve”, forcing the player to look for another way out. The key to open the way out (lower left) is located behind the danger in the upper left, and the target is located behind the gates that trap the player. An example of such a goal would be a passage that collapses behind a player. In general, this creates a cave that is interesting to explore on its own, but Unexplored 2 also has the ability to add creatures and events that blend in at run time.


Figure 12: Locks and keys have been added to the cave.

Using the process described above, the graph is used to generate and populate a fully detailed tile map. The application of various parameters reflecting the cave nature of this level leads to very varying results with destroyed underground structures (blue squares marked with the letter c) and wide abysses with spikes (lilac circles):


Figure 13: Cave Level in Full Detail

Summarize

I hope you got a general idea of ​​how we approach the generation of levels in Unexplored 2. This is a complex multi-stage process, which I plan to write more about in the near future. At least I already promised you to write about the application of cyclic dungeon generation. But you can tell a lot more, from generative storytelling techniques, rendering lines and shading methods to the lengthy design process that we used to create the luck system, as well as other aspects.

Part 2. From tiles to curves, or fun with Voronoi counts

Unexplored 2 content generator generates tile maps. A typical result looks like this:


These tile cards are stacked on top of each other and use different tiles to indicate the types of surface of the earth (in this example grass or dirt), as well as various decorations. In this case, there are several bushes (large green circles), stones (black circles), plants (small green circles), flowers (white circles) and decorative textures (gray squares). There are also special tiles that indicate gameplay data, for example, spawn points marked with the letter “s”. In addition, tiles can be marked with additional information, for example, height level or special subtypes.

Tile maps are a data structure convenient for generators. But at the same time, it is quite straightforward, and the grid is often noticeable in the game. However, after loading the data into the game and placing the assets, the result looks like this:


I think that we hid the tiles pretty well, and that's how we got it.

Voronoi Magic

The trick is that individual tiles correspond to cells in the Voronoi diagram. This diagram can be used to generate much more natural looking shapes. The Voronoi diagram is created by sowing the plane with random points and dividing it into cells in such a way that each point on the plane belongs to the cell corresponding to the nearest starting point. In procedural content generation, Voronoi diagrams can be used in several interesting ways.

A typical Voronoi diagram is created from a random, but fairly uniform distribution of the generating points, which looks something like this:


In Unexplored 2 we use a different kind of distribution of generating points. First, we generate one point for each tile. So we can be sure that each tile on the tile map will correspond to one cell in the Voronoi diagram.

If we place the generating points in the middle of each cell, we get a straight grid that looks exactly like a tile map (for this and other images below I made a chess version in which half of the tiles are rendered yellow so that you can do a little better see patterns):



The easiest way is to improve the chart by simply randomizing the position of each generating point. When moving points, it is worth checking that the point does not go beyond the original tile.

The result looks something like this:



Already better, but very noisy, and thus do not get beautiful winding lines. The picture can be improved by performing “relaxation” of Voronoi diagrams (this is a standard technique for them, which I will not discuss here). But it will still always remain a little noisy, and it is difficult to effectively predict the figures on a scale that exceeds the scale of individual tiles.

To solve this problem, we need not only to move randomly, but to approach this smarter. Different types of movement can have a very different effect. For example, when using Perlin noise, interesting curvy tile cards are obtained. Or you can turn the entire grid into hexagonal tiles by simply moving every second line of the generating points to the left:



We made a real breakthrough when we began to move the generating points in certain patterns to create rounded corners. The first stage of this process is already being performed inside the level generator. The angles between different types of the earth's surface are recognized, and corner tiles are marked with different figures, indicating the way they are deformed to generate a more beautiful environment:


In this case, the difference in elevation levels also causes angles to appear on the tile map. That is why you see additional rounded corners in the grass at the top right and bottom left, where the slopes were generated.

The game uses this information to shift the generating points of the Voronoi graph. Each rounded corner shifts the location of the originating point (see image below). In addition, it also shifts the generating points of its four orthogonal neighbors. This process is cumulative; generating points can move several times if they are near several angles. However, after processing all the offsets, the generating points are a little randomized (about 10% of the tile width in each direction), and the final offset is limited to a maximum of 40% of the tile width.


The result is already getting pretty high quality:



But we have not finished yet ...

Decorate wisely

The overall shape has become better, but the edges are still very straight and look kind of jagged. We will hide this by placing curved assets on the edges where the colors differ. However, the real trick is that one curve is often placed on two edges, and their angles relative to each other are used to determine the direction of the curve.


The result looks like this:


Next, we used 3D assets to add texture clippings:


Finally, we add another asset to fill the level. The location of these assets is determined by the previously generated level data, and in general follows simple principles. We use small assets surrounding larger ones to create natural and beautiful transitions. In particular, it is worth noting that stones are added at the foot of the cliffs, creating variability and visually softening the vertical slopes that are necessary for gameplay:

Local variability

Angles are not the only type of displacement we use. In particular, we want the edges to be straighter next to the artificial structures (for example, the destroyed walls shown below):


In our system, this effect is easy to achieve. We simply add another displacement rule, which prohibits the displacement of tiles with man-made structures. The generator uses small squares to mark such tiles, and the game ensures that all offsets are simply ignored:



If you look at the ground, you can clearly see that certain areas are made straight, while others bend more naturally:


Isn't it beautiful?

There are other rules that can be easily added using this technique. For example, sometimes we force tiles to create a hexagonal pattern so that the narrow paths remain wide enough to move around them. I am sure that we will find other uses for other patterns.

This is one of many reasons why I love Voronoi diagrams. Another time, I will write about how we use them to generate and decorate Unexplored 2 world maps.