Procedural Clocks, Digital and Analog

I want to make 3DWorld's procedural buildings more dynamic and less static. Some of the rooms, in particular in the basements, are often devoid of movement. People and zombies are less common here. One idea I had was to put clocks on the walls, starting with basement swimming pool rooms. I couldn't decide if I wanted to add digital or analog clocks, so I implemented both. These clocks will display the current system time on the user's computer to the nearest second. Today's post will be relatively short.

The best place to put a clock is probably on the center of the wall at one of the long ends of the room. The issue is that the center of the wall often has a door. My fix was to increase the ceiling height in some of these larger pool rooms to make space for placing a clock above the door. The ceilings can be raised any amount up to a floor's height, but limited by the terrain and other buildings above that room. You'll find these taller pool rooms are more common with office buildings because they tend to have deeper basements with more overhead space.

Analog clocks were easier to create. I used a standard clock face texture for the numbers, drawn onto the end of a horizontal cylinder that was placed on the wall. The clock has an hour hand, a minute hand, and a second hand. All three are created from a five vertex polygon with a point at the end. They rotate about the center of the clock in realtime, where each hand moves once a second on the frame where the second transitions to the next one. I decided I preferred the one second increments of the second hand rather than continuous motion. It was more efficient as well, since I only had to update the vertex data once a second rather than once a frame (which is often > 60 per second).

Analog clock above the door on a pool room wall.

Should I add a ticking sound, or would that be too annoying for the player? Just kidding, of course I added a ticking sound. It's not present in the video below, but it's now active when the player is near a clock.

Digital clocks were more difficult. I wanted to make them with the old style of red LED seven segment displays. Should I also add green clocks? I'm not sure. This brought back memories of my time working with these displays in my electronics projects when I was younger. I had to look up one of those projects online to find the tables to map digits from 0-9 to display segments. The code ended up being long enough that I put it in its own source code file. The first table I found online was wrong and produced an incorrect "9" digit. Sigh.

I added a total of six digits (a pair for hours, minutes, and seconds) and two colons. Digital clocks typically don't display seconds, but I wanted the update rate to be more frequent than once a minute.

Digital clock on a pool room wall showing time in HH:MM:SS.

It would be a shame if the player never entered a basement swimming pool room to see my clock artwork. So I added them to office building first floor lobbies as well, on the back walls of the stairs. Now they're difficult to miss. It will also be easier for me to keep track of time and avoid staying up too late working on this project!

Digital clock on the back of the stairs in an office building lobby.

Here's a video of the clocks moving/updating. I don't have the ticking sound enabled here since I went back and added it after writing 90% of this post.

That was pretty fun. I need to find more dynamic objects that I can add. Maybe I should make rooftop signs using seven segment displays. The only problem is that you can't create all of the letters with the limited number of segments. For example, you can't create a 'K', 'M', 'R', or 'W' with only 7 segments. I think it would require at least 15 segments for all numbers, uppercase, and lowercase letters. That would be a much larger table and significantly more effort.

Procedural Buildings: Office Security Rooms

3DWorld's procedural office buildings already have some special purpose rooms on the ground floor. There are storage rooms with shelves along the walls, utility rooms with furnaces, water heaters and sinks, and server rooms with computer servers. The next room I wanted to add was a security room. And what does that room contain? A desk and walls covered with security monitors, which use the same 3D model as TVs and computer monitors.

But what do we display on the monitors? The most appropriate content is security camera video feeds, which means I also need to add security cameras to the building as well. The best places to add these are the two ends of primary hallways on each floor. This placement covers the building entrances, stairs, elevators, and secondary hallways to the offices and other rooms. These cameras allow the player to watch people and zombies walk around the building in realtime.

I started by adding monitors across all four walls of the room, wherever there was space. They're currently stacked two high. Right now they have the feet/stand attached, which makes them look a bit odd, but I'll fix that later. I also put a breaker box on the wall next to do the door so that the player can turn the power off to blocks of rooms and affect the state of lights, cameras, and monitors. This made debugging the update logic easier as the player had direct control over everything.

After placing the monitors and setting up the screen drawing code, the first test used the same camera for every monitor. Which camera? The one in the player's head that the world is normally drawn from. I was expecting each monitor to show a copy of the player's view, but instead I got the result below. The problem is that I'm reusing the mirror reflection code to draw the monitor images, and this code enables the player model. In addition, the front vs. back face culling was set up incorrectly, so the view on the monitors is the inside of the player model's head. Interesting, but not what I expected.

