Lock and Key Puzzle Generation
This week, almost a year after its inception, I pushed some updates that that make Metazelda more like it should be.
The changes include:
- A vastly simplified, more flexible algorithm;
- The ability to generate switch-based puzzles (ones that require you to flip a switch between on and off states to access certain rooms);
- Javadoc on all the important classes.
The following algorithm for generating dungeons is implemented in the net.bytten.metazelda.generators.DungeonGenerator class’s generate() method.
This algorithm generates lock-and-key puzzles that are guaranteed to be solvable by construction.
Dungeons are generated over several phases:
- Create the entrance room
- Create a tree of linked rooms (including locked doors)
- Place the boss and goal rooms
- Place the switch and switch-locks
- Make the tree into a graph
- Compute the intensity (difficulty) of rooms
- Place keys within the dungeon
First of all, some definitions are needed so that you will understand what I mean by ‘dungeon,’ ‘edge,’ ‘symbol,’ and so on.
I use the word ‘dungeon’ interchangeably with ‘puzzle,’ but there’s no reason this algorithm couldn’t be used for non-dungeon lock-and-key puzzles.
Let’s forget for now that the keys and locks are items and objects in the game and consider an abstraction: a key is a boolean variable – you either have it or you don’t – and a lock is a test of this variable. We’ll give each of these boolean variables its own letter, i.e. A, B, C.
Each boolean variable is initially false (the player starts with no keys), but goes true when the player collects the key. For the sake of simplicity, we will say these variables never go false again: our puzzles effectively have colored keys (such as in Doom) that can be reused rather than the small keys in Zelda that can only be used once.
In Metazelda, we keep track of ‘Symbols’ to figure out which boolean variables have to be, or might be true.
Rooms containing Symbols are said to give the player that Symbol (they set the boolean variable for that Symbol to true). Locks are also labelled with Symbols, and can only be unlocked if the player has that Symbol (if the boolean variable is true).
Lock-and-key puzzles can be represented by graphs. The nodes of the graph are the rooms, and the edges (aka links) are the doorways between the rooms.
An edge is either conditional or unconditional. A conditional edge is labelled with a Symbol, which means it’s locked. The player must have that symbol to be able to travel through that doorway. The player is always able to travel through unconditional edges.
This algorithm generates puzzles in such a way that to get the nth key, the player must first get all keys 1 to n-1. This is a useful simplification as it allows us to cheaply map the number of keys the player has collected to the rooms the player is able to access.
The set of rooms accessible with n keys but inaccessible with n-1 keys is known as key-level n. You can think of it as the nth level of the puzzle.
During generation, the algorithm keeps track of which rooms in the dungeon are part of which key-levels so that symbols (keys) can be placed in rooms to guarantee the puzzle’s solvability: for every key-level n, the nth key must appear in a key-level m, such that m < n.
The precondition of a room is the condition that must be true for the room to be accessible to the player. This is the set of keys that the player must have collected to be able to get into it (aka the key-level), and the state that the switch must be in.
Each room has an ‘intensity,’ a number between 0.0 and 1.0, which specifies its relative difficulty within the dungeon. Clients of the library can use this to decide which and how many enemies to place in the room. The algorithm itself uses this number to put keys in the most difficult rooms.
The metazelda package provides an API that allows you to apply several different kinds of constraints on dungeon generation by implementing net.bytten.metazelda.constraints.IDungeonConstraints.
The kinds of limitations you can impose on dungeons are:
- Spacial limitations: forcing the dungeon into a particular shape. See the SpaceConstraints class.
- Limit the number of rooms.
- Limit the number of keys.
- Specify whether the dungeon contains a switch puzzle.
- Limit the coordinates that the initial room can be placed at.
- Arbitrary post-generation checks: if the check fails, it will try generating another puzzle.
Some stages of the algorithm can fail, either due to the random nature of the algorithm, or due to the externally-imposed constraints.
When this happens a RetryException is thrown. The generator catches this and will attempt generation again (until after MAX_RETRIES (20) attempts, anyway).
Creating the entrance room
The first step in generating the dungeon is placing the entrance room, the starting point of the puzzle. This is recorded in the key-level room mapping at key-level 0 (since no keys are required to access it).
Creating the initial tree of rooms
The spanning tree of the eventual dungeon graph is generated by repeating the following steps until there are no spaces left for rooms according to the constraints placed on the generator. While this is going on, the algorithm tracks the current key-level, which is initially 0.
- Choose a random room that has already been placed with an edge bordering an empty space. This is the parent room.
- Randomly choose which adjacent empty space to extend into.
- Create the new child room in this empty space, and link it to the parent room.
- The parent property of the child room references the parent room, and the child list of the parent room is updated to include the child room.
- At regular intervals, the current key-level is incremented, and the edge to the parent room is made conditional based on the symbol for the new current key-level.
- The precondition for the child room is the current key-level.
- The child room is added to the key-level room mapping for the current key-level.
Placing the boss and goal rooms
This part of the algorithm decides which rooms out of the ones already placed will be the boss and the goal rooms.
- It searches through all the rooms for empty dead-end rooms (ones with no children), whose parent rooms are similarly empty and have only one child.
- It filters out those rooms that are linked to their parents by conditional edges.
- It randomly chooses one of these rooms and makes it the goal room.
- It makes the goal room’s parent the boss room.
- The goal room and the boss room are removed from their key-level, and added to a new one above the highest one already placed.
- The edge from the boss room to its parent is updated to be conditional on the new key-level.
Adding the switch puzzles
This works by:
- Generating the path from the goal room to the start room by following the parent relation on each room.
- Picking a random room in that path to act as the base of the switch puzzle. (Using the ‘solution’ path ensures that the switch puzzle has significance to solving the puzzle.)
- Randomly locking the base room’s links to its children with conditions that require the switch to be in a particular state. If an immediate child is already locked, then all of its children are locked with the same switch-state condition, and so on.
- Placing the switch object in any room that is not a descendant room of the base room, and is at the same or lower key-level.
Making the spanning tree into a graph
Until this phase, the dungeon graph is a spanning tree. The graphify phase randomly links up neighboring rooms so that the graph is not a simple tree.
Some notes on how it does this without trivializing the puzzle:
- The boss and goal rooms are not touched.
- Rooms can be linked by an unconditional edge if their preconditions are the same.
- Rooms whose preconditions are not the same can be linked by a conditional edge if their preconditions differ by a single symbol, and the condition on the edge is that symbol.
Computing the intensity of rooms
Intensity is initially applied with numbers outside of the usual 0.0-1.0 range by recursively visiting every node of the spanning tree of the dungeon.
Every room’s child rooms in the same key-level will have a higher intensity than it, and rooms in the next key-level start at a bit below the highest intensity of the key-level below it.
Afterwards, all intensities in the dungeon are scaled to between 0.0 and 1.0.
This gives the puzzle a jagged tension curve as found in Calvin Ashmore’s thesis on Key and Lock Puzzles in Procedural Gameplay.
Placing keys within the dungeon
Finally, placing the keys in the dungeon in such a way that the puzzle is solvable is the simplest part: the key for each key-level n > 0 is placed in the highest-intensity room in key-level n-1.
blog comments powered by Disqus