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

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

Therefore, randomized cards provide us with infinite replayability, each time setting us different tasks. In addition, the pleasure is enhanced by the fact that the player's progress depends on his own skill, and not on trial and error. The scheme of each new card is 100% unknown, which also adds to the intensity of the process of studying it.
')
Of course, the advantages of procedural maps are meaningless without a great variety of mechanics and content - monotonous hack-and-slash will not work here. Therefore, all roguelike who have stood the test of time have deep gameplay.

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

Ways

There are many ways to generate maps. Naturally, no method is a universal solution, so most developers customize their chosen
ways for their games. Of course, it is possible to develop your own way from scratch, but in order to start exploring 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 for each image where explanations can be found.

Bsp-trees

BSP-trees can be used to create the simplest and most characteristic of roguelike maps - rectangular rooms connected with each other by corridors.


BSP-tree, example 1 ( source )


BSP-tree, example 2 ( source )

Tunneling algorithms

Tunneling algorithms (tunneling algorithms) dig through corridors and rooms in solid “ground”, almost in the same way as a real dungeon architect. Except that when using algorithms, useless or unnecessary paths are often obtained.


Example Tunnel Plotter ( source )

The highly-randomized tunneling algorithm of the Drunkard's Walk (“Drunk Walk”) is useful in creating cave-like maps with a mix of open and closed 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. In contrast to other methods in this, the developer, after generating a map, must independently provide connections, because some algorithms have a high probability of creating divided areas.


Cellular automata, example 1 ( source )


Cellular automata, example 2 ( source )

As can be seen from the above types of algorithms, in the article I want to talk about procedural generation of dungeons . The action of 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) a player can meet an opponent for whom he is completely unprepared and must run. In the dungeons there is a sufficient amount of negative space that can be used to control the visible and invisible from the point of view areas, and all this is presented in an easily digestible form, i.e. in the form of rectangular rooms, corridors and walls of caves. Separating meetings with enemies into rooms allows you to create more intense gameplay and fit more content in a small space. Yes, when you are trying to escape, a meeting with one enemy may end with a meeting with another, but this is why every experienced roguelike lover will advise you never to run into suspense!

Design

In addition to choosing the method of generation (or a combination of several methods), you must set and configure all the parameters to create maps that are suitable for gameplay. Many small rooms or a few large ones? A bunch of long corridors or no corridors at all, just rooms connected by doors? A spacious winding cavern system stimulating the player to explore, or a linear cave decorated like that for the sake of the atmosphere?

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

Study 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 should be given the opportunity to relax and, more importantly, to give space in which you can figure out if everything went wrong. In particular, in Cogmind, such additional space is also useful for using stealth - with the correct use of components and tactics, many opponents can be avoided.

But when adjusting card parameters, the main factor to which I pay attention is the number and density of loops. By loops, I mean places in which several paths lead to one point. On the map without loops or almost without loops, the player will often have to go back, and it's not interesting to go back! Of course, players can decide to go the route of the previous path, for example, to pick up items or avoid the enemy, but it can not be forced to pass several times a single route. On long paths ending in dead ends, at least there must be treasures or doors to new areas. In Cogmind, the maps are quite large by the standards of roguelike, so I had to be especially attentive to senseless ways.

Here it is also worth noting 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 card “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 proper mechanics, it will not be very interesting to play - too many long paths ending in dead ends.

