Herbert Wolverson - Procedural Map Generation Techniques

Video Statistics and Information

Video
Captions Word Cloud
Reddit Comments
Captions
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.
Info
Channel: Roguelike Celebration
Views: 19,352
Rating: 4.9741101 out of 5
Keywords:
Id: TlLIOgWYVpI
Channel Id: undefined
Length: 27min 28sec (1648 seconds)
Published: Thu Oct 15 2020
Related Videos
Note
Please note that this website is currently a work in progress! Lots of interesting data and statistics to come.