So far I've added people, rats, and spiders to buildings. They can all be considered a sort of enemy of the player in gameplay mode. What other hostile animals can I add? How about poisonous snakes that attack the player when they get close.
Snakes are similar to rats because they stay on the floor and can't climb walls and other objects like spiders. Snakes are limited to the ground floor and currently can't be picked up by the player. They're more aggressive than rats, and will bite the player when in range rather than running and hiding under furniture. However, they completely ignore the player when the player isn't right next to them. This makes them easier to avoid, assuming you're paying attention to your surroundings and being careful when entering new rooms.
There are currently two types of snakes, those with rattles and those without. All snakes can damage the player by biting, but only rattlesnakes are
poisonous and will do damage over time. This uses the same mechanic as
spider bites. The only item that can cure the player of poison is the medicine bottle, which can be found in house medicine cabinets and on rare occasions in drawers. I modified the player inventory to allow medicine bottles to be collected and consumed later if not immediately needed, which make it a bit easier to survive snake and spider venom.
I used a similar approach to spiders when drawing snakes, forming them procedurally in code from transformed cylinders, cones, and spheres. They consist of 18 connected segments, representing individual ribs, with a head at one end and either a tail or a rattle at the other. I found two different textures to use for their scales, and added a random color variation from light brown to nearly black. Each snake has two eyes on the sides of its head and a forked tongue that will occasionally come out.
Four snakes on the kitchen floor. One is a rattlesnake. The center snake has its pink tongue out.
Snakes have a unique movement and animation system. Each segment moves individually in a smooth motion that follows the path of the segment in front. The head moves in a sine wave pattern to give the body movement a wavy, flowing path that I based on the movement of my pet snake Audrey and other images and videos of snakes I found online. Snakes can also curve or straighten their bodies to fit through narrow openings and avoid collisions.
Collision avoidance was by far the most difficult feature to implement. Snakes must avoid the following objects, ordered from highest to lowest priority:
The edges of the building bounding cube (otherwise bad things happen such as the code crashing or the snakes disappearing)
Exterior building walls (outside the building they're not drawn correctly)
Interior building walls
Open and closed doors
Stairs and elevators
Static room objects (furniture, appliances, etc.); fortunately I was able to reuse all of the rat collision logic for these.
Other snakes, rats, and spiders
Themselves; it's important to avoid self intersections; this one was quite challenging
I already had code for most of the items near the top of the list. The only real difference between snakes and rats related to static object collisions is that representing snakes as a bounding sphere is too inaccurate. For the purpose of detecting collisions for the snake itself, I only need to consider a bounding sphere around its head. The rest of the body will follow the path of the head and will also avoid the same static objects. However, checking for collisions with other snakes and the snake itself requires finding intersections with each cylindrical body segment.
It took quite some time to get all of this working. When a collision is detected, a new head direction is randomly chosen within the 180 degrees around the collision normal. Directions closer to the initial head orientation are given a higher weight so that snakes are more likely to continue along a similar path rather than reversing direction and doubling back on themselves. The most common modes of failure for collision detection resulted in the snake getting stuck with its head slightly inside a wall or other object (including its own body).
I was able to fix all but one case of the snake getting stuck with reasonable effort. The final case was where a snake was forced into a curve while colliding with another snake, and it spiraled into itself to the point where its head was completely surrounded by its body and it couldn't move. After several failed attempts, I finally fixed this by setting the collision normal to be the direction of the colliding segment coming from its head. This would force the head to turn toward the direction of the tail on collisions, rather than curving toward itself.
I also found and fixed a pretty funny bug. When the snake was stuck against an object such as the player, it would choose random new direction each frame. This would cause the head orientation to jiggle around randomly. In addition, this triggered the animation system to update, which resulted in the snake's eyes spinning around its head!
Here's a YouTube video showing a number of snakes in the living room of a house. They glide around on the floor and attempt to avoid objects, each other, and themselves. I find it quite interesting how they can weave between the table and chair legs using collision avoidance forces. Note that I already fixed the rat vs. snake collision bug. I was incorrectly using the snake's bounding sphere radius rather than the snake's body radius to move the rat to a non-colliding position.
It's time to discuss indirect room lighting. This is turning out to be a long and technical post. I've scattered some screenshots around in there somewhere for those of you who don't want to read the wall of text. I'll also add Wikipedia links for some of the technical terms.
I want to improve the quality of lighting inside my procedural buildings. Most of my previous screenshots have shown the combined contributions of three types of lighting:
Direct lighting from room ceiling lights and lamps, pointed downward in the lower hemisphere as a 180 degree spotlight so that I can use a single shadow map
A very weak sky lighting representing light coming in through windows, which at least tints walls different colors in otherwise unlit rooms
A fake constant ambient term that varies by floor/basement/attic
This looks reasonably good in well lit rooms where the lights are on. However, rooms with their lights off have very flat colors and all surfaces tend to look the same. This is both uninteresting and unrealistic. Also, places in shadows and along the upper wall and ceiling of lit rooms have very little indirect light and suffer from the same problems.
I've been trying to add proper indirect lighting support for some time now. Has it been as much as a year? Maybe. The difficulty is getting a good quality of lighting with low noise and low light leakage through walls, and having this lighting update in buildings as the player moves around without causing lag and hurting the framerate.
I consider this a solved problem for fixed size static scenes in 3DWorld. I can precompute lighting offline, save it to disk, and reload it in under a second when the scene is loaded in 3DWorld. This works well on scenes of moderate complexity such as San Miguel. I even had this working for my office building basement using player controlled dynamic lights, and in the static Sponza scene all the way back in 2014. This system worked by sending millions of rays from the sun, sky, and local point lights into the scene, calculating their reflections/refractions, and accumulating their paths into a 3D volume texture.
Why can't I use the same solution here? Well, in theory I can. The only problem is that the player has to wait 20 min. for the lighting to be computed before entering a building. [Technically we can also let the player enter the building and wait 20 min. for lighting to appear.] That doesn't work very well in an open world game with thousands of buildings, does it? Now I can hack things and use a few tens of thousands of rays rather than millions to get the computation down to a few seconds. My first attempt at this gave me the following results:
Failed attempt at indirect lighting on building interiors. Did I show this screenshot in a previous post?
That's actually a really neat effect. It looks like the walls are made of dirty aluminum foil due to the way their normal maps interact with the lighting. That's not the look I was going for here, but I can't pass up the opportunity to show off my accidental artwork. I was able to fix this of course, but the floor didn't get much better than that black and gray pixelated mess you see above. So I could get noisy garbage lighting in a few seconds, or wait tens of minutes to get something that looked nice. Neither case was acceptable, so I lost interest in this last year.
... Wait, that screenshot is from Feb. 2020. So this was over two years ago? Wow, I didn't realize it had been that long. Surely I've gotten a new computer since then, it's super fast, and that solved all of my problems, right? Nope, same computer. It's too much effort to install all of my software and development tools on a new PC.
Optimizations
Anyway, I got back to working on this a few months ago. There are actually quite a few optimizations I can use to speed this up and get more rays (= less noise) in less runtime. I can also reserve one of my CPU cores for drawing the scene rather than using them all for lighting computation, which allows me to get a reasonable framerate for walking around in the building while the lighting is being computed in the background.
I'm storing precomputed lighting values in 3D voxels
(volume elements). Each fragment (pixel in non-OpenGL terms) of drawn
geometry queries its indirect lighting from the nearest voxel, biased in
the direction of the surface normal. One of the reasons why tracing light rays is slow is because I need to accumulate light into all voxels along the entire path of the ray rather than only at the hit points. This nearly doubles runtime, especially for long rays in open space when using a fine voxel grid. I need to store lighting data for the empty space in a room to get proper lighting on dynamic objects such as people, animals, and whatever items the player moves around. These objects aren't present during lighting computation, so there are no ray hit points associated with them.
One of the biggest optimizations I discovered is to only calculate lighting on the floor of the building the player is on. It seems so obvious now that I think about it. This cuts the number of active light sources by a factor of 10x for a 10 story building, which is quite good. But it gets better than that! I can build the 3D acceleration structure I use for ray intersection checks for only objects on the current floor rather than the entire building. I don't get another 10x runtime reduction though, because ray query time scales as the log of the number of objects in the bounding volume hierarchy. The actual speedup is more like 20x for a 10 story building. That's still pretty good though. The cost I pay for this decision is incorrect lighting on floors above and below the player when looking up or down stairs.
Another related optimization is that I only need to store the lighting for a few floors of one building at a time, and I only need to draw it for the floor the player is on. This reduces memory usage on both the CPU and the GPU. I pass the 3D bounding cube of the current floor into the fragment shader and use my original constant ambient term rather than the indirect lighting calculation for anything drawn outside the current floor. This way the slice of valid indirect lighting can follow the player around and everything else looks as it did with indirect lighting disabled. I was even able to go back and further optimize ray intersections to simply clamp rays to the range of z-values (altitudes) spanned by the current floor since any rays extending outside the range are ignored anyway.
I chose a range of 5 floors to store in memory. This allows the player to walk between the floors of houses without invalidating lighting data along the way, since all floors can fit within this range. If I had used only one floor, the lighting would need to be rebuilt every time the player walked up or down the stairs. Note that some houses with both basements and tall attics can exceed this range and require some amount of re-computation. Office buildings can be as high as 20 floors and won't all fit in memory at once. I decided to disable lighting updates while the player is in an elevator so that lighting is not unnecessarily computed for floors the player doesn't even stop on. Lighting updates will begin when the elevator door opens, where the first light to be updated is likely the one on the ceiling in front of the elevator.
The next step was to prioritize lights that have more of an effect on the area visible to the player. This includes weighting based on lights near the player and in the view frustum, and lights inside/affecting the room the player is in. This change allowed me to generate lighting almost immediately for nearby rooms, have the lighting follow the player around as they moved from room to room, and compute lighting for rooms not yet visible in the background when the player stops.
Noise
Those optimizations, plus some smaller ones that I won't list, allowed me to have near realtime indirect lighting. It works well for rooms that are fairly well lit. Unfortunately, it still has a lot of noise in rooms that are less well lit due to the relatively small number of rays reaching these rooms from light sources on the ceilings of other rooms. These rays take several bounces to get there. The fewer ray samples there are, the higher the variance, and this leads to random noise. Here's one example:
Indirect lighting in a room with the light off. All light comes from other rooms, most of it indirect. Lighting is noisy in cases like this.
It's noisy, but it's fast. Getting results of this quality before these optimizations involved suffering through a minute of low, laggy framerate before any indirect lighting appeared. If I increase the number of light rays by 10x I can almost completely remove the noise, but the player must wait for the lighting to appear again. It's a typical runtime vs. quality trade-off. I would call this partial success.
Indirect lighting in a kitchen with the lights off again. The area under the chairs is dark.
It's unclear if this solution is worthwhile in these situations, but it appears to work great in basements, parking garages, and attics. There are fewer objects and no windows, so it tends to be faster. Basement lighting is normally uniformly dark, so having indirect lighting is a huge improvement even if it's noisy. The same is true for attics. I added config options to only enable indirect lighting in basements and/or attics where it's faster and more effective. I may make this the default going forward.
Light Leakage
I ran into another problem: light leakage. Indirect lighting is stored in a 3D grid of equal size voxels. If a voxel is wider than a wall, the floor and ceiling on each side of the wall often query the same voxel. This may result in light areas around the edge of a wall in a dark room where the adjacent room has a bright light. Similarly, there may be dark edges around a wall of a lit room next to a dark room. I can't make walls thicker without breaking other parts of building generation, and I can't make the voxels too small due to computation time and memory constraints. Fortunately, my optimization to limit indirect lighting to the current few floors avoids this same problem in the vertical direction involving the ceilings and floors.
If you look closely at some of the screenshots in this post, you can see bands of bright or dark areas around the edges of walls, ceilings, and floors. There are similar dark edges around the curved sides of ceiling light fixtures that are turned off. It's not too bad after I made a pass at tweaking constants in the code.
Indirect lighting in a basement room. There's less noise when the light is on. You can see a red tint on the ceiling from light that bounces on the red rug on the floor. The man standing in the room has indirect lighting as well.
Here's another basement where the noise is almost undetectable. It helps to have lit rooms with dark ceilings. Also, I added a screenshot of a parking garage with cars.
Indirect lighting in the basement makes it easier to see the pipes near the ceiling. Without it they're in shadow and appear very dark. You can also see some darkening above the water heater.
Parking garage with indirect lighting. The indirect component makes the pipes and ceiling easier to see, and softens the shadows under the cars.
Windows
So far I only discussed indirect lighting from room ceiling lights and lamps. There's another source of indirect lighting. Can you think of it? I'll give you a hint: Bedrooms shouldn't be dark like basements when the light is off during the daytime. That's right, I need to include the indirect lighting from the sun (and moon) coming in through the windows. I can treat each window as an area light source and generate rays through it that enter the building. This works well, but sadly now there are more than twice as many light sources to handle in a typical house. On top of that, windows seem to need more rays to reduce their noise, so we're back to having a slow lighting solution. Fortunately, it's still much faster than it was before.
Bedroom with the ceiling light off. All light comes in from the windows. You can see the soft shadows under the bed and dresser.
Bedroom brightly lit from both the ceiling light and the sun outside.
Here's a comparison of the same room with and without indirect lighting. The second image has brighter walls with more color variation and fewer shadows.
Bedroom with direct lighting from the ceiling light (pointed down) and a constant ambient term.
Bedroom with both direct and indirect lighting from the ceiling light, and indirect lighting through the windows.
I'm not quite sure why there's an orange tint around the light on the ceiling. Maybe it's because the color of the light is somewhat orange-ish rather than completely white. It could be that the color is saturated to white in some areas but not around that cylinder. Or maybe there's an orange rug above it in the attic and I'm getting some sort of incorrect light bleeding from that. I have no idea. I should go back and revisit this, if I can manage to find that house again. (It's not one of the houses next to the player's starting position.)
[Update: I found the house again. It looks like the light itself is yellow. It appears white because the direct + indirect/ambient saturates the colors to white, possibly because the gamma correction is off. The light shines downward with a 180 degree field of view in the bottom hemisphere. Therefore it doesn't shine directly on the ceiling. The lighting near the light in the center of the ceiling is yellow light reflected off a dark brown floor, plus the edges of the light fixture itself, which I guess results in that shade of orange.]
Dynamic Lighting / Player Interaction
So we're done, problem solved, right? Not quite. Up until now I've treated buildings as static. In reality the player can turn lights on and off, open and close doors, and move furniture around. All of these things will obviously affect the indirect lighting. As you might expect, adding support for dynamic indirect lighting introduces a huge amount of complexity. I haven't quite figured everything out yet.
Let me start with turning room lights, closet lights, and lamps on and off. It can either be the action of the player, the building AI people, or one of the new motion detection + timer lights. (I added that last one to automatically turn lights on and off in some office buildings.) This also includes the player opening and closing bedroom window blinds, which I have somewhat working. The full precomputed lighting on a building floor is the sum of the indirect lighting from each light source. This means that turning a light on is as simple as adding a new light to our queue of lights to process that will be accumulated into the total. Turning lights off is more complex. It can be implemented by subtracting light by using a negative intensity ray, but we need to be careful to make the rays deterministic so that the positive and negative rays will exactly cancel each other out. A lack of determinism leads to - you guessed it - more noise. Finding a deterministic solution that worked across multiple threads proved to be difficult.
One possible optimization is to cache the contribution of each
light source separately. This avoids re-computation when the player turns lights on
and off, and also solves the determinism problem. The downside is that
this is both complex and takes significant memory. The light volume
itself consists of 128x128x128 = 2M voxels in {X, Y, Z}. Each voxel
holds a floating-point number for each of the {red, green, blue,
intensity} components of light. 2M * 4 bytes * 4 components = 32MB of
data. A single building floor can contain as many as 100 lights, including ceiling lights, closet lights, lamps, and windows. We clearly
can't be storing 3.2GB of cached data across all lights. How can this be
improved? Most lights will only affect a few rooms on a single floor
rather than the entire 5-story horizontal slice of a building. If I was to compute
the bounding cube of influence of each light, it would be constrained to a small subset by the walls, the floor below, and the ceiling above. This would reduce memory
usage to as low as 1MB per light. That would still be 100MB of data for
100 lights, but this number is reasonable.
I was pretty happy with the system I had in place for recomputing indirect lighting when room lights were toggled by the player. I considered doors next. Opening and closing doors is more complex because they can influence multiple lights that illuminate the room on each side of the door. When a door is closed, light rays that previously reflected off the door back into room will instead exit that room and add light to the adjacent room. This requires the indirect accumulation to shift between the two rooms, and possibly other nearby rooms connected with open doors.
It was easy enough to determine which lights are affected by which doors by using the room connectivity graph. The hard part was figuring out how to correctly rebuild the ray spatial acceleration structure when a door opens or closes. The problem is, indirect lighting ray tracing is running in another thread in the background. I can't simply rebuild the data structure while it's being used. Instead, I have to wait for the current light's computation to finish, or kill it if the current light will be invalidated by the door state change. Then I have to remove the contribution of each light that will be updated, using the door's original state. Next, I can update the door's state and rebuild the acceleration structure. Finally, I have to re-add each light's contribution using the door's new state.
This sort of works, in theory. In practice it's problematic because I need to update the door's open/closed state in the drawing code immediately, otherwise it will look odd if the door doesn't move until the lighting is completed a few seconds later. So I have to use two different door states: first the drawing state changes, then the lighting state changes once old lights have been removed. To make matters worse, what happens if the player toggles the door back to it's original state before the lighting has been updated? Or what if the player opens or closes some other door that affects the same light(s)? I can build a queue of door state changes and light update passes, but the system may not be able to keep up with the player. Even if it can keep up, it's probably going to be wasting a ton of CPU cycles recomputing everything.
I experimented with this for quite some time, but was never able to get it working correctly in all cases. Instead I left it as-is, where it only works correctly when the player opens or closes a door when there's no current lighting calculation and no pending light updates. Otherwise the lighting is wrong in various ways. Then I later disabled door updates entirely because the failure cases where light or darkness appeared from nowhere caused too many issues. Door state changes now only have an effect if they happen when lights are off, because the new door state will be picked up and used when lighting is recomputed as lights are turned on.
Doors are trouble for other reasons. Remember the potential light caching optimization I mentioned a few paragraphs above? Well, any door open or close events will have to invalidate cached lights whose area of influence cubes intersect the door. (In fact, any player movement of furniture should affect lighting as well, but I'm going to ignore that for this discussion.) It's only worthwhile to cache lights if they remain valid for multiple on/off toggles without a door state changing in between. So, which happens more frequently, a light toggle or a door open/close? I'm not sure. Given the fact that door state changes affect multiple lights, my guess is that light invalidations are more frequent than light switch toggles, meaning there's not much benefit in caching per-light data. This is why I haven't yet implemented light caching. The cost of high memory usage, code complexity, and frequent invalidations combined to likely outweigh the benefits.
Indirect lighting is still a work in progress. I have it disabled by default and can toggle it with a key press. I'll probably enable it for basements and attics where it works best, and for screenshots. If I can find more ways to either improve computation time or reduce noise then I may enable it by default later.
The technical reader may wonder why I don't simply use screen space ambient occlusion. I've considered this approach, and done some experiments, but I found that it doesn't work very well in this application. First, I'm using Forward+ (tiled forward) lighting and don't have normals available in the fragment shader. This makes SSAO more difficult to implement. Also, there are lots of partially transparent materials (windows, glass tables, car windshields), alpha masked leaves and grass, ray marched clouds, and various other drawn objects that are unfriendly to SSAO. Besides, it's not a physically correct approach and it doesn't add neat effects such as color transfer between surfaces.