Testing 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 the location on the maps of objects. Its decision depends very much on the game itself. The random arrangement of objects can be interesting (yes, that's exactly what I did for 7DRL!), But the most fascinating gameplay can be obtained only by taking into account the terrain and reasonably choosing places. This stage often depends on the parameters of the dungeon, which will be discussed below in a separate section.

It is worth mentioning that in my game Cogmind dungeon areas are used, partially created by hand. Such procurement areas need to be built into ready-made dungeon generation algorithms. Before making 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.

The fragments of the map fragments have many advantages, in fact, having all the advantages of manually created levels: the control over a separate part of the gameplay is improved, and their uniqueness attracts attention to them and makes them more memorable / meaningful. In addition, they become points of contact that players can discuss among themselves. I'm not too zealous in the creation of 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 from the point of view of the 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 "prokapyvayutsya" tunneling. Corridors and rooms are dug up in much the same way as a dungeon architect would build housing for his master's servants. An empty map is generated by one or several 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 the right parameters, they can create fairly realistic environments.


See the underground complex controlled by robots!

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 repetitive patterns. But a few years ago I came across this project , which introduced me to the most important concept - the tunneling mechanisms can change their own parameters in the process of movement (this site has a good overview of this idea). The result is a more diverse dungeon, especially on larger maps that are used in 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 flaws never became obvious, because the creator of the algorithm did not use it in a real game:


It looks cool, but not too realistic.

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


A dungeon dug out by a single tunneling mechanism with an even width (starting from the upper center point) eventually begins to create more corridors with an odd width (blue), although originally corridors with an even width (orange) were created.

I can not worry about using even-width corridors because they are more likely to create off-center connections that do not look very nice. I like the corridors 2 cells wide in terms of gameplay, because they are narrow, but still provide enough space for maneuver around other units. But as a standard for a game like Cogmind, corridors 3 cells wide will most likely be better, because battles in it are usually fought at a distance — enough space is needed to select the right line of fire.

Anyway, over the years I have created my own algorithm based on the same principle: tunneling mechanisms that create a dungeon can evolve over time in order to vary the schemes.

Options

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


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

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

The size

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


The biggest card. The scheme and style are not fully ready yet, but the algorithm itself is 90% complete - you need to clean the code to reduce jagging.

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

The world will become bigger and more places will appear in it, so we need to distribute the main maps so that transitions between regions occur less frequently. With some styles of play, battles may 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 focuses more on gathering information. In addition to the sensor parts that were in the 7DRL version of the game, the player will be able to examine the card using the terminals. Large cards will motivate players to use these sources of information whenever possible. Having learned more about the map of the map and the movements of the enemies, you can take a hiding route, but the map is not so small that this knowledge leads to success too quickly.

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

Composition

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

In the 7DRL version there were much more hidden corridors and places, so it seemed that it was easier to hide than it actually is - the enemy can find you without any problems or even get around you on a short path, because he knows the dungeon better than you!

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

Scheme

In the process of generating tunneling mechanisms pave the way for the player to move from the entrance to the exit, which are usually several and they are separated by a guaranteed distance. The way of movement of tunneling mechanisms and their decision making is the most important aspect that determines the appearance of the map.

Whenever possible, most mechanisms try to break through rooms along their ribs. They are used as places where you can hide / wait or find details. They may also contain cars 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 cornering or changing widths, tunneling mechanisms sometimes create connections. They are used not only for aesthetics - in such connections there can be terminals through which the bots-operators 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 ​​presence in the connections of the corridors of the terminals was used in the very first layout of the game.

Also, tunneling mechanisms 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 close to a patrol or scout you will most likely be found.


The halls usually contain large cars that can be divided and create obstacles out of which to hide.

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 study. The action takes place underground, so many areas will turn out to be caves, and cellular automata are usually the best choice for generating them.

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

Evil science

In this method, cellular automata are also used — we apply the neighborhood rules to open and close cells in a natural way, but instead of constantly applying the rules for the entire map, we simultaneously select cells randomly . (We make roguelike and love random, so we use random!)

In terms of performance with full optimization, the Andy method is faster than the standard one, while yielding comparable results and at the same time it is much more flexible for my purposes. I do not have much experience with cellular automata, but having experimented with them, I could hardly adjust them to get a good result. Andy's method easily creates good results. Of course, “good” is a subjective point of view, but what I wanted, I could not achieve with the help of vanilla cellular automata. I needed more variability, and the flexibility of this method made it very easy to achieve many beautiful cards. I am sure that variability can be achieved with the help of cellular automata (due to the change of rules in the generation process), but this 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 one map in the form of a mix of sharp and rounded, large and small areas.

One of the variables that can be changed using this method is usually not possible when using cellular automata - the number of cells visited at random from which additional variability is created from. By reducing the number of rules applied, coarser maps are created, but the last smoothing phase is still applicable to them and creates quite interesting results:

Connectedness

As in the case of 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 do not seem to exist at all. One solution is to completely remove such remote unrelated areas, but in the case of some styles of caves it is inapplicable, because naturally there are a lot of inconsistencies that arise when using algorithms for creating long maps with narrow corridors (instead of large room spots).

Therefore, it will be better to create new connections for connecting these areas. One option is to “grow” some areas so that they can connect with others again. The second is to break through the tunnels between them.I prefer tunnel connections, because they 1) correspond to the style and theme I need, and 2) create a system of caves from a multitude of small caves, which can be considered as rooms and place objects in them (this advantage will become obvious in the next section on 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 use in the game, and it creates a more general generator). In my decision, most of the U-shaped folds are eliminated, it performs several phases of digging corridors that may not apply to all caves, has a customizable ratio of corridors and branching corridors created as caves. Sometimes he decides to dig wider tunnels based on the parameters set, as well as the relative size of the caves to be joined.


