Backrooms Style Basements

I've put a lot of effort into creating extended basements for houses that stretch far underground in maze-like hallways and rooms. It's time to work on something similar for office buildings. There are currently two styles of office building basements: parking garages and underground office/storage areas. I added support for creating mazes of hallways for the office/storage areas that produces something similar to house extended basements and works pretty well.

I wanted to do something different with parking garages. Parking garages are already kind of scary in 3DWorld with their dim lighting, open spaces, and small creatures (rats, spiders, flies, and cockroaches). I was looking at some images of creepy and abandoned basements and came across liminal spaces. Many of these are from the backrooms concepts and games. While I've never played any of the actual backrooms games, this looks like something that should be fun and relatively easy to procedurally generate. It's really just another form of maze-like hallways, except with a mixture of larger rooms, irregular room shapes, pillars, and oddly placed objects. So I set about trying to create something similar.

This is a long and technical post with lots of text. I'll add some images to break up the wall of text, and try to add links to some of the discussed algorithms and approaches. Here's an image of the final product before I've even discussed what I did.

Example "Backrooms" area with concrete walls, floors, ceilings, and pillars.

Here I've made all the surfaces concrete, including walls, floors, ceilings, and pillars. This gives more of an empty, unfinished space than the typical carpet, stucco, and tile materials found inside above ground building rooms. Light colors vary randomly from white to yellow. Sorry if the lighting near the ceiling appears too dark to you. I haven't finished working on the indirect lighting for these rooms yet.

Room Layout

The first step was to take the existing house extended basements hallway generation and expand it to create an underground rectangular area as large as possible in both dimensions. Well, as large as possible within reason, bounded by a distance several times the length of the building and any terrain or other buildings that block it. If the extracted area was large enough, it was made into one big room. These additions were relatively uncommon but huge, up to about a thousand feet on a side with hundreds of overhead lights. So far, so good.

The second step was to divide this area up into sub-rooms and hallways by placing random walls. I came up with a few requirements for wall placement that I added to over time while working on this:

1. Walls can't block the entrance door (or other doors, or stairs - see below).
2. Two parallel walls must have enough space between them for both the player and building people to walk.
3. Two walls can't meet at right angles or corners with a gap too small for the player to fit through. The ends must be either moved further apart, or joined to fill the gap.
4. No single line of sight can extend for more than half the length of the room, to avoid making the "maze" too easy to traverse.
5. Multiple paths should connect in loops. In other words, it should not be a perfect maze. The goal is to make the area confusing to the player and ensure the trick of following the walls to the right or left won't reach the inner spaces.
6. All areas are reachable by the player and building AI people. There should be no large areas of disconnected space.
   

Requirements 1-3 were relatively easy to meet by incrementally adding blockers and either re-placing or moving candidate walls. My fix for requirement 4 was to generate the empty space by inverting the walls after initial placement was complete. These space boxes were then split and maximally merged in both X and Y in two separate passes. Any resulting space box that was longer than the limit of half the room size had an additional wall placed randomly that cut through it. This seemed to work well.

Requirement 5 was addressed simply by not using a true maze generation algorithm. For requirement 6, I inverted the walls and constructed the space boxes again. Next, I ran a graph connected components algorithm on the space boxes to find disconnected area. I then iterated over all walls and found ones that had a different sub-graph on each side. I cut a doorway into a random place in some of these walls to connect the areas (if possible). Once all areas were connected, the algorithm was done. This didn't connect 100% of areas; in some cases there were very small walled off spaces where no door could fit. This was acceptable, as it's unlikely the player would even realize these small spaces can't be reached.

Debug visualization showing walls in red and connected regions of space (sub-rooms) with unique colors. The doors between sub-rooms are visible. These rooms typically have large connected central areas.

