Interview: How Does Level Generation Work In Brogue?

Roguelikes are my favourite genre of game and Brogue [official site] is one of my favourite roguelikes. It has the genre's carefully interlocking systems, which drive players towards important decisions and produce plentiful fun anecdotes, but it also presents them via an interface that's approachable and without the bloat that can make its peers intimidating or fatiguing to play.

I think a large part of Brogue's appeal lies in its level generation, which creates tight spaces full of interesting environmental detail, with traps to avoid, chasms to fall into, and a strange ASCII beauty. I spoke to the game's creator, Brian Walker, about what his design goals for those levels are, how you balance a game you can't predict, and the exact process by which the game creates those levels.

Note: A few months ago I put out a call for article ideas from the Supporter community, called the People's Games Journalist. I have been slow to move but this article represents the first of hopefully many spawned by your ideas. In particular, this article is a response to a request by reader amateurviking for more interviews that address in detail the creation of a single part of a game. Thanks for supporting the site, amateurviking!

RPS: What were your goals for the level generation in Brogue?

Brian Walker: Primarily, my goal was that the dungeon should feel concrete and exciting -- not just a flat substrate for monsters and items, but a living and atmospheric place to explore, filled with useful information and tactical significance. Indiana Jones is a good template: a lone adventurer in a hostile place, guided by torchlight, searching for clues, hunting for treasure, surviving by his wits, never knowing when some infernal machinery will activate and cause the floor to collapse, or flesh-eating rats to burst out of the walls, or water to flood the area. I want it to have a hand-designed quality that is revealed in stages as you discover that a hidden lever opens a twisty worm-filled passage to a key that unlocks a vault of hidden artifacts. Procedurally generated levels will probably never quite close the gap with hand-crafted levels designed by experts, but I want to push it as close to that standard as I can -- including for selfish reasons, so that I can explore fresh levels and be surprised by its secrets like any other player.

RPS: What's the step-by-step - the procedure, say - for the procedural generation of Brogue's levels? Please be specific.

Walker: The algorithm starts with one room, placed at random in an empty grid. Then, it draws another room on another grid, which it slides like a piece of cellophane over the level until the new room fits snugly against an existing room without touching or overlapping. When there’s a fit, it transfers the room from the cellophane to the master grid and punches out a door. It does that repeatedly until it can’t fit any more rooms.

That first room can sometimes be a “cavern” -- a large, winding, organic shape that fills a lot of the space of the level. Those are made by filling the level randomly with 55% floor and 45% wall, and then running five rounds of smoothing. In every round of smoothing, every floor cell with fewer than four adjacent floor cells becomes a wall, and every wall cell with six or more adjacent floor cells becomes a floor. This process forces the random noise to coalesce and contract into a meandering blob shape. The algorithm picks the biggest blob that is fully connected and calls that the first room.

There are a bunch of different techniques for drawing a room, chosen at random each time -- for example, two large rectangles overlaid on each other, a large donut shape, a circle or a “blob” produced like the cavern described above but with smaller dimensions. Sometimes, we’ll generate the room with a hallway sticking off of it at a random point, and require that the end of the hallway connect to an existing room.

At this point we have a simply connected network of differently shaped rooms. The problem is that there are no loops in the geometry; the entire map is a single tree, where each room after the first has exactly one “parent” room (that it grew off from) and any number of “child” rooms (that grew off from it). It turns out it’s not much fun to explore that kind of level, because it requires a lot of backtracking and it’s easy to get cornered by monsters. So, we start inspecting the walls of the level. If we can find a wall that has a passable cell on both sides of it, where the two cells are at least certain distance apart in terms of pathfinding, we punch out a door (or a secret door). Do that a bunch of times and you get a level that’s nicely connected.

Then we move onto lakes. Lakes are masses of a particular terrain type -- water, lava, chasm or brimstone -- that can span almost the entire level. They’re atmospheric, they enable long-distance attacks, and they impose structure on the level at a large scale to prevent it from feeling like a homogenous maze of twisty passages. We pull out the cellophane and draw a lake on it using the cellular automata method, and then we slide the cellophane around to random locations until we find a place that works -- where all of the passable parts of the level that aren’t covered by lake are still fully connected, so the player is never required to cross the lake. If twenty random tries fails to find a qualifying location, we draw a smaller lake and try again. If we can find a qualifying location, we drop the lake onto the map there and overwrite the terrain underneath it. Some lakes have wreaths -- shallow water surrounds deep water, and “chasm edge” terrain surrounds chasms -- and we draw that in at this stage.

