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.

Sunday, April 11, 2021

Procedural Buildings: Object Interaction

I'm continuing to work on my game where the player steals valuable items from houses and office buildings while avoiding zombies. My goal is to make almost every object inside the building both something the player can steal, and something the player can interact with either before or after stealing it. I also want to make this as silly as possible rather than a horror game. I started with the basic set of player object interactions required for gameplay, and some other easy ones, which were implemented earlier:

  • Picking up objects
  • Opening room, closet, and bathroom stall doors (which may be locked)
  • Opening and closing dresser, desk, and nightstand drawers
  • Turning on and off ceiling room lights and lamps
  • Throwing and kicking basketballs and soccer balls
  • Drinking beverages (wine, beer, Coke, water, and newly added poison)
  • Riding elevators up and down
  • Spinning office chairs

This time I've added many more object interactions to increase the fun level. Why stop at stealing when you can trash someone's house in the process? Add graffiti, make a mess, and run up their utility bills. The zombies won't care, but when those people return to their houses after the invasion, won't they be in for a surprise!

  • Basketballs and soccer balls can now be thrown at zombies to make them temporarily retreat 
  • Spray paint cans that can be used to add graffiti to walls, ceilings, floors, and other flat surfaces
  • Markers that will draw on walls, ceilings, floors, whiteboards, pictures, rugs, mirrors, etc.
  • Turn sinks on and off (to waste water)
  • Flush toilets (to waste water)
  • Pull toilet paper off the roll (future work: wrap toilet paper around objects)
  • Tilt pictures hanging on the wall
  • Various other objects make sounds and/or animate
  • Player can use elevator buttons (fully functioning elevators are in the planning stage)

None of these really affect gameplay, except for the first bullet point where hitting a zombie above the legs with a ball will cause it to retreat for a few seconds. This gives the player some time to get away. I might add other throwable items, such as books, at a later time. None of these interactions affect the value of items the player has or the player's survivability.

Spray paint and markers are my favorite so far. My daughter Kate also loves to make her artwork in the office buildings. Too bad I haven't implemented a save system for this yet! The player must first find a can of spray paint or a marker on a storage room shelf or in a desk drawer. These will be a color randomly chosen from a set of common colors for those items. Picking up this object will allow the player to carry it around and use it with the action key.

Each key press (or each frame if the key is held down) will generate a circular spot of color as long as it's not too close to the previous spot (optimization). Spray paint and markers have a max range and will only write on certain types of large, flat, static objects. This includes walls, ceilings, floors, windows, mirrors, bathroom stalls, cubicles, stairs, elevators, rugs, pictures, and whiteboards. Each spot is an alpha blended point sprite quad drawn with a circular blur texture. Multiple points placed near each other will merge into solid lines of color that look like real brush strokes. These are oriented in the direction of the surface and shifted a bit in front so that they're drawn on top as decals. The draw order is preserved for blending, so the player can paint over existing spots with new colors. Spray paint that's sprayed from far away creates a larger but lighter circle, while close up sprays produce smaller and stronger color spots.

These quads are stored in a dynamic buffer and sent to the GPU each frame. I could probably break them up into blocks and store them on the GPU in VBOs as an optimization. For now it seems to be fast enough that this isn't needed, unless I really expect players to spend tens of minutes painting the walls. The graffiti will remain in the building until the player starts drawing in some other building. I only allow graffiti in one building at once for now, as an optimization. Paint and marker can be seen through the windows and open doors of a building. Here is an example of my artwork:

Inspecting my artwork in this office building hallway. All it took was three cans of spray paint and a dry erase marker.

Markers will write on whiteboards, but they write just fine on the walls as well. If you take your time it's possible to create very accurate and detailed drawings. The capacity of a spray paint can or marker is large enough to create quite a bit of color. At this point there's no way to erase them, so you need to be careful not to make a mistake.

I left a surprise for someone to find when they get back to the office after this zombie invasion.

Toilet paper rolls can also be taken off the holder and used. (The holder can be stolen as well.) I haven't quite figured out how to use toilet paper, other than pulling it off the roll down to the floor. I was thinking that I would have the action key wrap toilet paper around objects. Or maybe the roll can be thrown and will trail toilet paper behind it. I guess we'll see what I end up doing.

Here's some graffiti to point out that the roll of toilet paper can be taken for some extra fun.

[Yes, the toilet paper roll is attached to the block window. The house near the player starting position is the only house I've seen that's like this. This looks bad for normal transparent windows, so I remove the toilet paper in those cases. But a roll on a glass block window isn't as bad. Maybe it's glued on? So I allow it.]