This is what you see when the "camera" is inside the player model's head and the front vs. back face culling is wrong. There are 36 monitors along the walls of this security room.

With that fixed, I get the expected recursive view through the player's eyes. Each monitor shows the set of monitors inside it, for a picture inside a picture inside a picture... Except that the top row is backwards because I've inverted the camera direction for cameras at the other end of each hallway. Anyway, so far, so good. It appears to be working. This image is only for debugging purposes.

Recursive camera view where the camera is in the player's head, looking forward in the bottom row and backwards in the top row.

 

At this point I have the cameras all set up correctly with the location and view direction of the 3D camera object. Each camera is on the ceiling tilted downward at a 10 degree angle. This gives a relatively good view of the end of the main hallway and, in most cases, the connector hallways, stairs, and elevators. This is typically what is monitored in office buildings as it includes the main public spaces.

Ground floor hallways have the lobby reception desks, but upper floor hallways all look the same. The elevator and stairs floor numbers are only sometimes visible. I needed a way for the player to tell which monitors showed which floors. My solution was to add a system for on-screen text drawn over the main image texture and shifted slightly closer to the camera to be in front of the picture. This uses the same text drawing system I have for signs and book titles. The text string consists of the room name, floor number, and direction ("E", "W", "N", and "S"). Currently all camera rooms are named "Hall" in office buildings. Technically, the ground floor is the lobby.

Camera images are updated by rendering the building interior to a texture each update frame. This is too expensive to perform each frame for dozens of visible monitors. My solution is to update only one image per frame. The camera chosen for update in a given frame is the one with the oldest (least recently updated) image across all monitors visible to the player. This way cameras will be updated round-robin. For example, if there are 10 monitors visible, each one will be updated once every 10 frames. This is good enough to get interactive framerates on the monitors. When the player gets close to a monitor to view the image in higher resolution, there will be fewer monitors visible in their periphery, which will make the visible monitor(s) update more frequently. I also reduced camera resolution from the default screen resolution (I use 1920x1024) to 1024x768 to improve framerate. Monitor images emit light and can be seen in the dark.

This system allows the player to watch people, zombies, and animals move in the hallways in realtime. I expect this to help the player plan to avoid zombies in gameplay mode by determining which floors are safe vs. dangerous. This is important when the player plans to exit the elevator on a particular floor and may become trapped by a nearby zombie. However, the side hallways and room interiors aren't visible to the cameras, so there's always some risk.

Security monitors showing a person walking in the second floor west side hallway (top center). The east side hallway is shown below, and hallways on other floors are to the sides.

The player has some additional interactions. Monitors can be turned on and off by clicking on them with the action/interact key. Cameras and monitors can both be stolen by the player. Any monitor showing a camera that's powered off or stolen displays an animated static texture created from random white noise. Here's an example where I've removed the two cameras at the ends of the ground floor hallway.

Security monitors show static when their cameras have been stolen by the player or powered off with a circuit breaker.

These monitors look a bit wrong with the metal legs at the bottom. Stands are generally removed for monitors that are mounted to walls. Fortunately, the stand and logo are drawn with a separate material. I can reuse the material selection system that I implemented for use with rotating fan and helicopter blades to disable drawing of certain materials for hanging monitors. Now it looks like this.

Security monitors with the stand at the bottom removed. The logo is also gone because it's part of the same material.

Note that these rooms are darker than they should be because the indirect lighting computation was broken at some point, likely when I was working on swimming pools for the previous post. I eventually did realize this and fixed it (after hours of effort). But I didn't want to go back and recreate these screenshots, especially the ones resulting from bugs that had been fixed by now.

Cameras are created from black and gray untextured metal materials. They had low contrast against the mostly grayscale colors used for office building walls and ceilings. This was especially true at the ends of long hallways with the broken indirect lighting, where the ceiling lights didn't reach this far. I added a red light to the front of each camera that flashes on and off once per second. The light is emissive when on and can always be seen, even in complete darkness. This way the player can notice the flashing lights and know they're being watched. I was able to avoid sending new vertex data to the GPU each frame by toggling the material emissive field on and off for all cameras in the building every half second.

A security camera hanging from the ceiling by the front entrance door with a blinking red light added. A camera is placed at each end of the primary hallway on each floor. This building has 38 cameras.