Next up are the flavorful local features of terrain -- tufts of grass, outgrowths of crystal, mud pits, hidden traps, statues, torches and more. These are defined in a giant table of “autogenerators” that specifies the range of depths in which each feature can appear, how likely it is and how many copies to make. For each one, we pick a random location and spawn it. A lot of them spawn in patches. Those are generated by picking an initial location and letting it randomly expand outward from there, with the probability of further expansion lowering with each expansion -- like pouring some paint on an uneven floor and letting it flow outward into a puddle.

The next major step in level generation is what I call the machines. This is the most complicated part of the level generation by far. Machines are clusters of terrain features that relate to one another. Any time you see an altar, or an instance where interacting with terrain at one point causes terrain at a distant point to do something, you’re looking at a machine. There’s a hand-designed table of machines -- 71 of them at the moment -- that guides where and why each machine should spawn and what features it should create. Each machine feature further specifies whether it should only spawn near the doorway of the room, or far away from it, or in view of it, or never in a hallway, or only in the walls surrounding the machine, and so on.

There are three types of machines -- room machines that occupy the interior of an area with a single chokepoint, door machines that are spawned by room machines to guard the door, and area machines that can spawn anywhere and spread outward until they are the appropriate size. Some machines will bulldoze a portion of the level and run a new level generation algorithm with different parameters on that specific region; that is how you get goblin warrens as dense networks of cramped mud-lined rooms, and sentinel temples as crystalline palaces of circular and cross-shaped rooms. Sometimes a machine will generate an item such as a key and pass it to another machine to adopt the item; that is how you get locked doors with the key guarded by a trap elsewhere on the level. Sometimes the machine that holds the key is guarded by its own locked door, and the key for that door is somewhere else -- there’s no limit to how many layers of nesting are allowed, and the hope is that nested rooms will lend a kind of narrative consistency to the level through interlocking challenges. The game keeps track of which portions of the level belong to which machines, and certain types of terrain activations will trigger activations elsewhere in the machine; that is how lifting a key off of an altar can cause a torch on the other side of the room to ignite the grass in the room. The machine architecture is a hodge-podge of features intended to translate entries of a table into self-contained adventures with hooks to link them to other adventures.

After the machines are built, we place the staircases. The upstairs tries to get as close as possible to the location of the downstairs location from the floor above, and the downstairs picks a random qualifying location that’s a decent distance away from the upstairs. Stairs are used automatically when the player walks into them, and they’re recessed into the wall so that there’s no other reason to walk into them. That limits the number of locations in which they can spawn, but they’re generally able to connect pretty closely to the locations on adjacent levels.

Then we do some clean-up. If there’s a diagonal opening between two walls, we knock down one of the walls. If a door has fewer than two adjacent walls, we knock down the door. If a wall is surrounded by similar impassable terrain on both sides -- think of a wall running down the middle of a lava lake, or across a chasm -- we knock it down. This is also where bridges are built across chasms where it makes sense -- where both sides connect and shorten the pathing distance between the two endpoints significantly.

Items are next, beyond what was already placed by machines. There’s a cute trick to decide where to place items. Imagine a raffle, in which each empty cell of the map enters a certain number of tickets into the raffle. A cell starts with one ticket. For every door that the player has to pass to reach the cell, starting from the upstairs, the cell gets an extra ten tickets. For every secret door that the player has to pass to reach the cell, the cell gets an extra 3,000 tickets. If the cell is in a hallway or on unfriendly terrain, it loses all of its tickets. Before placing an item, we do a raffle draw -- so caches of treasure are more likely in well hidden areas, off the beaten path. When we place an item, we take away some of the tickets from the nearby areas to avoid placing all of the items in a single clump. (Food and strength potions are exceptions; they’re placed without a bias for hidden rooms, because they are carefully metered, and missing them can set the player back significantly.) There are also more items on the very early levels, to hasten the point at which the player can start cobbling together a build.

Last are monster hordes. They get placed randomly and uniformly -- but not in view of the upstairs, so the player isn’t ambushed the first time she sets foot on the level. Sometimes the monsters are drawn from a deeper level or spawned with a random mutation to keep the player on her toes.

And that finishes the level!

Many of the probabilities throughout this process vary by depth. Levels become more organic and cavern-like as you go deeper, you’ll start to see more lava and brimstone, secret doors become more common, grass and healing plants will become rarer and traps and crystal formations will become more frequent. It’s gradual, but if you manage to grab the Amulet of Yendor on the 26th level, the difference is noticeable during the rapid ascent.

