Procedural generation in Distrust

Hello! My name is Maxim, and I want to tell about how we did the procedural generation, and more precisely about how it turned out in the end. This article does not claim to be the title of complete documentation, which would require much more text. The article aims to describe the basic mechanisms for generating the game world and its essences, without going into certain narrow rules and exceptions, of which there are quite a few.

Before you is a building-warehouse, generated procedurally:

About the game

Distrust was conceived as survival in an abandoned polar station, where the player will manage a team of several people. The initial idea was that the base is generated procedurally, that it will be 2D in isometry, and the gameplay is not only the standard search for resources for the genre and maintaining stats of characters, but also various interactions between characters, dialogues and observations, the purpose of which is to calculate among team members something that is a threat to the rest of the characters.

In the development process, we revised some of the ideas, for example, due to the fact that the game world is mostly hidden in darkness and the player often has to shine a lantern, we wanted to make light and shadows especially beautiful, and it turned out to be easier in 3D.
')
It was a difficult, interesting, full of completely diverse events adventure, which is currently coming to its logical conclusion: now the free demo of the game is available on Steam, and the full version is released in the second half of August.

Description of the game world

The game world Distrust is a polar station or base, which consists of several zones. The zone is a territory enclosed by a fence with one passage into the next zone. The passage is a locked gate, an armored door, just a block of snow, and the like. To open the passage to the next zone, the player needs to complete a specific quest: clear the snowdrift with a tractor, collect the bomb and blow up the door, pick up the code and so on. The goal of the player is to withdraw characters from the base, passing all zones from the first to the last and, accordingly, completing all the quests.

The zone consists of buildings. Buildings can be of different types: hospital, warehouse, residential unit, etc. Inside the building are marked up for rooms, which can also be of different types: kitchens, laboratories, boiler rooms, bedrooms and others. Each type of room looks different and can be furnished with a certain props.

The gameplay is to perform different tasks by the heroes of the team under the player’s control. Tasks are 70% of the gameplay of the game. They can be quite diverse - starting with the looting of the bedside table and ending with the sacrifice, but in fact all this is one and the same entity - task, as we call it, the difference is only in configuration. It is not hard to guess that the game in our game is a huge amount, and the functionality that they provide is huge!


The creation of the game world is described below and visually looks like this:

Props

Before we understood what kind of generation we want to see in the game, what principles should be its basis, to get the game world we wanted, we tried different options, added something, reworked and configured again and, only having gained some experience and stuffing some bumps, we found a solution that allowed us procedurally to create such worlds that it would be interesting to play.

As a result, we stopped at the following option: each zone is generated in such a way as to accommodate a pre-configured budget, and begins with the smallest generation entity — the loot items. Loot is any items that a player can see in the inventory and use it to manipulate them. Examples of such items are candy, bandages, first-aid kits, master keys, and the like. You can get loot in the game only by completing certain tasks.

The main part of the budget of each zone is loot and a list of requisites that can be used during generation. By props, we mean the objects of the game world with which the characters interact in one way or another. These can be bedside tables, beds, electric generators, stoves, cabinets, and so on. The props when generating we divide into three groups:

Scenery - do not carry any functional load and serve to make the rooms look natural and diverse - these are chairs, drawers, pipes, etc.
Loot - designed to accommodate loot - cabinets, cabinets, storage shelves, etc.
Utility - always bear a certain functional load and are necessary for the characters to survive - these are beds, stoves, stoves, etc.

So, the procedural generator begins its work with the preparation of the budget loot. At this stage, the input data is the configuration of the loot budget for the entire zone, which must somehow be distributed. As already mentioned above, only a certain task can give out some loot, for example, a task to “slash vegetables” will give you a package of frozen vegetables, and a task “to slush keys” will give you a master key. In this case, the task "to slough up the vegetables" cannot appear on the bedside table, only on the refrigerator.

Based on these two postulates, we conclude that the generator should form a list of tasks by which characters will be able to collect all the loot. He should do this on the basis of the budget provided, that is, so that frozen vegetables are in the refrigerator, cartridges are in the locker for weapons and so on, and this furniture would be available for a specific zone, based on the settings of the zone itself. The generator establishes these correspondences, looking through the list of budget loot properties, this list contains configurations of each individual attribute, it contains a link to the prefab, a list of states, lists the tasks that the given attribute supports and some other properties.

Thus, comparing the budgets of the loot and the requisite available for the zone, the generator generates a list of loot, on its basis forms a set of tasks, choosing them from those specified in any requisite from the budget for this zone, and fills the specific tasks depending on Like a certain loot. For example, for a zone it is necessary to distribute three first-aid kits, a task to “give out a first-aid kit” can issue only one first-aid kit, which means in the zone it is necessary to distribute three such tasks.