Here's a video I recorded where I enter the security room, view people walking on the monitors, and steal some cameras. This was created before I removed the monitor stands and fixed the indirect lighting.

There was one other addition I made. After experimenting with this a bit, I wanted an easy way to test the system that handled offline/unpowered cameras and monitors. It's inconvenient when the player has to walk long distances around the building to remove the cameras. So I added a breaker box on the wall by the door to allow the player easy access to controls that disabled cameras. However, this turned out to not be as useful as I had imagined because all of the primary hallways across floors happened to be connected to the same circuit breaker. This meant I could turn all of the cameras off, but I couldn't control them individually.

Another problem was that the original circuit breaker box generator only added labels for the elevator and parking garage breakers. If I happened to toggle the breaker associated with the security room, this would turn every monitor off. I would then need to manually turn each one back on after flipping the breaker back. This made testing more frustrating. I had to label the security room breaker. But if I was going to write the code to figure this out and generate a custom label, I may as well label every breaker with the room(s) it controls. But what about breakers that affect multiple rooms? My solution was to assign a priority to each room type, and label the breaker with the highest priority room type it controls. For example, the room type "office" is too generic to be shown on every breaker. Obviously, the "security" room should be assigned the highest priority based on the original problem I'm trying to solve.

Breaker panel with all breakers labeled with the rooms/functions they control. Sorry about the shadow on the right side labels!

That's all for this update. I may go back and add cameras to other rooms, or possibly houses. I'll have to think about this later.

Pool Rooms and Pool Rooms

When I say "pool room," do I mean a room with a pool table, or a room with a swimming pool? The answer is, both! I've added rooms with both pool tables and swimming pools to my scenes. I started with pool tables, and then later added swimming pools because I kept thinking about them every time I looked at the code. I'll describe how I added each type of room to 3DWorld's procedural buildings below.

Pool Tables

Some of the houses I've generated have quite a few unassigned rooms in the basements and extended basements. These are windowless rooms that don't work as bedrooms and some of the other room types. They're currently assigned functions such as storage rooms, laundry rooms, and card rooms. I've decided that a pool table would be a good fit for some of these rooms, at most one per house. I added code that picked the largest room and assigned it as a pool [table] room if it was large enough to fit the table with enough space around it for people to play pool.

I briefly considered trying to create an entire pool table with code, but I wasn't convinced it would look very good. Cubes can only go so far. Fortunately, there were plenty of free pool table 3D models available online. I chose one with the nice green felt surface and no other objects since I wanted to add the balls, etc. myself. The goal was to have a single table 3D model with a unique placement of pool balls and pool cues. I found a texture atlas image with all of the numbered ball patterns that I could apply to randomly placed spheres with random rotations/orientations. I added some couches to the room and a rug on the floor to get something like this screenshot. So far, so good.

Pool table with individual pool balls that the player can take. I have indirect lighting enabled because it looks much better this way. See the green reflecting on the ceiling?

Next, it was time to generate some pool cues. These are simple shapes made from truncated cones that I can already draw. I spent some time trying to find a pool cue texture online, but eventually gave up and drew my own in the Gimp image editor, using an image as a reference. Now that I had pool cues, I had to figure out where to place them. I decided to put a wooden cue holder on the wall with four slots, then place the cues randomly either in the holder, on top of the table, or on the floor leaning against the table. It took some extra effort to move the cues around as the player pushed or pulled the table. (Pool tables are too heavy for the player to pick up.)

Pool table with pool balls and pool cues in the holder, on the table, and leaning against the table. The balls are in different positions compared to the previous screenshot.

That looks pretty good. Each pool ball and pool cue is a separate object that the player can take and put in their inventory. I'm considering allowing the player to actually hit the balls around with the cues. I have most of the ball physics in place already, so it may not be that difficult. The main problem is that the pool table 3D model has complex geometry for the pockets that makes collision detection and physics difficult. It's not clear how to put the balls into the pockets. I'm leaving this as future work for now and moving on to swimming pools.

Indoor Swimming Pools

My original plan was to add only outdoor pools to residential yards. This mostly worked, but the system I have in place for exterior areas doesn't allow for as much detail as interiors. It also doesn't handle objects that extend under the terrain mesh such as in-ground pools. Plus, I really liked how the underground backrooms water from a few blog posts ago turned out. I did add water to bathtubs, but that's not quite the same because the player can't even enter them.

