Sunday, October 24, 2021

Procedural Buildings: Clothes Hanging in Closets

I showed some simple colored, 2D textured billboard shirts hanging in closets in the previous post. Various people, including my daughter, commented that they didn't look very much like real shirts. That's true! Fortunately, Paul Spooner offered to create some proper 3D models of shirts, pants, and clothes hangers. I was able to replace my temporary shirts and hangers with these improved models and add actual 3D volume to these objects, as well as an increased amount of variety.

Of course this wasn't trivial. There was some work involved in integrating new classes of 3D models into 3DWorld's object management framework. First, I had to add support for multiple 3D models of the same object type for building interiors, similar to what I had to implement with cars and people. Then I had to add flags for models to enable two sided lighting, change the rotation point, override the default texture, and extract the object name from the model filename. All of these features will likely be useful in the future. In fact I've already started incorporating some of these features into the other (existing) types of room objects.

Here are some screenshots showing the current contents of closets. There are five different hangers, a tee shirt, a long sleeve shirt, and hanging pants. Some of the shirts are textured, while others are brightly colored. The player can steal the clothes and hangers, as well as push/rotate them to the sides by walking through them in the closet.

The original shirt models, textured with a logo.

Adding some colored shirts, but keeping the pants gray. The yellow shirt on the left is too bright, so I've replaced it with dark green.

The shirts here are placed too close together, and the yellow and white shirts intersect. I've fixed this by replacing a shirt or pants with an empty hanger in this case.

Shirts on the left, pants on the right. Everything casts a shadow.

Shirts and pants hanging in a closet with a lamp and box at the bottom. Some of them have been rotated.

I think closet interiors would look better if there was better ambient lighting. I haven't quite figured out how to do that efficiently yet. I'll post updated screenshots if I can find a way to improve this. Also, the clothes hangers are very thin, which makes their shadows blocky when viewed up close. It would definitely work better if I could somehow make that circular light source a small area light rather than a point light as that would give it softer shadows.

What's the next step? Maybe adding clothes to dresser drawers?

Saturday, October 16, 2021

Procedural City: Residential Updates

I've been working on a variety of different aspects of 3DWorld's procedural city over the past few weeks rather than a single larger topic. I decided to just combine everything together rather than making lots of small posts. This post shows the major additions and improvements I've made, starting with exterior changes and ending with interior changes.

Cars Entering/Leaving Driveways

This task took by far the most time due to the complexity of the logic required to implement it. Up until now, cars would choose destination intersections and drive between them, meaning they were always actively moving on the road network. Parked cars stayed parked forever. I added a config file option to allow a certain percentage of cars to enter driveways and temporarily park. After a few minutes have elapsed, they start up again, back out of the driveway, and continue to a different destination. This was more complex than it sounds because I had to handle both the car physics for these turns and the logic to avoid hitting other cars and people in the process.

I started with a reservation system for driveways so that no two cars try to use the same driveway at the same time. Some cars are always parked and will reserve their driveway forever, but the other driveways are available to the first taker. I limit usable driveways to ones that are long enough to fit the current car or truck without requiring the garage door to be open. While destination intersections can be in other cities, destination driveways are always in the city the car is currently in. This simplifies the logic a bit.

The most difficult step was determining when it was safe for cars to enter and leave driveways. They always pull in, and either back out or pull out depending on the orientation they started in. The tricky case is when a car is making a left turn into a driveway and needs to check for traffic in the opposite lane that it will be crossing. It's not enough to check for cars blocking the driveway at the current point in time, they need to find all cars that can potentially cross that path for the duration of their turn. This involves locating nearby cars on the current road and cars about to turn onto the road and predicting where they will be a few seconds in the future using their distance, current speed, and max speed. The test is somewhat conservative to add a safety margin. The case where a car is backing or pulling out is similar, except it needs additional time when backing out to switch from reverse to forward. However, once they're on the road, cars behind them will see them and stop if needed. So it doesn't need to be as conservative. Cars exiting driveways must also check for cars stopped at a red light and blocking the driveway, and wait until their path is clear.

Sometimes when the driveway is close to an intersection, it can be blocked for long periods of time, preventing cars from entering or leaving it. It's generally okay to let a car sit there and wait to exit a driveway. However, there's only one lane (no dedicated left turn lane), so a car stopped waiting for a left turn will block traffic on its side of the road. This can lead to gridlock, especially when this happens on both sides of the road at the same time. My fix is to have the car only wait a short time and continue to loop around the block if the driveway is blocked by a stopped car. This can result in the car looping around the block forever, but at least the system doesn't deadlock.

Here's a video showing a car entering and leaving a driveway. The video is sped up a bit, and the time a car waits in the driveway was reduced from a few minutes to a few seconds. Yes, I added back up lights.


The next step was to make these cars avoid hitting pedestrians who were walking on the sidewalk between the road and driveway. This was challenging because car and pedestrian update logic is run on two different threads at the same time, which means the cars and pedestrians can't directly access each other. I couldn't figure out how to make the cars stop to avoid pedestrians, but I did eventually figure out how to make people stop at the edges of driveways to avoid cars. The logic for this is different for cars entering driveways, leaving driveways, and parked in driveways. It's similar to the logic used for pedestrians crossing roads, except with driveways instead. It's similar to the car driveway entrance and exit checks as well because it also involves predicting the paths of nearby cars.

The system works in many cases, but there are some modes of failure. For example, pedestrians can block each other or push each other into driveways. It's possible for a car to start backing up just as someone crossed into the driveway behind it. I could add a flag to the driveway indicating a person was in it to keep cars from moving. But I'm worried that this can lead to a dependency cycle where one or more pedestrians and one or more cars are all waiting for each other to move, and none of them can make progress.

There's also the case where someone will walk around an obstacle such as a fire hydrant or another person, slightly into the road, bypassing the driveway. To handle this case, I extend the driveway partially out into the road. But then there's the even more difficult case where a pedestrian decides to cross the road directly in front of the driveway. They may stop there waiting for a car to pass before crossing, blocking the driveway in the process. It's not clear how to fix this. Even if the car was aware of this person, all it could do was wait for the person to move. So it seems that this situation must be resolved by the pedestrian moving ... somewhere. Maybe to the side of the driveway? Maybe I shouldn't let people cross in front of driveways in the first place? It's difficult to work on this because this situation is rare, and the simulation isn't deterministic enough for me to reproduce the same failure mode between tests. I saw this particular failure only once.

Here's a video where a pedestrian stops to wait for the car to enter the driveway rather than being run over.

