"Labyrinth" DLL

About

Level design can be simplified by representing the layout of an in-game environment as a graph. This abstraction is what this DLL attempts to provide in order to generalize the procedural generation of maps in a game.

The main idea is to have a graph where the client app can choose vertices to generate (using coordinates), which the DLL runs as an asynchronous process. The client app can then select vertices to retrieve the data of when they are completed (this can be achieved with a callback function in the client app that accepts a VertexData parameter).

In the example below, the client app uses all vertices within 4 units from the center point (7, 7, 0), but generates 4 vertex groups to do so. Note that even though only a few vertices are used in group (1, 1, 0), the whole group is generated. Therefore, when the client app needs to use more vertices in this area, they will not need to generate them independently.

The goal is to do vertex generation when it’s least needed to avoid discreet loading zones, as every vertex the client wants to use should already be available by the time they need to be accessed.

Recent Development

Testing in Unreal Engine

The DLL functions can be used in UE5 to generate basic debug shapes for testing (the setup is more convoluted than it would be in a plain C++ project because UE doesn't use standard iterators).

Example:

Note that in this example, many more vertices are being "retrieved" than the ones seen here, but they are not generated so they don't appear. This is a design decision that may change, as the client app should expect their "retrieved" vertices to be generated automatically if they don't already exist.

Another Example:

You'll just have to trust me when I tell you this graph is connected. There are 2 8x8x8 vertex groups shown, connected by a limited number of "bridge" vertices (in this case, only 1), but this amount is controlled by parameters in the DLL.

Design

Maintaining a balance between a generalized, completely customizable map and an algorithm that handles a lot of the brunt work is an ongoing challenge as I decide what should and shouldn't be exposed to the client. This is one of the things I wanted to try and was why I chose to make this a multi-purpose DLL as opposed to a specified implementation in a single project.

"Neighbor" refers to any vertex that is physically close to another vertex. For simplicity, this DLL requires that all edges only connect vertices that neighbor each other. The directions that define where neighbors are is customizable using a uint32_t enum (for example, 4-directional up/down/left/right or 8-directional up/down/left/right w/ diagonals).

Algorithm Steps

First and foremost, the map needs to be connected. To ensure this (while still allowing for complex paths between nearby vertices), we group vertices within areas of a set size instead of generating them individually. With this setup, we can ensure the full graph is connected by connecting every vertex group to its neighbor groups, as long as we enforce connectedness during the generation of each individual group.

1. Vertex Selection

Vertex groups need to do a lot of randomization. It keeps them distinct from other groups but also means that the same resultant map can be generated given the same set of coordinates. Therefore, the seed of a group is set to the hash of some given coordinate vector.

First we select the center, which is simply one of the vertices in the middle of the group (this is open to change in the future).

Next are the perimeter or "bridge" vertices, which connect vertex groups to one another. This is a more complicated process.

Instead of using this group's coordinates as a seed, we add the coordinates of the neighboring group. This ensures that both groups independently arrive at the same values, so their bridge vertices will connect.

To make sure the group itself is connected, we start with a complete grid and randomly remove vertices, making sure that they are not reserved (center or bridges) and that they are not a cut-vertex for the current graph.

Checking for cut-vertices is both the most important and the most expensive part of the map generation process, as the state of every valid vertex must be known. For this reason, future improvements will likely be made in the VertexGroup::IsSubgroupConnected function.

IsSubgroupConnected is a recursive boolean function that propogates outward from a vertex using its valid neighbors until all vertices are accounted for or a dead end is reached. When we use it in the vertex removal code, we start from the center vertex, since we know it will never be removed. The result is a recursive function that tells us if removing a given set of vertices would disconnect the graph.

2. Edge Selection

Selecting adjacencies for each vertex in the group is significantly easier. First, we can randomly generate a tree that spans all valid vertices (the vertices selected in previous steps). We know this is possible because the group is connected.

From here, randomly adding n edges introduces exactly n cycles as well. This gives us control over a key aspect of the map's graph: its number of cycles, possibly as an explicit parameter exposed to the client app. This step is not shown here.

Finally, we add the proper adjacencies to the bridge vertices so that they are adjacent to the corresponding vertices in another vertex group. For this we iterate through the neighbor bitmask once again and bitwise-OR the vertex's adjacency bitmask with the proper neighbor index.

The recursive tree generation algorithm works by simply traversing a random path (using the neighbor model and only visiting vertices of degree 0) from the starting vertex until a dead end is reached. Then, the base case is triggered and we go backwards in the path until a new path can be made as a branch of the existing path. This continues until a tree is created which visits all vertices in the group.

You can see that a lot of variation between vertex groups comes from these steps, as shown in the demonstration below, which depicts 16 vertex groups, which are all 16x16x1 units each.

Full Code Samples