It's not easy to add water to above ground rooms due to the way they need to be cut into the terrain on the ground floor, and it doesn't make sense to have swimming pools on upper floors. That leaves basements and extended basements. House basements generally don't have rooms that are large enough to fit a pool. That leaves extended basements. This is convenient because I can reuse much of the extended basements water code from flooded backrooms to handle the water in indoor swimming pools. I've enabled underground pools for both houses and smaller office buildings that have no parking garages or backrooms. This allows me to separate the water logic between flooded backrooms and swimming pools because no buildings will have both.

The first step is similar to selecting pool table rooms, where the largest room is found and considered for a swimming pool. The main entrance door is determined, and the length of the room opposite the door is extended as far as possible up to a maximum distance or until an obstacle is reached. Obstacles include other underground rooms of this building, rooms of nearby buildings, and low points on the terrain. The room is also expanded by a smaller amount in width to allow for a larger (wider) pool and more space to walk around it. The room is rejected if the final size after all room expansion is too small.

The pool is then cut into the floor in the center of the room and takes up most of the space. A minimum of one doorway width is added along the sides, and two doorway widths along the ends. The end closest to the main entrance door has stairs added so that the player and building AI people can enter and leave the pool. The maximum water depth and number of stairs is determined by the length of the pool, and max depth is limited to one floor's height (about 8 feet). Pools above a minimum length have sloped bottoms with a shallow end at the stairs and a deep end at the far wall. Two or three gold colored metal railings are placed along the stairs.

I chose several shiny tile textures with normal maps for the walls, ceilings, and floors of the room, and the interior lining of the pool. The high specular component of the material makes them appear reflective and wet, and also helps to increase the overall lighting of these rooms. The ceiling and floor textures are the same at the moment. The wall texture looks exactly like the walls in the indoor pool room where I took swimming lessons many years ago. Water is drawn using the same shader to render reflections, refraction, and absorption that I used with flooded backrooms. I only had to tweak the constants to make it look good for swimming pools.

Here is what we have at this point:

Indoor underground swimming pool with shiny tiles on the walls, floor, and ceiling. Kind of plain.

That looks pretty good, but it's too empty. It's time to add beach balls and pool floats. I found a good striped color texture for use with large plastic beach balls. These are placed either in the water or off to the sides. These balls can be picked up, thrown, and kicked by the player. They float on the water surface and will rise to the surface if released by the player when underwater. They can be carried by the player to other rooms in the building.

Pool floats are modeled as simple torus-shaped inner tubes. I experimented with making them partially transparent, but I couldn't get the alpha blending/sorting to work between the water surface and multiple pool floats that may be visible through each other. I also considered using two sided transmissive lighting similar to what I used with tree leaves, but the current rendering and shader system didn't easily support this. So instead I opted for a simple small amount of emissive lighting in the color of the float's plastic to increase their brightness and reduce the shadows on their undersides. Pool floats can be picked up by the player but can't yet be pushed around or stood on. However, they have proper torus collision detection, so it's possible to throw a ball through their centers.

Here's a screenshot showing an example pool at this point in development. Notice that I've also increased the number of ceiling lights in pool rooms.

Brightly lit pool with pool floats and beach ball.

Pool with a float and two beach balls. This pool is in an office building, which is why the lights are rectangles.

That's looking better. Next I wanted to add some simple benches and a diving board to the larger pools. Maybe you wouldn't expect a diving board to be installed with a low ceiling underground pool though? And while I'm working on this, I may as well add a second pool inner surface material that's white with a rough finish. This is the style of the lining in the outdoor pool in my real back yard.

Diving boards caused some trouble with player collision detection because the system I had in place didn't support an object that could be walked on that was suspended above the floor. I eventually got this working, but the player can't actually jump off; they can only fall off the sides or end.

Pool with balls, floats, benches, and a diving board.

I was looking for diving board 3D models and found a nice model of a side pool ladder, so I decided to add those to the pools as well. I later went and added these ladders to the outdoor in-ground pools found in residential neighborhoods.

At this point I felt that the room looks pretty good. There were some minor fixes, such as reducing the period of the wave ripples and adjusting lighting inside the pool. It's time to move onto AI, player, and gameplay for swimming pools.

I would say the most difficult step was making zombies interact correctly with swimming pools. This actually took nearly half the total development time of pools! The default behavior without handling them was that people and zombies walked over the water like it didn't exist. The problem is that the water is actually under what would normally be the floor of the room. The AI system needs to special case handle the floors in these rooms by checking if points are over/under the water during path finding and physics updates.