The first time I saw this interaction there was another pedestrian coming from the other direction later who had to wait for the car to exit the driveway. That would have made a better video, but I failed to record it correctly that time and wasn't able to witness this happening again. Minor changes to the AI logic results in major changes in the simulation.

Above Ground Swimming Pools and Chain Link Fences

I showed off some in-ground swimming pools in the previous blog post. This time I've added above ground pools as well. In addition, I've placed chain link fences around the houses to separate the pools (typically in private back yards) from the public area and road.

Residential neighborhood with both in-ground and above-ground pools, surrounded by fences.


The fence placement logic was more complex than I expected because it had to avoid crossing the driveway, other fences/walls/hedges, trees, and AC units on the side of the house. I also added checks for fences blocking porches and exterior doors. The final placement algorithm is able to fully fence off around 90% of pools and will remove the pool and fence segments when it fails. This should ensure no pools are publicly accessible and all meet local safety requirements. Maybe people will be hit by cars when crossing driveways, but they won't be drowning in their neighbors' pools.

These screenshots show how a pool is fenced off on both sides of the house, and a close-up of a chain link fence.

A house with a back yard in-ground pool fenced off with a chain link fence on both sides.

Close-up of a chain line fence constructed of metal cube bars and an alpha mask chain link texture. The gap on the left is there because it doesn't know the width of the wall/fence/hedges that will be placed on the left side at the time where the fence is added.

Improved Hedges

Residential plots are separated by a combination of fences, walls, and hedges. I was previously drawing hedges as simple textured cubes. That may be okay for fences and walls, but plants are shaped more organically than cubes. They look fine from a distance, but bad close up. I decided to generate a cube-shaped shell of leaves draw as individual quads in random orientations, and instance these over nearby hedges. This adds no measurable frame time but definitely improves the look. The new hedges have more detail and volume, though you can still see the underlying cubes if you get close enough.

New and improved hedges that have random leaves sticking out of a textured cube to give them more detail and volume.

Umbrellas

This was a silly one-off change. I thought it would be interesting to add umbrellas to most of the pedestrians when they were walking outside in the rain. (Yes, I do have full weather simulation and effects that work in all gameplay modes.) I found a simple umbrella 3D model online and added code to draw it above 75% of people when it's raining outside. Here is what that looks like.

A partly cloudy, rainy day where most of the people on the sidewalks are carrying umbrellas.

Pushable Objects

Now we get to the changes I made to building interiors.

I added a gameplay action key to allow the player to push objects placed inside buildings. This works with smaller objects that can be picked up and carried such as chairs and small tables. It also works with large furniture and appliances that are too heavy for the player to steal such as refrigerators, couches, beds, dressers, and bookcases. Basically anything not attached to the wall or floor is pushable. The heavier the item, the longer it takes to push it around. I allow the player to push items into closets but not out of their starting rooms, to keep the pushing logic simple. Items can be pushed into doorways or against doors to prevent them from being used. This is helpful for keeping zombies out of certain rooms, but can also restrict the player's movement. I later added another key to pull objects so that they can be moved away from doors, etc.

There are now separate keys for "take", "interact", "push", "pull", and "flashlight". I had to add multiple player crosshair colors and shapes to indicate which items can be taken vs. interacted with vs. only pushed/pulled.

Rolls of Tape

This was a fun mini-project to work on. I already had spray paint, markers, and toilet paper that the player could make a mess with in gameplay mode. I decided to add rolls of duct tape that could be used to stick tape on objects and wrap it around building interiors. Tape rolls of various colors can be found in drawers, in boxes, and on shelves. These can be picked up and used by the player. The action key will toggle between "stick tape to nearest object" and "rip off tape and stick the end to something". In between the tape will unroll as the player walks around, wrapping around objects such as walls, doors, and furniture along the way. The tape roll will shrink along the way and eventually run out, but the player can also backtrack to remove and recover the last unstuck segment.

Here's an example screenshot of two colors of tape stretched across a hallway.

My artwork created with black and gray duct tape stuck to the walls of this hallway.

This doesn't work perfectly. Sometimes tape will go slightly through objects, or won't stick to them in the correct places because their bounding/collision shapes don't exactly match how they're drawn. There's also no collision detection between the player and building AI people vs. the tape. Oh, and it doesn't quite work right if you try to pull a line of tape into the elevator with you and go to a different floor. I have no idea how to handle that case. I suppose the tape should break as it likely would in that situation in real life. But on the plus side it's fast enough that you can put down a ton of tape, and it stays in the buildings forever.

There's no real gameplay mechanic for tape at the moment. It's the same for spray paint, markers, and toilet paper. Maybe at some point I'll allow the player to block off doorways, hallways, or objects with tape to limit the movement of enemy zombies. It could be too overpowered though. I also feel that the tape should restrict the player as well, but then I would have to add a tape removal mechanic to keep the player from trapping themselves in a room. (This is also why I had to add a "pull" action to counter the "push" action.)

Improved Basements

The basements in some houses didn't look very much like basements, and were a bit disorienting with their random interconnected rooms. I added more basement items, including water heaters with pipes and laundry baskets in laundry rooms. I also made the exterior walls a darker concrete block texture that has good contrast with the stucco/plaster interior walls. Knowing where the exterior walls are helps the player navigate in the basements of large/complex houses in the absence of windows.

Here's an example of the new basement look. The planet picture looks a bit odd here, but I don't feel the need to change that right now.

The new basement look: water heater, laundry basket, and concrete block exterior walls. I'm still holding the infamous tape roll I used in that hallway above.
   

Close-up of a water heater, complete with warning label. Only some of them have the label.

Clothing

I've finally started to add clothing, beginning with colored shirts hanging in closets. Right now they're simple 2D textured billboards with alpha masks to make the edges of the quads (outside of the shirt fabric) transparent. I haven't figured out how to make them properly 3D, due to a combination of performance issues with high vertex count models, and the lack of free shirt 3D models. At least they're properly hung on the hangers and cast nice shadows. And as always, the player can steal both the shirts and the hangers.

Colored shirts hanging in the closet, drawn as alpha masked billboard quads.

I plan to make them sway back and forth when the player bumps into them eventually. That seems like a lot of complexity to add for such a simple effect though. Maybe I'll also add some designs or logos to shirts.

Saturday, September 4, 2021

Residential Neighborhood Improvements

This is just a short post on my improvements to 3DWorld's residential neighborhoods. I've now fixed most of the problems with driveways and garages. For example, I widened the right angle bends of driveways coming out of garages so that cars should have enough space to turn. I added walls, fences, and hedges to separate the different yards from each other. I also added in-ground rectangular swimming pools to some of the back yards.

