Diablo 1 is a classic 1996 roguelike in the hack and slash genre. It was one of the first successful attempts to introduce the broad masses to roguelike, which had previously had niche graphics in the form of ASCII art. The game spawned several sequels and many imitations. She is known for its dark, gloomy atmosphere, thickening as the player descends into the dungeons, located under the city of Tristram. It was one of the first games for me with procedural card generation, and the possibility of generating such believable levels just shook me.

Recently, I learned that due to the detection of various files with debugging symbols, several game fans took on the task of reverse-engineering the source code to clean it up and figure out what the code written by the developers looked like. So began my weekly excursion into the study of how lead developer David Brevik created these levels. Perhaps because of this, the magic of the game for me partially collapsed, but I learned many techniques that will be useful for developers of similar games, so in this article I will share them.

Thanks to David Brevik and the team of Blizard North for creating such an amazing game, as well as galaxyhaxz and the Devilution team for their amazing work in restoring the readable source code of the project.

Introduction

Diablo is a game of isometric tiles. The game consists of 4 stages, each of which has 4 levels. Stages of the game: Cathedral, Catacombs, Caves and Hell. There are also several fixed levels, such as the city of Tristram, which I will not discuss in the article. In Diablo there are separate procedures for generating levels for each of the 4 stages, so I will first talk about their features, and then consider separately the work of each of the stages.
')
I was only interested in how the levels were generated. To learn about quests, monsters, etc. I recommend reading Jarulf's Guide To Diablo and Hellfire , in which these aspects are described in detail.

General features

Although each stage has its own level generator, all of them have common features.

Dungeons and tiles

Each level of the game is generated to fill a grid of 40 x 40 tiles. The X axis corresponds to the southeast, and the Y axis corresponds to the southwest.

These tiles are used only for level generation tasks. After creating a level, each tile is divided into 4 "dungeon fragments" that are rendered on the screen.


This more detailed grid is used to determine passable tiles, and also provides more efficient reuse of graphics memory. Earlier, I wrote about tile sharing schemes .

This means that the standard Diablo map consists of more than a hundred tiles, many of which are minor variations of others to take into account all possible ways of combining them. We will talk about this later.

To my surprise, unlike other games in this series, dungeon maps are not made up of pre-created blocks. Almost everything is created secretly with the help of algorithms.

Multistep process

Each dungeon generation procedure is divided into two stages. "Pregeneration" does not deal with the choice of tiles at all. It simply generates an array in which passable tiles are marked, tiles with doors, and some other high-level details. At the second stage, this dungeon preparation is converted into an array of tiles, after which the generation is performed and changes are made taking into account these tiles.

It should be incredibly convenient for the designer. You can experiment with the floor plan completely regardless of the choice of tiles and style. But in many cases they are interrelated, providing a more holistic sense of level.

All stages of the creation of blanks dungeons begin with a level filled with a solid "solid", after which the individual parts of the level recursively turn into floor tiles. I will tell you more about this below.

Finished Fragments

Finished fragments are pre-created level blocks that are simply inserted into a randomly generated level. They are used for most of the game quests. At each level there can be only one ready fragment, the location of which at each stage is selected separately.


Butcher's Den is one of the first finished fragments found in the game.

Mini-sets

Mini-kits are another way to insert pre-created content into the level. These are small pieces, usually about 3 × 3 in size, randomly inserted into the dungeon. There is a simple pattern matching pattern, due to which they appear only in the “right” places. Often they are encoded with additional requirements, for example, mini-sets cannot be placed close to each other, they cannot be superimposed on the finished fragments, and so on. Some mini-sets always search and replace, while others do so with a fixed probability.

Mini-kits are used in Diablo for many different purposes. They are used to place large objects from tiles, such as stairs, to correct combinations of tiles that do not connect well with each other, as well as to add tiles of random variability.

Themed rooms

Themed rooms are small spaces bounded by a wall and a door. Typically, they are randomly located in some pre-defined objects. For example, in libraries there is always a bookcase with two candles on each side, several random book holders and monsters. Monster den contains monsters and a random item, and so on.

At the athedral stage levels, the generator creates suitable rooms that are recognized by shading and are reused. At other stages, the algorithm finds open spaces in which walls and a door are drawn to create rooms.