It was relatively straightforward to have people treat the entire pool (including space above it) as a large collider to avoid walking into/through. This mostly worked, except for cases where one person pushed another over the pool when two people tried to pass each other on the narrow walkway between the room wall and the side of the pool. I had to add a check when the person was over the pool and have them fall into it with a smooth falling motion, rather than immediately dropping to the bottom in a single game frame. This was accompanied by a splash and ripple effect added to the water surface. Once they reach the bottom, a new target location is chosen as the closest point that's just beyond the pool stairs. The AI will turn and exit the pool in this direction. They climb the ramp and stairs to exit, and then revert to normal building room navigation when they're no longer inside the pool. I also added hard boundaries for the three non-exit sides of the pool to keep people from pushing each other through the pool walls.

Zombies proved to be more difficult than regular AI people since they follow the player. I had to change their behavior to keep them from falling in when the player was close to the edge of the pool or inside the pool. There was one bug that took me hours to fix where zombies intentionally walked into pools. I had to add debug printouts and debug visualization code to figure it out. The problem was that I had vertical wall collision objects along the sides of the pool to keep the player from walking through them when inside the pool. These were being picked up by the building AI navigation system even though they're not used for AI collisions. When the player was near the edge of the pool such that their bounding cylinder overlapped one of these walls, the zombie's target point was moved from the player location back toward the zombie location until there was no collision. This moved the target point inside the pool when the zombie was directly opposite the pool from the player. The fact that the path crossed through a blocking object (the pool) was ignored because the game logic assumes that if the player can stand there, so can a zombie. But this logic shouldn't apply when the target position has moved from the player due to collisions. The fix came in multiple parts: Ignore vertical pool walls, reject target locations inside of another object, and always enforce pool collision checks.

Zombies will still sometimes fall into pools, but it's not intentional. Usually it's because they're in a group pushing each other to get to the player. The zombie closer to the wall will sometimes push an adjacent zombie into the pool, particularly when cutting a corner. This is okay because there will always be at least one zombie outside the pool to chase the player.

Here's a screenshot of zombies having a pool party before I fixed the bugs. They try to follow the player, but keep falling into the pool. You can see the heads of a few zombies poking out of the water near the exit stairs on the far end of the pool.

Zombies in and around the pool. They try to chase me but keep falling in!

I decided to make the player "hidden" from zombies when fully under the water. When the player is standing in the pool with their head out of the water, the zombies can see them. But since zombies don't willingly enter the pool, they will simply walk around it and hang out by the stairs waiting for the player to exit. Zombies in the pool with the player will mostly ignore the player, but may attack when the player is located along their path and their head is out of the water.

I reduced the player's speed when walking (or swimming?) in water. The reduction scales with the depth of water around the player and reaches 40% when fully underwater. This isn't enough of a reduction to simulate real water movement, but a higher reduction makes it take too long to get out of the water when the player falls in. I already added a similar speed reduction for other cases such as when the player is climbing stairs.

 

The final step was to allow for player drowning when staying underwater for too long. This is mostly for game balance as it prevents them from hiding under the water until the zombies leave the pool area. I added an oxygen bar in cyan that only appears when oxygen is below 100%. The player has 30 seconds of air when underwater. When out of the water, the oxygen bar will refill completely at 10x speed, in 3 seconds. I increased the strength of the wavy water effect postprocessing shader as oxygen is reduced and made the screen begin fading to black when oxygen drops below 10% as a sign to the player that they're about to drown. Drowning will play a special gurgling sound and reset the player to the starting location with an empty inventory and no money.

 

I'm considering adding the player's dead body in the pool, if I can find a good animation or pose for that. It could even be a pickup item! I currently only spawn a pool of blood on the floor when the zombies kill the player. I guess they eat the player, or something like that? I'm not sure what happens to the items in the player's inventory on death. Maybe some items should drop? Only the item the player is holding at the time of death?

Here's a video showing how zombies and the player interact with swimming pools. I disabled the bug fix so that zombies fall into the pool because this is more entertaining to watch. Of course it also makes gameplay too easy.

Now that I have swimming pools with nice blue water, the water in flooded basements seems too clean. I changed the backrooms water material to be 50% mud to give it a dirty brownish color, and the increased variety looks much better. Here's a new screenshot for reference.