The next step was to add random pillars, as seen in some of the liminal spaces and backrooms images. Once again, the inverted space boxes were found to be useful in determining the large regions of empty space where I could fit pillars. I extracted maximally merged rectangular areas of spaces, and added a 1D or 2D grid of pillars to these candidates with a 50% random probability. There was also a chance to join adjacent pillars with walls in a random dimension (X or Y) to fill some of the extra space. Since pillars were placed in empty space with some border, this guarantees they can't intersect doors or other walls, and can't block the path of the player or building AI.

This is an overhead view where I've disabled the terrain and grass drawing and forced walls and floors to always be drawn even when they're not visible. Keep in mind that the room is actually underground and wouldn't normally be visible like this. It should give you an idea of the general room layout.

Overhead view of a large underground network of connected rooms that runs under a road. The walls, pillars, and ceiling light fixtures are visible.

Those white lines are the edges of the ceiling light fixtures. Their top surfaces are normally occluded and not drawn. Lights aren't actually enabled in this situation because the player is outside the building, so everything has an unlit gray color.

Sub-Rooms

The result of the above wall insertion algorithm was a set of rectangles joined into connected areas, which I'll call "sub-rooms", themselves connected by doors. These aren't true rooms because of some limitations I have on room generation:

• Rooms must be rectangular (4 sides, 4 corners).
  
• Rooms are generated at building creation time.

Technically, some of the existing rooms aren't rectangular. There are hallways that have right angles in certain office building floorplans, though these are actually two rooms joined by invisible doorways that span the entire hallway width. There are also some rooms with curved walls created from pie-slices of round buildings, but they're really still rectangles clipped to the outer walls. And we have some complex building floorplans with oddly shaped rooms, but these are due to limitations of wall placement and not really intended.

Creating rooms as part of building generation rather than deferring this until the buildings become visible is somewhat historical. The interior walls are needed to compute correct night time windowing lighting and various other effects. I also used to place people and cars in all buildings at the same time, rather than populating buildings incrementally as they come into view of the player like I do now. There are performance reasons as well: Creating all interior geometry at once allows better use of multiple threads, and packs them all into a single vertex buffer for more efficient drawing. Note that I do have tile-based building creation for infinite cities, but that has some runtime lag when generating new tiles. I don't generally use this for fixed size cities such as my current island map.

Anyway, the problem with creating all of these backrooms sub-rooms at once is that there are a huge number of them, potentially much more than the room count of the main buildings. This would take too much upfront time and memory. I could rewrite the way the interior rooms and walls are generated to make them more incremental, but that seems like too big a change to jump into when I'm already in the middle of this basement backrooms implementation. So instead I'll have to add a sub-room system that works with things like object placement, collisions, and AI path finding. This way I only need to generate the backrooms basement area when it becomes visible to the player. This happens when the player enters the building, considering it's windowless and underground.

The same performance problem exists for the walls separating these sub-rooms. Adding them to the regular building wall vectors would take significant GPU memory to store all of the geometry, and would mean that I have to rebuild the wall data structures when the backrooms are generated. It would also slow down iteration over walls that's done as part of collision detection, occlusion culling, AI path finding, and animals updates. So instead I added the walls as room objects, recording their range in the objects list so that I can more easily find them later during queries. The interior walls dividing parking garages into rows are handled the same way.

There are two types of sub-rooms: Single rectangle, and multi-rectangle. Most of the time there will be a large multi-rectangle central region connecting to the entry door. The single rectangle sub-rooms are usually small rectangular areas sandwiched between sets of intersecting parallel + perpendicular walls. We can ignore any small sub-rooms that weren't connected to the room graph by a door. We know that the remaining rooms are at least wide enough for the player to walk inside because (a) requirement 2 above, and (b) there was enough space to place a door connecting the sub-room to the adjacent sub-room. These can be assigned a function just like other building rooms. I made rooms with a single door into bathrooms. Rooms with multiple doors are typically assigned as basement utility or storage rooms, unless there's no space to add objects.

Here is an example of a utility room adjacent to a bathroom. The mirror on the medicine cabinet reflects objects as usual.