The player can turn bathroom/kitchen sinks and tubs on and off. The sound of running water is played for a few seconds when these are turned on. I've considered letting the sound play in a loop while the water is running, but I'm not sure how practical it is when the player can turn on every sink in a building. Maybe it should only play when the player is in the bathroom? I don't know, it still seems like the sound would be annoying. I've also added an animated stream of water coming from bathroom sinks when they're on. Here's a screenshot, though you can't really see the animation in the water.

I turned on the water in this sink. You can see the reflection of the previous screenshot in the mirror.

It's silly to tilt the pictures in someone's house after you've stolen all of their valuables and drawn all over their walls. However, this was fun and easy to add.

Does that picture look crooked to you? I swear it was like that when I got here!

The next item on my list is working elevators. I currently have elevators that will move up and down based on the direction the player is looking. I want to add real elevators with call buttons on each floor and a button for each floor inside the elevator. These will control the vertical position of the elevator and the opening and closing of its doors. I've added the call buttons, and they do light up when pressed, but they have no effect on elevators at this time. This is intended for use by the player and not building AI people. Implementing all of this could be time consuming, but sounds like another fun and interesting mini-project.

I really should record another video of all these building interactions. I wish I could figure out how to make audio recording work so that I can show off all the sound effects I've added. Maybe I'll put a video up on YouTube once I get elevator buttons working.

Sunday, March 7, 2021

Procedural Buildings: AI and Player Interaction

I'm in the process of working on my game where the player steals items from houses and office buildings that are infested by zombies. The goal is to have both the player and the zombies interact with objects inside the buildings as part of gameplay. This includes entities such as room lights, doors, pickup objects, items on the floor, drawers, etc. Most of the items placed in rooms have been static up until now, but I want to make almost every object be interactive. That means the player must be able to pick up, drop, move, open, close, etc. the various room items. AI People inside buildings will also interact more with objects, even if that only means better object collisions and physics.

Here are some of the interactions I'm working on. Sorry, I don't have too many pictures for these. This is mostly a list of concepts and ideas I'm working on implementing for gameplay. I'll probably post some YouTube videos of early gameplay a bit later. At this point I have the high level gameplay system written, it's just a matter of filling in all the details.

Lights

Every room and hallway has one or more light placed somewhere on the ceiling. In addition, some bedrooms have lamps placed on nightstands and dressers. I recently added small lights to the ceilings of some of the walk-in type closets that the player can enter. Each of these lights can be toggled on and off by the player. This feature has been around for a few months now. It allows players to get a better view of a room by turning on the lights, while at the same time having many of the room lights off by default to improve framerate. (Lights are expensive for large buildings containing a thousand rooms.)

I've added the ability for AI people in buildings to turns lights on and off as well. AIs will turn the light on as they enter a room, and turn it back off again when they exit if no one else is in the room. This only applies to people in buildings near the player to avoid unnecessary toggling of distant room lights.

I also added logic to query whether or not the player is in a lit room that takes into account shadow casters. I plan to use this at some point to allow the player to hide from enemies in the darkness. The system is mostly implemented, but I haven't enabled it yet.

Doors

The player can open and close interior room and closet doors with a key press. Exterior building doors automatically open and close to admit the player. I've added logic for the AI to open doors, which is controlled by a config file parameter. If the AI can't open doors, the path finding algorithm will attempt to navigate around closed doors if possible. I had to rewrite the door drawing code to allow doors to have different open vs. closed states on each floor of the building, rather than having a single door that extends down between all floors. The rewrite allows doors to be drawn sparsely based on player location and view direction, which was required to handle millions of doors across all buildings in the scene.

I added the concept of locked doors a few days ago. The user defines the probability of doors being closed and/or locked in the config file. Locked doors can only be opened after the player finds a key, which are hidden around the building in drawers. The same key can be used for every door of that building, but won't work on doors in another building. AI people have similar flags for whether or not they have keys and can open locked doors. If the player has a key but the AI doesn't, it's possible to lock the AI in a room. The key + locked doors system will be important for later gameplay.

Pickup Items

I added a player inventory and made almost every placed item something that can be picked up. There's an inventory weight limit, so some of the larger items such as the couch and refrigerator are too heavy to pick up and carry. But the player can pick up most smaller furniture, fixtures, appliances, items on tables, etc. This includes fun things like toilets, sinks, stoves, nightstands, rugs, pictures, potted plants, TVs, chairs, ceiling lights, exit signs, men's/women's restroom signs, etc. Every item has a weight and a monetary value, and some items have special effects. The player's goal is to steal the maximum value of items and make it out of the building alive with their loot. Heavy items will slow the player down while they're being carried.