Here's an update screenshot. You can see that I now allow a mix of commercial office buildings and residential cities.

Residential city with skyscrapers in the background. There are now walls, fences, hedges, and swimming pools.

And here's a screenshot with cars and people enabled. I fixed the placement of swimming pools so that they're not next to roads.

Residential city with cars and pedestrians enabled.

I spent some time working on pedestrian path finding for residential areas. I might post a longer discussion on this, but here's a brief overview of the system. People are randomly spawned on a sidewalk outside the player's view. Each person has a destination in their current city, which can either be the door of a house or a car parked in a driveway. Pedestrians now walk on the sidewalks next to roads rather than through city blocks and yards. I moved the streetlights, traffic lights, and fire hydrants off the middle of the sidewalk and to the edge of the road to allow them more collision-free space for walking.

A unique requirement of residential cities is that people can't walk through other residents' yards, except for their neighbors in the same block if there are no fences, walls, or hedges around the property. This initially created some problems where people got stuck against fences/walls/hedges trying to go around the block to get to their destination. My final solution was to first place their target at the point on the sidewalk closest to their destination house or car. When they're close enough to this point (within the axis aligned projection of the house/car onto the sidewalk), they can walk into their own yard to complete the path. That worked surprisingly well compared to some of the other things I tried.

Monday, August 30, 2021

Connecting Procedural Cities with Roads

It's time to revisit my city connector roads, which I implemented a few years ago but haven't touched since then. The problem statement is that I've generated some number of procedural cities (8 in this example) on the island map, and I want to connect them to each other with roads that cars can use to drive between cities. There are constraints that roads can't intersect each other or the wrong city, can't travel over water, and have a limit on slope when following the terrain. The goal is to find a lowest cost valid path from one city to the other taking into account path length, elevation change, and number of turns. There's also an option to add bridges and tunnels to span areas of high elevation change. Bridges are added when their construction cost (based on span length) is lower than the cost of filling in the terrain under the road, in cases where the terrain is too steep for the road to follow it. Tunnels involve weighing the cost of cutting through terrain vs. leveling it out to a reasonable grade.

The original code created two types of connector roads, a straight road from one city to the other, and a road consisting of an east/west segment and a north/south segment with a single bend between them. These two types of roads were enough to connect most of the cities together. One simple improvement is to allow connecting cities with a path having a single jog consisting of three segments plus two bends. This is just one more segment and one more bend than the previous case, but the existing code is very messy and special cased.

The first task was to separate out the various blocks of code that assign the road points/segments, determine if segments are valid, calculate segment cost, actually place the roads, and connect the segments to the road graph so that cars can navigate them. The goal is to have these different pieces be modular so that I can select between different road assignment algorithms and share the rest of the code. The optimal structure is for these stages to create or take a list of points defining the path of the road, where the road itself is constructed by expanding the segments between points by the half width of the road. This transform replaces the 2D rectangular area math with a simpler points-and-lines system. Since the roads are all a constant width, it's also possible to expand the collision objects by the road half width so that collision tests can use faster point containment checks rather than box overlap checks.

With that refactoring out of the way, I was able to experiment with new routing solutions. I first added the three segment roads and fought to make the road placement system accept that. The results were a bit more optimal in path length and elevation change, but overall didn't look very different. Then I attempted the next big idea of using the terrain heightmap with a path finding algorithm that traced the road across the heightmap grid to connect the endpoints. The plan was to eventually use the A* (A star) algorithm to improve the speed of the brute force force depth first search. I spent many hours trying to get this working, but had to eventually give up and revert the changes. There were several major problems with this approach:

  1. It was slow. The heightmap is roughly 7000x7000 pixels, which is 50M elements. While most roads only spanned a small subset of the island's area, walking across hundreds of pixels for each road segment to calculate costs took quite some time. This drove the road routing cost from ~50ms to several seconds. Even using the A* algorithm won't get the time down to what it was.
  2. Trying to connect the grids was a huge mess. Each city has its own custom spaced grid of roads that's not aligned to the heightmap grid. A single road is something like 2.35 heightmap pixels wide, not an integer value. I had to create short road segments to connect the point on the city road grids at each end of the path to the heightmap grid, where the connectors were odd off-grid segments. This caused a lot of problems with floating-point rounding errors, segment overlap, etc.
  3. I never figured out how to correctly account for the slope of road segments. A single segment is on the order of a hundred terrain grid points in length. Each new grid added to the segment changes the elevation of the endpoint of the road, which affects the slope and the amount of material to add or remove under the road for the entire segment length. In theory I have to recalculate the cost of the entire segment after moving an endpoint. It's not easy to place a global constraint on max segment slope when adding one incremental grid at a time.
  4. I want to minimize the number of right angle bends in the road to make it more realistic. However, it's not clear how to take the number of bends into account when calculating costs for A*. I don't have a good upper bound on the cost of the best path.
  5. I don't actually have a plan for this. I have no reason to believe it will create anything better than what the current (simpler) algorithm will create. Are roads with many bends realistic? Maybe only in the mountains. But the current solution, which tries to avoid mountains to begin with, might do a pretty good job already.

That's a shame. I was really hoping to get some funny road fails such as in my previous post. It looks like I've added a lot of error checks to prevent those problems since then, and I really can't get the road placer to do anything wrong + interesting. No crazy epic fails. It will either fail to add the connection or exit with an error if I try to force it to add strange or incorrect roads. I even tried to create a serpentine road that switched back and forth between different orientations, but I couldn't get it to successfully place any roads like that. I suppose there could be various reasons why. Those roads take more space and are more likely to collide with something, and have higher cost. Having all those short road segments is probably going to fail the max slope checks for at least one location as well. Sorry, I guess I don't have a silly screenshot to post of random switchbacks in the flat plains next to the city.

Anyway, here is what the city connector road network looked like with the old algorithm. Cities are the regular grids, roads are gray lines, and all the small colored squares are buildings. Bridges are white, tunnels are brown, and parks are green. Roads and cities can't be placed over water (blue) or mountains (gray/white). Note that this isn't the full 7Kx7K island; it's closer to 5Kx3K pixels.

Cities and connector roads using the old algorithm. 12 roads, 2 bridges, and 3 tunnels, cost=19.

And here's what I get with the new algorithm that allows three segment/two bend connectors.

Cities and connector roads using the new algorithm. 16 roads, 0 bridges, and 1 tunnel, cost=26.

