content/posts/devlog/roguelike/dungeon-generation.md

   1 ---
   2 title: "Dungeon Generation in Roguelikes"
   3 date: 2021-04-23T09:44:35-04:00
   4 tags: ["roguelike", "explanation"]
   5 ---
   6
   7
   8 ## Intro
   9 As always, I've been working on a terrible browser-based game. This time, it
  10 will be revolving around gameplay mechanics from roguelikes(or roguelites
  11 technically)+jrpgs.
  12
  13 The thing I specifically want to look at today is the topic of Dungeon
  14 Generation - both in and out of code.
  15
  16 Roguelikes all tend to share one mechanic: Procedurally Generated Dungeons. The
  17 idea is that every play-through is different, every floor of a dungeon is
  18 completely unique. As a result, it requires the player to learn the mechanics of
  19 the game over multiple runs as most roguelikes also include perma-death as a
  20 required feature.
  21
  22 Dungeon Generation in roguelikes are a very interesting topic for two reasons.
  23 There is a definite technical component to being able to generate "good"
  24 dungeons quickly. Dungeons that are large enough, with enough rooms/pathways to
  25 be interesting, but that don't take forever to generate. The goal is each floor
  26 is generated randomly when the player enters - we don't want load times
  27 equivalent to stepping into a room in Morrowind. The second reason is one that I
  28 think roguelikes can miss out on - dungeon generation must fit the environment.
  29
  30 Most roguelikes have a generation alorithm that gets assigned to every single
  31 floor. But that's not really that helpful. Dungeons should reflect the
  32 environment the player is in. Having square rooms in a castle dungeon makes
  33 sense. Having square rooms in a cave, not so much.
  34
  35 A lot of dungeon generation information you find online tend to focus on the
  36 techtechnical component: HOW do you generate a dungeon. I'm hoping to also cover
  37 the second bit here.
  38
  39 ## Random
  40 The easiest to explain algorithm is the "Random" one, but it's probably the
  41 hardest to get right. Random dungeons are exactly what you'd think -> just
  42 randomly place obstacles and interaction points around the dungeon. As a result
  43 it's very easy to actually MAKE the dungeon.
  44
  45 It also has the added benefit that the "random" look works really well for open
  46 fields. Think areas that are strewn with trees or rocks or something like that.
  47 It could also work really well for large underground caverns since you would be
  48 peppering the inside with obstances.
  49
  50 But we're not just making a dungeon - we're making a game. And truly-random
  51 dungeons are hard to tune. How do you ensure that every chest you place is
  52 actually reachable by the player? How about the one set of stairs? How do you
  53 ensure that the player doesn't spawn in a box, closed off from the rest of the
  54 dungeon. How do you ensure that they don't spawn right next to some stairs?
  55
  56 Each of these questions (and many many more) result in you tuning you random
  57 generation more and more. You'll never get it 100% right. There'll always be
  58 edge cases reported by your places that you didn't even think about (did a
  59 monster spawn in deep water so the player didn't even know it was there and is
  60 now reporting that they didn't get an achievement for killing all the monsters
  61 on a foor?).
  62
  63 I started with a purly random dungeon generation system myeself. It's definitely
  64 not a bad call to make - but you just have to be aware of the edge cases. But I
  65 kept having to tune/adjust things and I'd still end up with play testers saying
  66 they got spawned in a box, or couldn't reach the stairs. That's frustrating
  67 enough to probably just stop playing.
  68
  69 The nice thing about random, however, is that you don't NEED to generate the map
  70 in its entirety. Nor do you need it to be entirely random.
  71
  72
  73 ### On-demand generation
  74 So you have the container for your map.. and your character is spawned in a
  75 particular point `(x,y)`. Given a field of view (`v`) really you only need to
  76 generate a box defined by the points `(x-v, y-v)`, `(x+v, y-v)`, `(x-v, y+v)`,
  77 and `(x+v, y+v)`.
  78
  79 If the player steps in a direction, you only need to expand the generated
  80 portion of the map by 1 tile (or whatever your fov is). In this way, your entire
  81 dungeon is being generated as the player discovers it. You get a few benefits
  82 like not needing to store the entirety of the map if the player doesn't visit
  83 it. You can tune drop rates for everything just by how much of the map is
  84 discovered vs. isn't. You can also almost guarantee that EVERY point on the map is
  85 reachable by the player and that they'll discover the stairs exactly when you'd
  86 like them to.
  87
  88 ### Pseudo-random Fabrication
  89 Now, lets get the pedantics out of the way - nothing we're doing is random, it's
  90 all pseudo-random. The difference is that in this generation mechanic we're
  91 actually building the map from pre-defined map parts.
  92
  93 The downside, of course, is that you have to spend a bunch of time generating
  94 the pieces of map and you do have to have to have some guidelines. But, being
  95 able to tune each individual section of map gives you a ton of control over the
  96 actual gameplay. It also allows you to use non-standard map shapes (get outta
  97 here square rooms) and generate really unique looking maps.
  98
  99 You would need to rotate the location of interactables, but with enough of these
 100 map pieces being put together in random orders it gives you a lot of variation
 101 for your players. And if the unlikely event that they end up getting the EXACT
 102 same map somehow (you know, cause random), the locations of all the interactable
 103 items will be randomized.
 104
 105 ## Standard Dungeons (Connected Squares)
 106 There are a million of these tutorials as this is the standard look for
 107 dungeons. I think they work wonderfully when you're actually exploring a dungeon
 108 in a castle or something - but otherwise they seem out of place
 109
 110 The premise is pretty simplem but it involves iterating over the map numerous
 111 times to achieve the look you want. The steps themselves are pretty
 112 straight-foward.
 113
 114 1. First go over the map and generate rooms (squares or rectangles, whatever you
 115    want).
 116 2. Then go over the map again and connect the rooms together via pathways.
 117
 118 Normally you'll make multiple passes over the map to generate the appropriate
 119 room density that you want. The more rooms, the easier it is to connect them
 120 all.
 121
 122 The connection part CAN be confusing, but the easiest way is to actually look at
 123 various path-finding algorithms. Since the map doesn't actually exist, any
 124 pathfinding algorithms will find the straightest line possible between your
 125 rooms.
 126
 127 Simply iterate over each pair of rooms and connect them using your chosen
 128 path-finding algorithm. [A\*](https://csis.pace.edu/~benjamin/teaching/cs627/webfiles/Astar.pdf)
 129 is always a good choice to understand the real basics of the algorithm so that
 130 you can implement it yourself. Or at least so you understand what's happening
 131 before using whatever package in your programming language of choice.
 132
 133 The pro's of this technique is that it's a very well documented approach. You
 134 can adjust the density of the map very easily.
 135
 136 So easily, in fact, that you can ramp up the density to the point that all of
 137 the rooms overlap. The iterate to remove random sections of obstacles (walls)
 138 that are inside the room. That will allow you to generate LARGE rooms where
 139 everything is accessible.
 140
 141 ## Drunk Walking
 142 The Drunkards Walk is a very simple algorithm and one that I stumbled upon
 143 without really knowing about it. The idea is simple and is based on these requirements:
 144
 145 1. You want to generate organic looking maps
 146 2. You want to ensure that all sections of the map are reachable
 147
 148 The organic maps requirement is probably the most interesting one to me. The
 149 ability to random generate maps that don't look like a bunch of pre-defined
 150 shapes. You could, technically, achieve that same look a myriad of ways, but
 151 this seems the easiest.
 152
 153 The method is as follows:
 154 1. Create a "walker" on your map of some size (maybe 4 tiles? maybe 9? whatever
 155    you feel like)
 156 2. Start them on one side of the map, with their edges being walls, and their
 157    interiors being walkable floors.
 158 3. Make them march to the opposite side, adding some jitter along the other
 159    axis.
 160
 161 The size of the "walker" dictates the minimum width of the space you're
 162 generating. If you want something to feel more open, make it larger. But if
 163 you're making caves or something, just make them smaller.
 164
 165 The "drunken walk" step sounds confusing, but it's pretty straight-forward. If,
 166 for example, we start the walker on the west side of the map, they will be
 167 walking to the east. Every step they take to the east should be coupled with
 168 them randomly shifting north/south by a MAX of the size of the walker.
 169
 170 That's it.
 171
 172 When you're done, you have a single corridor. To build a map, add more walkers
 173 all moving along the same plane (west->east for example), and then add one or
 174 two walkers moving from the perpendiclar plane (north->south in this case). This
 175 ensures that all corridors will be connected, and gives you really neat looking
 176 maps. To me, they work wonderfully for caves/pathways.
 177
 178
 179 But, by playing with the size of the walker you can change the entire look of
 180 the map. Really wide players give you huge open spaces!
 181
 182 the only thing this DOESN'T do, is actual square looking rooms like if you were
 183 in a real dungeon..