Procedural Dungeon Generation - Part I
This article is out of date. I’ve redesigned the algorithm for several reasons. There’s an updated post here, albeit with a different writing style.
I mentioned in my post, The Inception of Lenna’s Inception, that I wanted to combine Zelda’s game mechanics with roguelike randomization for my game Lenna’s Inception. The Binding of Isaac went some way towards this, but doesn’t contain the item-based puzzles that (to me, at least) characterize Zelda.
In this post, I’ll introduce an abstraction for Zelda-like item-based puzzles, and an initial algorithm for generating puzzles procedurally.
Dungeons in Link’s Awakening are broken down into discrete rooms of fixed size, laid out in a grid. Some rooms have walls separating them, and some of those walls have doors, which are possibly locked. In these rooms you can find, amongst other items that are unimportant for the sake of this article:
Keys that unlock a door (and leave the door unlocked, but can only be used once);
A single boss key (aka a big key) that unlocks the door to the boss;
Switches that lower and raise piston blocks elsewhere in the dungeon that block your way;
And equipment such as the Roc’s Feather that allows you to jump over pits that otherwise don’t let you pass.
The following image is an example of what a really minimalist dungeon in Link’s awakening might look like. (And I mean really minimal. If there was a level like this in a Zelda game, I’d be getting my money back.) More often there are multiple locked doors, and multiple keys, and a miniboss or two in there. For some real examples from real Link’s Awakening, see the Zelda Infinite website.
The player starts (obviously) at the start, and the goal is (obviously) to get to the goal. But: you can’t go to the goal without first beating the boss; you can’t get to the boss without jumping over the pit surrounding his door; you can’t jump the pit without getting the feather; you can’t get the feather without unlocking the door to it; and you can’t unlock the door without getting the key. You have to find the right sequence of rooms to go through to get to the goal.
These inter-room puzzles are the kind I want to generate procedurally. There are also intra-room puzzles, where you have to perform some specific action (e.g. killing all the enemies) within the room to get that room’s item, but they’re not the focus of this article.
All of the elements of these puzzles – the keys, switches and equipment – have one important thing in common: there’s originally some obstacle you can’t pass until you find a certain item that eliminates the obstacle. There’s an abstraction we can make here.
Enter the Legend of Metazelda.
Let’s forget for now that these items are keys, switches and equipment, and instead think about boolean variables: you either have a key or you don’t; the switch is either on or off; you either have the equipment or you don’t. We’ll give a letter to each of these boolean variables, e.g. K, S, E, etc. Each of these variables is false initially, but goes true when the player collects the key, hits the switch or picks up the equipment. For the sake of simplicity later on, we’re going to assume these variables never go false again: keys are not consumed by use with a locked door, and the switch does not need to be turned back off to solve a puzzle.
An extension to the algorithm would allow consumable keys and off-switch puzzles, but is not explored in this post. The extension may not even be necessary for a game to be entertaining: keys and doors can be made colored like in Doom; and the player might not notice that they never need to turn a switch off (especially if there are multiple sets of switches and pistons).
The next thing to abstract is the grid of rooms: it’s now a graph. Each node in the graph represents a room, and can contain the letter of a boolean variable to set true on entry. Nodes are connected via edges to other nodes. These edges are unidirectional, permitting travel in only one direction, but two edges in opposite directions between the same two nodes can be considered to be one bidirectional node as a useful shorthand. Each edge is optionally labelled by the letters of boolean variables that must all be true for the player to be able to travel along that edge.
Here’s how the example dungeon looks now:
In the Legend of Metazelda, the player starts dungeons at the node where the arrow points and by moving along edges to other nodes, collects letters that grant access along other edges to more nodes, eventually reaching the goal node (the double-lined circle in the diagram).
Warning: Computer Science (skippable)
It’s interesting to note that Metazelda dungeons are a special case of Extended Finite State Machines.
If you don’t know what a finite state machine is, google it. They’re used in lots of places, regular expressions for example. If you have a good link that explains them, put it in the comments, and I’ll include it here.
An extended finite state machine extends the model of a FSM with “if conditions” on the transition edges. In a Metazelda dungeon, the EFSM states are our nodes, the transitions are our edges, the input symbols are the movements of the player character, the “if conditions” are the boolean variables the edges are labelled with, and the update function implements “V := true” where V is the boolean variable name written in the node we move to.
The version of the algorithm in this article produces solvable dungeons by virtue of the fact that the boolean variables only ever transition to true. If you were to add variable transitions to false (e.g. consumed keys, off-switches), you would then need to check that the modified dungeon is still solvable at intermediate steps. Scientifically speaking, you would need to find out whether the goal is still a reachable state. Presburger Engines are used to solve reachability for the general case of EFSMs, but I suspect these boolean-variabled Metazelda dungeons are simple enough to do relatively easily with just a SAT solver (although I have yet to figure out exactly how).
Generating Metazelda dungeons
How can we generate these dungeons? Purely randomly would not work – what if it generated a dungeon with a locked door and the only key in the dungeon was behind that door? It would make the dungeon unwinnable. Players don’t like that. It’s really bad level design.
I spent a long time looking for algorithms for this that someone had already documented, but I couldn’t find any. There is a real dearth of concrete information about procedural generation on the web, so in the end I rolled my own algorithm.
The first things to define are the data-structures this algorithm uses. Although the abstract Metazelda dungeons are graphs, we hope to eventually be able to lower them into two-dimensional grids of rooms (or three dimensions, if adding multiple floors). For this reason, we implement the dungeon graph as a two-dimensional array, each slot in the array representing a node (room). Each room has an array of four values that define whether there is an open unidirectional edge in each of the four directions. This is still a graph, it’s just a specialized one.
(N,E,S,W) = (0,1,2,3) NUM_DIRS = 4 class Edge: condition: Letter or None class Room: x,y: Int item: Letter or None edges: Edge or None # index with N,E,S,W type Dungeon: # dynamically-extendable 2D array of (Room or None) # indexable by the (x,y) coordinates of a room # implementation left as an exercise for the reader
Following are some utility functions that go with these structures, and are used in the algorithm:
def Room.random_free_edge(): d = random.randint(0,NUM_DIRS) tries = 0 while (this.edges[d] is not None) and (tries < NUM_DIRS): d = (d+1)%NUM_DIRS tries += 1 if this.edges[d] is None: return d return None def adjacent_coords((x,y),d): # Return the coordinates of the next room in the given direction if d == N: return (x,y-1) if d == E: return (x+1,y) if d == S: return (x,y+1) if d == W: return (x-1,y) def opposite_dir(d): if d == N: return S if d == E: return W if d == S: return N if d == W: return E def Dungeon.adjacent_space_dir(room): # return direction of travel from room to a random adjacent space # or None if there are none d = random.randint(0,NUM_DIRS) tries = 0 (x,y) = adjacent_coords((room.x,room.y),d) while (this[x][y] is not None) and (tries < NUM_DIRS): d = (d+1)%NUM_DIRS tries += 1 (x,y) = adjacent_coords((room.x,room.y),d) if this[x][y] is None: return d return None
Then adding a room to the dungeon containing a given item can be implemented recursively.
def Dungeon.add_room(item: Letter or None, enable_backedge: bool): # Add a new room to the dungeon containing given item. Conditions to enter # the room are randomly generated, and if requiring a new item in the dungeon, # will cause other rooms to be added, too. # # "enable_backedge" controls whether unidirectional edges between new rooms # and pre-existing rooms may be added. # condition to enter the room cond = None # make a random choice: either do the "_either:" or one of the "_or:" blocks # -- see note (0) randomly_either: # choose new boolean variable that must be true to enter this room cond = this.new_unused_letter() # add an item for this letter to the dungeon so the room is reachable this.add_room(cond, enable_backedge) randomly_or: # choose a boolean variable with a letter already obtainable in the dungeon cond = this.random_preexisting_letter() randomly_or: # leave cond None, meaning entry always available pass # choose where to place the new room (loc,d) = None randomly_either: # add padding rooms (and potentially more conditions along the way), but # disable backedge generation -- see note (3) loc = this.add_room(None, False) d = this.adjacent_space_dir(loc) # add_room can create a room with no adjacent spaces, so d might still be # None -- see note (1) randomly_or: pass if loc is None or d is None: # choose an existing room with a free edge (loc,d) = this.random_external_room() # -- see note (2) # create new room room = new Room (room.x, room.y) = adjacent_coords((loc.x,loc.y), d) room.item = item # link new room to loc edge = new Edge edge.condition = cond room.edges[opposite_dir(d)] = edge loc.edges[d] = edge if enable_backedge: randomly_either: # add a unidirectional edge into an adjacent room. # the conditions to enter our room necessarily imply the conditions to # enter the adjacent one -- see note (3) bd = room.random_free_edge() (bx,by) = adjacent_coords((room.x,room.y), bd) if this[bx][by] is not None: # player can move from our room into the adjacent one, but not the # other way room.edges[bd] = new Edge randomly_or: pass return room
To use the algorithm, initialize the dungeon with a single room (the start room), and use Dungeon.add_room(‘X’, True) to fill it (where X is the goal).
Lots of randomness is used in this algorithm. Probably a lot of the work of implementing it will be tweaking the probabilities to make it design dungeons well. At the very least, you should make the probabilities dependent on the number of rooms already in the dungeon, otherwise the sizes of the generated dungeons are unbounded.
This algorithm can generate dead-ends with no useful items in them. It doesn’t have to be a total waste of time to the player though – money, health, maps and compasses can be easily added to these dead ends in a post-processing step. These dead ends are easy to search for because they have only one out-going edge attached to them, and no item.
When connecting the room to a pre-existing room, it randomly chooses an external room:
(loc,d) = this.random_external_room()
This means it picks a room that has a side beyond which no other rooms exist (it also returns that side as a direction). This prevents the algorithm from getting stuck inside a small bounded space delineated by a perimeter of pre-existing rooms. Implementation is left as an exercise to the reader.
A smarter algorithm might pass into Dungeon.add_room how much space is needed by dependent rooms, and then when connecting to pre-existing rooms, chooses a room where there is enough space.
I added “backedge” generation to make the dungeons less tree-like and more graph-like. It adds a unidirectional edge between the new room and an adjacent pre-existing one, and is the only way cycles are generated in the dungeon graph with this algorithm.
Backedges are generated only when doing so cannot create a short-cut past a pre-existing obstacle. For this reason, backedge generation must be disabled when adding the padding rooms between existing rooms and the new room. This does however mean that the only rooms with backedges are the ones that contain important items – keys, equipment.
As a modification, you could force the padding rooms to be generated with edges such that cond must be true on a subset of them. Then backedges can be generated for that subset.
Update: this part of the algorithm can cause the generation of trapped rooms that the player cannot escape. Part 1.5 has a fixed implementation the algorithm in Java that fixes this.
Adding Bosses, Boss Keys, Equipment and Minibosses
In Zelda, some of the puzzle elements are guaranteed to occur in each dungeon, and usually occur in a certain order:
The player first defeats the miniboss.
Defeating the miniboss grants access to the rest of the dungeon where the equipment and the boss key can be found.
The boss is in the room immediately before the goal.
This can be implemented by writing specialized versions of add_room for the goal, boss, boss key, and equipment:
Placing the goal first places the boss, and then adds a bidirectional edge directly to it.
When adding the boss room, it always has the boss key as a condition. This triggers placement of the boss key.
When adding the boss key room, it always has the equipment as a condition. This triggers placement of the equipment.
Placing the equipment first places the miniboss, and then adds the equipment room with a bidirectional edge directly to it.
Of course, this algorithm hasn’t dealt with the concrete layout of rooms in the dungeon. It’s still quite an abstract representation.
“Lowering” converts this abstract representation of nodes and edges into something concrete, with specific room layouts, doors, and intra-room puzzles. Some of the characteristics of the rooms are already known (important items, open walls/doors), so this information could be used to select a specific room layout from a library of pre-designed rooms. Or another level of procedural generation could design the rooms.
I’ve published this algorithm for multiple reasons. The first is that I hope I can get feedback about it from readers. If anyone has implemented something like this before and has some helpful advice, it could speed along development of Lenna’s Inception.
Secondly, from the point of view of a player, I want to do what I can to help improve games with roguelike procedural generation. If you use this algorithm, let me know so I can play your game!
Part II will go up when (if) I work out how to extend this algorithm to generate dungeons that contain consumable keys, and puzzles requiring turning switches off. I suspect this will require the use of a SAT solver to check intermediate steps, so it will get a whole lot more mathsy.
I may also post a (short) Part 1.5 when I have a demo implementation of this algorithm.
Update: Part 1.5 is up!
2012/01/21 » tom
Really interesting read, thanks! I have to admit that I zoned out a little towards the end, but only because I was busy thinking about how a similar approach could be applied to my own project! I’ve always found procedural generation fascinating, but you’re right in that there’s not a huge amount of information on procedural generation about.
If you haven’t already read it, there was a very insightful article on gamasutra recently about level design in the original Zelda. It’d be interesting if some of the points raised in that article could be build into a generation algorithm to try have it produce interesting, thoughtfully designed levels.
blog comments powered by Disqus