Dungeon Generation in Diablo 1

Original author: BorisTheBrave
  • Transfer
image

Diablo 1 is the classic 1996 hack and slash roguelike. This was one of the first successful attempts to introduce the masses to roguelike, which until then had niche graphics in the form of ASCII art. The game spawned several sequels and many simulations. She is known for her dark, gloomy atmosphere, thickening as the player descends into the dungeons located under the city of Tristram. It was one of the first games with procedural map generation for me, and the possibility of generating such believable levels shocked me.

I recently found out that due to the discovery of various files with debugging symbols, several fans of the game took on the task of reverse engineering the source codeto clean it and figure out what the code written by the developers looked like. So began my week-long 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 Blizard North team for creating such an awesome game, as well as galaxyhaxz and the Devilution team for their amazing work on restoring the project’s readable source code.

Introduction


Diablo is a game consisting 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, for example, the city of Tristram, which I will not consider in the article. Diablo has separate level generation procedures for each of the 4 stages, so I will first talk about their features, and then consider separately the operation of each of the stages.

I was only interested in how the levels were generated. To learn about quests, monsters, etc. I recommend reading the Jarulf's Guide To Diablo and Hellfire , which describes these aspects in detail.

General Features


Although each stage has its own level generator, they all 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", which are rendered on the screen.


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

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

To my surprise, unlike other games in this series, dungeon maps are not composed of pre-created blocks. Almost everything is created by using algorithms.

Multi-stage process


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

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

All stages of creating dungeon blanks begin with a level filled with solid “hardness”, after which the individual parts of the level recursively turn into floor tiles. I will discuss this in more detail below.

Finished Fragments


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


Butcher's Den is one of the first pre-made snippets found in the game.

Mini sets


Mini-kits are another way to insert content into a level of pre-created content. These are small pieces, usually about 3 × 3 in size, randomly inserted into the dungeon. There is a simple pattern matching scheme, thanks 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 overlap with ready-made fragments, and so on. Some mini-kits always search and replace, while others do this with a fixed probability.

Diablo mini kits are used for many different purposes. They are used to place large objects from tiles, such as stairs, to fix combinations of tiles that do not connect well with each other, and to add random variation to tiles.

Thematic rooms


Themed rooms are small spaces bounded by a wall and a door. Usually in them in a random way certain predetermined objects are located. For example, libraries always have a bookcase with two candles on each side, several random bookends and monsters. Monster Lairs contain many monsters and a random item, and so on.

At the levels of the Сathedral stage, the generator creates suitable rooms that are recognized by filling 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 thematic room has certain requirements for the size and 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 by similar variations. The most standard tiles (for example, floors and flat walls) have various variations, which reduce the monotony of the level. Tile replacements are never reused side by side.

Comparison of patterns and “corrections”


As mentioned above, mini-sets are used as a search and replace mechanism that corrects generator flaws. But at most stages, there are procedures that detect and fix more specific problems. I will not go into details, because there are just a bunch of them. Suffice it to say that Diablo is pretty buggy, and closer to the 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 the “lockout”: it checked whether it was possible to go through the entire dungeon, and started the generation again if it wasn’t.

Quests


Most quests were created using ready-made fragments, but some used their own logic. For example, Zhar the Mad generates thematic library rooms, the entrance to Poisoned Water is generated by mini-dialing, 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 bottlenecks in the form of doorways. Let's see how it was created.

image

Dungeon blank


The first thing the algorithm does is draw the core of the card. He randomly selects up to three rooms 10 × 10 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 finished 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 recursive budding technique in a function called L5roomGen, which is initiated in each of these rooms, and by selecting an axis.

L5roomGen Function


  • She passes the rectangle of the original room, from which you need to start budding, as well as the preferred axis.
  • With a probability of 1/4, the preferred axis changes.
  • The random size of the new room is selected, with 2, 4 or 6 tiles on each side.
  • For each side of the original room along the selected axis (i.e. SE / NS for X, SW / NE for Y):
    • The rectangle of the new room aligns with the center of the edge of the original room
    • The check is made that before that there was nothing drawn and we did not reach the end of the map. Walls require a border of one tile.
    • If the check is successful, a room is drawn.
  • For each room to be drawn, it is called recursively L5roomGen, to which the new room and the axis opposite the previously used one are passed.

Ultimately, this procedure starts with several rooms cut out inside the "hard" tiles, and then repeatedly glues new rectangles to cut out new passable areas. At this stage, all the "rooms" are open on one side, because each new room is located directly next to the previous one, without passes for placing walls.

Then the generator calculates the number of generated traversed tiles. If it is below the minimum threshold, which increases with each level, the dungeon is destroyed and the generation attempt is performed anew.

Dungeon


So far, the algorithm has only the "solid" and gender tiles. 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 its unusual variation. The tileset 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 edge, but there are no tiles with a wall on the southeast edge. To create walls on other sides, you need to find a “solid” 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 for sorting walls by depth.


To deal with this, Diablo skips some walls during the marching cubes phase:


Additional walls are added later, at the “fixes” stage. I think this simple procedure most affects 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 simply will not be created. This means that the dividers between rooms are "thinner" than you can usually get in the resolution at which marching squares are executed.

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

The generator then randomly adds dividing walls. Separating walls always go straight along the axis from one wall to another. They start from the corners, so the areas are beautifully divided into rooms. In 25% of cases, a wall is a series of arches, in 25% of cases it is a series of arches with a grating blocking the entrance, and in all other cases it is a solid wall. In the case of gratings and solid walls, somewhere along the separating wall, a door or arch is randomly added to make the space passable.

The fill procedure detects potential themed rooms.

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

