Procedural dungeon generation in roguelike

Procedurally generated cards are a basic feature of roguelike. For a genre that is almost synonymous with the concept of “randomness” (and for good reason), randomized cards have become the easiest way to demonstrate its key element, because they affect many aspects of the gameplay - from the research strategy and tactical positioning to the location of objects and enemies.

Note - in tips for completing strategic games, key points on the general battle map are usually described and what needs to be done in them - following the indicated sequence of steps, you can win every time. Of course, players can enjoy trying to solve the puzzle, but no matter how exciting the game is, interest disappears after finding all the solutions.

Therefore, randomized cards provide us with endless replayability, each time setting different tasks for us. In addition, pleasure is enhanced by the fact that the player’s progress depends on his own skill, and not on trial and error. The layout of each new card is 100% unknown, which also adds tension to the process of studying it.

Of course, the advantages of procedural maps are meaningless without a lot of variability in mechanics and content - a monotonous hack-and-slash is not suitable here. Therefore, all roguelike that have stood the test of time have deep gameplay.

This post is the result of my work on generating maps for Cogmind.

Ways

There are many ways to generate maps. Naturally, no method is a universal solution, so most developers tailor their chosen
methods to their games. Of course, it is possible to develop your own way from scratch, however, in order to start studying this topic, it is better to consider the most popular approaches.

I will not go into details of the implementation, because such information is full on the Internet; instead, I’ll just leave links to the sources of each image for explanations.

Bsp trees

BSP trees can be used to create the simplest and most typical roguelike maps — rectangular rooms connected by corridors.


BSP tree example 1 ( source )


BSP tree example 2 ( source )

Tunneling algorithms

Tunneling algorithms dig corridors and rooms in solid “ground”, much like a real dungeon architect would. Except that when using algorithms, often useless or redundant paths are obtained.


Tunnel Plot Example ( source )

A highly randomized tunneling algorithm, Drunkard's Walk, is useful when creating cave-like maps with a mix of open and enclosed spaces.


Drunkard's Walk Example 1 ( source )


Drunkard's Walk, 2 ( source )

Cellular automata

Cellular machines are great for digging out natural looking cave systems. Unlike other methods, in this developer, after generating the map, it is necessary to independently provide connections, because some algorithms are more likely to create divided areas.


Cellular Automata Example 1 ( source )


Cellular Automata, Example 2 ( source )

As you can see from the above types of algorithms, in the article I want to talk about the procedural generation of dungeons. Most roguelike takes place underground, which is logical in terms of design. The very randomized nature of the “bagels” means that at some point in time (and quite often) the player can meet an opponent that he is completely unprepared for and must run away from. In the dungeons there is a sufficient amount of negative space that can be used to control the visible and invisible areas of the viewpoint, and all this is presented in an easily digestible form, i.e. in the form of rectangular rooms, corridors and walls of caves. Dividing meetings with enemies into rooms allows you to create more intense gameplay and fit more content in a small space. Yes, when you try to escape, a meeting with one enemy may end with a meeting with another,

Design

In addition to choosing a generation method (or a combination of several methods), you must set and configure all the parameters for creating maps suitable for the gameplay. Many small rooms or several large ones? A bunch of long corridors or no corridors at all, just rooms connected by doors? Is there a spacious winding cave system that encourages the player to explore, or a linear cave designed this way for the atmosphere?

The map layout does not just reflect the topic, it affects the process of passing the game (or part of it). Many roguelike use rather small rooms and narrow corridors due to the high percentage of close battles. In Cogmind, battle is most often fought at a distance, so usually wide corridors and large rooms are used in the game.

Exploration and fascination

In addition to creating maps that complement the game mechanics, it is also important to pay attention to possible routes of movement from one enemy to another. Empty corridors and rooms are actually useful because the player does not have to fight at every turn. Real players need to be given the opportunity to relax and, more importantly, to give space in which you can figure it out if everything went wrong. In particular, in Cogmind, such additional space is also useful for using stealth - with the proper use of components and tactics, many opponents can be avoided.

But when configuring the card parameters, the main factor that I pay attention to is the number and density of loops. By loops, I mean places where several paths lead to one point. On a map with no loops or almost no loops, the player will often have to go back, but it's not interesting to go back ! Of course, players can decide to go the route along the previous path, for example, to pick up objects or to avoid the enemy, but he can not be forced several times to go the same route. On long roads ending in dead ends, at least treasures should be laid or doors should be found in new areas. Cogmind has fairly large maps by the standards of roguelike, so I had to be especially careful about meaningless ways.

It is also worth noting here that the development and configuration of the map generator is often not performed in the game itself. You can see the whole map and study it at a high level, but this does not mean that if the map “looks good”, then it will be interesting to play on it!