I count 7 of the new connector road types. There are more roads, but also a higher road cost. This makes sense because cost is summed across all roads in the scene. The average cost per road has increased from 1.58 to 1.69, likely because of the added cost of road bends and the improved ability to connect two distant cities. There's now only one tunnel and no bridges. I believe that's because the new algorithm has more freedom in placing roads due to the extra segment/jog, so it can avoid the cost of building bridges and tunnels to pass through steep terrain.

Is this result better? I'm not sure, maybe. It depends on whether we're trying to maximize connectivity or minimize cost. However, the new algorithm does scramble around all of the secondary buildings. The new building layout around the starting point is now completely different, which makes it easier for me to get lost. I liked the old layout where I knew which buildings had which interesting layouts, architecture, or items. So I think I'll probably keep the old road network, but leave the option to switch to the new one.

Overall, it's not clear if this was a waste of time or not. I definitely cleaned things up in the code, added error checks, experimented with different solutions, and added more configuration options. Maybe I'll get back to this sometime later. Now it's time to move onto something else.

Tuesday, August 10, 2021

Procedural Buildings: House Improvements and Residential Neighborhoods

I've been working on improving the look and placement of procedural houses over the past two months. After finishing up the room object placement project, I went back and made some rooms into garages for houses that didn't already have detached garages. Then I converted the chimneys of some houses from roof decorations to exterior chimney geometry with proper fireplaces. Now that houses are nearing completion, it's time to use them to create proper residential neighborhoods with grassy plots placed inside grids of roads. These changes are described in more detail below.

This post is rather long, and maybe should have been split up into two smaller posts. It started out shorter but kept growing in length as I fixed various problems and added text and images for my fixes.

Garages

I've had detached garages as separate buildings off to the side of houses for a while now. They're relatively rare because they can only be added to the inside part of L-shaped houses without going outside the valid building bounds. Most real houses have garages, so I needed to add additional garages to the main floorplan of some houses.

It was difficult to fit this step into building generation in a way that didn't require significantly changing the control flow. The current house generation algorithm determines the exterior walls first, then places windows and doors, then generates the walls, and finally assigns rooms. Garages are special because they're integrated into all of these steps in some way. The garage is an assigned room, and its door replaces windows and is aligned to the side wall. It wasn't clear exactly where garage assignment should be done in this control flow, because it requires knowing the interior walls before a room can be assigned to be the garage. So I had to special case the garage room assignment to happen earlier in the control flow, just after the interior walls are added. The garage door then removes windows that overlap it. I moved the exterior door assignment after garage selection. If the door is placed too close to the garage door, I move it to the opposite side of the house or choose another door location.

I used several different heuristics to weight rooms as garage candidates, and then choose the candidate with the highest weight. Garages must be large enough to fit the largest sized car (but not a truck), and have a higher weight when their aspect ratio is close to 1.75. Garages also have a higher weight if they have exactly one door to the house, and a high weight if they're against an exterior wall on two sides. They must have at least one exterior wall to place the door in.

After several attempts/iterations, I have it working. Some garages have parked cars in them. Some have shelves with objects placed along one or more walls (except the wall adjacent to the door). Here's an example screenshot of the interior of a garage.

A car is parked in a garage attached to this house. There are storage shelves next to the window.
 

Chimneys and Fireplaces

Most of my generate houses have chimneys on the roof, but they're simple placeholders that aren't connected to anything. I wanted to make them look more like real chimneys, and connect to interior fireplaces. The first step was to move some of the chimneys outside the footprint of the house so that they're against the exterior wall. My real house has a chimney like this. The fireplace is a (possibly wider) cube at the bottom of the chimney that spans most of the height of the ground floor.

Chimneys turned out to be more work than I expected. Adding exterior chimneys changed the house's bounding cube slightly, which lead to various minor issues that I came across a week later. Removing windows and doors that overlapped the chimney and fireplace was also tricky, because it lead to some window strips with odd lengths that couldn't fit an integer number of windows. The existing window placement system was coupled with the exterior wall generation so that it created whole windows, but I didn't want to try and stuff the chimney generation code into that control flow as well. Instead, I simply removed the partial windows, so that short walls sections next to chimneys were windowless.

The next problem I ran into was placing the fireplace. The easy part was adjusting room assignment to not make rooms with fireplaces into bathrooms, garages, laundry rooms, etc. While fireplaces usually go in the living room, I allowed them in bedrooms, dining rooms, and kitchens as well. This took some pressure off the room assignment algorithm and made it more likely to succeed.

The difficult part was handling walls that intersected the fireplace. It's certainly not correct to have a fireplace that's split across two rooms. However, when I got to this step in the control flow, it was too late to move the chimney/fireplace because then I would have to update the windows and doors again. I considered moving the walls instead, but that would invalidate things like garage placement. I'm sure I could always give up and regenerate a new house until the fireplace can be successfully placed, but that wasn't a great solution. All of these different constraints are too complex to manage. In the end I settled on only adding fireplaces when there's no wall in the way. This means that some chimneys still connect to nothing, but it's better than when they always connected to nothing. I don't think this would be too obvious to the player anyway since this case doesn't happen very frequently.

Here's an example of a fireplace placed in a living room. I also had to update the algorithm that placed rugs and furniture in the rooms so that they didn't block or intersect the fireplace. Maybe sometime in the future I'll place objects on top of fireplaces or otherwise improve their looks.

A fireplace has been added against the exterior wall of this living room.

Residential Neighborhoods

At this point I had two types of areas: cities full of office buildings placed in a grid of roads, and randomly placed houses and other secondary buildings with no roads. I've been trying to connect the secondary buildings with roads, but so far haven't been successful. What I have are buildings placed in a rural setting, but too close together. There are too many hills and not enough straight line spaces between buildings to place roads. I'm sure I could squish some windy roads between everything, but it wouldn't look very natural. No city planner does something that insane.

I gave up on that approach and decided instead to use the existing city road grid system to create residential neighborhoods. The main change was to place a large number of houses rather than a small number of large office buildings, but I had to make many other changes as well. The concrete sidewalks and pavement was replaced with grass lawns. Benches were removed. Parking lots were replaced by driveways. I kept the scattered trees, rows of trees along the streets, and city parks though because they seem to work with residential neighborhoods as well.

Here's a screenshot of an early attempt at a residential neighborhood. It was a good start.

Early attempt at a residential neighborhood with houses placed in the grassy areas between a uniform grid of roads.

