Return to Video

Herbert Wolverson - Procedural Map Generation Techniques

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

more » « less
Video Language:
English
Duration:
27:29

English subtitles

Versiuni Compare revisions