RPS: What challenges did you face when trying to create those levels?

Walker: The biggest problem is that edge cases in level generation can be tough to find. When I add a new feature to the level generation algorithm, I’m usually thinking about addressing a particular configuration of terrain in a certain way. But the game will always think of fifty more configurations of terrain that I didn’t anticipate, most of which cause the feature to fail in some tragic way, and some of which will be extremely rare. And having a promising character get stuck because of a terrain generation glitch is a really bad experience. So I have to test and fix those features a lot.

That was actually the initial purpose of the “seed” feature: so I could reproduce rare level generation bugs when players experienced them. Random number generators just generate sequences of numbers that seem chaotic in normal uses. They generate the same sequence every time, unless you start the sequence from a different seed number. So when a game of Brogue starts, the RNG is seeded with a master seed -- by default, the time of day. Then, the first thing it does is pull forty random numbers from the RNG and write them down in a list. When you descend to a new depth, the game pulls the next entry from the list of numbers and uses it to seed the RNG before it generates the level. That means that the levels will be exactly the same every time you play from the same master seed. But what started as a feature designed to help with reproducing bugs is now the foundation of seed contests, where a bunch of players around the world start from the same seed and compare how they each fared in the identical dungeon.

Level generation is the heart and soul of a roguelike game. More than anything else, the feel of the environment and its continued novelty defines the experience. Designing it to produce exciting experiences is like building a magical machine that can tell you stories forever. I started writing Brogue by imagining the perfect roguelike dungeon environment that I always wanted to play in, and I built the prototype level generator first to create that experience. Once I had exciting environments that begged me to explore them, exploring them became the enduring motivation for building the rest of the game.

RPS: Given the procedurality of the levels, how do you make sure that the game is fair? Is there a post-level generation check that balances out things like potions/enemies/items to account for difficult or sparse terrain, etc.?

Walker: Absolutely! There are a ton of little tricks going on behind the scenes to make Brogue fair, even though character progression is driven by randomly generated items. Strength potions, life potions and scrolls of enchanting are “rubber-banded” in their generation so that you get approximately the same number in each game, and at approximately the same rate. At each new depth, their generation probability rises, and each time they are generated, their generation probability sinks. Adjusting the size of those deltas determines how tight the rubberbanding is. Food is generated even more strictly than that; there is an absolute lower bound on the amount of nutrition generated by a given depth, and it spawns whenever necessary to stay above that bound. There are also vaults that permit the player to pick any one of a number of strong items, and these vaults are very likely to appear at least once in the early dungeon -- so it’s very rare that the game doesn’t provide enough items for an experienced player to cobble together a build.

RPS: How do you guarantee enough variety without creating geometry that is 'wrong' or too random or occasionally filled with extremes? What makes the difference between a prescriptive set of rules that produces boring levels without the touch of a designer, vs. freedom in those rules for organic and exciting randomness?

Walker: Well, one approach that I specifically avoided is defining any sort of vault on a grid. There are no grids in the data files! Instead, machines have to adapt the terrain as they find it. Any area of the level that has a single chokepoint could be adapted into a room machine. This made the machine system a lot harder to build, it requires exhaustive testing, and very rarely one can find rooms that are somewhat malformed (though never in a way that prevents progress). But I think it’s worth the extra hassle, because procedurally generated vaults feel more organic and offer more potential for interesting surprises.

RPS: Are ASCII graphics limiting or freeing when it comes to procedural generation? Brogue is unusually beautiful for an ASCII game.

Walker: They are admittedly limiting in the sense that you get only one font glyph and two colors per square, which forces some tough design decisions when there is a lot of secondary information to convey. But they are freeing in the sense that they convey spatial location and identity of all of the dungeon’s contents with crystal clarity, and then leave the rest to a well seeded imagination. To that end, Brogue is overflowing with flavor text -- there’s flavor text for every monster and item, there’s an entire line of the UI that is permanently dedicated to flavor text, and it’s all constantly describing what you see, hear, smell, feel and taste as you wander through the dungeons. You can’t get away from it! A full color dynamic lighting engine also does some heavy lifting here to make the fires burn hot and to make the swaths of luminescent fungus shimmer. A challenging game tugs at you to optimize your strategy, but Brogue tries very hard to convince you to see its dungeon as a place rather than a system of equations.

RPS: Thanks for your time.

For more on what makes Brogue great, read our tale of drinking towards permadeath using the game's selection of mysterious potions.

This post was made possible by the RPS Supporter Program. Thanks to all who support the site!