The next step is the creation of entities for props. What it is? The entity is an abstraction that stores the state of an object on the stage, allows you to somehow manipulate it, it is responsible for instantiating the prefab on the stage, setting it up, switching its states, performing characters on the object, saving and loading it. In fact, all interaction with game objects on the scene is done with the help of entities. The input parameters at this stage are the list of loot drags from the last stage and the same budget of the prop, but not only loot but also functional, which we call utilitarian. In the case of loot props, the generator first creates entities in such a way as to accommodate all loot tasks, for example, to distribute the same three first-aid kits, the generator chooses from the budget of the prop that supports the "give out first-aid kit", for example, laboratory table or medical cabinet . A utilitarian props created directly on the basis of the configuration, which describes what objects and in what quantity can be in the zone. For example, in a zone there can be from five to seven electric generators, from three to five beds, and so on.


And the last thing you need to know to understand the operation of the generator at this stage is the concept of “room tag”. In fact, this is simply a listing that characterizes the type of room, for example, a kitchen, a bedroom, a boiler room, and so on. Depending on the type of room, it can only have props of the appropriate type, the bed cannot be in the kitchen, and the refrigerator can be in the boiler room. The props configuration also contains a list of room tags in which it can be located for matching. The resulting entities furniture is distributed by the generator depending on the tag, and the output is a dictionary, in which the key is the room tag, and the value is the prop divided into three lists: loot , utility and scenery . Moreover, the first two are ready-made and customized furniture essences, while the third list is only configurations of the props, which acts as decorations. The generator needs to place the entities from the first two lists, while the third is an auxiliary one and is needed to fill the rooms more naturally. So, now we can briefly describe what is happening at the moment:

Based on the loot issuing loot prepared at one of the steps and the configuration of the prop, as well as room tags, the generator creates a dictionary in which for each type of room there are two lists that need to be placed somewhere in the zone, plus one auxiliary, from which generator will create new entities on the fly as needed.

For a clearer understanding, I’ll clarify that at the end of the described stage the game entities of a certain zone have already been created, tasks have been prepared and contain the loot necessary for the player. The outlines of the zone, albeit not geometrically, are already traceable gameplay.

Buildings and rooms

This is how the room looks just before instantiating the walls, floor, roof and furniture:


Taking the dictionary from the previous stage, the generator sequentially places the prop from the loot and utilitarian list. But, you ask, in the world there is still nothing but the essences of the furniture itself? Where can I put it? The generator can put furniture only in any room. Rooms can only be in a building and therefore, if there are any buildings, they are examined for such a room that they can accept the necessary furniture, and this room should not be completely filled. Of course, everything related to rooms is also configured from the editor. We refer to room configurations as room templates.


In these templates, the room tag is marked, the total area of ​​the room’s fullness is Filled Space, on the basis of which the generator considers the room as full or not, and the ratio of the three props in the room, with which the generator manages to uniformly and naturally furnish the room. Each zone has a list of room patterns that may appear in its buildings. So, back to the creation of rooms and buildings. The easiest way to describe this mechanism is as lazy, that is, as long as there is an unfilled room of the desired type, it will be filled with props in such a way as to keep the relationship between functional, loot and decorative according to the room pattern. As soon as the desired room does not appear, the generator will try to create another such room in one of the buildings, and filling the buildings with rooms is also subject to numerous rules. So, for example, warehouses are not in the same building with the laboratory, in one building there can not be more than two boilers, and so on. If this fails, and none of the existing buildings are ready to accept a new room, then a new building is created. It happens as follows.

Form generation

It's time to introduce you to the geometric heart of our generation. That it is responsible for the correct placement of the props inside the rooms, the creation of rooms inside buildings, buildings within zones and zones within the entire database. The form generator is responsible for ensuring that game objects do not subsequently crash into each other, buildings stand at a certain distance from each other, for generating forms of rooms and buildings, and similar things.

A form is an entity based on a list of squares, each of which is represented by a list of points. Using the forms, the generator actually makes a markup of the game world, according to which in the subsequent stages all game objects on the stage will be placed - be it prefabs of the props, walls of buildings or a fence around the zones. But first things first.

At the previous stage, we stopped at the fact that the generator is forced to create a new building inside the zone, in which it will be able to create a room in which it will place the necessary prop. Building creation begins with the selection of a blank, which is a small image in .png. The picture turns into what we understand by shape - a list of squares and points - with the help of an algorithm, which, by the way, our colleague found in the vastness of Habr .


This algorithm explores the picture pixel by pixel, forming the shape of a building as a list of points and splits it into rectangles, on the basis of which rooms are then formed. That is, having received a special picture at the entrance, the algorithm returns the shape of the building and the shape of the rooms inside it. Further in the house a route is built between the rooms, the positions of the doors inside the building and the position of the entrance door to the building are selected. In addition to the form for the building, its essence is created immediately, which will control the rooms inside, and one of the rooms just marked in it is declared to be a room of the type necessary for the generator, depending on the set props, and an entity is created for it. For example, if the generator had to generate a new building during the placement of the refrigerator, then one of the rooms in the new building will be announced by the kitchen, since the room tag for the refrigerator is a kitchen, and due to the fact that it is empty, the refrigerator will obviously be put into it and removed from the list of loot props.

