Recursive Level Generation

One of the pitfalls of some random level generation algorithms I read about is that they rely on grids for marking open and closed spaces. Typically these algorithms will run at load time and generate a static level. For my current project, these limitations prevented me from using a grid based algorithm. Because of this I created the algorithm this post will cover. My goals for this design are that it would be capable of generating infinite amounts of level with low overhead and that the level could be changed on the fly. I will only use pseudo code so people can write their version in the language they are most comfortable in.

Node Design

A major component of this algorithm is the node data structure. A node is basically a unit of level. A node can be anything from a stretch of hallway to an intersection to a room. Each node knows not only what type of node it is, but also what nodes it connects to. For simplicity’s sake, we have nodes keep track of the direction the nodes it is connected to are in. This is where recursion comes in. If you wanted to know information about a node two nodes above the current one, you wouldn’t check some index two greater than the current, instead you would look at the node above the node above the current node.

Diagram of node structure and an example

Spawning Nodes

The first step when making this algorithm is to make it spawn a series of nodes. Starting very basic, the first set of nodes I created were a vertical hallway, horizontal hallway, and a four-way intersection. This set would allow the algorithm to spawn nodes in all four directions. I chose to keep vertical and horizontal hallways separate because I didn’t want to deal with rotating objects, but this could still work if you want to use one hallway model. After this we can define our functions that will handle spawning of nodes in each direction. Some pseudo code for basic node spawning in the up direction could look like this:

This is very oversimplified but it shows some general flow. Really you’ll want to track more things than just distance from the player. For example, you probably don’t want two intersections to connect without a stretch of hallway in between, so it may be a good idea to pass into the function how far it has been since the last intersection. Another thing to check for is making sure you don’t build a hallway that runs into another one. However, this isn’t as much of a concern for my application as you will see in the next section.

An example of how nodes spawn recursively. Distance remaining indicates how many nodes until the algorithm terminates.

Deleting Nodes

This section can be considered optional because not everyone will want to delete nodes that are outside of the range for generation. I’m using this for a game that is supposed to be scary so changing the scene behind the player, as they move and at select points, is a desired effect. The algorithm can be tuned to aid in preventing hallway overlap as mentioned previously.

The basic principles behind this step consist of finding the start of when nodes are out of range, then deleting all the nodes past the first out of range nodes. In this part you have to follow the paths set up previously, using recursion, to find the nodes too far from the player. Below is some example pseudo code of the recursive function. It is assumed that you start this loop knowing which node the player is standing on.

Adding Nodes as the Players Moves

Since the first step we did was define a set of spawning functions, this function should be very easy. You simply find the end of the node path then call the spawning functions starting at the end nodes. Very similar to the delete functions, these functions have to loop through the nodes while incrementing the distance from the player. One difference, though, is that the function needs to look for the condition where it reaches the end of the path and is still within the maximum spawning range instead of outside of the range. Once these nodes are found, just call the node spawn functions on the final nodes in the direction of the open adjacent nodes.

Advanced Applications

So far I have just talked using the most basic examples, but what if you want to make something more complicated than simple hallways? Up until this point it could be assumed that we were using hallways and intersections of the same, square size. This is a simple limitation to overcome. You could just add another variable to the node structure that would hold the width and height of that node. Then, you could simply factor in the size of the old node and new node when choosing where to spawn world pieces.

A building really isn’t complete with only hallways so another desired feature could be rooms. One way you could connect a room to a hallway would be to have a chunk of hallway that has a door on the side that only rooms can connect to. In this case, rooms are likely much larger than hallways so it would be important to add a minimum distance between doors similar to how intersections are spawned.

The list of further possibilities is endless: stairs, diagonals, dead ends, or turns. One could even modify this algorithm to not delete nodes out of range, and instead save them and do collision checks when spawning future halls. Nodes help with all these modifications through being aware of their neighbors and providing a foundation data structure to build off of.