Here is an example of a map that looks good like a cave system, but without the right mechanics it will not be very interesting to play it - there are too many long paths that end in dead ends.

Testing the connections on the card after the generation stage is an important step for deciding whether to use the card (more on this below). More complex procedural methods allow you to embed this requirement in the generation process itself:


A graph-based map generation technique that provides the total number of loops ( source ).

Content

Another challenge is locating objects on maps. Her decision is very dependent on the game itself. The random arrangement of objects can be interesting (and this is exactly what I did for 7DRL!), But the most exciting gameplay can be obtained only by taking into account the terrain and choosing places wisely. This stage often depends on the parameters of the dungeon, which will be discussed below in a separate section.

It is worth mentioning that my Cogmind game uses dungeon areas partially created by hand. Such blank areas need to be embedded in ready-made dungeon generation algorithms. Before the manufacture of such blanks, I had the problem of creating and modifying them; this process is more convenient to perform in REXPaint in combination with text files.

Blanks of map fragments have many advantages, in fact, having all the advantages of manually created levels: control over a separate part of the game process is improved, and their uniqueness draws attention to them and makes them more memorable / significant. In addition, they become common ground that players can discuss among themselves. I'm not too zealous in creating blanks - another advantage of procedural maps is to save time on creating content. But you may need more control over the appearance and content of locations that are important in terms of plot.

Cogmind

Cogmind maps use a combination of tunneling algorithms and cellular automata, which we will discuss below.

Part 2. Map generation: tunneling algorithm

Maps of the main Cogmind dungeon are “dug” by tunneling. The corridors and rooms are dug up in much the same way that a dungeon architect would build housing for his master's servants. An empty map is generated by one or more tunneling mechanisms that move around the map, revealing all areas that will become free space: corridors, doors, rooms and halls.

I like tunneling algorithms because with suitable parameters they can create quite realistic environments.


Behold the robotic underground complex!

sources of inspiration

First, I need to pay tribute to the sources of my inspiration. Previously, tunneling algorithms did not interest me, because when generating large dungeons, they usually created boring repeating patterns. But a few years ago I came across this project , which introduced me to the most important concept - tunneling mechanisms can change their own parameters during movement (this site has a good overview of this idea). The result is a more diverse dungeon, especially on the large maps used by Cogmind.

Specifically, this algorithm has some oddities - why do we need all these useless and redundant corridors? Why does he never create corridors of even width? * I think that many of his shortcomings never became obvious, because the creator of the algorithm did not use it in a real game:


It looks great, but not too realistic.

* I suspect that this is somehow connected with the fact that it is easier to work with symmetric tunneling mechanisms in the code. Although I wrote my own algorithm for working with arbitrary widths of corridors, because from the point of view of logic, tunnels should narrow and expand two pixels at a time, corridors of even width gradually became corridors of odd width, because they narrowed to a width of one cell, and then began to expand again !


A dungeon dug by one even width tunneling mechanism (starting at the top center point) over time begins to create more corridors with an odd width (blue), although corridors with an even width (orange) were originally created.

I can not worry about using corridors of even width, because they are more likely to create off-center connections that do not look very pretty. I like the corridors with a width of 2 cells in terms of gameplay, because they are narrow, but still give enough room for maneuver around other units. But as a standard for a game like Cogmind, corridors with a width of 3 cells are most likely to be better, because battles in it are usually carried out at a distance - you need enough space to select the desired shooting line.

Be that as it may, over the years I have created my own algorithm based on the same principle: the tunneling mechanisms that create the dungeon can evolve over time to vary the patterns.

Parameters

In the behavior of the tunneling mechanism, you can control many parameters: the width, direction, speed, probability of rotation, the probability of creating rooms, the size and shape of the created rooms, the space left between the mechanism and other objects of the dungeon, the moment of completion ...


Example: An enlarged border between corridors and rooms may be desirable if you do not want to make it easier for a player to pave the way to the next room / corridor. In my case, I made the border small, because what good is the destructible terrain if it cannot be used to your advantage to make situations more dynamic? (But be careful - a determined enemy can even shoot you through the wall!)

Everyone who knows the procedural generation of cards knows that the same algorithm can produce very different results when changing parameters. Later I will show other functions that, in combination with this algorithm, make it even more dynamic, but in fact we have already examined everything necessary for the basis of the game.

The size

Many Cogmind cards will be even larger than 7DRL, and they will have more open spaces. The main dungeon was 100 × 100 per map, and the largest maps would be up to 200 × 200. This is four times as much:


The biggest map. The layout and style are not yet completely ready, but the algorithm itself is 90% complete - you still need to clean up the code to reduce the dentate.

