The outline for a method to incorporate lock-and-key style progression in a generated game world.
Firstly, a short explanation of what I’m trying to do: There are plenty of examples of procedurally generated (or “randomly generated”) level content for games, but they often lack a certain type of structure. Generally they are used to produce very open worlds, where the player is free to explore as they like. I am trying to make something that will create worlds with gated progression. At its simplest this is Doom with a locked door that needs the red key which is off on a side path protected by monsters. Less obviously lock-and-key examples would be games like Zelda and Metroid, where you need to gain certain abilities or special items to reach areas.
Initially I thought to generate a simple world and then develop techniques for adding on progression gates over it. My first breakthrough came with giving up this idea. Instead I worked on generating the gating mechanisms at the same time as I generate the layout of the world.
The second important factor was to forget about the physical layout of the world. What actually mattered was the connections of possible-movement between game areas. So instead of working on a map of the world, I now work on a graph with the nodes as areas of the world and the edges as pathways between those areas that the player can move along.
Here’s a graph representing a very simple world:
The player starts in the node at the red arrow, and wants to get to the node with the chequered flag. But the pathway is blocked with a lock, so the player must first travel to the node with the key. Not at all complex, but now the world has some progression structure to it. This graph’s layout was generated by a general purpose “add a goal, and lock it away” function – before that function was called, the graph consisted just of the starting node. The neat thing is that the same function can be used to place the key, so creating:
When choosing where to add the node containing the key, the algorithm limits itself to picking amongst those nodes that it knows are accessible to a player who can access the lock. This means that there was no possibility for the cyan key to be locked behind the pink door, as the cyan lock is accessible to a player with no keys at all and so the cyan key must be too. The placing of the cyan lock now means that the pink lock/key no longer satisfy these requirements, but so long as they satisfied them when they were placed, and all locks placed afterwards satisfy them, it is guaranteed that with some work the player will be able to open the pink lock.
Here’s where my world-graph generator is at currently. The player starts at the red node, and wants to explore the world (there are actually multiple specific ‘goal’ nodes in the map, but I figure it has enough confusing colours already.) The player can freely move along the grey lines, but must have the correctly coloured key to travel along the coloured lines. The nodes that hold keys are coloured indicating what key they contain. Unlike the above examples the generator produces dummy nodes so that not every node is a key or goal, and may join dummy nodes together if they share the same key requirements.