Flooded backrooms with muddy water.

Everything is working well now. I may add some sort of player swimming ability later if I can find a good way to control it with the keyboard. I might also try to improve outdoor pools and actually allow the player to enter them.

Animated Birds in Cities

It's time for another update. This month I've added animated birds that fly around 3DWorld's procedurally generated cities, above the people and cars. Birds are a good fit for cities as they fill the areas above the ground with movement. I did already have butterflies, but they were usually too small to notice. In fact, it was a challenge to even find one without the debug overlay to show their paths. I also had helicopters, though they were sparse and only visible high up in the air.

I started by placing instances of a static 3D model of a pigeon to the tops of city benches and trashcans. In addition, I added some small groups of pigeons on the open concrete ground areas between some of the buildings. These contributed a good amount of small detail to cities, but they lacked animations. Therefore, it didn't make sense to have them fly around. I wanted to use an animated bird model instead.

The 3D bird model I used was created by Paul Spooner and can be found here. This bird has five animations for standing/idle, taking off, flying, gliding, and landing. I created a new bird class that used a finite state machine to switch between these five states in a cycle that moved each bird along a path from object to object. I initially used the same bench and trashcan placement as pigeons, but later added resting spots on the tops of transformers, power poles, news racks, stop signs, fences, hedges, walls, and mailboxes. At some point I may add landing spots on houses and office buildings.

The bird flight model consists of three main stages: takeoff and orient, fly to destination, and glide down to land. A bird can apply accelerations independently in the vertical and horizontal directions to adjust its velocity to reach certain target locations along its flight path. Vertical velocity adjustment is used to change altitude, with limits applied for maximum rising and falling velocity as well as a maximum altitude that's determined by the bird's size and average building height. Horizontal acceleration is used to control steering to allow birds to change direction mid-air when orienting toward destination points. I've added a maximum turn rate similar to that of people to limit turning to smooth circular arcs.

First, each bird will choose a destination by randomly selecting an unoccupied location from the pre-generated list. Only locations visible to their current position are considered, to guarantee a valid flight path exists to that point. The visibility query includes all large objects such as buildings, telephone poles, benches, etc. Once a destination is chosen, it's marked as occupied so that no two birds try to land at the same spot. When the bird takes off, its original resting location is freed for use by other birds in the future. This way birds can continue to fly around indefinitely.

Takeoff consists of rising in the air to a target altitude while at the same time turning in a wide circle to point toward the destination. This creates a spiral path in the sky. Unfortunately, when the bird starts pointing away from its destination, this arc can leave it in a position where the landing spot is blocked by a building or other city object. If the bird was to continue to the destination from this location, it may collide with one of these objects. I spent some time trying to work out object avoidance, but eventually realized it was easier to choose a new destination in this case. I changed the bird update logic to check for ray (actually projected cylinder) collisions once every 16 frames while turning or ascending, and select a new destination each time a collision is found. This can produce more circling behavior. I feel that this actually increases the realism and variety of bird movements.

Once the bird has reached its intended flight altitude, it continues on that course until it nears the destination. I tried a number of different approaches to find the correct point where each bird starts its descent. First, I decided to calculate the distance at which the time to land was equal to the duration of the landing animation. The problem with this approach is that it assumed a constant velocity and was inaccurate if I wanted the bird to slow during descent and landing. It also treated the framerate as a constant, which may not always be true when the player is actively moving.

The second approach calculated the horizontal distance required for the bird to reach max altitude, and started descent when the horizontal distance to the destination went below that value. This assumes the ascent and descent acceleration and velocity were the same, which was a limitation. It also didn't properly account for extra time taken to reorient toward the destination, where the circular path covered less horizontal distance than the same path length in a straight line. The result was that birds would either reach the landing spot too early while they were still high in the air, or too late such that they would need to glide for long distances at low altitude. Low altitude flying is more likely to result in collisions with objects, including people and cars that normally aren't considered because they're below the flight path.

In some cases birds would overshoot their landings and have to fly back, which caused more problems with flying through ground-level objects. I tried various approaches such as having them slow down just before landing, but that only threw off the landing timing even more. My final hack was to add an attraction force from the destination that was enabled when the bird got close to pull it onto the right path. This mostly worked. I later updated the code to use the angle of approach to adjust the force.