Here you can see several issues, and there are more that aren't visible in the screenshot. Some houses are missing driveways, or have garages facing the wrong way. Others have streetlights blocking their driveways. I suppose having garages on the wrong side is the biggest problem. I'll explain how I handled that below. As for streetlights, I added a check for driveway intersections and moved the streetlight to the side of the driveway closest to its starting position.

I suppose another issue is that there are too many roads and too few houses. Most blocks have between 6 and 10 houses, which isn't very many. However, if I make the blocks larger, then the placer does some strange things. I already add an area in the center of the block where no houses can be placed to prevent interior houses that don't share an edge with a road where a driveway can be added. That works to some extent, but when the block is large enough other bad things can happen. Maybe it would be better if I made the road spacing different in X vs. Y so that the blocks are long an thin, with two long rows of houses on either side? Maybe it would work better if I divide the block into plots ahead of time such that each plot borders a road, and then place a single house on each plot. This is how city planning usually works, so it must be a good idea, right? That required significant changes to the building generation code, but gave me some interesting results.

Dividing city blocks into a uniform grid of house plots produces evenly spaced small houses.

Well that looks okay but not great. The houses are relatively small and have a very regular placement with 8 houses on most blocks. The reason they're small is because I had to add some spacing between the individual plots to make sure I can fit driveways and other details. Maybe there's too much spacing, and houses should be larger, or placed more densely per block? How about decreasing the spacing:

Uniform blocks again, but this time with less space between houses so that they can be larger.

Does that look better? I think so, but it's not obviously better than the original random house placement. I think I like the previous look of the houses because there's more variety in their sizes and placement. Maybe this plot assignment would look better if I insert some sort of border between the plots such as fences, hedges, or even slightly different colored grass. I added a config file option to switch between random placement and uniform plot placement. I'll get back to experimenting with this later, and maybe enable it if/when I space the roads further apart.

I enabled cars and pedestrians to test out how they worked. Cars can drive on the roads (as usual) or park in driveways. People walk to houses and parked cars. They really like to cut through the yards though, so maybe I need to add some fences around the properties to prevent them from trespassing. I suppose they would be less interesting to watch with that change.

Here's an updated screenshot with some of the fixes and improvements. I don't see anything obviously wrong here, though there are still some issues if you look for them in other parts of the city.

Residential neighborhood with cars on the roads, cars parked in driveways, and people walking around. I placed a Ferris wheel at the end of the street in the distance.

Placing driveways turned out to be challenging, and I still don't have it completely worked out. The driveway placement code first attempts to connect a garage to the road. Since garages currently are placed on a random side of the house, this is only successful 25% of the time, or 50% of the time for houses placed on the corner that can connect to either road. If this fails, or the house doesn't have a garage, then it attempts to connect the driveway to the nearest edge of a cube of the house, taking care to avoid chimneys/fireplaces. (I should probably move the outdoor AC units off driveways as well.) If this placement step fails it will instead add a driveway along either the left or right side of the house. Houses are placed such that there's always room for a side driveway, though two adjacent houses can have their side driveways between them overlapping each other. I suppose this is okay, because it creates what looks like a single wider driveway. Then I have to check for two overlapping cars on those driveways.

I haven't quite decided how I want to handle garages that are placed on the wrong side of the house. I guess I can start by calculating the edge(s) of the house closest to the road and passing that into the house generation code. Then at least I know if the garage is on the wrong side. If it is, I can use the brute force solution of regenerating the house until the garage is on the correct side. If that turns out to be too slow or messy, maybe I can rotate or mirror the house to put the garage on the proper edge? Or maybe choose a less optimal room as the garage, for attached garages? I'm not sure, I'll have to experiment with it.

... Okay, after experimenting, I've improved it somewhat. First of all, I can make sure detached garages are placed on the side nearest the road by mirroring them to the opposite side of the house if needed. If their entrances are in the wrong dimension (X/Y), I can make the driveway come out and make a right angle turn to meet the road. It seems like there's enough space between the houses to fit the turn, though it sometimes looks a bit odd. For interior garages, I can limit them to the side of the building facing the road, relax the constraints on size a bit, and not add a garage if this fails.

Here's what one of these right angle driveways looks like. I tried swapping the garage direction, but that causes other issues with placement and I gave up on that approach. It's not the best solution, though I suppose it's better than not having a garage or having the driveway unconnected.

One of those funny right angle driveways that has to be used because the garage isn't facing the street and there's not enough space to rotate it 90 degrees.


I really should add fences between some of the houses, at least when using a uniform grid of plots where the fence location can follow the plot boundaries. Maybe I should add swimming pools and other yard objects. That's a good task for some later time. I have such a long list of features to add! Every time I implement something, I add one or more items to the list.

Here are some screenshots of a somewhat overhead view of a residential neighborhood during the day and at night. I have cars, pedestrians, and people in buildings enabled. The night scene includes light from streetlights and dynamic car headlights. Everything I mentioned above has been fixed, including the garages connected to driveways and the streetlights blocking driveways.

A residential neighborhood show during daytime.

The same residential neighborhood show at night time. The moon is out so it's not as dark as it could be.

I also made overhead map view work correctly with residential cities, including drawing of driveways and parked cars. Here's an example showing the same city as the above images. This map is interactive and shows the cars moving in realtime. I can pan and zoom to inspect the layout of houses, driveways, etc. It may look like some driveways are missing, but I believe all houses have driveways.

Overhead map view of the same residential neighborhood, showing houses, driveways, and cars. The green square at the top is a park.

Oh, and just for fun, here's the result of incorrectly setting the house size too small compared to the plot size. This produces tiny square houses with a single room and multiple floors.

Tiny single room, multi floor houses resulting from a bug in the building generation logic.

In theory this system should scale to residential neighborhoods out to the horizon over multiple square miles. The most I've attempted so far is 18,000 buildings + 8,000 cars + 60,000 people. Keep in mind that all buildings have procedural interiors, and (non parked) cars and people are dynamic with their own AIs. I'm not sure how much higher I can make these numbers before I run into issues with memory usage and frame rate. I'll likely experiment with this later to see how large and how many cities 3DWorld can handle.

Sunday, June 6, 2021

Procedural Buildings: Making Everything Interactive

My new goal for procedural buildings gameplay mode is to make nearly every object interactive. This includes all of the various smaller objects, appliances, room fixtures, etc. Basically anything that can be picked up or has moving parts. When I say "interactive," I mean the player can either pick them up and somehow use them, or use the interact key on them in-place for some effect (animation, sound, state change, etc.) Any object a person would expect to be able to pick up or change in a real building should be interactive here. At this point I've handled the majority of smaller objects, as explained in the sections below.

New Interactive Objects