Each type of themed room has specific size requirements and the stage at which it is generated.

Tile replacements

Some cards have a special adaptation of the tiles, but they all have a common feature: some tiles can be replaced with similar variations. The most standard tiles (for example, floors and flat walls) have various variations that allow to reduce the level of monotony. Tile replacements are never reused next to each other.

Pattern matching and “fixes”

As stated above, mini-sets are used as a search and replace mechanism that corrects the generator’s shortcomings. But at most stages there are procedures that detect and fix more specific problems. I will not go into details, because they are just a bunch. Suffice it to say that Diablo is quite buggy, and closer to release it became obvious that it would be easier to add recognition of specific problems than to eliminate their fundamental causes.

One of the most common “fixes” was “lockout removal” (lockout): it checked if it was possible to go through the entire dungeon, and started the generation again if it was not.

Quests

Most of the quests were created with the help of ready-made fragments, but some of them used their own logic. For example, Zhar the Mad generates themed library rooms, the entrance to Poisoned Water is generated by a mini-set, and Anvil of Fury has a specific level generation code. I will not go into details, but the code is full of similar checks for quests.

Cathedral

The cathedral is probably the most iconic of the stages of Diablo. It is characterized by long rows of Gothic arches, cramped rooms and many narrow spaces in the form of doorways. Let's see how it was created.

Dungeon Harvesting

The first thing the algorithm does is draw the "core" of the card. He randomly selects up to three 10 × 10 rooms in predetermined positions along the central axis X or Y. A wide corridor connecting the rooms is also drawn along the axis. If there is a ready-made fragment on the level, then it is always located in the center of one of these rooms. These central dungeon rooms are marked as unsuitable for new walls, so that they always remain large open spaces.

All other rooms are generated by the “budding” recursive technique in a function called L5roomGen , which is initiated in each of these rooms, and the choice of axis.

L5roomGen function

• It is transferred to the rectangle of the original room, from which you need to start budding, as well as the preferred axis.
• With probability 1/4, the preferred axis changes.
• A random size of a new room is selected, 2, 4 or 6 tiles on each side.
• For each side of the source room along the selected axis (i.e., SE / NC for X, SW / CB for Y):
  
  • The rectangle of the new room is aligned with the center of the edge of the source room.
  • A check is made that nothing has been drawn before that and we have not reached the end of the map. Walls require a single tile boundary.
  • If the check is completed successfully, the room is drawn.
• For each rendered room, L5roomGen is called L5roomGen , which transfers a new room and an axis opposite to that used previously.

In the end, this procedure begins with several rooms carved inside the "solid" tiles, and then repeatedly sticks new rectangles to cut new passable areas. At this stage, all the "rooms" are open on the one hand, because each new room is located directly next to the previous one, without gaps to accommodate the walls.

Then the generator counts the number of generated passable tiles. If it is below the minimum threshold, which increases with each level, the dungeon is destroyed and an attempt to generate is performed anew.

Underground

So far, the algorithm has only tiles "hard" and gender. We need to replace them with real wall tiles. For this, Diablo uses the marching squares algorithm, which I described in a previous article .

However, the game uses an unusual variation of it. Taylset of the cathedral contains walls, but they are always located on the far edge of the tile. Therefore, there is a tile with a wall on the northeast face, but there are no tiles with a wall on the southeast face. To create walls on other sides, you need to find a “hard” tile that has an additional wall that extends outward from the border of the tile. It sounds strange, but in fact it is very convenient to sort the walls by depth.


To cope with this, Diablo on the marching cubes stage skips some walls:


Additional walls are added later, at the “patch” stage. I think this simple procedure has the most effect on the “style” of the cathedral. Since the opposite walls are attached to solid tiles, in the case of two rooms separated by one wall tile, the opposite wall will simply not be created. This means that the dividers between rooms are “thinner” than can usually be obtained in the resolution at which marching squares are performed.

After placing the main walls, the generator adds four free-standing columns to each of the central rooms and the colonnade of arches for the central corridor. This allows you to give the cathedral a sense of being designed more thoughtfully than other levels, and also helps players navigate.