Up until now, I had been assuming the takeoff and landing locations were at a similar height. That changed when I added the tops of telephone poles as bird resting spots. This large elevation difference broke the takeoff and especially the landing logic. It was particularly bad in the case where the two end points were close together horizontally and required a steep climb or fall. One easy partial fix was to constraint the destination to not be so close that the slope was higher than some threshold (I used 30 degrees). The second part of the fix was to shorten the ascent and descent stages to as little as the time to play that animation cycle, and then add a speed cap in the horizontal direction to allow for higher relative vertical velocity.

The landing sequence was still a bit difficult to line up with a steep descent. This sometimes resulted in the bird reaching the correct altitude for landing with a small amount of horizontal distance left to travel. This caused some instability where the bird alternated between small positive and negative vertical velocity and resulted in oscillation between flapping and gliding animations. In the end I decided to leave this behavior unchanged because these more chaotic landings provided a nice variety compared to the smooth and graceful landings of longer distance flights from objects at similar heights.

Wow, that was a wall of text! It's time to show some pictures, and a video at the end.

Let's play a game. Can you find all the birds in this scene? Look closely. There are at least 8 of them.

I know, I can't find them all either because their white color blends in with the ground and buildings. Here, I made them red, now can you find them? Did you find the one on top of the telephone pole on the very right edge?

After taking these screenshots, I decided to make some of the birds darker colors. Now they come in a random grayscale color that ranges from bright white to near black. Black birds are easier to see against some of the city objects. They're even easier to pick out in residential neighborhoods where they can often be seen against the blue sky as a background.

Here is a video where I follow a bird as it flies around the city. Please excuse the wait, there's no way for me to tell when the bird is about to take off or where it plans to land. I can only wait to see what it does.

As usual, the code can all be found in my GitHub repo. The source file that contains the bird behavior is here.

Bonus: I also worked on helicopters, since they're similar to birds. They both fly through the air from one destination to another. I now have three helicopter models, all with proper rotating rotor blades. This isn't a large enough topic for its own post, so I'll just add the video here.

Basement Water, Improved

This is a short update to my previous post. I've found a way to add most of the features that were missing from my previous basement room water.

Walls Blocking Waves

One problem with my water implementation is that the ripples/waves pass straight through walls because the fragment shader that draws the water doesn't know where the walls are. Let's fix that. I don't want to add a strict line-of-sight test for every point in the water to the source of the splash because that's unrealistic and difficult. Waves can pass through narrow gaps and expand outward; trying to clip them to the exact walls looks incorrect. Instead, I can calculate the extents in each of the four cardinal directions (+X, -X, +Y, -Y) and pass them to the shader as planes bounding the waves for each splash. This is done by casting a number of rays (I used 90) out in each direction from the splash origin, clipping them to the building walls, and tracking the max distance a ray can travel in each of the four directions. This is similar to how room ceiling lights are bounded to optimize lighting in the fragment shader.

The effect is that any splash bounded on one side by a wall will have its waves blocked by the wall. This is particularly apparent for splashes made in enclosed rooms that shouldn't propagate outside the room. This appears to fix most of the obvious cases where waves went through walls.

Refraction

Adding refraction for underwater objects such as the floor requires modifying objects that were previously lit and drawn. Fortunately, I already have a system to read the current color buffer and pass it into the shader as a texture. If I then make the water fully opaque rather than transparent, I can manually blend the refraction into the background using the computed alpha (transparency) value. Now that I have the underwater part of the scene as an image, I can use the same texture coordinate domain warping approach I used with reflections to add refractions. This produces a nice wave distortion of the floor and other underwater objects under the ripples.

Caustics

Finally, it's time to add fake caustic lighting effects to the underwater objects. This is another color transform the fragment shader applies to add the effect to previously drawn geometry. Caustic lighting appears as bright and dark spots in areas where the rippled (non-planar) water surface acts as a lens to focus light onto certain areas below the water.

Most of the reference images you can find for water are taken in outdoor areas with the sun and a water body such as an ocean, lake, river, or swimming pool. My basement water is different for two reasons. First, the light source is a array of overhead rectangular area lights rather than a single high intensity light such as the sun. It's not clear exactly how to compute caustics efficiently in this case. Second, indoor water isn't subject to forces such as the wind and tide that create waves or smaller surface irregularities. Undisturbed indoor water is almost completely flat. When objects are dropped into the water, this creates ripples. The ripples from multiple nearby splashes merge and create interference patterns. Adding many splashes gives the water a very chaotic wave pattern.