I've added lots more object types that the player can be picked up and use. In addition, I made the mouse wheel switch between usable items so that the player can freely select among the inventory items. This allows for more flexibility and improved player "artwork." For example, if you have multiple colors of spray paint or whiteboard markers, it's much easier to change colors to create more complex designs.

The player can now either pull the toilet paper down from the hanging roll, or remove rolls of toilet paper from the holder. These removed rolls can then be carried around and dropped one square at a time on the floor or on top of other objects. I originally intended to stretch the paper out in a continuous band so that it could be wrapped around objects. Unfortunately, I was never able to make that look visually correct, or behave properly when the player or AI walked through it. Instead, I had to go with simpler individual squares. A single roll has 200 squares, and the roll will gradually decrease in radius until they're all used up and the inner tube is all that remains.

Check out my toilet paper artwork, made with individual TP squares dropped on the floor.

Kitchen cabinet doors can be opened, similar to desk/dresser/nightstand drawers. They don't yet contain items. I haven't modeled or drawn the cabinet interiors, so for now they simply show as black quads drawn over the opening. I also tried adding transparent holes, but those only show the interior of the wall behind the cabinets. It's not great, but it's better than drawing the cabinet faces and making the doors look fake. I'll have to get back to this and improve it later, then hide additional items in cabinets.

All of the kitchen cabinets have been opened. There's no interior yet, just a black hole sucking up all the light.

Kitchen sinks, bathroom sinks, and bathtubs can now be turned on and off. Sinks have simple animated water drawn when turned on, using a single partially transparent textured cylinder. The nearest sink generates a looping sound of running water that fades with volume based on the distance to the player.

Both bathroom sinks have been turned on, showing running water. It even shows in the mirror reflection.

Players can now enter and hide from zombies in bathroom stalls and showers, as long as the doors are closed. This will display a "[Hiding]" message near the bottom of the screen so that the player is aware that they're safe. I'm not sure how much sense it makes for someone to hide from a zombie in an all glass shower, but it was fun to add. It's not like my zombie gameplay makes much sense anyway!

I'm hiding in this shower stall with the door closed, and the zombies in this room are too dumb to notice me.

The player can interact with various appliances. Microwaves beep, TV channels can be changed, and computer monitors can be turned on and off. I plan to eventually make the rest of the appliances interactive in some way. Maybe I can figure out how to open the doors on some of the 3D models.

Players can open and close the blinds on house bedroom windows. This works with both the vertical and horizontal styles of blinds. I haven't implemented the logic to change the ambient lighting in the room because it's unclear how to do that efficiently without re-processing the lighting for the entire building. If I ever find a better way of doing indirect lighting, I'll make this work somehow.