Then the generator randomly adds separating walls. Splitting walls always run straight along the axis from one wall to another. They start from the corners, thanks to which the areas are beautifully divided into rooms. In 25% of cases, the wall is a series of arches, in 25% of cases it is a series of arches with a grill that overlaps the entrance, and in all other cases it is a solid wall. In the case of gratings and solid walls, a door or arch is randomly added somewhere along the dividing wall to make the space passable.

The fill procedure detects potential themed rooms.

Stairs are placed to connect with other levels. If it is impossible to place them, the attempt to generate the dungeon begins anew.

As for the placement of mini-sets, “fixes” and replacements, I will not discuss them in detail. My favorite is PANCREAS1 mini kit, which has a 1% chance of placing a pile of bloody flesh on the floor tile. At the end, 5-10 lamp objects are placed to decorate the dungeon.

Catacombs

Unlike the Cathedral, seeming to be a projected building, the Catacombs feel much more natural. They are characterized by square rooms connected to each other by a multitude of winding corridors. In many places, instead of the doors are wide openings. increasing the likelihood that a player will be surrounded by many enemies.

To generate the catacombs, the most complex generation algorithm in the game was used. I suspect that the lack of time has forced developers to use simpler solutions in the subsequent stages.

Dungeon Harvesting

The procedure for creating a blank dungeon for the catacombs is quite unique. In all other stages there is a single boolean value indicating the presence or absence of the floor (plus a set of bits for additional details). Catacombs store the dungeon preparation in the form of an ASCII card, almost like a classic roguelike. And this is not particularly surprising, given the recognition of David Brevik that he drew inspiration for Diablo from Angband .

The main room generator is again a recursive algorithm, but this time a recursive partition. The CreateRoom function CreateRoom called for the entire dungeon area of ​​40 × 40 minus 1 border tile.

CreateRoom function

• The CreateRoom function CreateRoom passed a rectangle that indicates the area within which you want to generate rooms. Functions are also passed details about the source room (initially null).
• If the area is too narrow, exit the function.
• A random size is selected for a room ranging from 4 to 9 tiles on each side, taking into account the maximum size of the area in which the room should be located.
• A random position is selected in the area to place the room.
• The room is drawn on an ASCII card. In the picture with a '.' Tiles of the floor are indicated, the symbol '#' is the surrounding wall, and the letters 'A' , 'B' , 'C' and 'E' are the four corners.
• If the room has an original room:
  
  • A random tile is selected at the nearest edges of the original and new rooms.
  • This information is recorded in the list of corridors, which will be used later.
• The remaining parts of the area, excluding the current room, are cut, creating four rectangles.
• The size of each rectangle is reduced by two tiles to create space between the rooms, and then the CreateRoom function is called recursively, the region for which this rectangle is used, and the created room as the source.

If there is a ready-made fragment on the map, then it will always be in the first room created by CreateRoom, and its dimensions are made such that it contains this fragment.

After calls to CreateRoom an ASCII array is obtained, similar to the one shown below (thanks nomdenom for extracting it from the code):

 A##B #..# A####B #..# #....# #..# #....# C##E #....# C####EA#####B #.....# #.....# A########B #.....# #........# #.....# #........# C#####E #........# A#B #........# #.# #........# #.# #........# #.# #........# #.# #........# #.# C########E #.# #.# A#BC#E #.# A####B #.# #....# #.# #....# #.# #....# #.# C####E #.# #.# A#####BC#E #.....# A###B #.....# #...# #.....# C###E #.....# C#####E 

In this case, the “root” room, originally created, was the lowest.

Then, the previously collected information on corridors is applied. A line is drawn between each recorded pair of points. When it crosses a wall, a 'D' written, and when it crosses a solid tile, ',' . Corridors have a random width: 1, 2, or 3. Corner tiles are used to help navigate.

If the doors are next door to another door, then they are skipped, and the corridors can overlap each other, which allows you to hide the simplicity of the generator.