Tunnels connecting separate caves.

Managed Generation

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


The path of the square cave map.

If we assume that we do not have any significant destination at each impasse, then on the map above we will often need to go back, and even more tunnels that have been dug out 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: the rough edges of the map are full of back streets, which 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 glance around the entire visible area and quite accurately determine where the passage is and where it is not. In the caves you can not be sure that you did not miss something important until you check everything carefully. It becomes boring, especially when you do 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 shape in which the cave should fit, for example, as shown in the narrow corridor below.


Interesting caves created by controlled cellular automata.

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

Mines

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


In the mines more connections and loops.

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

The algorithm can rarely 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 understand if this scheme is enough for our needs; we will also most likely notice the bottlenecks in which enemies can gather to stop the player, and areas outside the main path in which treasures can lie. However, for a program, a map is simply coordinates that indicate what this or that area is and do not give any clues about the overall composition or scheme. How can we teach the game to understand and use the map in the same way as we do? We need "dungeon metrics."

Requirements

The first and most important thing is to make sure that we need the resulting card. Without limiting the results, one algorithm can create many variations of maps, and some of them may be unsuitable or non-playable at all. In such cases, we should discard such a card and start generating anew.

Composition

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


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

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


These two maps are generated using the same algorithm, only the required number of rooms differs (at the top - 20 or more small rooms, at the bottom - 20 medium and 5 large).

Search for ways

In some games, pre-computed map data is used 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 entry point to the map. This will not be a problem for cellular automata, if we assume that the tunneling phase performs its work, but tunneling algorithms that create maps using several tunneling mechanisms should check that all the mechanisms connect the tunnels created by them.

Another possible constraint that the search for paths may 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 best reward (development / leveling) the player receives when they reach the exit. If the exit is too close to the entrance, then this 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 a manual selection of a set of cards used in the game. This approach works, but the number of map variations is limited by the set chosen by the developer. (However, in some games this method is used.)

When choosing cards for use in the game or simply to improve the algorithm, it is useful to examine the map from different angles. For example, the monochrome map view is useful for checking the available space in the game and the general scheme, without being distracted by separate parts of the map.


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

Look at the images in the previous sections, which have separate 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 piece of advice for effectively solving problems in the development process: always output a random seed number (seed) used to generate each card (I add them to the list). Because of this, we can always transfer this number back to the generator in order to regenerate the same map and deal with errors or consider options for improving the algorithm.

Records

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

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


Finding caves on the map using the fill before connecting them.

This is another advantage of the creation of numerous caves not connected to each other by cellular automata and their connection at the post-processing stage: the caves are naturally divided into separate “rooms” by the algorithm itself! This means that in the future we can take advantage of the analysis methods used for ordinary dungeons with rooms and corridors. More on this we will explain 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 path finding or ambush), connecting rooms and corridors with certain connections, connecting tunnels with caves, as well as caves that are accessible from the current cave. My favorite data, which I will discuss later, is relative isolation / connectedness.

The decision on how to use the map as a whole may also be affected by the overall statistics obtained for the finished map. This data is such 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 out unsuitable cards.

Analysis and its application

How can we use all of these collected data, except to make a decision about its suitability? The most obvious application is the placement of items.

Robots and parts in the game for the 7DRL were created without taking into account whether they are in a room or a corridor; it was possible to find a bunch of parts lying around somewhere in an arbitrary place. It would be more logical to keep them mostly 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 be hostile?”) .

As mentioned above, there is a high probability of having terminals in the corridor connections, and there must be more cars in large halls. Security guards most often patrol intersections. Choosing the best places would be difficult without recording the details of the map scheme.

Connectedness

My favorite tool for analyzing cavern systems is to determine the relative connectedness of each cave.


Visualization of connectedness of caves. The brighter the cave, the better it is connected to the system.

Since the number of direct connections is not useful 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 a smaller value of connectedness.

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

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