Small sub-rooms are assigned as bathrooms if they have a single door; otherwise, they become utility or storage rooms.

Object Placement

Lights are initially placed in a 2D regular grid pattern on the ceiling. This is done after wall and door addition. Any light that intersects an object is moved randomly by various amounts in all four directions until a valid location is found. If no location is found after a maximum number of attempts, that light is omitted. This tends to produce a somewhat staggered/irregular grid with occasional missing lights.

Small single rectangle sub-rooms are easy to populate. First, I check to see if each one has at least one ceiling light, and place a light if needed. Those assigned as bathrooms have the usual toilet, sink, and medicine cabinet. (No showers or bathtubs in office basements!) Utility rooms are populated with objects such as furnaces, water heaters, and boxes. Storage rooms currently have only boxes and crates on the floor. I was able to extend the existing room placement code to take the sub-room bounds so that I could reuse it for these cases.

This leaves the irregular areas. I can't use most of the existing object placement code because it only works with rectangular rooms. I can reuse the code that randomly places boxes on storage room floors because it already has wall and door detection build into it. I also added code to place some random soccer balls, basketballs, wooden chairs, office chairs, and wall-mounted fire extinguishers. These objects are placed relatively sparsely, only a few per building basement. They add to the variety of these otherwise empty areas and serve as landmarks in the maze of walls, without getting too much in the way of navigation. We don't want so many of these objects marking the way that the backrooms become easy to escape.

Why place sports balls in office building basements, you ask? Well, they're useful for gameplay mechanics. Balls can be thrown to chase away or distract zombies in the likely case you get cornered in a dead end area. Adding balls made it easier to debug collisions without requiring me to first find a ball in some other building and bring it into the basement with me. And they can be moved around to mark the player's path - assuming zombies don't kick them out of the way.

... Not that marking the path is really a problem. Now that I think of it, the player can just paint on the walls and floor with spray paint, draw with markers, leave a trail of toilet paper, or even block off dead ends with duct tape. Maybe I've made it too easy for the player?

I've marked the way to the exit stairs with a trail of toilet paper, arrows drawn on the floor and walls with spray paint and markers, and duct tape across the dead end paths. Hopefully I won't get lost this time!

I also enabled the usual placement of electrical outlets, a light switch by the door, wall vents, and ceiling vents for the larger room. Since these objects are placed on true room walls (exterior building walls in this case) and ceilings, this works independent of the interior walls and sub-rooms.

Movable Office Chairs

One downside of adding chairs to these rooms is that they can block the path of both the player and building AI people. Walls are spaced to allow everyone to pass between them, but there may not be enough space if a chair is in the way. Small wooden chairs can generally be walked around or over by the player, so they're not too much of a problem. Rotating office chairs are wider. Sure, the player can always pick these up, but chairs will quickly fill up the player inventory space with low-value objects. It's not like you can easily get outside the building from within the basement to drop off your inventory items.

My fix was to make these office chairs pushable by the player. The player can already rotate chairs because the 3D model instances have a rotation field. It was easy to add an instance translation as well and make player collisions translate these chairs. Of course, I had to add collision detection for the pushed chairs to make sure they can't clip through walls and other objects. Fortunately, updating the model instance translation doesn't require rebuilding the vertex data for room geometry. This makes it a cheap update that can be done per frame, rather than the push impulse that can be used to move furniture a fixed distance once every so many frames. However, I still need to redo AI path finding every time an office chair moves. This is needed for the AI to avoid getting stuck against or walking through a chair that was moved into its pre-planned path.

This solution works for the player, but what about for the building AI people? I was initially going to allow them to move chairs as well. But then I realized that allowing the player to construct barricades from chairs that block hallways and door would be an interesting game mechanic. So I'm going to allow these chairs to block zombies for now.

The player can push office chairs like this all around the underground room, except through doorways into other rooms and up/down stairs.

AI Navigation