After recording all the corridors, the ASCII card is cleared. Corner tiles become wall tiles, and tiles next to ',' also become walls. Finally, the characters ',' are replaced by the characters '.' . So we get the dungeon plan shown below.

 #### #..# ###### #..# #....# #..# #....# #D## #....# #.# #D#### ##D#### #..# #.....# #..# ###.....# ##D######## #.D.....# #........# #.#.....# #........# ### #.##D#### #........# #.### #.##...# #........###.D.# #.##...# #........##..#.# #.##...# #........##..#.# #.##...# #........##..#.# #.##...# #........##..#.# #.##...# ###D#######..#.# #.##...# #.......#..#.# #.###D## ###.....#..### #.# #.# #######D##.# #.# #.# #....#.# #.# #.# #....D.# #.# #.# #....###### #.# #.# ##D####....## #.# #.# #...........# #.# #.# ####....###D####.# ### ######.....##.# #####.D.....##.# #...D.#.....D..# #####.#.....#### ######### 

As you can see, this procedure can leave quite a lot of empty space on the map. Therefore, the next step of the generator is “filling the voids”. He searches for any adjacent wall segments to which additional floor rectangles can be glued. Rectangles can be at least 5 × 5 and not more than 12 × 14.

Void filling continues until a minimum of 700 tiles is reached, or the retry limit is reached. If the generator failed to reach 700 tiles, the dungeon generation starts from scratch.

This gives us the dungeon preparation shown below.

  ########## #........# ########### #........# #.........# #........# #.........# #........# #.........# #### #........# #.........# #..# #######..###.........# #..# #..............# #..# #..............# #D## #..............# #.# #D####.........# ##D#### #..# ########### #.....# #..# ###.....# ##D######## #.D.....# #........# #.#.....# ########........# ### #.##D#### #...............# #.### #.##...# #...............###.D.# #.##...# #...............##..#.# #.##...# #...............##..#.# #.##...# #...............##..#.# #.##...# #...............##..#.# #.##...# #......###D#######..#.# #.##...# #......# #.......#..#.# #.###D## #......# ###.....#..### #.# #.# #......#########D##.# #.# #.# #.........# #....#.# #.# #.# #.........# #....D.# #.# #.# #.........# #....###### #.# #.# #.........# ##D####....## #.# #.# #.........# #...........# #.# #.# #.........# ####....###D####.# ### #.........# ######.....##.# #.........# #####.D.....##.# #.........# #...D.#.....D..# ########### #####.#.....#### ######### 

Underground

Again, the catacombs are different from the standard formula levels. Instead of the marching squares algorithm (which assigns tiles based on squares of 2 × 2 dungeon blanks), their own pattern matching procedure is used, which examines each of the 3 × 3 rectangles of the dungeon blanks and selects the corresponding tile for the dungeon. Patterns determine what each dungeon blank tile should be: wall, floor, door, solid tile, or a combination of both. I do not quite understand why.

The rest of the function will seem familiar to you from the Cathedral. Stairs are placed on the map up and down, the dungeon is checked for the possibility of complete passage, and various corrections are made. As described in the “General Features” section, rooms are inserted, and then a number of mini-sets and tile replacements are inserted.

I think that mini-kits somehow affect the doorways, but they are pretty boring to read without tools, so I didn’t go deep into this topic.

Caves

Caves levels are filled with vast open spaces and lava rivers. The walls of this area are rough and wavy. The only rectangular components here are wooden platforms, which apparently appeared later than the caves themselves.

This stage is one of the most beautiful in the game thanks to animated lava. It is felt that it is very different from the previous levels made up of rooms. Therefore, I was very surprised that the main part of the generation is modeled according to the principles of the Cathedral stage, and the cards are given a more “caveman” look using tricky tricks.

Dungeon Harvesting

Creating a cave level begins with one random 2 × 2 room located somewhere near the center of the map. Then the generator calls DRLG_L3CreateBlock procedure for each edge of this block.

At drawing at this level of rectangles usual filling is not used. The entrails are always solid, but each tile on the border has a 50% chance of becoming a floor, and otherwise remains solid.

DRLG_L3CreateBlock procedure

• This function gets the edge of the rectangle, i.e. starting point, direction and length.
• Selects the size of the newly created block in the range of 3-4 on each side.
• A new block is randomly placed relative to the input edge.
• If there is not enough space to draw the block, then exit is performed.
• The block is drawn.
• With probability 1/4, exit is performed.
• DRLG_L3CreateBlock is called DRLG_L3CreateBlock for three edges, except for the one from which we came.

