Noah: Our next speaker is Herbert Wolverson.
Herbert is a hobby game developer, and he has been since the 1990s.
He developed Nox Futura, One Night in the Dungeon,
and a bunch of 7DRLs. He also wrote a book
about Rust roguelike game development, and he's currently writing another book
about learning Rust through making games.
This talk is called Procedural Map Generation Techniques,
and this is acctually something I'm super excited about, as I've always
wanted someone to give a talk about this topic.
So without further ado, here's Herbert.
Herbert: Hi. Welcome to Procedural Map Generation.
I'm Herbert Wolverson of Bracket Productions,
which is really just my consulting company.
I'm gonna be talking to you about using algorithms to generate
maps, and then using more algorithms to fix the maps you
just created and find out if they're even usable.
There's a lot of content to cover, so I'm gonna be going on
at quite a rate of knots.
So, who am I? As Noah just said, I'm the author
of the Rust Roguelike Tutorial, on the address on the screen there.
I talk way too much on Twitter @herberticus. If you ever want to
get in touch with me, /u/thebracket on Reddit is the best way to find me.
I love hanging out on the roguelike dev forums, answering short answer
questions with SAS. I do have a book coming out very soon, Hands-on Rust:
Effective Learning through 2D Game Development and Play,
which will be out on PragProg.com.
I promise I won't keep promoting that, but I really wanted to mention it,
and all the sourcecode that goes with this talk can be found on GitHub
at that address. That'll be repeated on the final slide of this presentation.
So we're gonna give a quick shoutout to Rogue, from 1980,
because we really wouldn't be here without it. It's one of the
seminal and first uses of procedural generation that really defined
the genre. It splats out up to nine rooms, connected randomly.
It's been said that they did that because they needed to keep
the game small and really couldn't fit in 50 beautifully hand-designed
levels, but really that created one of the strengths of the genre
in the first place. When you start a new game, you have a different
map every time. So every time you play, instead of memorizing that
I need to go up, up, up, right, you're learning instead that
I should interact this way with different monsters, and interact
this way with rooms, navigate like this, learning the system rather
than learning the game itself, giving you effectively infinite replay.
Also, any talk on procgen really has to mention Dwarf Fortress,
because no other procgen game has ever managed to cram this
much procedural generation into one binary.
If you haven't played it, go out and do so.
Support them on Steam, and tell them how awesome they are.
They generate everything from a massive overworld with
sweeping mountain ranges, dense forests, volcanoes,
demon-infested fortresses, fill it up with procedurally-generated
civilizations who either like or hate each other, and then
you can drill all the way down to Urist and find out which
proedurally-generated deity he worships, which procedurally-generated
tavern he drinks in, and learn all about his quest to cross the land
and find the perfect sock.
At the mid-scale, you can zoom in to any particular land block on the map,
find out that it is beautifully rendered, still matches the overall shape
of the overall world above it, the trees gain foliage, lose foliage,
depending on their type and the type spawns appropriate to the biome.
In other words, there is pretty much every procgen technique that you
can think of in this game. Hang out in the Bay 12 forums
and that is a great place to learn about them.
So one thing that's clear from both of these games is that,
while they're random, their randomness doesn't define the game.
The randomness is fed into an algorithm that generates something
that approximates what you want to get, but ensures that it is different
every time. So, we're gonna start looking at some algorithms
for doing that.
A simple room placement. If you've done any of the
roguelike development tutorials, then you've seen this one.
You start with a solid map. You pick a random rectangle.
If there isn't a room already there, you fill in the rectangle.
You keep adding rooms until you meet whatever criteria you've
come up with for enough, and then you join the rooms
together with corridors. Let's watch this in action.
As you can see, it's placing rooms randomly. When you see the
red rectangles with the exclamation marks, they tried to generate one
that overlaps, so you have to discard it and try again.
And then it joins them together with corridors. In this case, they went
with a simple dog leg algorithm, that randomly switches between
being either vertical first or horizontal first.
That's pretty much exactly the algorithm from the Python
roguelike dev tutorial that the roguelike dev subreddit recommends
that you start with.
So a good refinement of that is Binary Space Partition rooms, or BSP.
Binary Space Partition is fancy developer talk for chopping in half.
It gives a similar result to random room placement,
but it pretty much guarantees that everything is better spaced out.
You'll find that it's used in Nethack, amongst other games.
So to do BSP, you divide your map in half, and you randomly decide
whether you want to divide vertically or horizontally, and divide that half in half.
Then you keep dividing your halves all the way down until you have
a space that's roughly the right size you want to use for a room.
And I personally like to then add a gutter of one tile around it,
to ensure that you don't get rooms joining together, unless that's
what you want. So watching that in action,
you see that there's absolutely no rejections, the rooms are nicely
spaced out, and you wind up with a pretty usable map.
So complete change of gear, Cellular Automata.
I personally love this one, because it involves an ordered-looking
natural map from complete chaos. You know, I said you don't always
start with complete random? Well, this one, you do.
You can literally make half your map walls half your map floors,
randomly picked, no chance of getting through it,
and you'll end up with something you can use.
If you played Conway's Game of Life or seen articles about it,
it's the same principle here. So once you've got your map,
you make a copy of it, you iterate every tile that isn't
on the edge, and you count the number of neighbors, including diagonals.
If there are no neighbors, then it becomes a wall. If there's one to
four neighbors, it becomes empty. Five or more neighbors, it becomes
a wall. Now, you can and should tweak these rules to suit your game.
Let's watch this in action. Completely random soup quickly turns into a
far more natural looking structure that can actually be turned into a
pretty useful map. And it's a really simple algorithm, really fast,
and given the same seed, you get the same result every time.
Next one to talk about is Drunkard's Walk. This is another popular one for beginners.
So the basic principle of Drunkard's Walk is that you start with a solid map, find one
Umber Hulk, and ply it with beer until he's staggering randomly.
Place him somewhere on the map. As he staggers, he randomly smashes
through walls, and carving out a map. Don't bother worrying about whether
he backtracks. Let him stagger wherever he wants. Pick a maximum distance for him
to travel, or her. I'm really not sure how Umber Hulk's gender works.
If they travel too far, they pass out, and you can pick another
Umber Hulk, spawn them somewhere within the open map, and let them smash.
Then you stop spawning Hulks when enough of your map is open.
In this case, I've used one-third of the map.
So watching this in action, you can see that each Hulk is staggering
completely randomly, carving out more and more of the map.
One big advantage of this is that you can guarantee that your map will
be contiguous. It won't generate any areas that your player
can't reach. It tends to give you maps that looks like it was
carved out by water, ideal for creating limestone caverns and similar.
Another algorithm, Diffusion Limited Aggregation.
I highly recommend the RogueBasin article on this one.
So for the simple version of this, you start by digging out a small
target seed, and then you pick a random point anywhere on the map, a random
direction, and shoot a particle. If you're really lucky, the particle
will hit one of the already open areas. If it doesn't, you keep shooting until it
hits something. Something I've heard from a lot of military friends.
In the event that you do hit a target area, then you carve out the last solid
area that you passed through. This tends to give you a very winding,
open map. Again, it's guaranteed to be contiguous.
And there's a lot of ways that you can tweak the algorithm to make something
more interesting.
So the Central Attractor is much more likely to always hit the target.
You randomly spawn your starting point and then shoot the particle directly
at the middle of the map. This pretty much ensures that you
get an open space in the middle, ideal, for example, for you to put
a dragon with his hoard, and then a more interesting pattern forming
around the edges, which could be where the hobbit would lurk while he
torments the poor dragon. On the right, you can see what happens if we
use the same Central Attractor algorithm, but simply apply
a symmetry down the vertical. You start to get maps that look
a lot like they either want to eat you, or maybe it's a butterfly,
maybe it's a Space Invaders character.
I recommend using this one sparingly, but a bit of symmetry like that can be
applied to any algorithm when you want to produce something
that looks a lot less random.
Another algorithm that everyone should have in their toolkit is the
Voronoi Diagram.
So to make one of these, I do recommend Googling it.
You randomly or deliberately place seeds all over your map.
You randomly place them if you just want to produce something random.
If you place them very deliberately - for example, you can equally space
them all over the map - you can produce something that looks
very, very much like a beehive.
And then you iterate every point on the map, and it joins the
area belonging to the closest seed. There are various fancy algorithms,
like Delaunay triangulations, to do this quickly. In the source code I've
provided, I just brute forced it and did it the hard way.
Now, one neat trick for customizing what you get is that you can
use a different distance algorithm to determine which group
every tile joins. So on the left, I've used Pythagoras, and it gives you
relatively smooth edges. Using Manhattan distance, which is the same distance
that you get if you ask a New York taxi driver how far it is to get to
somewhere, a number of blocks north plus number of blocks east,
it gives you a much more manmade-looking, sharp-edged structure. And Chebychev
is a similar distance algorithm, and tends to give you somewhere in between
the two. So what do you do with Voronoi diagrams? Well,
the first thing you can do with them is find the edges, place walls there,
and wind up with an alien cell structure. Another good thing to do is
decide that when you're spawning monsters, you'll spawn the monsters together
within a Voronoi cell.
So, for example, you've decided that the orc king should always be
seated with his retinue. Then, you should probably spawn them
in the same cell together, if possible. Likewise, if you decided that orcs
must never, in fact, be near dark elves, make sure that you spawn them in
far away cells. You can also use this for very effective city generation.
In my PROCJAM game, Apocalypse Taxi, I used the edges of Voronoi cells to
determine where the roads went, and then randomly populated the content of each
cell with something like heavy industrial city, light industrial, and it worked pretty well.
Combined with other techniques, this can be extremely useful.
The next one up is Perlin/Simplex Noise, which is used all over the place,
more than you might think.
So Perlin/Simplex Noise are basically a bunch of gradients combined together
with a few variables we'll talk about in a moment.
You can generate it in either two or three dimensions. If you look in X/Y value,
it gives you a number between -1 and 1.
And the nice thing is, if you look at an adjacent one, it will be smoothly
moving either up or down, relative to the neighboring squares.
It's also continuous, so if you decide to look from X 1 through 2,
and then decide to zoom in to 1.5 through 2, you'll actually get
exactly the same shape as you saw on the right-hand side in the first one.
So what do the variables mean? Now, the number of octaves
give how many different gradients it's mixing in. Gain is how long the various
gradients last. Lacunarity adds in randomness, and as you can see,
from the picture on the right-hand side, which I guess is my left, this starts
to feather it in and make it look a lot more random.
Now, frequency is how frequently each of the various octaves
peaks. So, what I recommend you do is find a Perlin/Simplex Noise tool
and simply play with these values until you get something that you like.
So what can you do with them? The answer is actually quite a lot.
The most common use is to make an overworld. Because Perlin
is deterministic by random seed, every time you use the same seed,
you get the same map. Now, what I've done here is
altitudes from -1 to 0 blued out as water, altitudes from 0 to .75
are in green, shaded as terrain, altitudes above that are marked
as mountains. And this is very common. You'll find this used in a lot of games.
And as I mentioned, you can zoom in. So as you zoom in, you start to see more
of the gradient. The problem is that the gradients are actually
kind of dull.
Now, you can fix that. The best way to fix that is to make a second layer
of noise. So in this case, we've got a second layer of noise that is much more
bumpy, has much more fine-grained detail, but looks terrible as
a continent as a whole. And then as you zoom in,
you change the percentage of each of the two gradients that you're
mixing together. So when you're zoomed all the way out like that, you're seeing
the relatively coherent overworld. As you start to zoom in, you see
bays, peaks, valleys, troughs. And the great thing is, this is
actually really easy to implement. There's a lot of really good
Perlin/Simplex libraries out there. I highly recommend it.
You can use it for anything from making a pirate game with cool seas
to sail around, or just building the overworld for your map.
You can also use it if you want to generate realistic-looking
clouds, particles. You can even make wood grain with it, with the right values.
And that brings me to one point that I can't emphasize enough.
You very rarely need to use just one technique on a map.
So here, on the top left, we've used WSP technique to produce a
pretty linear-looking dwarven fortress. On the right, Cellular Automata
has made a really open-looking sort of cavern system. It might
be a dangerous underworld. So running with that theme,
I simply took the left half of the dwarven fortress and the right half
of the Cellular Automata, and you have what looks like a fortress
that suddenly breaks out into a nasty underworld. Well, I thought,
a better theme for that might be that the dwarves were digging, they
came to the underworld, and they needed to protect themselves.
So I added a prefab, a predesigned section in the middle, adding fortifications.
And so, with two very simple techniques, you've produced a map that actually
tells a story, rather than just being a bunch of random rooms.
Another popular combination is take a map and then use DLA
to fire particles at it, and blast parts of the map away.
This starts to look like dwarves failed to pay their maintenance bill,
or had a serious water problem, as the map becomes more and more
organic-looking while keeping its basic structure.
I mentioned prefabs before. Prefabs are a great idea.
So you can make a massively random map, but if you start injecting
human design elements into it, then you get the chance to really make the game
your own.
So I've got a prefab here that is definitely not a trap. It's death
traps surrounding a treasure chest. You've probably seen that in a lot
of console RPGs. You enter a room, you see a chest,
with nothing guarding it. You can be pretty sure that
something bad's about to happen to you.
So the room structure makes it relatively easy to place a prefab. You can go
through the room list, find a room that's bigger than the prefab, and you know
the prefab fits there.
On a map that doesn't have rooms, it can be a little more tricky.
What I usually do is I pick random locations, look and see if the prefab
will fit, and place them. If it won't, then I don't place it there.
If I've got a nice, big list of prefabs, then I'll keep going until I've added
a few of them and been careful not to add all of them, so the game is
different next time I play.
Very quick change of gears, because the next set of algorithms
all are going to rely on this one, the Dijkstra maps.
I highly recommend that you go to RogueBasin and read
The Incredible Power of Dijkstra Maps on there. It is an excellent article.
And Dijkstra maps are a very powerful tool if you're into making roguelikes.
I recommend that you learn about them.
To make them, you start with one or more starting points.
In this case, the blue knight. The rest of the map gets marked to a sentinel
value, meaning you can't go there. And then you look at all the tiles
adjacent to your starting point. If you can walk into them, you put
a 1 on them. You can get there in one step away from the starting point.
Then you keep going. So every walkable tile that's next to a 1
gets a 2, and a 3, and a 4, and a 5.
Eventually, you have a complete map that tells you, first of all,
the sentinel value means that you can't go there. So now, you've got
a list of all the cells you can't use. Likewise, the numbered tiles tell
you how far away you are from a starting point.
So the first big use for this is when you've generated something like
Cellular Automata, that can give you chunks of a map that you can't get to.
Pick a central point, find one that's open, generate a
Dijkstra map, and then all of the tiles that are open that have the
sentinel value on your Dijkstra map can't be reached, and I've highlighted
those in red on the map. You can delete those, because
nobody can get there. Or, if you've got a game system
that encourages tunneling, then go ahead and hide the stuff that needs
to be reached with tunneling in those areas.
This can also help you with placing a starting point on your map.
Making sure that you cull the unreachable areas before
you pick a starting point ensures that you won't place the player
somewhere that they can't get out of, and it avoids the
always embarassing case of the map that's only got two tiles
that you can actually walk on.
That has happened to me.
So typically, to place a starting point, if I know that I want to be on the
left, I'll place somewhere in the middle on the left, and then I'll
simply look around for a neighboring tile that is open and hasn't been culled
by the Dijkstra map.
To find an endpoint, you can use the same thing, if you want
to go left to right. A lot of games prefer to have more of a
structured progression. Once you've culled the map,
you know that anywhere on the map can be - that is still open after you've
removed the areas you can't get to, it's safe to place an exit.
So you find the rough area you want to put the exit and you place on a nearby
open tile. I've gone ahead and marked the optimal route through that map.
You can also, if you really dislike your player, use Dijkstra to find
the least accessible part of the map and put the exit there.
If they're starting in the middle, this is a really bad idea,
because three-quarters of the map is basically irrelevant.
However, if you want to hide something, this is a great way to do it.
Find the starting point, then find the least accessible point on
the map, hide something there, and you force the player to go on a
treasure hunt, if they're gonna get the bonus item.
That leads to one of my favorite techniques for refining a map,
once you've generated it. I call it the "Hot Path."
Once you've got your start point and your end point, you generate
the path between the two. I use ASTAR. In this case,
I think I used a Dijkstra map and just walked the distance between the two.
Then you make another Dijkstra map, using all the points on the path as
your hot path. Then, on that Dijkstra map, everything with a tile value of under,
say ten, is the hot path and is close, but not necessarily directly
on the best path through the dungeon.
So what can you do with this? Well, if you prefer a less-branchy game,
you can use it to remove the parts of the map that are completely irrelevant.
If your game involves a great deal of progression from, say, left to right,
this is a good way to do it, and a good way to not force the player
to explore huge, winding labyrinths with no real purpose to them.
If you're using a room-based generation, then this can be even more useful.
I've marked in yellow the rooms that are on the hot path that go directly
from point A to point B. Also, that means the grey
rooms aren't really necessary. Or are they?
Maybe the grey rooms could be culled, if you just want to have a go to room,
go to room, go to room type of game. Or, the grey rooms could be where
you hide bonus things. You might have the yellow rooms mark some breadcrumbs
to give the player a clue as to where to go, and teach them by putting
really scary things in the grey area that are off the beaten path
and only to be done once you're a little more experienced.
You can also use this knowledge to order the progression of the story.
So you know that if the player's gonna go through this dungeon, they're
probably gonna go through one to nine.
And that's okay. If you're telling a story, let's say your grandfather
tells you that it is your destiny to go out and save the world, he's probably
going to want to tell you that somewhere around room one, so you can't avoid
the old windbag. Somewhere around two, somebody should show up and
tell you that your destiny is futile, you should abandon it,
give up, and the whole adventuring thing isn't for you, and so on.
Alternatively, you might have decided that you wanted to do the old
saw of the locked door that has a key somewhere on the map.
Supposing that you've decided that room five is gonna be where the locked
door shall be, it would be a good choice because you can do a flood-fill and
discover that there's nowhere else, there's no alternates to going through
the exit from room five.
So you place a locked door there, and now you absolutely know that the key
has to be somewhere between rooms one and four, for this to be a
solvable puzzle. It would really suck if you decided to spawn the key
in room six, and leave yourself with a map that cannot be solved
without finding some other way to open the door. You know, unless
of course that's your point. And really, that is the point
of what I've been trying to say, is guide your randomness
and then use algorithms to check your randomness, to make sure that
it matches what you want.
I've written quite a bit about other algorithms on my
roguelike tutorial, tried really hard to be language-agnostic, even though
all the examples are in Rust. So, I do recommend checking there
for a few more. I wanted to talk about Wave Form Collapse, and realized
that I needed another 30 minutes.
Alright, so like I said before, the source code for this talk is all up on my GitHub.
That repost should have gone public a few minutes ago.
And just to be a terrible shill one more time, my book
Hands-on Rust: Effective Learning through 2D Game Development and Play
will be in beta on PragProg relatively soon, next few weeks, as long as
I get off my butt and finish editing it, and in your favorite bookstore
pretty soon. If there's any questions, I'd be happy to take them.
Noah: Wonderful. Thank you so much for that talk.
Herbert: Thanks for having me. Noah: Yeah. We have a few questions.
The first one is from Darren Gray, who asks, "How do you make
generated maps not look very samey?" For example, he says that
he can always notice when an overworld is generated with
Perlin noise.
Herbert: Yeah, that's actually a fun one, and I play spot the Perlin.
One of the best things to do is to generate multiple noise maps
and mix them together. So if you've decided that this region is mountains,
start mixing in height values from another more mountainous-looking height map.
That gets you something that is, as well as just going up,
actually goes up and down, up and down, and starts to look more like
mountains and less like a boring little gradient.
You can also have a lot of fun generating your Perlin, and then
run something like a Russian on it. Running a simpler
Russian simluator, especially if you decide that some rocks are
harder than others, gives you a beautiful map in no time.
I think that's how World Machine works.
Noah: Cool. Our next question is do you know any techniques for
generating vertical structures, or Z levels in map generation?
Herbert: That is something I am honestly terrible at.
I've seen Wave Form Collapse used to make some absolutely
amazing Voxel-based cities. I can't honestly pretend that I know how
to do that.
Noah: Cool. That looks like all of the questions that people have
put in.
But thank you so much, and then I'm sure if you hang out
somewhere in the social space, people will come and ask you more questions.
Herbert: Yes, I should be around there and on the Discord tonight.
I'll be editing my book and alternating between the two. Thank you.
Noah: Cool, thanks so much.