Some objects must be picked up in multiple parts. For example:

  • Beds: take pillows, then sheets, then mattress; bed frame is too heavy to pick up
  • Potted plants: take plant, then soil, then pot
  • Pictures: take picture, then frame
  • Tables: must take everything off the table before the table itself can be picked up
  • Wine Racks: must individually remove every bottle of wine before taking the wine rack

Bottles function as power-ups/special effects, depending on what type of drink they are. Empty bottles have no effect. Coke and water heal the player. Beer and wine make the player drunk, which enables some neat scree space effects like drunken wave, double vision, and blurry vision. [I would like to thank my daughter Kate for input on these effects!] This will all be important for later gameplay. I plan to add other drinks such as poisons that hurt the player in some way (damage, blindness, slow speed, etc.)

I had some difficulty handling objects on shelves and in closets because they're not actual C++ objects stored with the building. They're only drawn as part of the shelves and closets when they're visible to the player, so they're all temporaries created in the drawing code. It took quite a bit of work to allow the player to pick these objects up, and to have the system remember what was taken if the player walked away and came back later. I didn't want to allow the player to pick up a valuable item from the same shelf or closet more than once, even if they walked to the other side of the map and back. What I did was to "expand" these storage containers into real objects when the player attempted to use the "pick up" key on them so that they can be properly handled. This required quite a bit of code reorganization. It also has some runtime cost because expanding an object requires rebuilding the vertex data for the entire room detail geometry of that building.

Look at all these great items in here for me to steal. Unfortunately, I don't have the carrying capacity to take them all, and this guy isn't happy to see me here.

Drawers

I need a way to distract players from zombies so that they're caught off guard. What better way than encouraging players to spend time searching through desk, dresser, and nightstand drawers for keys and other valuables. Each drawer can be individually clicked on to open and close, and can contain a single item. The player can decide to pick up the item to add to their inventory. Some drawers are empty, some contain boxes, and on rare occasions a drawer contains a key. I plan to eventually add other items to drawers such as bottles, books, papers, pens, pencils, cell phones, wallets, and money. At some point I may also allow the player to open kitchen cabinet doors.

The room key can be found in a dresser, desk, or nightstand drawer. Other drawers are empty or contain boxes.

Dynamic Items

Okay, the player can now pick items up. What about dropping them? Simple spheres are the easiest type of shape for implementing collision detection and physics. I started by adding soccer balls and basketballs to some bedrooms. These can be picked up, carried around by the player, and dropped. I later decided that it was more fun for the player to throw balls rather than dropping them. The player can also kick them while on the floor, or in mid-air, if they get close enough. AI people walking around the building will also kick any balls they happen to run into.

I've implemented proper collision detection and physics for balls, including gravity, momentum, static and kinetic friction, and elasticity. Most of this was adapted from my other/existing gameplay framework, though it's all new code. Balls will roll around on the floor (including proper texture rotation), bounce off of room objects, bounce down the stairs, and even roll under beds and possibly get stuck. They cast and receive dynamic shadows from room lights.

Balls contribute to gameplay by emitting sound which alerts zombies. They can either be helpful when thrown as a distraction/diversion, or harmful when the player accidentally kicks one. I've scattered them around in the middle of floors to maximize the chance of the player accidentally running into a ball.

Soccer balls and basketballs can be picked up, kicked, and thrown by the player. The basketball has rolled under the bed.

Sounds

I've added lots of new sounds for building gameplay mode. Everything discussed here has sound: switching on and off lights (clicks), opening and closing doors and drawers, picking up objects, throwing and kicking balls, bouncing of balls, drinking from bottles, and even walking on the floor. I've included damage sound effects for the player and various zombie moans for people in buildings.

Sound is important for gameplay. Zombies can't see through walls, but they can hear noise made by the player. Louder or repetitive sounds can be heard from further distances and are more effective at attracting zombies from other parts of the building. It's important for the player to try to be as quiet as possible while searching the house for valuables.

Another strategy is to make a lot of noise in one part of a house to attract zombies, then sneak to the other end of the house to do your searching. Or you can place some balls near a doorway and hope a zombie runs into them, making noise and attracting other zombies (away from you). If you're feeling bold you can close some doors so that zombies must open them to enter rooms. This can either be used to distract other zombies, or alert you to a nearby zombie entering the room that you're in while you're searching. If you have a key you can even lock a zombie out of the room, assuming it doesn't have a key.