Why do we need big cards? Firstly, Cogmind always needed more space, because the battle is mainly fought over long distances - on average, enemies are 15 or more cells away from the player. Maps become even larger in order to accommodate changes in the content of the game.

The world will become larger and more places will appear in it, so we need to distribute the main maps so that transitions between regions do not occur so often. With some styles of play, fights can become larger; who knows, maybe you decide to create a small army of robots to start a small war? The player can now do more in the game, so he needs more space for this.

In addition, the game now puts more emphasis on collecting information. In addition to the sensor details that were in the game version for 7DRL, the player will be able to study the map using the terminals. Large cards will motivate players to use these sources of information whenever possible. Having learned more about the map scheme and the movements of enemies, you can take a secret route, but the map is not so small that this knowledge leads to success too quickly.

Many areas of the map that are empty on 7DRL will now be occupied by machines, so less map space will be free. At the current stage of map generation, the algorithm is only interested in the connectedness of the map, its passage and the ratio of open / closed spaces; the location of objects we will consider below.

Composition

As stated above (and shown in the images), there are quite a few wide corridors and open areas on the new maps.

The version for 7DRL had much more hidden corridors and places, so it seemed that it was easier to hide than it really is - the enemy could easily find you or even go around you in a short way, because he knows the dungeon better than you!

The openness of the map makes the player think more about attracting attention, because it can lead to a collision with the enemy.

Scheme

During the generation process, tunneling mechanisms pave the way for the player to move from entrance to exit, of which there are usually several and they are separated by a guaranteed distance. The way the tunneling mechanisms move and their decisions are the most important aspect that defines the look of the map.

If possible, most mechanisms try to break rooms along their ribs. They are used as places where you can hide / wait or find parts. Also, they may contain machines that are sometimes used simply for the atmosphere, and sometimes not . Rooms with several doors are usually a kind of intersection, opening access to branches from the main corridor.

When turning or changing widths, tunneling mechanisms sometimes create connections. They are used not only for aesthetics - in such connections there may be terminals through which operator bots can control the activity occurring in the neighborhood.


These connections, located along the main corridors, most likely contain access to the terminals.


The idea of ​​having terminals in corridors connected was used in the very first layout of the game.

Tunneling mechanisms also contribute to large areas called halls. If you want to go unnoticed, then before passing through such halls, you should think twice, because when you move next to a patrol or a scout, they will most likely find you.


The halls usually contain large cars that can be divided and create obstacles from them that you can hide behind.

We will return to the maps generated by tunneling in the following parts of the post.

Part 3. Card Generation: Cellular Automata

Unlike the 7DRL game, which only extended to a ten-level “main dungeon,” Cogmind will cover a much larger area. Naturally, the larger the world, the higher should be the variability of areas for research. The action takes place underground, so many areas will turn out to be caves, and cellular automata are usually the best choice for their generation.

But in fact, I will not use the standard solution of cellular automata. (The standard process is written here , here and here ; I will not consider it in detail.) Instead, I will use Andy “Evil Scientist” Stobirsky’s favorite idea, which he described in his blog .

Evil science

Cellular automata are also used in this method - we apply the neighborhood rules to open and close cells in a natural way, but instead of constantly applying the rules for the whole map, we select cells at random at the same time . (We do roguelike and love random, so we use random!)

From the point of view of performance with full optimization, the Andy method is faster than the standard one, while it gives comparable results and is much more flexible for my purposes. I don’t have much experience working with cellular automata, but experimenting with them, I could hardly tune them to get a good result. Andy's method with easecreates good results. Of course, “good” is a subjective point of view, but what I wanted, I could not achieve using vanilla cellular automata. I needed more variability, and the flexibility of this method made it very easy to achieve many beautiful maps. I am sure that variability can be achieved using cellular automata (due to a change in the rules during the generation process), but it will not be as easy as I managed:




I like how on many maps the random distribution of the application of the rules creates variability even within the same map in the form of a mixture of sharp and round, large and small areas.

One of the variables that can be changed using this method and is usually impossible when using cellular automata is the number of cells visited at random, from which additional variability is created. With a decrease in the number of rules applied, rougher maps are created, but the last smoothing phase is still applicable to them and creates quite interesting results:

Connectedness

As is the case with any algorithms for procedural generation of cards based on cellular automata, an important task is to ensure connectivity. If there is no way to move between several unrelated areas of the map, then these areas seem to be completely absent. One solution is to completely remove such distant unconnected areas, but in the case of some cave styles, it is not applicable, because naturally there are many incoherences that arise when using algorithms for creating extended maps with narrow corridors (instead of large spots of rooms).

