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 realized that our small indie team didn’t 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. Procedural level generation allowed us to create a large, infinitely changeable world that we could not get by building individual levels manually. Using procedural generation allows you to add more content and improve the gameplay.

What is MERC ? MERC is a squad tactical simulator in real time with a top view. The player simultaneously controls a squad of four mercenaries in the dystopian world of Neotopia, 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 is reminiscent of the Blade Runner style: dark rainy slums and rooftops of the city with many winding streets and neon lighting. The plot is the war of powerful corporations for control of Neotopy. The detachment is hired to perform various tasks of corporations, such as the abduction of competitors' scientists or the killing of deserters. Each mission received affects relationships with different corporations and as a result changes the game world. Given all this, let's consider the requirements for procedural level generation.


')

Level Requirements

Levels are a maze of urban slums and rooftops, but in order for them 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 a hand-made feeling. To do this, we have determined that the procedural level must:

• contain one main route
• contain 1-3 dead-end paths for mining purposes
• contain 1-3 short cuts used as alternative routes
• generate random objects of design and shelters in each level fragment
• generate enemies based on “tempo graphics”
• generate different types and levels of enemies based on mission complexity
• work with the NavMesh Unity system
• be deterministic and generate exactly the same levels for playing together over a network

These requirements are tailored to our gameplay, the world and the planned duration of the missions. Other games will have their own system requirements for procedural levels. We wanted the mission to take place in just ten minutes and two times slower with a careful study of the level. This meant that a small parameter in path lengths became an important parameter.

The most difficult was to comply with all the conditions, while creating holistic and interesting levels. How did we manage to achieve this? If you imagine the finished level with its structure, caches, pace and mission objectives, it is difficult to understand how to create all this procedurally. I decided that it would be easier to break the level into layers. It is necessary to perceive the procedural level as 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) level.

Level route generation

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

Zack's report is very interesting, and I advise you to look at it. I'll tell you about it briefly: to generate the main 2D route, we used the modified Hilbert curve algorithm. It creates an interesting and unique winding route, ideally suited as a 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 view from above. Imagine that the illustration below shows the street map of our game in a 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 a part of them. A short path does not allow reducing movement throughout the map, but simply cuts off part of the main route, for example, in order to avoid some enemies. We added restrictions to the code so that short paths are not too long and frequent. When adding these short cuts to fragments of levels, we often blocked them with doors that could be “hacked” or other obstacles that required some kind of player action. 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 gameplay, and are ideal for locating loot, hidden caches, and special mission objectives, such as finding and eliminating a character. Depending on the goals of the mission, we randomly generate from one to three dead-end paths for each level. All mission specific objectives are located at the end of the dead ends.



The idea is that the detachment arrives on a transport vessel in the starting cell of the map, from which the main route begins. Then the player, managing 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. The objectives of the mission are located outside the main route, which forces the player to explore the level. Other dead ends are not necessary to explore, they are caches and additional mining. This gives the player a choice: break through the level and quickly go through a mission, or spend more time on research.

After completing the generation of the complete route with short paths and dead ends, we will convert it into a list of loaded level fragments. Each level fragment is a Unity scene, so we gave each scene a name after the template that defines its configuration. After generating the level, we transform each cell of the map into a scene name corresponding to a pattern. The template contains the theme of the fragment, the connection and the notation for variation. For example, using the pattern <theme> _ <junction of the main route> _ <junction of the short path> _ <junction of the dead end> ​​_ <variation> the level fragment may have the name of the scene “slums_03_-1_-1_A” .

A theme is a visual style of level fragments. All level fragments of one theme should be seamlessly connected to any other fragment of the same theme. For example, all fragments of the theme level “slums” (slums) should be logically and graphically combined with each other at connection points. We also created the theme “rooftops” , in which, instead of streets connected to each other, roofs of buildings are connected by slopes and floorings. Usually, all fragments of the same theme are the same size. Our fragments have an average size of 40x40 units.

In accordance with the structure of the Hilbert curves and paths generated by us, each level fragment will have two connections of the main route , zero or one connection of the short path, and zero or one connection of the dead end . The level fragment never contains both shortcut and deadlock connections, 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 (to mark a non-existent connection, "-1" is used, for example, there is no short path connection in the figure).



For example, a fragment of the level with the designation of the connection of the main route “03” has connections below (0) and to the right (3). The mark of the connection of the main path is always in order of magnification (i.e., “03”, not “30”). It is important to remember that when assembling fragments of connection levels it is not necessary to line up absolutely exactly. By adding irregularities to some compounds, we will increase the variability and reduce the smoothness of the connection of fragments. However, the connections should still be aligned relative to each other, so that the paths must necessarily join.

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



When loading each level fragment, we move it to the desired displacement in the world based on its position on the route. This means that the fragments cannot contain meshes (meshes) marked for static batching in Unity (because the system will break when they are moved). However, Unity's dynamic batching works fine on the system. Below are examples of randomly generated level structures (red areas — short paths through buildings, blue areas — building variations). This is only a concept check without final clearance.



I would be happy to discuss this topic in more detail and will gladly accept any suggestions. You can contact me on Twitter .

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