As for the arrangement of mini-sets, "fixes" and replacements, I will not consider them in detail. Most of all, I love the PANCREAS1 mini-kit, which has a 1% chance of placing a pile of bloodied flesh on the floor tile. At the end, 5-10 lamp objects are placed on it to decorate the dungeon.

Catacombs


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

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

image

Dungeon blank


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

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

CreateRoom Function


  • A CreateRoomrectangle denoting the area inside which rooms need to be generated is passed to the function . Details are also passed to the function about the original room (initially null)
  • If the area is too narrow, the function is exited.
  • A random size is selected for the room from 4 to 9 tiles on each side, taking into account the maximum size of the area in which you want to place the room.
  • In the area, a random position is selected to place the room.
  • The room is rendered on an ASCII map. The figure symbol '.'designated floor tiles, a symbol '#'- the surrounding wall, and the letters 'A', 'B', 'C'and 'E'- the four corners.
  • If a room has a source room:
    • A random tile is selected at the nearest edges of the original and new rooms.
    • This information is recorded in the corridor list, which will be used later.
  • The remaining parts of the area, with the exception of the current room, are cut out, creating four rectangles.
  • The size of each rectangle is reduced by two tiles to create a space between rooms, and then a function is called recursively CreateRoom, the area for which this rectangle is used, and the created room as the source.

If there is a finished fragment on the map, it will always be in the first room created by CreateRoom, and its dimensions are made so that this fragment is placed in it.

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

                                         
                                 A##B   
                                 #..#    
         A####B                  #..#    
         #....#                  #..#    
         #....#                  C##E    
         #....#                          
         C####E                 A#####B  
                                #.....#  
                                #.....#  
          A########B            #.....#  
          #........#            #.....#  
          #........#            C#####E  
          #........#   A#B               
          #........#   #.#               
          #........#   #.#               
          #........#   #.#               
          #........#   #.#               
          #........#   #.#               
          C########E   #.#               
                       #.#        A#B    
                       C#E        #.#    
                A####B            #.#    
                #....#            #.#    
                #....#            #.#    
                #....#            #.#    
                C####E            #.#    
                                  #.#    
                       A#####B    C#E    
                       #.....#           
                 A###B #.....#           
                 #...# #.....#           
                 C###E #.....#           
                       C#####E           

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

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

If the doors are adjacent 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 them ','also become walls. Finally, characters ','are replaced by 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 sections to which additional floor rectangles can be glued. Rectangles can be at least 5 × 5 and not more than 12 × 14 in size.

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

This gives us the dungeon blank shown below.

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

Dungeon


Again, the catacombs are different from the standard level formula. Instead of the marching squares algorithm (which assigns tiles based on 2 × 2 squares of the dungeon blank), it uses its own pattern matching procedure, which examines each of the 3 × 3 rectangles of the dungeon blank and selects the corresponding tile for the dungeon. Patterns determine what each dungeon tile should be: a wall, floor, door, solid tile, or a combination thereof. I don’t quite understand why.

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

I think that mini-sets somehow affect the doorways, but they are pretty boring to read without tools, so I did not delve 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 scaffolds, which apparently appeared later than the caves themselves.

This stage is one of the most beautiful in the game thanks to the animated lava. One feels that it is very different from 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 “cave” look using tricky tricks.

image

Dungeon blank


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

When drawing rectangles at this level, normal fill is not used. The interiors are always solid, but each tile on the border has a 50% chance of becoming a floor, otherwise it remains solid.

DRLG_L3CreateBlock Procedure


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

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

After creating a rough sketch of the dungeon shape, the generator applies the erosion procedures:

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

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

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

Dungeon


Dungeon blanks are converted to tiles using marching squares. Unlike Cathedral and Catacombs, the tileset is much more convenient here, and contains almost all the combinations needed for marching squares. There are no tiles for diagonally opposite walls in it, but they were eliminated in the workpiece phase, so they never appear.

Then, as usual, there are many mini-sets. The code has several mini-sets that define a separate section of walls and replace it with stalagmites and floors, which increases the openness of spaces.

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


A 3 × 3 wall turns into a lava lake.

Then several lava rivers are added. The generator makes several attempts to draw a river starting at the lava lake and ending at the wall. The following requirements are imposed on the river: it should not cross itself, the river has a length of 7-100 tiles, and there should be a suitable place for the bridge on it. The bridge tile ensures that the entire map remains passable. If there is space on the map, up to four rivers can be added.

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

Hell


Hell is the final stage of Diablo. In it, the main emphasis is already on monsters, and the design of levels goes by the wayside. This stage has the smallest tileset of all, and most of it is used for huge stairs and pentagrams. The hellish levels usually consist of several square rooms and have a symmetrical layout.

image

Dungeon blank


Hell generation starts with a random room of 5-6 tiles on each side (more if it has a ready-made fragment for the quest), and then the same recursive budding is applied as in Cathedral. However, generation is limited to 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 the full size.

Dungeon


Dungeon blanks are again converted to tiles using marching squares. Then, similar to the creation of the Cathedral, walls are added, as in 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 passed a serious test by battle and it is full of smart ideas.

Here are the most important lessons for me:

  • The devil is in the details: the individual components are not insanely complex, but when combined, they give something wonderful. I can imagine how the developers pored over improving the quality until the levels turned from just good to amazing. The number of tiles and the combinatorial complexity of tilesets is also very high - it is impossible to implement this without attention to how the elements are connected.
  • Search and replace for pattern matching is a very powerful tool with which you can implement many different effects. It fixes generation bugs, adds variability, inserts pre-created content, manages erosion and much more.
  • Dividing the dungeon generation into the passability map (dungeon preparation) and tile generation 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. Most of the code can be reused, while still creating very different styles.
  • If in doubt, stick more rectangles on the sides of the elements.

Also popular now: