Procedural Level Generation for MERC in Unity

Part one

Procedural level generation is a great way to add more content and unexpected scenarios to the game. For the MERC story missions, we wanted to create a large set of hand-made levels, but we realized that our small indie team did not have enough time or resources to produce content for such a big game. In addition, we sought to add randomness and increase the replay value of the game. The procedural generation of levels allowed us to create a large, infinitely variable world that we could not get by building individual levels manually. Using procedural generation allows you to add more content and improve gameplay.

What is MERC? MERC is a tactical squad simulator in real time with a top view. The player simultaneously manages a squad of four mercenaries in the anti-utopian world of Neotopy, gives orders and activates special skills. Each mercenary unit has its own special combat, technical and hacking skills that must be used in missions. Visually, MERC resembles the Blade Runner style: dark rainy slums and city rooftops with many winding streets and neon lights. The plot is a war of powerful corporations for control of Neotopy. The detachment is hired to carry out various tasks of corporations, such as the abduction of scientific competitors or the killing of defector employees. Each mission received influences relations with different corporations and as a result changes the game world. Given all this,

Level Requirements

The levels are a maze of urban slums and roofs, but in order to be fun to play, they must have a special structure. To create large levels of missions, we decided to collect them from small fragments. Thanks to this, we could manually make interesting and “reusable” fragments, add procedural randomness and give each level the feeling of hand-made. For this, we determined that the procedural level should:

• contain one main route
• contain 1-3 dead ends for purposes and collecting prey
• contain 1-3 shortcuts used as alternative routes
• generate random objects of decoration and shelters in each fragment of the level
• generate enemies based on a "pace chart"
• generate different types and levels of enemies based on mission complexity
• work with NavMesh Unity system
• be deterministic and generate exactly the same levels for playing together on the network

These requirements are selected taking into account our gameplay, the world and the planned duration of the missions. Other games will have their own requirements for the system of procedural levels. We wanted the missions to be completed in just ten minutes and twice as slow with a thorough level study. This meant that small variability in path lengths became an important parameter.

The most difficult thing was to comply with all the conditions, while creating holistic and interesting levels. How did we manage to achieve this? If you imagine a finished level with its structure, caches, pace and mission objectives, it is difficult to understand how to create all this procedurally. I decided it would be easier to split the level into layers. It is necessary to perceive the procedural level as being created in several passes, each of which adds a new layer of complexity to the level. It is logical that you can start the process from a basic level. In our case, this is the structure (route) of the level.

Level Route Generation

The first problem of the system of procedural levels is the generation of an interesting main route containing dead ends and short paths. We found a solution in a report by Zach Aikman from Unite 2014 on the generation of Galak-Z game levels by 17-BIT (the full report can be viewed here ).

Zack's report is very interesting, and I advise you to watch it. I’ll talk about it briefly: to generate the main 2D route, we used a modified Hilbert curve algorithm. It creates an interesting and unique winding route, ideal as the basis for our levels. The developers of Galak-Z used it for the route in a two-dimensional side view, we used it to create a two-dimensional top view. Imagine that the illustration below shows the street map of our game in top view.


(illustration from the report on Galak-Z)

After generating the main route, you need to evaluate all possible map cells to create short paths, and randomly select some of them. A short path does not allow you to reduce movement along the entire map, but simply cuts off part of the main route, for example, to avoid some enemies. We have added restrictions to the code so that short paths are not too long and frequent. When adding these short paths to fragments of levels, we often blocked them with doors that could be hacked, or with other obstacles that required some player actions. This adds more variation to the main level route and provides another way to test player skills.



Then we randomly add side paths with dead ends in places where there are no map cells. They create alternative paths that interrupt the gameplay, and are ideal for placing prey, hidden caches and special mission goals, such as finding and eliminating a character. Depending on the objectives of the mission, we randomly generate from one to three deadlock paths for each level. All mission specific objectives are located at the end of dead ends.



The idea is that the detachment arrives on a transport ship in the starting cell of the map, with which the main route begins. Then the player, controlling the mercenaries, leads them through the level and fulfills the goals, reaches the end of the main route and is evacuated. At each level, you must fulfill the mission objectives. Mission objectives are located outside the main route, which forces the player to explore the level. It is not necessary to investigate other dead ends; they contain hiding places and additional production. This gives the player a choice: break through the level and quickly complete the mission, or spend more time researching.

After the generation of the full route with short paths and dead ends, we will convert it to a list of loadable level fragments. Each fragment of the level is a Unity scene, so we gave each scene a name according to the template that defines its configuration. Having generated the level, we will transform each cell of the map into the scene name corresponding to the template. The template contains the theme of the fragment, the connection and the designation of the variation. For example, according to the template <topic> _ <connection of the main route> _ <connection of the short path> _ <connection of the dead end> ​​_ <variation> the fragment of the level may have the name of the scene “slums_03_-1_-1_A” .

ThemeIs a visual style of level fragments. All fragments of the levels of one theme should seamlessly connect to any other fragment of the same theme. For example, all levels fragments threads «slums» (slum) and graphically should logically combined with one another at the points of the compounds. We also created the theme “rooftops” (roofs of houses), in which, instead of streets connected to each other, the roofs of buildings are connected by ramps and floorings. Usually all fragments of the same topic are the same size. Our fragments on average have a size of 40x40 units.

In accordance with the structure of the Hilbert curves and the paths generated by us, each fragment of the level will have two connections of the main route , zero or one connection of the short pathand zero or one dead end connection . A fragment of a level never contains a combination of a shortcut and a dead end, because they are never used. Each connection corresponds to a face of a level fragment, and each face is marked with a number from zero to three, as shown in the figure below (“-1” is used to mark a nonexistent connection, for example, there is no short path connection in the figure).



For example, a level fragment with the connection designation of the main route connection “03” has connections at the bottom (0) and to the right (3). Marking the connection of the main path always has an order of magnification (ie “03”, not “30”). It is important to remember that when assembling fragments of connection levels, they do not have to line up absolutely evenly. By adding irregularities to some compounds, we will increase the variability and decrease the smoothness of the connection of the fragments. However, the connections should still be aligned with each other so that the paths are sure to dock.

Variations allow the level designer to create different versions of the same level fragment. For example, look at the two variations “A” and “B” connecting the main route “01” without a short path. When generating a level, the system randomly selects one of the variations of each fragment of the level, providing greater visual diversity.



When loading each fragment of the level, we move it to the desired offset in the world based on its position on the route. This means that fragments cannot contain meshes marked for static butching in Unity (because when you move them, the system will break). However, Unity Dynamic Batching works fine on the system. Below are examples of randomly generated level structures (red areas are short paths through buildings, blue areas are variations of buildings). This is only a concept check so far without finalization.



I will be glad to discuss this topic in more detail and will gladly accept any suggestions. I can be reached on Twitter .

In the second part In the article “Procedural Level Generation for MERC in Unity”, we will discuss the lighting and NavMesh problems that we have solved, as well as the process of character generation in the mission based on pace.