I'm not entirely sure what the caustic lighting patterns on the floor should look like in this situation. So I'm going to do something simple and calculate the lighting from only the water surface normals that are used for reflections and refractions. This is simple but not physically correct. The only problem is that I can't simply adjust the normals because lighting has already been applied to the underwater objects. The best I can do is to adjust the color of the refracted pixels based on the signed wave height to increase or decrease their brightness. I had to turn the effect down so that it's not as obvious that this is a hack. I think it's still noticeable, and is the only observable effect of the ripples directly below the player.

Anyway, here is an updated video of basement water. I think the water effect looks much more realistic now.

 And here are some screenshots after I walked around in the water.

Basement water, now with refractions, caustics, and wall blockers.

The scene from above, but after moving backwards and waiting a few seconds.

In case you're curious what this looks like with the lights off, it's dark as expected:

Water shown in a dark basement with the lights off, and the only light coming through the stairs opening from the floor above.

Update

I just realized that I haven't enabled reflections in these screenshots. The zombie/people reflection code was also broken, and I had to fix it. Here are the new video and three updated screenshots with both reflections and refractions.

Basement Water

I've added a layer of water to the lowest levels of some of the office building backrooms basements. It's about a foot deep and mostly clear. The water is drawn using a physically accurate method that includes computing a Fresnel reflection term and calculating wavelength dependent absorption and scattering. Scattered light uses the color derived from nearby room ceiling lights and includes a shadow term. The top surface appears reflective at shallow view angles. The reflection code was reused from what I originally implemented for bathroom and dresser mirrors.

I've also added a system for tracking the 32 most recent splash effects and adding them as ripples that distort the water's surface. Each splash source generates sine waves that propagate out and are computed per-pixel in the fragment shader. This changes the normal used for lighting and also the texture coordinates used for reflection lookup. In addition, splashes add a local dirt/foam effect that temporarily makes the water a bit cloudy.

Everything that touches the water produces a splash with magnitude that depends on the force of the movement. This includes the player, people, and zombies walking through the water. It includes collisions of balls with the water when kicked or thrown. Pushing and dropping objects in the water generates splashes, as does opening and closing doors submerged in water.

This video shows my progress so far. I initially tried to get a good splash by dropping the fire extinguisher in the water, but it was difficult to see from that steep view angle. Ripples are easier to see when viewed at an angle from further away when the reflection term is stronger. The slight lag that occurs while the zombie is chasing me is due to the loading of a different 3D model for a zombie on the floor above me that never quite comes into view.

Here's an image of the same scene. The default is clear, clean water. The water absorbs the red component of the color more than the other wavelengths, and scatters the blue color the most. This results in the water appearing to have a blue tint that varies from light blue/white nearby to a deep blue in the distance where the camera's path through the water is longer due to the view ray slope. The absorption wavelengths can be adjusted in the shader to give the appearance of other fluids such as dirty/muddy water and even blood.

A basement full of clean, clear water that takes on a blue tint.

The same scene, but with dirty, muddy water. However, it has the same reflectivity, only the absorption has changed.

The same scene, now shown with bloody water. (Now that I took the screenshot I realize the foam should be dark red rather than white.)

The main() function of the fragment shader code can be found in my GitHub repo here.

I haven't yet figured out how to add refractions for the floors and walls under the water because these have already been drawn by the time the water is drawn over them. It's not particularly easy to customize the lighting and shading of these objects based on the water above them like I do with terrain. There are no caustic lighting patterns on the underwater objects either, for similar reasons. I have a caustic texture that I use when drawing the terrain under ocean water, but that same approach doesn't work well here. I'll look into a screen space approach that reads the current buffer contents before the water is drawn and includes that in the water shading, which may allow me to add these features.

Oh, and the water is currently only a flat plane with no height displacement due to waves. Also, the simulation is mostly run on the GPU, which doesn't have access to the wall locations. This means that waves propagate along the surface and through walls rather than reflecting off of them. I may be able to partially work around this by computing the bounds of each ripple by ray casting it against the walls on the CPU, then sending it to the GPU as a uniform buffer. This is how I handled room lights.

Finally, it would be nice to have an animated splash effect when objects enter the water. This would add some 3D volume to the water surface. I may be able to reuse the technique I used for raindrop splats in previous work.

I'll continue to think about these limitations to see if I can resolve them in the future.

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.