Basketballs and soccer balls can now be throw at other objects to interact with them as well. For example, you can throw a ball at an elevator button or light switch to press it. (Since balls aren't normally found in office buildings, I allowed the player to carry items between buildings in some cases in order to test this.) Balls can be thrown at TVs and computer monitors to turn them on and off. I plan to model damage to these types of items and maybe also windows by adding crack decals in the future. Another example is that balls can be thrown at pictures hanging on walls, which will tilt them.

Boxes

I explained how items can be nested inside other items in my previous blog post. What better way to increase the level of object nesting than allowing players to open boxes, revealing another level of hidden items inside. Unlike drawers that can only contain a single object, boxes can contain as many objects as will fit. I've written a placement algorithm that will attempt to stack them up or place a X by Y array of objects inside. These objects include books, toilet paper, paint cans, spray paint, bottles of water/coke/beer/wine, soccer balls, and basketballs. The contained items are less interactive and can't be used as consumables (power-ups) to make the game a bit more fair for the zombies.

When open, the 3D model of a box changes to expose the four open flaps. I check for collision of each flap with the room walls to avoid incorrect geometry intersections. These colliding flaps are bent further upward to avoid the wall. This can be seen in the bottom box in the stack to the right of the image below. Note that box flaps are not yet checked for collisions with other adjacent or stacked boxes.

All of the boxes in this storage room have been opened, revealing wine, spray paint, books, etc.

This change significantly increases the total number of items found in buildings, especially those with many boxes. However, these nested items aren't generated or drawn until the player opens the box. So I don't think it's going to affect performance too much unless the player spends hours opening thousands of boxes across many buildings in a local area. Note that once a box is opened, the state will be saved even if the player moves far away from the building and comes back.

Closets

I had previously only allowed the player to open and enter smaller closets with standard hinged doors. Now I've extended this to all closet shapes and sizes. Medium sized closets have doors that fold to each side, and larger/wider closets have doors that slide to each side. Since these closets have more interior space, they can contain a wider variety of items. This includes the usual boxes, and also lamps, computers, keyboards, and paint cans.

Here's an example of a closet with folding doors, followed by a closet with sliding doors, followed by a different closet with folding doors. I turned the closet lights on to make the items on the floor easier to see.

A medium sized closet with folding doors containing a lamp, box with a soccer ball, and box of colored spray paint cans.

A large closet with sliding doors containing a computer, box of toilet paper, basketball, etc.


A closet with folding doors containing a lamp, can of paint, computer, and some boxes.

Each closet has its own hanger rod and ceiling light that can be turned on and off by the player, or stolen for money. The player can close the closet doors and hide from zombies. When the doors are closed and the light is off, the interior of the closet is very dark. At some point in the future I may add clothes hanging in the closets.

Light Switches

The player has been able to turn room lights on and off with the 'S' key for a while now. However, I thought it would be better to add light switches to each room. These are generally placed next to a door in a way that the open door doesn't block them, and they're not obstructed by furniture and other objects. Rooms with exterior doors have multiple light switches, one at an interior door and another at an exterior door.

Every room now has at least one light switch on a wall next to a door.

I used white wall plates with rocker switches that change position when the player uses the interact key. This is the style of light switches used in my actual house. Each switch will toggle all lights in a room, unless the player has stolen the lights from the ceiling.

Book Stacking

Up to this point, soccer balls and basketballs were the only type of item the player could pick up and throw/drop. That's no fun, we need more drop-able items. I decided to allow the player to place books on the floor or any other flat horizontal surface, including stacking them on top of boxes and other books. The stack can be made as tall as the player can reach, or up to the ceiling when collision is disabled (flying mode). Books can be picked up again from the stack if they have nothing resting on top of them - in other words, only from the top of the stack. Stacking books on furniture such as nightstands and tables prevents the player from taking those items unless the books are removed.

Books stacked by the player on a table. Each stack has proper collision detection within the stack.

Books can now be removed from bookcases. Between individually placed books and those found in bookcases, drawers, and boxes, there are plenty to work with in most buildings. Some of the larger buildings contain thousands of books. There's no hard limit on the number of books that can be brought to one place.

I haven't added any true gameplay purpose for books yet. Maybe I'll allow players to throw them at zombies. Maybe I'll enable collision detection so that they can be stacked up to block the path through a doorway. Or maybe I'll hide something of value in some of them. I'll have to think about that later.

Friday, April 30, 2021

Procedural Buildings: Object Management

I've explained how 3DWorld generates procedural buildings and populates them with objects in previous posts. My cities test scene contains about 15,000 total buildings. Together they contain on the order of:

  • 40K shapes (mostly cubes)
  • 100K floors/stories
  • 600K rooms
  • 2M walls (cubes)
  • 1M doors
  • 10M placed objects (not including nested/contained objects) - my best guess
  • 25M nested objects - my best guess
  • 2B+ triangles - my best guess

How is 3DWorld able to generate and draw all of this in realtime? I use various tricks, including "only generate and draw what the player can see." Let me break them down by category and describe them in some detail. This is going to be a long post full of mostly text. If you're not interested in all the technical details, you can skip to the short elevator video at the bottom.

 

Generation

I currently place all buildings at once during scene load, and generate their exterior geometry on multiple threads in parallel. I do have a tile-based system that will generate blocks of buildings as the player moves around, for potentially infinite cities. This works pretty well, but has some drawbacks. For example, there can be some framerate stutter when generating new building tiles.

But the biggest limitation is that I haven't figured out how to get people, cars, and helicopters to properly interact with buildings generated per-tile. My goal is to have a living world where everything is simulated for the entire city, even if the player can't see it all. This means that you can walk or fly around very quickly and any AI agents that you see are in the process of going somewhere. If I was to generate a building when it first becomes visible, then all the AI's interacting with it would appear in their starting states. That can look unnatural, for example if a person is spawned in a location that intersects furniture. It's also not possible to model things like road/hallway congestion that has accumulated over time when using this approach.

So for now I'm generating all of the buildings and their large scale geometry during scene load. All I really need is the rough exterior geometry that's visible from the distance, the windows for night lighting, and a rough floorplan for the AI people to use in path finding and navigation.

 

Exterior Walls and Windows

I've explained how exterior walls work in previous posts, so I'll give a shorter update here. I use a view distance of several miles, so building exteriors are visible from very far away. In addition, their window lights can be seen in the distance at night. This means I need to draw not only a lot of buildings, but also a huge number of windows. Drawing every window with individual polygons would be slow and take significant GPU memory.

My solution was to split the exterior walls and windows into two different drawing passes that use the same vertex data (quads). Windows are drawn first, and the pixels are written to a stencil buffer that's used to mask the areas where exterior walls are drawn. A horizontally and vertically repeated texture is used to control the location of each window within a wall quad. The interior part of windows are nearly transparent so that the player can see through them, while the surrounding frames are opaque. (Window panes are also drawn as emissive for night lighting.) The space between windows that should remain as walls uses an alpha value of 0, which is rejected by the alpha test, skipping writing to the stencil buffer.

With this solution, I can create an unlimited number of building windows by drawing each wall exactly twice using vertex data that's partially shared. In fact I only need to draw windowless sections of walls once. The actual implementation is more complex than this, but that's the high level idea. This system has worked pretty well so far.

However, there's something missing here. Since windows are drawn as quad cutouts, they have no depth. Exterior walls are zero thickness. Doesn't that make things look wrong? Well, it's not clear that walls have no thickness when viewing distant buildings because the inside edges of the windows aren't really visible at that distance anyway. When the player gets close to a building, I generate and draw window frames that do have some thickness. These cover up the edges of the walls so that you can't even tell that they're simple 2D quads with two different wall textures on the outside vs. inside. I can hide all of this so that it appears correct to the viewer.


Interior Walls, Ceilings, Floors, and Doors

There are two high level approaches for drawing building interiors: Generate, store, and draw them per-building, or batch them across buildings. I chose to batch across buildings to reduce the number of draw calls to a reasonable number, which improves frame rate at the cost of increased GPU memory usage for storing geometry that may not be drawn. The downside of batching across buildings is that I have to generate and draw vertex data for many buildings that aren't actually visible. Note that I took the other approach for smaller and more numerous interior room objects, as described later.

The second reason I generate rooms, walls, and doors for every building in advance is that it allows me to place people in rooms and simulate their movement within the building. I don't need to place all of the objects in rooms to get the AI working, but I do have to generate a basic floorplan. The goal is to have a system that can simulate people in buildings even if those buildings aren't currently visible to the player.

I generate the entire interior wall, floor, and ceiling geometry for each of the 15K buildings in the scene at load time. There are over a million walls, so isn't this very wasteful? Well, there's a trick I can play. If I use the same vertical/stacked floorplan for a range of floors, I can actually have the walls extend through much of the building so that the same triangles are shared across many floors. I can also skip drawing of the top surface, bottom surface, and any invisible/hidden edges of walls. Ceilings and floors are even easier: I only have to draw the bottom surfaces of ceilings and the top surfaces of floors.

I initially tried to use that same approach with building interior doors, where a single door face extended the entire height of a building section and was shared by multiple floors. It worked well until I allowed the building AI people to open doors. The problem is that it looks very wrong when the AI on a floor above or below the player opens a door in front of you. Why did that door just open? Was it a ghost? The obvious solution was to split the doors into separate drawn objects for each floor, but that nearly doubled GPU memory usage for building geometry from 490MB to 880MB.

Why was I generating every door for every building ahead of time again? Right, so that they could be batched together, because the player can see the interiors through the windows of many buildings even if they're far away. But it's not as easy to see the doors through windows. In fact they're the same general whitish color as the walls they're attached to, so they blend in pretty well. We can simply skip drawing doors for distant buildings and only generate them for nearby buildings as the player comes in range of them. The visual difference is barely noticeable. Maybe walls are better off generated for every building and drawn as large batches, but doors can be treated as interior objects and drawn separately for each nearby building. That was quite a big code change, but overall I'm pretty happy with the new system. I believe it's more efficient to draw doors this way as well.


Placed Objects

I've discussed exterior and interior building walls, windows, floors, ceilings, and doors. That leaves the vast majority of building objects/triangles: all the stuff that's placed in rooms. This includes objects such as furniture, appliances, lights, stairs, pictures, rugs, clutter, etc. These placed items are what make rooms look like bedrooms, bathrooms, kitchens, and offices. I'm not sure exactly how many of these items there are because they're not all generated at once, but I'm pretty sure there are at least 10M of them across all buildings. If there are 15K buildings, and buildings can have dozens of floors, hundreds of rooms, and dozens of items per room, that really adds up quickly.

These objects span a wide range of polygon complexity:

  • Textured quads (rugs, pictures, papers)
  • Simple generated collections of cubes (tables, books, desks)
  • Mathematical shapes/curves (spherical lights, round tables, trashcans, pillows)
  • More complex generated collections of geometry primitives such as cylinders, cones, spherical sections, etc. (bottles, railings, elevators)
  • Full 3D models loaded from files with tens of thousands of polygons (appliances, furniture, people, cars)

The key to making this efficient is placing the objects in a building only when the player is close enough to see them. These objects are only drawn when the building is within the player's view frustum. But that's not good enough, some of the larger office buildings can contain more than 10K objects, which include over 1M triangles, and can't be generated within a frame's ~16ms budget. I use several tricks to overcome these performance limitations.

First, my system never stores triangle geometry for more than one building on the CPU side at once. Each room object is represented as a bounding cube, type, color, and various bit flags, for a total of 60 bytes of data. I use a CPU side geometry buffer for expanding these objects into quads and indexed triangles that's shared across buildings. Once this vertex and index data is sent to the GPU, it's no longer needed on the CPU. It's fast to regenerate everything, and can use multiple threads, so we're free to swap the geometry of different buildings in and out to manage GPU memory usage. Furthermore, I can split the objects by type or material and divide those updates across multiple frames to help smooth out the framerate.

The next optimization is the inside/outside test. Each room is tagged as interior (windowless) vs. exterior, and has various bits representing which walls contain windows. When the player is outside a building, none of the objects placed in interior/windowless rooms are visible or need to be generated. Similarly, objects can be skipped if their rooms don't contain any windows on the walls facing the player because the player can't see into these rooms. For example, none of the objects in the basement need to be drawn because they're not visible from outside the building. [It's actually more complex than that, because we have to take into account objects visible through open doorways of rooms with windows as well. The full system is thousands of lines of code.]