To put the furniture in the room, the form generator tries to choose a random point inside the room so that when creating the game object the refrigerator is at the right distance from the walls. This is also regulated by its configuration, as well as what area it needs, but more on that below. In addition to the refrigerator, the room will be furnished with other props suitable for the room tag, in this case the kitchen. Moreover, the process of placing this props is as follows.

The generator examines the entire list of properties that have already been delivered to the room for compliance with the ratio of three types of furniture. So, for example, after placing the refrigerator in the kitchen there is one unit of props, and the ratio looks like 100% loot, 0% utilitarian, 0% decorative, but the configuration of the kitchen template shows MaxLootablePercentage is 0.5, that is, only 50% of the furniture in the room It must be loot, so the next to be inserted will be the prop from the utilitarian list, it will be chosen randomly and let it be the furnace. To put the oven, the generator also chooses a random point so that it does not hit the wall, but in addition to this, the generator cannot be allowed to have the stove in the refrigerator! For this purpose we use the built-in solution from Unity - colliders.

Each prefab of the props has colliders that characterize, firstly, the area occupied by them, this is the area that the characters cannot walk, in other words, this is the area of ​​the game object itself, its native collider, and secondly, one additional collider, wider than the "native", which we call the rug. The purpose of this rug is to ensure the availability of props for characters. Characters can perform tasks on props only from certain points and, it is not difficult to guess, they must be available and cannot be filled with other furniture, which would make them unattainable. When arranging furniture, the generator checks that its own furniture colliders do not intersect with their own colliders and other furniture mats, while the mats may overlap with each other, but not with their own colliders of other objects. This scheme allows you to avoid the intersection of objects of furniture with each other, and also ensures the availability of interactive points for the characters of the game.

The generator is assigned a certain number of attempts to this procedure in order to avoid looping. If for the specified number of attempts the generator could not place the stove, then try to put another object until it tries all of the two available lists - utilitarian and scenario (as there is lut furniture in the kitchen, but no other types) in order to observe the marked higher ratio. If it is not possible to insert more props, or the area of ​​the room is filled to the value of Filled Space, then the room is considered to be filled. At this stage, there are many other rules involved, the description of which evokes thoughts about Ikea - among them, whether the furniture should stand close to the wall or vice versa at a distance, a bedside table is placed next to the bed and much, much more, not so important in this the description, however, is still worth noting one rule, without it the rooms looked like a chessboard - each unit of the prop slightly rotates the generator at a random angle, the range of values ​​of which is also specified in the configuration. This little thing turned out to be really important and made the rooms much more natural and alive.


Summing up the two previous stages of generation:

The generator arranges props in the zone, creating new buildings as necessary and marking rooms in them in form and type and creating entities for them, so that all rooms are arranged according to the specified props of three types and many other generation rules that are not so important for understanding the general essence.

The final stage

From the previous generation stage, we actually have a ready-made game world. There are no game objects on stage yet, but it is enough to call one method of each created entity, as it will appear! But before the generator performs another important procedure - determines the position of buildings within the zone. Until now, each new building was at point zero zero and we did not care that there might be several of them. The generator randomly chooses the direction to move the building from the zero position and shifts it along with all the contents with a given step until the building shape ceases to intersect with all other building forms and the distance to all other buildings becomes greater or equal to configurations. Having done this procedure, the generator determines the shape of the zone based on the position of the buildings. According to the contour of this form, a fence will be built, and the zone form will participate in the “moving apart” process similar to the buildings, only with other zones. After the generation of all zones inside the base, they are also in the 0: 0 position and move apart from each other in such a way as to avoid crossing, but at the same time preserve the common direction in which the gate will be built.

It is possible to consider generation finished upon completion of the described stage. All base entities are created and in place. Next comes the well-known plug-in from the Asset Store called Dungeon Architect, but, believe me, there is almost nothing left of its use. Algorithms that work with geometry and probability theory turned out to be self-written, and not from plug-ins. In our project, Dungeon Architect deals only with the placement of snow tiles, walls, roofs, in a word, a routine. It would be a bit hard for us to abandon it altogether, but at first it seemed that he would solve all our problems and make generation with him would be easy, but there was simply no desire and time to cut it out completely. He is already engaged in direct sansing of objects and prefabs onto the stage.

A little more generation:

Instead of an afterword

Procedural generation turned out to be a completely non-trivial task. In the process of work, we sometimes caught ourselves thinking to drastically simplify the script, for example, to refuse to generate rooms, but only to arrange them in advance.

But after we gained experience and tried various options and approaches, we managed to make the generation exactly as we wanted. The whole team spent a huge amount of time in discussions to make procedural generation of our polar base technically feasible, customizable and beautiful. Frankly, we are often fascinated by the resulting rooms and the way they are furnished is really lively and logical - if this is a dressing room, then there is a closet next to one wall, opposite the shop, and in the side of the hanger. I am proud to say that, although it was not easy, what is there is bloody and furious, but I am very pleased with the result and I can say that the world in our game is really procedurally generated, it’s not a couple of trees that appear at different ends of the map or random snow tiles. This is a truly generated world based on all sorts of algorithms based on the laws of probability theory, normal distribution, and geometry.