💾 Archived View for gemini.xangelo.ca › posts › devlog › roguelike › dungeon-generation › index.gmi captured on 2022-04-28 at 17:29:50. Gemini links have been rewritten to link to archived content
-=-=-=-=-=-=-
← Newer: Gemini, an HTTP alternative
→ Older: DEVLOG: NewsRiver Updates
As always, I've been working on a terrible browser-based game. This time, it
will be revolving around gameplay mechanics from roguelikes(or roguelites
technically)+jrpgs.
The thing I specifically want to look at today is the topic of Dungeon
Generation - both in and out of code.
Roguelikes all tend to share one mechanic: Procedurally Generated Dungeons. The
idea is that every play-through is different, every floor of a dungeon is
completely unique. As a result, it requires the player to learn the mechanics of
the game over multiple runs as most roguelikes also include perma-death as a
required feature.
Dungeon Generation in roguelikes are a very interesting topic for two reasons.
There is a definite technical component to being able to generate "good"
dungeons quickly. Dungeons that are large enough, with enough rooms/pathways to
be interesting, but that don't take forever to generate. The goal is each floor
is generated randomly when the player enters - we don't want load times
equivalent to stepping into a room in Morrowind. The second reason is one that I
think roguelikes can miss out on - dungeon generation must fit the environment.
Most roguelikes have a generation alorithm that gets assigned to every single
floor. But that's not really that helpful. Dungeons should reflect the
environment the player is in. Having square rooms in a castle dungeon makes
sense. Having square rooms in a cave, not so much.
A lot of dungeon generation information you find online tend to focus on the
techtechnical component: HOW do you generate a dungeon. I'm hoping to also cover
the second bit here.
The easiest to explain algorithm is the "Random" one, but it's probably the
hardest to get right. Random dungeons are exactly what you'd think -> just
randomly place obstacles and interaction points around the dungeon. As a result
it's very easy to actually MAKE the dungeon.
It also has the added benefit that the "random" look works really well for open
fields. Think areas that are strewn with trees or rocks or something like that.
It could also work really well for large underground caverns since you would be
peppering the inside with obstances.
But we're not just making a dungeon - we're making a game. And truly-random
dungeons are hard to tune. How do you ensure that every chest you place is
actually reachable by the player? How about the one set of stairs? How do you
ensure that the player doesn't spawn in a box, closed off from the rest of the
dungeon. How do you ensure that they don't spawn right next to some stairs?
Each of these questions (and many many more) result in you tuning you random
generation more and more. You'll never get it 100% right. There'll always be
edge cases reported by your places that you didn't even think about (did a
monster spawn in deep water so the player didn't even know it was there and is
now reporting that they didn't get an achievement for killing all the monsters
on a foor?).
I started with a purly random dungeon generation system myeself. It's definitely
not a bad call to make - but you just have to be aware of the edge cases. But I
kept having to tune/adjust things and I'd still end up with play testers saying
they got spawned in a box, or couldn't reach the stairs. That's frustrating
enough to probably just stop playing.
The nice thing about random, however, is that you don't NEED to generate the map
in its entirety. Nor do you need it to be entirely random.
So you have the container for your map.. and your character is spawned in a
particular point `(x,y)`. Given a field of view (`v`) really you only need to
generate a box defined by the points `(x-v, y-v)`, `(x+v, y-v)`, `(x-v, y+v)`,
and `(x+v, y+v)`.
If the player steps in a direction, you only need to expand the generated
portion of the map by 1 tile (or whatever your fov is). In this way, your entire
dungeon is being generated as the player discovers it. You get a few benefits
like not needing to store the entirety of the map if the player doesn't visit
it. You can tune drop rates for everything just by how much of the map is
discovered vs. isn't. You can also almost guarantee that EVERY point on the map is
reachable by the player and that they'll discover the stairs exactly when you'd
like them to.
Now, lets get the pedantics out of the way - nothing we're doing is random, it's
all pseudo-random. The difference is that in this generation mechanic we're
actually building the map from pre-defined map parts.
The downside, of course, is that you have to spend a bunch of time generating
the pieces of map and you do have to have to have some guidelines. But, being
able to tune each individual section of map gives you a ton of control over the
actual gameplay. It also allows you to use non-standard map shapes (get outta
here square rooms) and generate really unique looking maps.
You would need to rotate the location of interactables, but with enough of these
map pieces being put together in random orders it gives you a lot of variation
for your players. And if the unlikely event that they end up getting the EXACT
same map somehow (you know, cause random), the locations of all the interactable
items will be randomized.
There are a million of these tutorials as this is the standard look for
dungeons. I think they work wonderfully when you're actually exploring a dungeon
in a castle or something - but otherwise they seem out of place
The premise is pretty simplem but it involves iterating over the map numerous
times to achieve the look you want. The steps themselves are pretty
straight-foward.
want).
Normally you'll make multiple passes over the map to generate the appropriate
room density that you want. The more rooms, the easier it is to connect them
all.
The connection part CAN be confusing, but the easiest way is to actually look at
various path-finding algorithms. Since the map doesn't actually exist, any
pathfinding algorithms will find the straightest line possible between your
rooms.
Simply iterate over each pair of rooms and connect them using your chosen
path-finding algorithm. A\* [1]
is always a good choice to understand the real basics of the algorithm so that
you can implement it yourself. Or at least so you understand what's happening
before using whatever package in your programming language of choice.
The pro's of this technique is that it's a very well documented approach. You
can adjust the density of the map very easily.
So easily, in fact, that you can ramp up the density to the point that all of
the rooms overlap. The iterate to remove random sections of obstacles (walls)
that are inside the room. That will allow you to generate LARGE rooms where
everything is accessible.
The Drunkards Walk is a very simple algorithm and one that I stumbled upon
without really knowing about it. The idea is simple and is based on these requirements:
The organic maps requirement is probably the most interesting one to me. The
ability to random generate maps that don't look like a bunch of pre-defined
shapes. You could, technically, achieve that same look a myriad of ways, but
this seems the easiest.
The method is as follows:
you feel like)
interiors being walkable floors.
axis.
The size of the "walker" dictates the minimum width of the space you're
generating. If you want something to feel more open, make it larger. But if
you're making caves or something, just make them smaller.
The "drunken walk" step sounds confusing, but it's pretty straight-forward. If,
for example, we start the walker on the west side of the map, they will be
walking to the east. Every step they take to the east should be coupled with
them randomly shifting north/south by a MAX of the size of the walker.
That's it.
When you're done, you have a single corridor. To build a map, add more walkers
all moving along the same plane (west->east for example), and then add one or
two walkers moving from the perpendiclar plane (north->south in this case). This
ensures that all corridors will be connected, and gives you really neat looking
maps. To me, they work wonderfully for caves/pathways.
But, by playing with the size of the walker you can change the entire look of
the map. Really wide players give you huge open spaces!
the only thing this DOESN'T do, is actual square looking rooms like if you were
in a real dungeon..
---
[1] A\* (https://csis.pace.edu/~benjamin/teaching/cs627/webfiles/Astar.pdf)
What the heck is a Database Index?: <no value>
---