Since the player can be in only one building at any given time, this significantly reduces the total amount of objects that need to be drawn. Similar optimizations can be used for the building containing the player. When the player is in a room with no stairs, we can skip drawing of objects and light sources on floors above and below the current floor. This is a good way to limit drawing in the current building where the exterior windows test doesn't help. I've also implemented occlusion culling of objects using the interior walls, exterior walls, ceilings, and floors of nearby buildings. These culling steps are more aggressive when used with high polygon 3D models compared with simple objects like books. There's a trade-off here where performing view frustum culling and occlusion culling on the CPU only makes sense to do on high polygon count objects that are expensive to draw.

The next category of optimization involves nested objects. This includes objects placed on shelves, books on bookcases, objects in closets, items in drawers, etc. These items aren't generated as part of the building or individually placed in rooms as separate objects. They don't even exist at the time the building is created. The items on a shelf only need to be generated when the room containing the shelf becomes visible to the player. Objects in a closet are only generated when the player opens the closet door. Objects in dresser, desk, and nightstand drawers are only generated and drawn when the player opens the drawer. I call these steps "object expansion" because these objects are nested inside other objects and must be expanded into real objects to be included in drawing or player interaction. In theory the system should be able to handle something like a book placed inside the drawer of a desk on a shelf in a closet.

Since each of these actions requires player input, we can have at most one object expansion per frame. This allows the system to handle an immense number of total nested objects hidden inside a building. In fact the object count can be nearly unlimited. In theory, maybe there's a performance problem if the player goes through every room in a collection of nearby buildings and opens/expands every object. However, that would take countless hours of time, and it's not something I'm worried about at this point.

If you think about it, this applies up the hierarchy as well, all the way to the level of terrain tiles. The full hierarchy includes:

  • Terrain tiles, each of which contains several
  • Buildings, each of which contains several
  • Floors, each of which contains several
  • Rooms, each of which contains several
  • Objects, each of which contains several
  • Drawers/Shelves, each of which contains several
  • Smaller objects

The nesting/expansion is exponential here. However, the time taken to generate, query, and draw all of this is almost constant because the expansion factor at every level ("several") is only in the tens. In fact, traversing this hierarchy is so fast that operations such as ray intersection and sphere collision detection take a few microseconds. This is also the key to efficiently simulating thousands of AI people in buildings every frame.

Here's an example of a large 19 story office building containing nearly 1000 rooms. These rooms are full of lights, desks, chairs, tables, whiteboards, trashcans, and all sorts of office supplies. That looks like a lot of triangles, right? What you don't see are the huge number of small items in interior rooms, on shelves, and in desk drawers that may not even have been generated yet. You don't see all of the 3D models of things like toilets in interior rooms. This single building is larger than the levels of most (non open-world) games, and there are thousands like this. This entire thing takes only a few milliseconds to generate!

Wireframe view of a large office building and some smaller surrounding buildings.

Lighting and Shadows

Most rooms contain at least one light source, and most objects cast shadows. Ceiling lights are implemented with both a downward pointing shadowed spotlight and an upward pointing unshadowed spotlight that's constrained to only light the bounding cube of the room. 3DWorld supports up to 1000 active room lights, though distance and visibility culling are generally able to reduce this number to only a few hundred. These lights are prioritized by distance and screen area and only the first 60 use shadow maps. The remaining lights use constrained cube volumes determined by ray casting against the walls, ceilings, and floors to determine the max extents of each light. This both improves performance and reduces light leaking through walls, ceilings, and floors.

Shadow maps are managed by a memory pool with free list to avoid repeatedly allocating and deleting shadow map memory on the GPU. They're also cached across frames when there are no dynamic shadow casters within the light's bounding cube/radius of influence. Dynamic objects such as building AI people, the player, balls, elevators, etc. will force the shadow map of that light to be updated each frame. Typically only a few of the 60 shadow maps are updated in any given frame, which gives reasonable performance. Room object occlusion culling and view frustum tests are enabled during the shadow pass (and reflection pass for mirrors) as well.


Conclusion

Since this post is all text and few images, I'll add a short video at the end showing that I have working elevators. The player can press the call buttons outside the elevator or the buttons on the inside. The buttons and floor numbers light up, and the elevator will go to the correct floor. The doors open and close as well. The elevator has sliding and "ding" sounds that I wasn't able to record in this video.


All of the code can be found in my open source 3DWorld GitHub project. For example, the code to place objects in rooms can be found here.