Therefore, it would be better to create new connections to connect these areas. One option is to “grow” some areas so that they reconnect with others. The second is to break tunnels between them. I prefer tunnels because they 1) correspond to the style and theme I need, and 2) create a system of caves from many small caves that can be individually considered rooms and place objects in them (this advantage will become apparent in the next part, devoted to dungeon metrics).

Here, my solution is slightly different from the solution of Mr. Evil Scientist (mainly because I take into account the specifics of its application in the game, and it creates a more general generator). My solution eliminates most of the U-shaped folds, it performs several phases of digging corridors that may not apply to all caves, has an adjustable ratio of corridors created as caves and branch corridors. Sometimes he decides to dig wider tunnels based on the given parameters, as well as the relative size of the caves being connected.


Tunnels connecting individual caves.

Controlled generation

Cogmind cave maps will not be as large as the main dungeon maps that I showed in the previous section, but even the small square cave maps are not so interesting to explore, at least in the style with the division that I chose. Take for example the map shown above (this is one of the styles that I'm going to use for now):


The path of the square cave map.

If we assume that we will not have any significant destination point in each deadlock, then on the map presented above it will be necessary to often go back, and even a larger number of dug tunnels will only turn it into a more complex network of connections (which will create more loops). But the map will still not be very interesting to explore because of the fundamental difference between caves and ordinary dungeon maps: in the rough edges of the map there are a lot of nooks that need to be carefully examined so as not to miss an important passage.

In an ordinary dungeon with flat walls and square rooms, we can quickly look around the entire visible area and determine fairly accurately where there is a passage and where it is not. In the caves, you cannot be sure that you have not missed something important until you check everything carefully. It becomes boring, especially when you did not immediately move in the right direction.

The solution lies in “controlled” cellular automata. Let the generation be done in the usual way, but we will limit the general form into which the cave should fit, for example, as the narrow corridor shown below.


Interesting caves created by controlled cellular automata.

Thus, we can use a sharp and sharp style with long branches, but at the same time everything will move in one general direction.

Mine

Another variation of this algorithm can be used for mines. Usually these are smaller maps, on which there are rectangular areas excavated for storage and processing machines, as well as the areas of the shafts themselves, connected to them by corridors.


There are more joints and loops in the mines.

Composite cards

Who said that the whole card should be controlled by one algorithm? In special cases for special areas, cellular automata can be well combined with tunneling algorithms.


Secret base?

Part 4. Dungeon Metrics

An algorithm rarely can create an ideal procedurally generated map, and even this happens, some post-processing is required to analyze its scheme. When we look at the map created by the generator, we can quickly see if this scheme is sufficient for our needs; we are also likely to notice bottlenecks in which enemies can gather to stop the player, and areas outside the main path where treasures can lie. However, for a program, a map is simply coordinates telling what this or that area is and not giving any clue about the general composition or scheme. How can we teach a game to understand and use a map in the same way that we do? We need "dungeon metrics."

Requirements

The first and most important thing is to make sure we need the resulting card. Without limiting the results, one algorithm can create many variations of the cards, and some of them may be inappropriate or even unplayable. In such cases, we should discard such a card and start generating again.

Composition

The basic simplest requirement is the resulting volume of playable, “open” space. The lower border ensures that the card will not be too compressed, the upper border will make it not too open.


These two caves are generated by the same algorithm, differing only in one parameter: the volume of required open space (above - 15-30%, below - 40-60%).

Another important requirement is the number of individual rooms / caves of different sizes.


These two cards are generated using the same algorithm, only the required number of rooms differs (above - 20 or more small rooms, below - 20 medium and 5 large).

Path finding

Some games use pre-computed map data to optimize the search for paths, but here I will not consider them (besides, they are not very useful in Cogmind with a completely destructible environment).

Finding paths is an important part of map analysis, because we need to make sure that we can reach one or more exits from the map entry point. This will not be a problem for cellular automata, if we assume that the tunneling phase will do its job, but the tunneling algorithms that create maps using several tunneling mechanisms should verify that all the mechanisms connect the tunnels they create.

Another possible limitation that a path search can impose is the minimum distance between inputs and outputs. If they are too close to each other, then most of the map will remain unexplored, which is especially true in Cogmind, because it does not have an XP system - the player receives the best reward (level development / leveling) when he gets to the exit. If the exit is too close to the entrance, then such a design can be considered bad, because the player will have little motivation to explore the map.

All the rest

An alternative to automating the selection process is procedural generation with manual selection of the set of cards used in the game. This approach works, but the number of card variations is limited by the set chosen by the developer. (However, in some games this method is used.)

When choosing cards to use in a game or just to improve an algorithm, it can be useful to look at the map from a different angle. For example, the monochrome view of the map is useful for checking the space available in the game and the general layout, without being distracted by individual parts of the map.


The usual view on the left is convenient for clearly recognizing and positioning caves, and the monochrome view more clearly shows the game and non-playable space. It is closer to what the player himself sees and feels.

Look at the images in the previous parts, which highlight individual tunnels, caves, rooms, connections, halls, etc. These are not processed images - the debugging functions of the card generator itself have many different modes that help in development.

Another tip for effective problem solving during development: always output in the generator a random seed (seed) used to generate each card (I add them to the list). Due to this, we can always pass this number back to the generator in order to regenerate the same map and deal with errors or consider options for improving the algorithm.

Posts

Having decided to choose the generated map, we have to do much more. It is time to analyze the content and layout to record as much useful information as possible.

The simplest component that we want to remember is the location of all rooms / caves. Rooms (and corridors) dug by tunneling mechanisms are easy to record because we create them ourselves and can record them in the process. The caves are another story, because they are grown at random. To find them, we simply scan the map with the standard floodfill algorithm.


Finding caves on the map by filling before connecting them.

This is another advantage of creating a set of caves not connected to each other by cellular automata and connecting them at the post-processing stage: the caves are naturally separated into separate "rooms" by the algorithm itself! This means that in the future we can take advantage of the analysis methods used for conventional dungeons with rooms and corridors. We will tell you more about this later.

When choosing how to use different parts of the map, location and size are not the only important information. We can record the location of doors and their direction (which is used to optimize some types of search for paths or ambushes), the connection of rooms and corridors with certain connections, the connection of tunnels with caves, as well as caves that are accessible from the current cave. My favorite data, which I will talk about later, is relative isolation / connectedness.

The decision on how to use the card as a whole can be affected by the general statistics obtained for the finished card. These are such data as the percentage of cell types, the maximum and average isolation of areas, the largest cave / hall, etc. Of course, they can also be used as additional requirements for screening unsuitable cards.

Analysis and its application

How can we use all this collected data, except for deciding on its suitability? The most obvious use is item placement.

Robots and details in the game for 7DRL were created without considering whether they are in a room or a corridor; you could find a bunch of parts lying somewhere in an arbitrary place. It will be more logical to store them for the most part in rooms, both for realism and in terms of gameplay (“is it worth opening the door to look for details, even if my scanners show that there are robots behind it that may turn out to be hostile?”) .

As mentioned above, there is a high probability of terminals in corridor connections, and larger cars should be in large halls. Guards most often patrol intersections. Choosing the best places would be difficult without recording the details of the map layout.

Connectedness

My favorite cave system analytics tool is to determine the relative coherence of each cave.


Visualization of the connectedness of the caves. The brighter the cave, the better it is associated with the system.

Since the number of direct connections in itself is of little use in many cases, I define “connectedness” as the number of directly connected caves plus the number of caves with which they are connected. In the visualization shown above, the separately located caves have a darker shade, which means less connectivity.

Less connected caves in different parts of the map are likely positions for entrances / exits; others will be good candidates for loot, secrets, or surprises unpleasant for curious researchers.

On the other hand, in caves with high cohesion, the concentration of enemy activity is most likely.

Isolation

All rooms of maps created by the tunneling algorithm are evaluated according to the value of "isolation". For isolation, a different calculation criterion is used, because map connectivity is much higher. It is based on the distance to the shortest path that a player can go from entrance to exit.


Visualization of the isolation of rooms. Dark red rooms farther from the shortest routes on the map.

The four entrances / exits (pink dots) are connected by the shortest paths between them (green lines), then from the entrance to each room a search is made for the paths to the nearest point of any of these lines. Note that the farther the room is from the path, the darker its shade of red. (In this visualization, all rooms do not have a red tint, the relative isolation value of which is below average. The “average” is based on the values ​​of the map.) The more the room is isolated, the more likely it will contain something valuable or interesting to the player. Of course, the idea of ​​"isolation" implies that the player knows where to move, although in reality this is not so! But this is normal, because the player deserves a small reward for a strong deviation from his path and overcoming a large number of obstacles.

Part 5. Dungeon blanks

Procedurally generated cards are wonderful, but even with the variability built into the algorithm, he will not be able to create anything that goes beyond its parameters. This is good, because it allows you to maintain the integrity of the style, but separate areas become a victim of this.

Manually created fragments of maps allow you to restore the necessary characterization of the style if necessary, whether it be a combination with the generated content or areas important for the plot in which a specific atmosphere is required. The blanks integrated into the rest of the card stand out and are memorized by this.


Just a silly example, but writing a separate algorithm for procedural skull generation would be too much overkill.

Billets allow you to deviate from the path, which otherwise would be too repetitive gameplay (even if the repeatability is hidden by several layers of random content). In addition, they provide players with a “common foundation” to discuss individual parts of the game. The more random and unpredictable roguelike, the more the discussion is limited to “general survival tips." Immutable fields allow us to open up a whole new category of discussions - “what can we do here ”, instead of “what can we do when XYZ”.

And this is not the only strategy - thanks to unchangeable areas, a completely new category of stories may arise, because readers who play the game will more clearly understand where the story is happening, having already seen the same area with their own eyes.

Create blanks

I decided to draw blanks in REXPaint , assigning different types of colors to each cell type and painting them on the first layer.


In the initial tests, the same palette was used as in the algorithm development program.

In other layers of the image, additional information is stored, because blanks are more than just their layout.


I changed the palette to simplify the design process, giving it a black background, similar to the one used in the game.

The figure above shows a fully configured workpiece with test content. Layer 2 (above layer 1) contains information about the connection / integration with the map (this yellow deuce,
which I will discuss below). On layer 3, unique cars / interior elements are drawn (these gray lines and rectangles). Layer 4 contains links indicating the location of static objects (green numbers / numbers).

All blanks with certain objects (and there are most of them) should have an accompanying text file that describes the objects placed on layer 4.


Test data / script for the preparation of the skull, which contains a random assortment of objects. Ideally, this information would be entered / viewed / changed directly in the workpiece editor, but in the case of Cogmind, workpieces and their objects are quite simple, so I decided to use text files.

Objects can be listed in any order, and we can use any letter or number as a link. Additional functions, including the possibility of randomized objects, will be implemented if necessary - we created only what the game needs to work at the most basic level.

And this is how the blank is loaded in the game on a real map:


A skull test appears in the game. (The map generator added an extra robot and object to it, because this area is not removed from the boundaries of a random object spawn.)

Integration

The main problem with blanks now is how to connect them to the rest of the map. If we just let the generator do whatever it wants, we can turn the blank into chaos and destroy all its meaning, so the dark gray cells around the skull forbid the map generator to block them. Instead, we control the connections from the workpiece.

Firstly, based on the instructions from the text file of the map description, the algorithm reads the .xp files (created by REXPaint), parses their contents, and then places the cells on the map (if indicated, then in random places) before proceeding with another generation. The yellow cell in the skull example indicates that when the construction of the corridors begins, the tunneling mechanism should begin to dig a tunnel 2 cells wide to the south (the closest border), starting at this point, and then connect to the rest of the map.


The part of the map description file that hosts the blank, where “type &” is the name of the file containing the image. Also, in addition to blanks, maps support other generalized [FEATURE] (elements) that are most useful for defining areas outside the scope of the generator.

Since the elements are located before the start of tunneling and random generation, they also support randomized placement, so, for example, you will never find the same interesting point in the same area of ​​the map.

Application

Cutting skulls and other interesting shapes from a map is not quite what I mean by its “character”. The blanks are ideal for creating more functional circuits that meet certain requirements of the game, like special NPCs and areas important for the plot.

I don’t want the players to “look for” a certain point on the map, so that the necessary meeting takes place. I just create it.


You meet a potential ally in the main hall, and if he doesn’t like what you say, his servant, hanging in the side rooms, will attack you, otherwise he will let you into a secret warehouse of weapons in the back room. (Or you can use the terrain scanner to find out that you can just shoot / drill a hole in the back room from another part of the map and take whatever you want.)

Approximately the same method is used to add manually created content to the caves, although here instead of an algorithm For tunneling, it’s more useful to use direct links so that they do not get out of control and flood the caves.


Hmm, we can go in the front door or not.

Part 6. Generation and filling of caves

Up to this point, most Cogmind cards were generated in the style of “rooms and corridors”. A wide range of customizable parameters, combined with a lot of thematic content (and presets!) Gave this style great potential in creating unique gameplay for different areas of the world.

On the other hand, bagels, combining several different card generators, can deal much better with setting new challenges and challenges for the player. Take a look at the assembly of some of the map types used in Dungeon Crawl: Stone Soup:


Examples of map generation variability in DCSS (for some descriptions, see here ).

Impressive!

Along with purely gameplay variation, I need to take into account the surroundings, ENT and Cogmind atmosphere, so the design of the cards depends on them, which reduces the possibility of too radical changes. But besides fully automatically created parts of the world, there is the possibility of adding more natural areas located in the interior of the planet, namely caves.

Of course, the problems of creating caves differ from the tasks of the original maps and related algorithms. Fortunately, from the point of view of lore and gameplay, caves have a completely different meaning, and there is no “living ecosystem” in them .used in the main areas of the world, so you do not need to migrate these turnkey systems to match the new architecture. (In addition, such a migration would reduce the effect of using a completely different map generator!) Therefore, all the caves are in branches - this concept is described in the Layout section of this article . Such branches have a different composition and purpose; you can read about them if you are not already familiar with them.

In this part I will not consider the content in detail (therefore, there are almost no spoilers in it); instead, we will study the design and technical solutions that are considered when generating caves.

Cave Generation

I already made a brief introduction to the method of generating caves above, in the part devoted to the algorithm of randomized cellular automata. Here I will not repeat the basic information, although at the time of this writing, the parameters for adding caves to the world had not yet been configured (images were created in the demo test program of the map generator), so you should take a look at how the cave schemes actually look in the game.

First, you need to know that after the release last year , one variation in the form of mines was added to the working cave generator :


Fully explored mine.

In fact, these are small square areas containing scattered caves mixed with dug rooms that are connected by tunnels.

Real cave systems are much larger, and since individual caves have more room for expansion, they are more likely to generate additional nooks.


Completely open map of caves without content. The map is overlaid with images of the main loops and paths.

For reference, I have drawn illustrations showing the relatively linear structure of the passage and the main loops . Of course, there are loops that can be used for tactical purposes, but in general they are much smaller than in other areas of the world - for some players this can greatly affect the strategy. Design in the style of “linear with loops” should not allow the map to be too linear, while saving the player from the annoying return back. (And of course, the player can independently create loops, destroying the necessary walls.)

Cave filling

Although the system for creating procedural schemes of caves was ready back in 2014, I added the first stage of content generation only last year.

It has the form of “meetings”, in which each cave (similar to rooms on maps from rooms and corridors) has its own content obtained from a pool of possible meetings, divided into four categories: small things, rewards, risk and rewards, threat. The meeting system is described in more detail at the end of the post on the composition of maps .

For example, in the case of a mine, the potential distribution of meetings might look like this:


A mine with distributed meeting types marked with the corresponding category color.

This function was used to fill other branches, including cave maps in the form of mines. But the mines are relatively small and they contain a fairly limited set of simple meetings, so they don’t need support for workpieces, which allowed me to quite simply create a wider range of unique (but still dynamic) content. Honestly, I did not have enough time to implement the cave blanks until the release of the game in 2015, which also played a role.

In full-sized caves, which are much larger than mines, better meetings are also required. And there must definitely be more. Blanks can help a lot in these areas, because hard-setting content is a slow and error-prone process. Scripting support for meetings has been significantly improved compared to the description in the previous part, and many other functions have also been added to the content of workpieces in other branches.

The last thing I really needed was support for the workpieces in the caves. Well, yes, in the caves there is support for blanks, but not blanks for meetings , which are a more important and flexible type.

There are two ways to add blanks to Cogmind cards. The first is to integrate them into the cave generator itself, which is not even part of the game engine (i.e. it can be launched without Cogmind itself), and by its very nature, its capabilities are limited, because it has blanks beforehow the caves will be generated. Therefore, these blanks had to play the main role on the map, for example, to be a huge and important immutable area or special inputs / outputs. If you use workpieces of this type too actively, then as a result the cards will become too repeatable and recognizable, because this system is not very flexible (at least if you do not make additional efforts to work on each new card). Therefore, it will be more efficient to add most of the cave blanks using the second method - the meeting system.

This raises the problem: how to integrate static blanks into a cave map that has already been generated?

The workpieces themselves have a predetermined shape, and it is obvious that we cannot change it to adapt to the environment, so the only option for us is to terraform the caves so that they fit the workpieces. This process should not affect the connectedness of the caves, and the result should look good and not turn the map into chaos.

I added two ways to integrate blanks and caves. I hope there will be enough of them.

Centered blanks

The most easily realized cave blank is very intrusive; it is simply inserted into the geometric center of the parent cave. (It should be recalled that here by a cave I mean a separate cave room, one of the many that make up the cave system.) Here is an example of an outpost blank inserted directly into a sufficiently large cave:


Geometric centering of the outpost in the parent cave.

Note that the territory of the outpost completely rewrites the closed and open areas below it, and around it there is an open buffer zone. The solution is radical, but quite suitable here.

I decided to center the workpiece relative to the geometricthe center of its cave (that is, to a position tending to the largest open areas of this cave) in case there is a large open area at one end of the parent cave and a long, extended corridor from the other. In this case, the geometric center of the cave will be at some distance from the simple coordinate center. In this situation, the coordinate center is likely to violate one of the rules governing the placement of workpieces of this type: workpieces can be superimposed on any land and the parent cave itself, but not other caves .

One of the limitations of a centered blank design is that they should be rectangular, but in the future I can get rid of this limitation if it seems annoying to me. Organic / rounded centered blanks can have a thematic purpose, especially in caves, but technically in the existing system they can be simulated by rounding the corners of the blank.

Here I must remind readers that the blanks are not static - many have different schemes and randomized content, so even with one type of meeting there is great variability. This leads to amusing situations for new players (“oh, I remember this place from the last time, there is a friendly robot inside - WELL, WHY HE SHOOTS ME”), and at the same time creates strategic difficulties for experienced players (“there is definitely there is a useful loot and I can take out the usual guards, but is it worth the small probability that I will be ambushed by more powerful opponents? ”).

As I mentioned several times when I talked about the structure of the world, branches should become less predictable parts of the world, compared to the main complex, in which procedurally controlled systems are actively used, but they are quite constant and predictable for an experienced player. Thus, I create two different types of main areas between which the player can move. From the point of view of design, workpieces are “manual” content located on the branches, so it is very important to implement them correctly.

Recessed blanks

These systems turned out to be more complicated.

It was necessary to find a way to add blank areas that almost did not affect the structure in order to create a more standard cave system in which the player finds interesting meetings outside the main route, or at least so that they are not inserted right in the middle of the cave. This meant that I needed to find a way to tear out areas for blanks at the borders of existing caves. That is, for such excavations, sufficient space was necessary, as well as a way to effectively find such spaces.

As you can see in the image above, the caves are packed quite tightly. Therefore, at first I decided that in order to significantly increase the amount of land (the area that can be dug) between caves, it is necessary to generate caves in two stages: in the first stage, the process of setting cave-like spots marking borders in the process of the usual map generation process is used similar to cellular automata; in the second stage, a normal process is performed, which will automatically avoid the “voids” dug in the first stage. These voids in the future should become available for tearing blanks. Although this sounds promising, the more useful this approach (i.e., the more voids), the stronger it affects the caves as a whole: it lengthens the corridors and increases the space between the individual caves, even if there are no blanks between them.

There is a much simpler alternative that does not reduce the integrity of ready-made cave schemes: you can simply expand the area to be dug around the outer borders of the map. Now we will have plenty of room to dig! Then the next stage begins: where exactly do you start digging? It’s very easy to determine by eye - we can immediately see places ideally suited for digging up small caves, but in the code of the cave they are simply numbered areas with a list of internal coordinates. Therefore, at this stage, the question was to select the minimum set of rules that allows you to search for suitable places and satisfy all conditions and potential patterns when tearing areas for workpieces.


It took me two hours to develop a suitable set of rules.

The resulting rules turned out to be rather brute force, but they worked, so I decided to use them.


Steps to embed a workpiece in a cave wall.

1. We select a random blank for a given meeting and turn it so that it looks in a random direction of the world.
2. We select a random open cell in the cave, which should become one front corner of the location of the workpiece. Then, based on the length of the front face of the workpiece, we determine where the opposite angle should be. If the second corner is outside the cave, then try to pick up other points.
3. We measure the distance along the imaginary sides of the workpiece until it collides with the wall.
4. У каждой заготовки есть задаваемое вручную значение «максимальной протяжённости» (maxProtrusion). Оно является ограничением глубины, на которую она может вдаваться в родительскую пещеру. Если расстояние, измеренное по любой из сторон, превышает значение maxProtrusion, то сдвигаем углы обратно к стене, пока оба значения не будут в пределах этого значения. (Если расстояния, при котором значение протяжённости можно соблюсти с обеих сторон, то возвращаемся к этапу 2.)
5. Проверяем правильность целевой области заготовки: «внешний прямоугольник» не может содержать лестниц (потому что он перезапишет их) а «внутренний прямоугольник» может быть только землёй — не допускаются даже открытые области той же пещеры, потому что они могут создавать неожиданные/нежелательные дополнительные входы в область заготовки.
6. Также проверяем, что существует стена хотя бы толщиной в одну ячейку вдоль сторон и задней части внутреннего прямоугольника (то есть он, например, не касается непосредственно другой открытой пещеры или области заготовки).
7. Располагаем заготовку на карте! Затем преобразуем в стену все ячейки земли вокруг внешней границы, которые соседствуют с открытым пространством заготовки.
8. Добавляем объекты в соответствии с описанием заготовки, например, терминал, позволяющий открыть дверь и подобрать кучу отличного оружия.

If within a certain number of attempts no suitable areas were found in the current cave, then we try to pick up other random preparations for the meeting, and if they do not fit, then we proceed to the next cave. (Meetings are chosen first, so the task is to find a place suitable for them.)

Unlike centered blanks, embedded blanks may not be rectangular, because their sides and rear boundaries are guaranteed to be in the ground, that is, their appearance in any case will resemble a cave, as shown in the example above.

The diagrams shown above are drawn in REXPaint . Here are screenshots of real workpieces generated in the game:


An example of an embedded workpiece in a game.