The original AI navigation system treated each floor of a building as a connected graph, with rooms as nodes and doors as edges. Stairs and elevators connected to the nodes as sources and sinks to allow movement between the graphs on each floor. Since the floorplans were mostly the same for each floor of a building, I was able to reuse the navigation graphs across repeat floors. I use an A* path finding (A-star) algorithm to find the shortest path through rooms and doorways. Path finding within a single room consists of choosing random points and trying to find unobstructed paths between these points to cross the room or reach a destination point within the room. This works for most rooms because they're relatively sparse with only a few objects such as beds and tables blocking the AI's movement. Most rooms are relatively open in their central areas.

This system doesn't work for backrooms style mazes with sub-rooms. The simple point-based path finding fails to find a path in almost all cases. I don't even have a nice room/door relationship that I can use to construct a graph in this case. I thought about implementing a proper navigation mesh solution, but that seems like too much work. I don't want to simply include a third party library for this, I want to write the code myself. This is a simple case with rectangular areas on a flat plane. It should be easy to implement, right?

The solution I came up with begins by creating a 2D uniform grid that covers the entire room. Grid-based navigation is much easier, even if the objects aren't actually aligned to a grid. The grid spacing is chosen to be sqrt(2) times the radius of an AI person, and the cell size is similar to the person's diameter. This spacing guarantees that diagonally adjacent spheres are tangent to each other and there are no gaps between adjacent spheres where colliders/blockers could fit. Any grid cells that don't overlap room objects such as walls are marked as passable, while the others are marked as blocked. This means that a person can fully fit within a grid cell (because it's the size of their diameter) and walk between any two adjacent passable grid cells without colliding with an object. I cheated slightly and forced the cells in the center of each door to be passable so that people can pass through the doorway, even if the cells are misaligned from the door center such that they clip through the door frame a bit.

Here's an example of the navigation grid for a small-ish room. Some rooms are several times this size.

Debug view of grid-based AI navigation nodes. All red spheres are locations where a person can stand without colliding with any room geometry. The AI can take any path through adjacent/touching spheres.

The path finding is now relatively simple. I used another (nested) A* path finding algorithm to find the shortest path from the closest grid cell to the starting point to the closest grid cell to the ending point. This path must follow a sequence of adjacent passable grid cells, either in X, Y, or diagonally. Once a path has been found, colinear points are removed to simplify straight segments. Then an iterative algorithm is run to remove unnecessary intermediate points that are not required for a valid path. This can create shortcuts that connect non-adjacent grid points as long as there are no obstacles in the way. It partially works around the rigid grid alignment. This path simplification removes most of the 45 degree grid artifacts from the path and also makes navigation more efficient by reducing the number of segments the AI must follow.

While this grid-based system works well in most cases, there are some situations where the current location or destination aren't reachable from a passable grid cell. This can happen in tight spaces such as small sub-rooms with objects placed along the walls. There could be a path that exists only when walking in a narrow area between two existing blocked grid cells. In this case, the starting and ending segments can default to using the original point-based path finding algorithm, which works well for short distances and tight spaces.

Ultimately, the path finding adds an extra hierarchy: The overall room functions like an entire building floor, and the sub-rooms function as standard building rooms. This abstraction helped me to divide the problem (and code) into multiple independent pieces that could be written and debugged in isolation.

I spent quite a bit of time debugging this path finding code. It was quite difficult to get right, and even more difficult to debug when something went wrong. And lots of things went wrong! I had people walking through walls, getting stuck and not moving, spinning in circles, etc. I had to add debug visualization of path points and edges in different colors, debug printouts, and runtime key bindings to toggle between different path finding and visualization modes.

Debug visualization for zombie and people AI path finding includes nodes (spheres) and the edges between them (lines). Green is for grid-based A* paths, while yellow is for point-based local paths. Red and orange are used for incomplete/failed paths and aren't present here.

Multiple Levels

