Brian Walker - Procedural level design in Brogue and beyond

hi everyone I'm Brian Walker I made broke and I was trying to think about what I should talk about today and I think the part of broke that I liked the most that I enjoyed programming the most and that I did first was the level generation and I don't know that that's always the way that people approach roguelike development I think sometimes people start with systems and then kind of build the roguelike build the level design system after that but for me it was all about designing cool levels and I was kind of thinking about what makes procedural generation so exciting for the genre that it's sort of at the center of the genre if you will and I think I the obvious one is that the skill curve is more about mastering the systems of the game learning how to adapt to what you're given and how to deal with the level do you find it rather than memorizing a level and memorizing the set of actions that it takes to beat the level but I think equally important to me at least is like the kind of feeling of exploration you get when you play a new level where it feels like a real place that you're discovering for the first time no one's seen it before assuming you're using like a 32-bit seed probably no one else has ever seen that level before and especially as a game developer I frankly don't know how people do it when they make static games because you have to play them so many times and having the privilege of seeing a new level each time means that you can approach it with a degree of novelty and sort of an interesting mnestheus of more static games probably have to lean on third party play testers more for it's not easier to develop you get an infinite number of levels I guess or roughly but it takes a lot of time to come up with the systems but it's also like a different skill set like I'm not sure that I would know how to build a static level where as procedural generation rather than like being an artist and like laying out elements of the level on a canvas you kind of like make it tweak and you decide which one feels better like which painting like more and you kind of iterate like that and you come up with an idea you try it you tweak the the hyper parameters for four years so it's it's like a different skill set I don't think it's necessarily harder but it's it's not a time-saver so let me just walk through the brogue level design algorithm and we will build the level that you saw so on the title slide at the start so the basic you know algorithm that brogue uses is room accretion which is a very simple algorithm you start with a room you add another room on to it and you keep doing that until the level is full so that's like the basic skeleton of it so there's a bunch of different ways that we can create these rooms overlapping rectangles so then the you know you just come up with two rectangles and you kind of place them on top of each other maybe symmetrically maybe not cellular automata or CA I think this is a pretty well-known technique you take a grid of cells you fill it randomly each one maybe 50% chance of being wall or floor and then any floor that's surrounded by a majority of walls becomes a wall and vice versa and you can play with the thresholds to get different levels of density and smoothness but it kind of causes sort of coherent organic shapes to kind of emerge from the static that you start with and then you know just circles overlaying small circles sometimes you had a hallway to it sometimes you don't these green green cells it picks out some door candidates from each direction for each room and that's basically how it comes up with rooms so it starts by placing one randomly and then it just starts generating rooms sometimes with hallways sometimes not and it scans through all the locations on the level one at a time in random order until it finds one where the where the room fits snugly against another room where the door links it up and where it doesn't overlap any other rooms so that's like the basic practice to come up with the skeleton level design there is a fatal flaw to it which is that it's like a perfect tree each room has exactly one parent except for the first room which has no parents and any number of children which means that if you pick any two points on that level there's exactly one path that doesn't backtrack to get between those two points which is like it looks nice on a screen but it's not that fun because it's easy to get cornered it causes a lot of backtracking when you play it so the next step is we basically go through again in random order and find wall tiles that have a floor on each of the two opposite sides and if the pathing distance between those two floor tiles is large enough then we just turn it into a door and you just do that until you've found all the candidates for that looks like that creates a nice you know densely connected level and then that level looks like this when you carve it into the the game assets and then the next step I think if you play this kind of a level the rooms are interesting in terms of their shape and connectivity but they're all kind of samey like it's it's amazing to see passages and I think it's cool to give a level kind of a coherent global scale to the features where you know you can see across the level you can affect things that aren't just in your local vicinity things can affect you and when they're not in your local vicinity and you can sometimes see like secret doors on the other side of the level but not necessarily know how to get to them so to accomplish that we put in lakes and these are again just cellular automata blobs that we create and then again find all the different places on the level where they could be placed and only place it if it doesn't block the level and by that I mean it blocks the level if you put it somewhere and that makes any pair of walkable tiles inaccessible to one another so we just scan through kind of brute force see if there's if it blocks and if not you just place it let them overlap and then kind of assign media types afterward after that you just kind of iterate through place dungeon features there there's a whole bunch of these I think coming up with cool terrain design is like a big part of level design seeing of luminescent fungus you have trees you have grass you have doors I choose torches later levels you have different kinds of kind of dangerous foliage chasms are another lake type you do this to sort of add some flavor to the dungeon and a lot of these features are interactive you know some of them will burn some of them will explode some of them will generate gases of various types and so on so after that's finished the next step is what I call machines and to sort of describe what those are let me give you a couple examples first so let's say you come into a room it's full of dry grass it's a big open space and there's an altar with a key at the far end of the room there's a torch on the wall near the door which you can see up here so the player runs over to the altar and grabs the key and the torch falls off the wall and ignites the grass near the entrance and then the fire gradually spreads toward the player and then the player has to either you know if they have a teleport that would be a good time to use it to blink fire immunity or just try to like find a spot that's already burned out before the fire reaches you so it's kind of an interesting spatial puzzle it's like a little different every time the stakes are super high although they can be depending on what other monsters are around what what your health level is and so on another example this is a great animation that I found online so the player runs down to the altar grabs the key and and somebody's find them on the way out and that's it's not a coincidence like if you see in the very first frame there's a statue way up there on the top and when you when you grab the key off the altar monsters burst out of all the statues and running you another example lava field so the the player comes in from the top left there's the altar with the key in the top right there's a door that's completely inaccessible down here across the lava pit somewhere on the level there's probably a potion of fire immunity or potion of levitation or maybe there's a lever hidden in one of the walls and use that to reach the altar and when you reach it then the lava kind of disintegrate or evaporates I guess in a cloud of steam leaving a pathway to get back out or to get to this room that's kind of nested within it and here's an example of a full level that's been generated not the one that we're generating step by step kind of here but just to give a sense of how this all kind of interlocks there's a key in the upper right of the level and a hidden walkway well it's it's a walkway to the key I don't know if you can see it clearly but it's surrounded by chasm tiles but those are actually traps they're hidden chasms you have to search to find them to find your way to the key there's actually another key here the M is a monkey who grabbed the key off the altar and is gonna run away when you try to get it from him so you gotta find some way to kill the monkey from a distance and get the key so you have two keys and those will open the door right here and the end the door right here so these two orange rooms will open up and each one will let you choose one of any items in the room the items are only kind of accessible when all of the items are in place so you can only pick one if you change your mind you can put it back and take a different one and so those are kind of like reward rooms they give you a choice of a bunch of items to make sure that they're sort of boosts the chance that you have the ability to put together a competent character based on the items you find and then in this room you discover at the bottom here which you couldn't see from elsewhere on the level there's like a vampire lair and there's the vampire and he's he's holding another key so you fight him he turns into a bunch of bats you kill the bats you fight them eventually you kill him you get the key and then that unlocks the room on the top right and that's a room with some kind of magical weapon in it so it's kind of like a like the level is kind of globally coherent like they're elements from all parts of the level that tie into the other parts to make it feel more like maybe not a narrative structure to the extent that that Tarn was talking about earlier but it at least sort of a physical structure to the level concrete set of goals where the whole level kind of interlocks as a whole and of course there's items and monsters around the rest of the level - here's another example a little less intricate but a different kind of machine the darker part of the level around the periphery is a goblin warren it's generated according to a different set of rules for room generation to make it kind of narrower passages different kind of flavor for the wall and fleurs goblins throughout items weapons and armour throughout some tough groups of goblins and then somewhere in the goblin war in which in this case is down here there's a goblin warlord which will have a particularly valuable item if you can fight your way to him and you have you have to enter it there's generally just one point of entrance for the war and so you know enter it there and fight your way through it and it's a it's it's pretty interesting to go from the kind of ordinary level on the top right I guess ordinary except for this walkway across the chasm to this kind of different feel for the level once you get into the Goblin ward so how do these machines work they depend on specific types of terrain and items you know in the the grass room you've got the altar of the key you got the torch you got grass everywhere and you can as I just described that you describe it kind of qualitatively in terms of how the things interlock it's not mapped out on a grid all that you need is is for the room to be full of grass the altars distant and the torches near so come up with a bunch of different relationships that define where these items need to be where the the terrain types need to be how much space each one needs whether they need to be in line of sight of the doorway the minimum number that need to be generated for the room to succeed and actually be built and so the idea is you define it with the minimum amount of specification that you need to make the machine work and that way the level generator can take this pre-existing level that we saw at the beginning where you just build rooms off of one another can can take that kind of skeleton and choose a spot and turn it into one of those machines instead of just placing a machine from a predefined grid and that makes them more interesting sometimes you don't necessarily know what you're encountering because some of them look similar at the outset and it's kind of more organic you don't sort of see the first tile of the room and know where everything in the room is going to be one kind of sub technique is how you build these sort of meandering pathways between two points so I used for a bunch of things you can use them with bridges that are you there from the start or that kind of and during the level tunnels through granite pathways between traps so how do you do this you just build obstructive terrain everywhere in random order one cell at a time and you don't build it if it would block the level now you just keep doing that until all that's left is a single wandering pathway between two points so there they're a bunch of different types of machines in the game I really think these machines are kind of the core of the brogue level generation in terms of the the atmosphere and tactics they create so one of them is reward machines those are the ones I showed you earlier with a choice of a bunch of different item types and they're generated in kind of rubber-banded fashion where the the probability goes up every time one is not generated and drops down when one is so you get roughly the same pace of reward rooms at any given game key guarding machines that's any machine with like an altar with a key in it where something terrible happens when you take the key generally and then flavor machines which just have interesting terrain which can be you know tactically relevant like maybe like every room with a decaying sleeping bag and a glyph of warding on the door and a pile of bones somewhere in the room maybe an item so then there's also those are kind of functional types of machines here the different spatial types the the first is room machines which you've already seen a bunch of basically the level generator will look for any point in the level where there's a choke point that dominates a particular number of sort of subordinate cells it doesn't need to be generated as a room at the outside it just kind of analyzes the level and finds a place where there's a single a single point that dominates a certain number of other points and it can turn that into a room and sometimes it'll it'll alter the room once it gets there I'll use cellular automata to kind of widen it out or open it up a bit another type is what I call vestibule machines so these are it sort of captures the area immediately outside of a room so find a choke point and then capture the area like a certain number of cells growing outward but not into the room but outward from the room so you could have about a bunch of glyphs that will trigger this this magic statue outside the door of this room you to kind of pick your way carefully to avoid this this kind of invulnerable monster attacking you here you have another like sort of walkway right outside the room guarding the door for the reward room and then just sort of flammable wooden obstruction in the doorway with something else somewhere else in the level that will let you burn it to get in and then the final sort of spatial type is just area machines it picks a spot on the level that doesn't need to be enclosed by walls necessarily so on the left you've got like a switch that you've got to throw an item on to to trigger the switch and access the key or over here you just have a bunch of goblins standing around a goblin totem which is generated by the machines as well so okay going back to the level that we're generating so here's where we left off now the machines kind of kick in so at first I don't know if you saw that in the lower left here this is two rooms and it picks that second doorway second up from the bottom and widens the interior to make it look like that and then it generates basically a spider sitting on an altar across this chasm so the player can't reach this castle this the spider at first and basically what you have to do is stand on the edge unless you happen to have some kind of teleport item or something you kind of attract the spiders attention the spider launches a web across the chasm and then you kind of climb your way across the web to reach the altar that the spider is standing on and there's an item on the altar when you grab it at this hidden walkway which is this blue pathway will emerge to let you get back so it builds that one first that's kind of a self-contained room next it builds a little less architectural II interesting just sort of a boss layer on the top left with a tough monster in it and then the next one is pretty cool where it picks I think yep so it picks this doorway here and determines that that's a choke point that dominates all these points on the level not including the layer in the top left or the chasm on the lower left and decides that that's enough space to build a goblin warren and then basically reruns the level accretion algorithm to redesign the space that's captured by that by that room so you can see it kind of drawing smaller more claustrophobic rooms there and then it comes up with that as the floorplan and steps through creating the elements of the goblin war and from there and then it's just building some flavor machines elsewhere in the level so then I guess it adds some items but the other main part of the the level generation is just to pick a location for some stairs it tries to line up the upward stairs with the downstairs location on the previous level to give a sense of kind of spatial continuity between levels and it tries to pick a spot for stairs where you don't like there's no reason to step on that space except to use the stairs so you don't need a separate command to use them so it picks spots where I like this spot for example there's walls all the way around it except on one side and that one side is not a choke point or hallway so that's the level and this is what it looks like when it's finished and you play it so that that's sort of the broke level generation techniques I thought would also be interesting you know I I was I think replaying probably Super Metroid a while ago and kind of daydreaming about what that game would feel like if it were procedurally generated along similar lines so I started developing what I call this it doesn't have a name yet but it's a roguelike platformer does it bother anyone when I call a platform or a roguelike you can be honest safe space it's just us and the 12 people watching on Twitch and the 30,000 who watch on YouTube well if it does bother you you can always call it a broke like I hereby license that that trademark so the roguelike platformer that I'm developing it's a 1x2 character a little different and that it has some height Mario style jumping very limited level destructibility which makes it kind of higher stakes when you design the level I wanted it to be a single giant level so you don't unlike a rogue game where you go through maybe 26 levels and sequence this would be one giant level it's more similar to kind of the Super Metroid idea you start at the very top and and the amulet of yin door is at the very bottom and then I think platformers probably work better with controllers which give us and it taketh because then it makes it much harder to do kind of finicky inventory manipulation so have to come up with a controller scheme that's good for inventory work and probably fewer items overall I also wanted it to feel more like a roguelike I didn't want it to be kind of like a reaction time based experience so kind of taking a page from braid it metals with the speed of time as you play never rewinds but if you're motionless standing on the ground not using any items than time is frozen automatically and if you're in the air or you used using an item then time is passing an ordinary speed and if you move along the ground and time passes in proportion to your speed along the ground and then you can just freely toggle into slow motion to kind of execute something complicated so it was it's a very interesting framework it's much different than building kind of a top-down top-down turn-based grid based roguelike pathfinding is a lot harder jumps are more complicated and the controller's is more difficult I and and the the basic key for the path finding is that you need some algorithm to look at two points and decide if you can jump between them which is actually a lot harder than it seemed at first or at least based on my abilities it's very finicky to create even harder to make a monster or a creature that will automatically actually follow that routine there's a lot of kind of tricky jumps that you can do a lot of configurations of headroom of obstacles in the way and I never got it to be perfect but you know game for good enough I guess so that means that you often need a lot of flying enemies because there it's easier to get ground-based enemies kind of stuck in the platforming and you can't really use auto travel so you need to add teleporters everywhere to make it not boring and then I think pretty crucial you have to prevent these kind of wells of doom or you can fall down into a pit and you can't jump back out and so the path finding method works well for that you just run a single pathfinding pass with the level entrance as the goal point of the path finding and then if there are any cells that that are passable but the cell below them is not so this would be a cell if there's any location where from that point you can get back to the start but from the the cell immediately below it you're stuck I just start building platforms there until you solve that and you just keep repeating that until the whole level is is passable and you're just about guaranteed to the limits of the accuracy of your pathfinding algorithm that there won't be any points that the player can get stuck I think working with gravity has been really interesting in a in a top-down roguelike game up-and-down is kind of analogous to left and right there's really no symmetry breaking feature but in a platformer gravity means that up and down is like feels qualitatively different and plays different from left and right so that allows for example vines that spread and grow and can have different effects on the game means that gases can have buoyancy or or weight to them they can sort of rise or fall as they expand and diffuse liquids can fall kind of dynamically they can evaporate terrain can create or or absorb either gases or liquids doors can block them until the doors are open and then let them flow through and then it also creates a bunch of liquid interactions like lava and water turning into steam you can kind of see the progression of the lower-left this is again sort of a machine concept like from broke where you grab the the item here and that triggers the trap which are these vents which release a bunch of water into the lava that creates a bunch of steam in the room and in this case I was able to just kind of stand under the water so the steam couldn't reach me but it your ability to do to do that is really dependent on the shape of the room so there's no kind of one-size-fits-all approach to that there's also you can you can talk about structural support I think some top-down games have a similar idea I think Dwarf Fortress in particular has cave-ins but I guess that's here it's maybe a little more straightforward to add because you can just sort of calculate directly which you can calculate and also see directly which terrain is supporting which other train so a bunch of explosions in the battle on the Left kind of sever all the platforms on the right and they collapse to the bottom and that's the aftermath like I said at the start I wanted to make one giant map with the start at the very top and the goal at the bottom and so unlike the room accretion method I used in broke I just used cellular automata for the entire thing I created this meandering blob shape across the entire level and then it just analyzes to find which regions are disconnected from the rest and just connects them with vertical or horizontal doors which need to be designed differently of course because of gravity and then instead of sort of depth level like wraiths can spawn on depths 8 through 15 or whatever and in a roguelike you just use distance from the start as your proxy for depth and then I also added these kind of shortcut doors throughout the level I really like how in Super Metroid you kind of explore that you're kind of channeled toward one path as you explore but then eventually that path kind of loops back and you can find a hidden connection that opens up the level makes it more connected as you as you continue to retrack it so these are one-way until you open them from the far side and in fact they're completely hidden if it does the job right until you discover them from the far side so that's kind of a complete level from top to bottom kind of hard to see in detail but I would say it's about the same length to play as a typical roguelike alright so that's it thank you very much cool we have time for a few questions if you want to take questions sure does anyone have questions so I'm curious when for the for that chokepoint analysis where the game has to figure out you said if putting a wall there would block walkability you're saying just brute-force it's are you checking literally every tile against every other tile ever Grande tile or is there like a shortcut there to make it more performant yeah you know you don't need to write the you don't need to look at every single pair of tiles on the level what what all you need to do I think and there's probably a more elegant way of doing it but one that works perfectly well is you just find the first you scan through the level find the first passable tile that you hit do a breadth-first search out from there to see what tiles are accessible from that point and then keep skating through and if you find a second passable tile that wasn't covered by the search then you know that the level is not connected so it's sort of one breadth-first breadth-first search to analyze the level if you're gonna place an obstruction everywhere you can in a large area as long as it doesn't block then you're gonna have to do one of those searches for every one of those points but you know I'm not dealing with a very large level so it's it's pretty tractable I had the same question a while back when I was reading an article about your level generator and I was trying to figure out how to calculate choke points I think there is a better algorithm that will find all of them in a single pass it's thinked arjen's minimal cut algorithms if you want to do your Wikipedia I actually have a question though when you were designing the level generator for broke how many techniques did you try that didn't work out that you ended up discarding well they're not like kind of discrete techniques like I would try it tweak and it would either work or not so I don't really know that I have a crisp answer but I would say most of the time that I've spent developing the game was spent tweaking level generation you know tweaking the various parameters of each type of terrain I I think I think that's the most exciting part of developing roguelikes I think it's why it's why I made broke I wanted a game that felt like that so I the bulk of the time went into that in terms of choke point analysis good tip I will look that up you might have to remind me of the name afterward but the the method I use is you basically start with a level filled and then you kind of retract it from the distant most point from the level entrance one cell at a time and as it retracts each retracts into a cell and that cell remembers how many cells in total have retracted into it and if you retract past the cell that has only a single it's it's only a single point then it knows that that's the number of cells that it's a choke point that covers so it kind of does do the whole level in one pass but again it aa great perfect convergent design great yes anyone else yes um in all the overlapping schemes that you have I thought the most fascinating one was the idea of the machines because I feel like that is like such a staged experience of like something really cool that's happening but were there any examples of when you were adding machines that because of the way that you generate the world you made it effectively insurmountable like the Indiana Jones where you can't get through the door in time or yes yes none of this will ever work perfectly in a hundred percent of the cases and if it does you're not being ambitious enough that's kind of my philosophy as a game designer I think you can afford an occasional edge case failure what you can't afford is an edge case failure that like completely blocks the player from progress so that's like the one but that's that's an arrow is sort of subclass of edge cases like there there may be machines where you can't get to a key and maybe that renders a reward room inaccessible but that's okay I every now and then as long as it doesn't happen too much and maybe they'll have some other item that lets them surmount that anyway the one that you can't have is where like you just can't reach the downstairs from the upstairs and yeah you always do a bunch of checks to make sure that doesn't inadvertently happen if there's destructible terrain you need to make sure that the player doesn't rely on that destructor terrain to keep the level passable so I think that's like that's like the one category that you have to be careful about and in fact the seed the level generation seed method this is where you can you can enter in your random seed and it creates the same level every time it's used for seed contests online where everyone can play the same level I originally came up with that because I needed to debug all of these like obnoxious edge cases that come off like one in ten thousand times like a player would encounter it I would say send me the seed and then I can sort of step through the level generation to figure out what went wrong all right one more let's see you oh sorry question regarding your the actual platformer how do you handle so the platformer you said has limited terrain destructibility but it seems like terrain destructibility in a platformer would break the levels traverse ability a lot more easily how do you handle that like do you just make any necessary trained indestructible or is there some way to hit make sure that when a player destroys something there's still a way to move between the points yeah it's a it's a really good question so tureen destructibility generally only happens once you get explosives and that usually happens in the deeper parts of the game and there's going to be mobility items throughout that will kind of like make the constraint less strict I guess so if you get a double jump item somewhere then suddenly you have a lot more leeway to accidentally blow up a piece of the level teleporters throughout that means as long as you found a teleporter that's kind of below that point you can use it to get back up and if you screw up the level on your own like if you if you intentionally break it so you can't get back out then like so be it it's kind of my attitude you can use they're kind of extra lives that you can find and you can trigger an extra life to teleport back up as a safety valve yep cool thank you so much thank you know

Channel: Roguelike Celebration

Views: 31,941

Rating: 4.9716887 out of 5

Keywords:

Id: Uo9-IcHhq_w

Length: 32min 47sec (1967 seconds)

Published: Wed Oct 10 2018

Reddit Comments

[u/___ml]

Preview of unnamed (B)roguelike platformer starts 19 minutes in: https://youtu.be/Uo9-IcHhq_w?t=1146

I'm so curious to see how this progresses.

[u/zzap129]

wow, that's interesting. I read about how levels are generated in Brogue, but nice to hear him talking and showing it on screen. And that platformer looks very nice.

[u/graspee]

Damn, was hoping for a roguelike.

[u/Lagavulin]

Really appreciated seeing this! It opened my mind about how level-generation has been at the core of this game all along...when I'd assumed it was play-mechanics.

And as someone who's played Brogue for several years, this was like watching my favorite band play live!!!

Also...as my favorite bands go...the crowd was every bit as judgey.

[u/simesy]

That was pretty cool. Why did I think Brogue had two authors? I must have got the idea early on that Pender picked up where Brian left off.