Procedural Generation
1. Representing the world
One thing that hasn’t changed much since its initial prototype is how the world is abstractly represented in code. The level is stored in an n x m array of nodes, with each node containing information about what exists in that location (e.g. is this a room, hallway, doorway, what biome is this, etc…). Nodes also store a reference to their neighbors, creating a graph. Being able to look up nodes in both an array or explore nodes as a graph provides important flexibility in how the game interacts with the world since many corners of the code base use this core system.
2. The hallways must be interesting to walk through
The first prototype for hallway generation was simple: place the rooms randomly on a grid, then use A* to connect each doorway node to every other doorway node, prioritizing previously placed hallways. Then, randomly select several hallway nodes and expand them to create unique biomes.
While this prototype did achieve our goal procedural generation goals, it had one major issue revealed by early playtests: walking for minutes on end through a straight hallway isn’t fun. So it was back to the drawing board. The level generation system had to be snakey and interesting while also not being overly frustrating or confusing to navigate like a maze would be.
The first solution was to utilize node weights in the A* algorithm for more than just prioritizing previously generated hallways. What if every node had a random weight value? This was better, but the sheer randomness was obvious when playing. The hallways had to seem at least somewhat realistic and a straight maze was not an option I wanted to entertain. Stumped, I looked towards other games that used procedural generation for inspiration and eventually looked towards Minecraft. Minecraft utilizes perlin noise to create “natural” looking curves and features in its terrain generation. What if I generated the node weights for the hallways using perlin noise? I had just implemented a technique I would later learn is called Perlin Worm Tunneling.
3. Biomes
My next goal was to implement a more interesting biome system with the goal of having fewer, larger biomes. To do this, I simply recycled the idea of using perlin noise. Once the initial map and hallways are generated, I create a new perlin noise map for the nodes. Then, I select a node at random to be an anchor point for a random biome. I generate another set of values, each +/- n from the anchor point’s noise value. Then, manifest destiny style, I add the surrounding nodes to this anchor point’s biome grouping provided that the surrounding nodes have not been added to a different biome already and are within the +/- n range generated earlier. This process is repeated DFS style with all of the captured nodes until there are no more neighbors within the range. Then, a different random (unclaimed) node is chosen to be a new anchor and the process repeats. This continues until a predetermined percentage of all the nodes are captured, with the remaining nodes being classified as the default biome.
To add additional flair to the hallways, “straightaway” portions are detected and generate with unique designs.
Some biomes may have unique features that require their assets to be larger than the size of one node. In the medfloor biome, the ceiling is curved like a train tunnel. For tight angles, additional assets beyond the bounds of a single node are needed. All walls are generated with these additional assets, and those which exist outside of a hallway node are deleted at runtime to prevent clipping issues.
4. Rooms
At runtime, several core rooms are selected to be placed into the world randomly, then several “shortcut” and “loot” rooms are randomly selected and placed around the world. Most rooms in the game feature at least some degree of procedural generation. Take the medfloor for example. This room has the player duck into rooms in order to dodge a wandering radiation monster. To make this interesting throughout multiple playthroughs, the layout of the room changes.
The core layout of the room consists of an L shape. On several sides of the L shape, one of 4 different layouts can generate. Within these layouts, random room designs generate. Notice the long L hallway is the same in all of the below pictures, but the surrounding designs change.
4. Navigation
Later playtests leading up to the launch of the game revealed another issue: being lost in the hallways is frustrating. The player needed some sort of indication if they were getting closer to their target room. This prompted the development of direction panels placed randomly throughout the world. When activated, an arrow illuminates on the panel pointing towards the correct direction, and a line temporarily appears on the floor to aid with navigation.
There is more to displaying the correct arrow on the panel than it may seem. Direction panels have a chance of generating on any of the existing walls of a hallway node (north, east, south, west). First, the node the panel exists in is mathematically calculated, then the node object is retrieved for use based off its coordinates. To find the correct direction, the A* system used in world generation is recycled to pathfind from the panel’s node to one of the destination room’s doorways. This path is then sent to the client to display the on-floor line. On the server the direction of the path is calculated by finding both the unit vector between the source node’s midpoint and the first node in the path’s midpoint (for direction), as well as the unit vector between the source node’s midpoint and the direction panel (the arrow will “face” a different direction depending on what wall it is on). Using these two vectors, the correct facing arrow can be selected and displayed as needed.
Back