Although this procedure is similar to L5roomGen , using a much smaller block size and drawing rough edges gives it a much more organic look. In addition, it does not include a border in 1 tile for walls, therefore, unlike previous generators, it can create loops.

After creating a rough outline of a dungeon form, the generator applies erosion procedures:

• First, he finds areas of 2 × 2 tiles with diagonally opposed solid tiles. It is often difficult to work with such formations when performing marching squares, therefore one of the continuous tiles is randomly replaced by the floor.
• All solid single tiles, surrounded by 8 floor tiles, are replaced with a floor tile.
• All long and straight sections of the walls are randomly roughened by replacing 50% of the walls with floor tiles.
• Diagonals from solid tiles are eliminated again.

All these procedures add more floor tiles, so the map becomes more open.

If it has less than 600 floor tiles, then the map is generated anew.

Underground

The dungeon blank is converted into tiles using marching squares. Unlike Cathedral and Catacombs, tilesets are much more convenient here, and contain almost all the combinations required for marching squares. There are no tiles for diagonally opposite walls, but they were eliminated in the blank phase, so they never appear.

Then, as usual, there is a lot of mini-sets. In the code there are several mini-sets that define a separate section of the walls and replace it with stalagmites and a floor, which increases the openness of the spaces.

Lava lakes are added. The algorithm searches for an adjacent section of the walls using a fill . If he manages to find a section of walls / solid tiles less than 40 tiles, completely surrounded by floor tiles, then they are replaced by lava. If the lake of lava is impossible to find, the generation of the dungeon begins anew.


A wall of 3 × 3 turns into a lake of lava

Then add some lava rivers. The generator is making several attempts to paint a river starting from the lake of lava and ending in the wall. The following requirements are made to the river: it must not cross itself, the river has a length of 7-100 tiles, and there must be a suitable place on it to house the bridge. Bridge Tile ensures that the entire map remains passable. If space is available, up to four rivers can be added to the map.

Then themed rooms are placed. At this stage, the walls of thematic rooms are wooden fences, through which it is impossible to pass, but you can watch. Wooden fences are also used in the two following procedures. The first one installs a fence on all the remaining sections of the walls that have fairly long straight sections. The second draws a line of fences on the map, from one wall to the opposite, and then inserts a door. Unlike the procedure for generating a cathedral, it does not look for angles to begin creating these walls.

Hell

Hell is the last stage of Diablo. It focuses on the monsters, and level design goes into the background. This stage has the smallest tileset of all, and most of it is used for huge stairs and pentagrams. Hellish levels usually consist of several square rooms and have a symmetrical scheme.

Dungeon Harvesting

Hell generation begins with a random room of 5-6 tiles on each side (more if there is a ready-made fragment for the quest), and then the same recursive budding is used as in Cathedral. However, generation is limited to an area of ​​20 × 20.

A vertical and horizontal corridor is added, stretched to the edge of the 20 × 20 area.

Then the dungeon blank is mirrored horizontally and vertically to get full size.

Underground

The dungeon's blank is again converted into tiles using marching squares. Then, similarly to the creation of the Cathedral, walls are added, as in the Catacombs and Caves.

Conclusion

I really enjoyed reading this code. Although there are obviously bugs in it, the names are assigned randomly, and some parts cannot be recreated in high-quality source code, it is clearly visible that this code has undergone a serious battle test and is full of clever ideas.

Here are the most important lessons for me:

• The devil is in the details: the individual components are not insanely complex, but in combination they give something remarkable. I imagine how the developers pored over the improvement of quality, until the levels turned from simply good to stunning. The number of tiles and the combinatorial complexity of tilesets is also very high - it is impossible to implement this without paying attention to how the elements are connected.
• Finding and replacing pattern matching is a very powerful tool with which you can implement many different effects. It eliminates generational bugs, adds variability, inserts pre-created content, manages erosion and does much more.
• Dividing the generation of the dungeon on the patency map (preparation of the dungeon) and the generation of tiles is also a very convenient technique, both in terms of design and debugging.
• If you want to give different areas a different style, then a great solution is to create a separate algorithm. , .
• , .