Isolation

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


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

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 is its shade of red. (In this visualization, all rooms whose relative isolation is below average are not red. The “average” is based on the map values.) The more isolated the room, 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 go, 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 maps are great, but even with the variability built into the algorithm, it will not be able to create anything beyond its parameters. This is good because it allows to preserve the integrity of the style, but separate areas become victims of this.

Fragments of maps created manually make it possible, if necessary, to restore the necessary specificity of the style, be it a combination with the generated content or areas important for the plot, in which a specific atmosphere is required. Billets, integrated into the rest of the card, are very highlighted and remembered by this.


Just a stupid example, but writing a separate algorithm for procedural skull generation would be too big a brute force.

Blanks 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", which allows them to discuss individual parts of the game. The more random and unpredictable the roguelike, the more the discussion is limited to "general survival tips." Immutable areas allow us to open up a completely 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 the unchangeable areas, a completely new category of stories may arise, because readers who have played the game will more clearly understand where the story is going on, having already seen the same area with their own eyes.

Creating blanks

I decided to paint the blanks in REXPaint , assigning each type of cells different colors of the palette and painting them on the first layer.


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

Additional information is stored in other layers of the image, 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 customized blank with test content. Layer 2 (above Layer 1) contains the connection / integration information with the map (this yellow two,
which I will discuss below). On layer 3 unique cars / interior elements are drawn (these gray lines and rectangles). Layer 4 contains links pointing to the location of static objects (green numbers / numbers).

All blanks that have certain objects (and there are most of them) must 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 range of objects. Ideally, this information would be entered / viewed / modified 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 reference. Additional functions, including the possibility of randomized objects, will be implemented if necessary - we have created only what is necessary for the game 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 item to it, because this area is not turned off from the limits of the random spawn of objects.)

Integration

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

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


The part of the map description file that hosts the stub, where “type &” is the name of the file containing the image. In addition to map blanks, other generalized [FEATURE] (elements) are also most useful for specifying areas outside the generator.

Since the elements are arranged before the start of tunneling and random generation, they also support random 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 the map is not exactly what I mean by her “character”. The blanks are ideal for creating more functional schemes that meet the specific requirements of the game, like special NPC and areas important for the plot.