We're almost done. The last thing I added was multi-level backrooms. Back when I was working on the room generation, object placement, and path finding, I was thinking this would be too difficult. Once I got everything else working I decided to give it a try. I already had code to split rooms into multiple floors, place stairs, cut holes in floors and ceilings for stairwells, and path find through stairs for AIs. The main difference is that most vertical rooms have the same floorplan (rooms, walls, and doors) on each floor. I didn't want that. I wanted each floor of this basement area to be unique, to make player navigation more difficult. The only thing more difficult than a maze is a multi-level maze. This turned out to not be very difficult to implement though. The AI path finding actually worked the first time!

Unfortunately, the framerate was unexpectedly bad. The problem wasn't related to the number of sub-rooms, walls, objects, etc. No, my system can handle a huge number of all of these efficiently. The problem was related to ceiling lights. In particular, there's a special case that does a complex occlusion query when a light is on a different floor from the player in a room with stairs. See, this is a single room, and it now has stairs. Every light on every floor other than the floor the player is currently on is "on a different floor from the player in a room with stairs." In my test case, this was 1208 total lights. 3DWorld was attempting to do an occlusion query for each of these lights, testing every single wall across every level of the backrooms.

This is important because we need to enable the lights on the floors above or below so that the opening in the floor or ceiling where the stairs are doesn't show a black hole. Light from the floors above and below must pass through the gaps created by the stairs openings. For example, the player could be in a dark room where the only light comes down the stairs from the floor above.

Example of light shining down the stairs from the floor above. I've turned off the lights on the lower floor to increase the contrast. This shows how important these lights are to the scene.

The first optimization was obvious: Separate the walls out per-floor and only test the walls on the floor the player is standing on. This was about a 4x speedup for the four story room I was using as a performance test case: 13.8ms => 3.6ms. Even with this optimization, it was still slower than I would have liked as this was more than a quarter of the frame time. The next optimization was to only run this logic if the stairs were visible to the player. This used view frustum culling and another occlusion query, but it only had to be called twice (once for stairs going up and again for stairs going down) rather than 1208 times. That reduced runtime from 3.6ms to 0.8ms, at least when the stairs weren't visible.

We're getting closer. Now it's only a performance problem when the stairs are visible. They key to solving this is realizing that there are only two cases where lights from floors above and below are visible to the player. The first is when the light itself is directly visible, meaning the path from the player/camera to the light passes through the bounding box of the stairs. This is simple and efficient test to perform. The second case is where the light itself isn't visible, but it illuminates a wall that's visible. The light has a finite and relatively small radius of influence. This means that we can use an approximate test of whether the stairs are within the light's radius and only enable the light if it is. The good news is that the vast majority of backrooms lights are neither visible through the stairs nor within a radius of the stairs. These two tests combined reduce the number of lights to draw in my test case from 1208 to only 177, a savings of nearly 7x! I went back later and added additional tests that rays from the camera passing through the four corners of the stairs cut in the floor/ceiling intersect the light bounding volume.

Ah, wait, there's one more case to handle. A ceiling light can cast its light rays through the hole cut by stairs that are behind the player such that the light illuminates a wall or floor that the player can see. Think of a shaft of light through an opening. So we have to track invisible stairs as well, and use them for culling lights from the floor above. The approach I used projects four rays from the light center to the corners of the stairs cut, similar to how I handled culling at the end of the paragraph above. Then we calculate the intersection points of those four rays with the lower floor that the player is standing on. The AABB (axis aligned bounding box) of the pair of end points unioned across each ray forms a volume that encloses the light that can pass through the cut. The light must be included if this volume is visible to the player. The check includes both view frustum culling and occlusion culling.

Flickering lights were also causing a performance problem because every flicker required recalculating indirect/ambient lighting for all objects in the entire room. I later realized that a single light had almost no effect on a large room like this, so I disabled that behavior.

At this point I feel that everything looks good and is working. I'll likely come back to this at some time  in the future.