Herbert Wolverson - Procedural Map Generation Techniques

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.