I do not 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 servants will be attacking you in the side rooms, otherwise he will let you into a secret armory in the far room. (Or you can use a relief scanner to find out that you can simply 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 the tunneling algorithm, it is more useful to use direct links so that they do not get out of control and flood the caves.


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

Part 6. Generation and filling of caves

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

On the other hand, “bagels”, combining several different card generators, can cope much better with posing new challenges and challenges for the player. Look at the build of some of the types of maps used in Dungeon Crawl: Stone Soup:


Examples of card generation variability in DCSS (see some descriptions here ).

Impressive!

Along with pure gameplay variation, I need to consider the entourage, ent and atmosphere of Cogmind, so the design of the cards depends on them, which reduces the possibility of too radical changes. But besides the fully automatically created parts of the world there is the possibility of adding more natural areas that are in the insides of the planet, namely caves.

Of course, the problems of creating caves are different from the tasks of the original maps and the associated algorithms. Fortunately, in terms of lora and gameplay, caves have a completely different meaning, and they lack the “living ecosystem” used in the main areas of the world, so there is no need to migrate these ready-made systems to fit the new architecture. (In addition, such a migration would reduce the effect of using a completely different map generator!) Therefore, all the caves are located 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 familiar with them.

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

Cave generation

I have already done 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 writing this part, the parameters for adding caves to the world (images created in the demo of the map generator test program) have not yet been configured, so you should look at how the game of the caves actually look like.

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


Fully explored mine.

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

Real cave systems are much larger, and since individual caves have more room to expand, they are more likely to generate additional back streets.


Fully open map of caves with no content. On the map superimposed images of the main loops and paths.

For reference, I have drawn illustrations that demonstrate 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 "linearity with loops" should not allow the card to be too linear, while saving the player from the annoying return back. (And of course, the player can create loops by himself, destroying the necessary walls.)

Filling caves

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

It has the form of "meetings", in which each of the caves (similar to rooms on maps of 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 about card composition .

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


Mine with distributed meeting types marked with the appropriate color category.

This function was used to fill in other branches, including for maps of caves in the form of mines. But the mines are relatively small and they contain a rather limited set of simple meetings, so they do not need the support of blanks, which allowed me quite simply to create a wider range of unique (but still dynamic) content. Honestly, I didn’t have enough time to sell the caves before 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 should definitely be more of them . Stubs can help a lot in these areas because the hard task of content is a slow and error-prone process. Support for scripting for meetings is significantly improved compared to the description from the previous part, while other branches also added many features for content blanks.

The last thing I really needed was the support of the blanks 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 maps. 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 run without Cogmind itself), and by its very nature its capabilities are limited because it has presets even before it is generated caves. Therefore, these blanks had to play a major role on the map, for example, to be a huge and important unchangeable area or special inputs / outputs. If you use this type of workpiece too actively, as a result, the cards will become too repetitive and recognizable, because this system is not very flexible (at least, if you do not put extra effort into working on each new card). Therefore, it will be more efficient to add most of the cave blanks using the second method, the meeting system.

Here a problem arises: how to integrate static blanks into a map of caves that has already been generated?

By themselves, the blanks 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 blanks. 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 billets and caves. I hope they will be enough.

Centered workpieces

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


Geometrical centering of the outpost in the parent cave.

Notice that the outpost territory completely rewrites the enclosed and open areas under it, and there is an open buffer zone around it. The solution is radical, but quite suitable here.

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

One of the limitations of the design with centered blanks 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 may 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 for one type of meeting there is a lot of variation. This leads to funny situations for new players (“oh, I remember this place from the last time, there is a friendly robot inside - GOD WHY HE FIRING IN ME”), and at the same time creates strategic difficulties for experienced players (“there definitely there is useful loot and I can take out the usual guards, but is it worth the small chance that I will be ambushed by more powerful opponents? ”).

As I mentioned several times when I spoke about the structure of the world, the 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 fairly constant and predictable for an experienced player. In this way, I create two different types of main areas between which a player can move. From the point of view of the design, the blanks are “manual” content located in the branches, so it is very important to implement them correctly.

Embedded blanks

These systems were more difficult.

It was necessary to find a way to add areas of blanks that would have almost no effect on the structure in order to create a more standard cave system in which the player finds interesting encounters 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 pull out areas for billets on the borders of existing caves. That is, for such excavations it was necessary to have enough space, as well as a way to effectively find such spaces.

As seen 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 (an area that can be dug) between the caves, it is necessary to perform the generation of caves in two stages: in the first stage, the process of specifying cavernous spots marking the boundaries during the normal map generation process is used; in the second stage, the usual process is performed, which will automatically avoid the “voids” dug in the first stage. These voids in the future should be available for tearing blanks. Although it sounds promising, but the more useful this approach (that is, the more voids), the more it affects the caves as a whole: it extends the corridors and increases the spaces between the individual caves, even if there are no blanks between them. This decision seemed to me too excessive.

There is a much simpler alternative that does not reduce the integrity of the ready-made cave schemes: you can simply expand the area to be excavated around the outer borders of the map. Now we will have a lot of space to dig! Then comes the next step: where exactly to start digging? It is very easy to determine by sight - we can immediately see the places that are ideal for digging out small caves, but in the cave code they are simply numbered areas with a list of internal coordinates. Therefore, at this stage, the question was to select a minimum set of rules that would allow you to search for suitable places and satisfy all conditions and potential schemes when pulling out areas for billets.


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

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


Steps for embedding the blank into the cave wall.

1. Select a random billet for a given meeting and rotate it to look at a random side of the world.
2. Select a random open cell in the cave, which should be 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. Measure the distance along the imaginary sides of the workpiece until it collides with the wall.
4. Each workpiece has a manually set value of “maximum length” (maxProtrusion). It is a limitation of the depth at which it can go into the parent cave. If the distance measured on either side exceeds the maxProtrusion value, then we shift the angles back to the wall until both values ​​are within this value. (If the distance at which the length value can be observed on both sides, then go back to step 2.)
5. : « » ( ) « » — , / .
6. , ( , , ).
7. ! , .
8. , , , .

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

Unlike centered blanks, recessed blanks may not be rectangular, because their sides and rear borders are guaranteed to be in the ground, i.e., their appearance will resemble a cave, as shown in the example above.

The above schemes are drawn in REXPaint . Here are screenshots of the real blanks generated in the game:


An example of embedded workpiece in the game.