Pedestrian Zombies - Gameplay in Cities

It's been a while since I worked on city outdoor elements. The past few months I've spent mostly working on building interiors. It's time to get back to gameplay and make zombies chase the player outside of buildings and in city streets. But first, I need to familiarize myself with how pedestrians work and fix a few things in the process.

Pedestrians currently ignore the player. There isn't even collision detection; pedestrians and the player walk right through each other. I really should fix that now.

Let me see. I remember adding collision detection between cars and the player awhile ago. Cars can push the player around on roads, but they don't make any attempt to avoid hitting the player. That sounds like a good place to start. I changed cars so that they'll quickly stop if the player is in their path, and sometimes honk their horn. This uses logic similar to the car pedestrian avoidance system. The silly player pushing effect is gone.

Now I'm ready to work on people using similar logic. I can put the player proximity check in the code that has the loop over nearby pedestrians, and even include collision prediction and avoidance. This is the system that looks for a future collision by checking for intersecting paths between the target person and nearby people using their current speed and direction. A detected intersection causes a repulsive force to be added perpendicular to the move direction that changes the pedestrian velocity and orientation, moving their path and avoiding a collision.

I tested this out on the player, and it appears to be broken. People sometimes misbehave by walking in random directions, or continue to walk into the player. I guess I was never able to make this code correct because it was too difficult to set up a controlled collision experiment between two people. But now I can! I can control the player and position him in exactly the right spot to trigger the failure repeatedly. Then I can add all sorts of debug printouts; it's actually easier to debug because the player's velocity is zero. It turns out that the bug was mostly due to a sign error, which was easy to fix. Now person collision avoidance ... almost works. Here's a video I recorded after the first pass fix.

There's still a problem when the pedestrian is near an edge of the sidewalk and the collision avoidance pushes them into an invalid area. This can either be the road or a neighbor's forbidden private property, which starts a few feet from the sidewalk. When this happens, leaving the valid area is considered a different type of collision and triggers a turn and direction change. You can see that near the end of this video. The pedestrian can sometimes turn back toward the center of the sidewalk and collide with the other person (or player) again. It's better than it was, but still not perfect.

The next step in the fix is to limit the turn angle. If I can have a repulsive force smoothly push a person away from another person, I can use a similar force to push them outside an invalid area. It's not critical that they turn immediately in most situations. These checks are really only to keep people from walking into the road and getting hit by cars, or straying into someone's yard and getting stuck on a fence, wall, or hedges. There's quite a bit of buffer room to the sides, so it's okay to leave the sidewalk slightly. They can return as soon as the colliding pedestrian has passed them (since pending collisions are almost always from two people walking toward each other).

In reality, this whole debug and fix process took many hours with multiple small fixes and a dozen failed attempts at fixing it. Fortunately, I did eventually get it working. (More on this at the end.) Time to move on.

The next step is to have zombies chase the player in outdoor areas. I already have people turn into zombies, both inside and outside of buildings, when gameplay mode is enabled. The models and animations are all reused from interior building AI people. Before I add player chasing behavior, let me make them act more like mindless zombies. I removed most of the car collision prediction and crosswalk logic so that they walk out into the street at random places and into the path of cars. They won't walk directly into the sides of cars, but they certainly don't fear getting run over. Cars usually stop for them though. After enduring much honking, I reduced the rate at which cars honk at zombies from 25% to 6% of the time.

So far, so good. It's time to add player chase logic when the player is within some sight distance. There has to be some reasonable distance limit to avoid a horde of thousands of zombies chasing the player from all across the city at once. We don't want zombies trying to walk through obstacles or having X-ray vision (unfair!), so it makes sense to do a ray cast with the large scene objects to determine if the player is visible and reachable. This involves testing the AABBs (axis aligned bounding boxes) of buildings, walls, fences, hedges, etc. And trees - zombies love to run into and get stuck on trees. This was because I had the bounding volumes set too large on trees, but I didn't figure this out until several days later. I'm still not quite sure what to do about chain link fences. Obviously, zombies can see the player through them. However, these fences tend to enclose entire yards, and zombies are unlikely to be able to reach the player through one of these fences, so why even try? Most likely they're just get stuck. One more problem I need to fix later.

It's finally time to add the player chase logic - for real this time. My initial attempt was to have zombies walk directly toward the player at a somewhat faster than usual speed and ignore any private property. That sounds simple, and seemed to work at first. That is, until the first time I saw a zombie get stuck on a mailbox or fire hydrant. Once I knew the trick it was pretty easy to get my pursuers all stuck against objects and no longer able to reach me. Making them almost half as fast as the player didn't help them catch me all that much. Well, at least that was worth a try.

But before I go and fix this with some really complex solution, I have to handle zombies reaching the player. Right now they simply surround and trap the player in a mass of janky animated models. Apparently, the player follow logic overrides the pedestrian avoidance logic. The obvious fix is to add player damage so that they player is long dead before the crowd gets large and dense enough to clip through itself. Then I realized that the player stays dead for a few seconds waiting for respawn while the zombies pile onto the dead body. It's actually pretty amusing, and I really don't want to "fix" it. I suppose the zombies are allowed to misbehave as a reward for killing the player.

The video below was recorded around this point in time. The reader may assume the task is almost complete - but we're far from it. There are many, many bugs left to fix. This seems to always be the case with game AI, especially when they interact with each other.

I forgot to mention in a previous post that I added ladders up to the roofs of some houses. [I can't write about every single feature I add or I'll spend more time writing these posts than I spend writing code!] I originally wanted the ladders to experiment with fall damage, which you can see isn't working yet. Which is a good thing because you can currently only climb up ladders and not down them. But I decided it would be an interesting way to escape zombies. I didn't think about the fact that they can still see the player on the roof and will attempt to walk through the building to get to them. I fixed this by checking that the vertical position of the player was within some range of the zombie as a test for "near ground level." Now they ignore players on ladders or roofs.

Maybe the YouTube video is too blurry for some viewers. Or maybe the zombie moans hurt your ears. In that case, I can offer a static screenshot.

Zombies giving chase in a residential neighborhood.

They really like to use the road as there are no cars enabled and no pesky telephone poles, traffic lights, and streetlights to get stuck on. I have this working in commercial cities with office buildings as well. There's more open space between buildings here, and no illegal private property to avoid. These are some reasons I didn't try to debug the failures in these cities.

Zombies giving chase in a city with commercial office buildings. Wow, the traffic lights look way too tall in this screenshot.

The simplest way for zombies to avoid getting stuck is to use the existing path finding solution rather than having them walking directly toward the player. After all, this system exists for a reason. I've spent enough long nights and blog posts on AI navigation and path finding that I'm confident it will do a better job than the simple straight path system I'm using now. The reason I haven't been using path finding is because it only supports finding a path to a destination building or parked car. It uses the bounding box of this object as the destination. How do I modify this to work with player following behavior?

What about creating a zero area destination box at the current player's location, and recomputing the path to that box each frame as the player moves? Oh, that's simple and just works the first time. Why didn't I do it this way to begin with? I suppose I was afraid I would get sucked into a week's worth of debugging path finding failures. (Spoiler: I eventually was.)

I thought this was nearly done, but testing exposed another problem. If the player entered a house or otherwise became unreachable, the zombies would stop following. If they happened to be in someone else's yard at the time, they would find themselves in an illegal area and often couldn't get back out. This was especially problematic if they were in a back yard and the closest path out of the forbidden area was through a wall in the back separating the neighbor's back yard, rather than around the house and out through the front yard. This resulted in many zombies running into walls. Surely zombies aren't that dumb, right?

My first fix was a hack that really felt like cheating: If a zombie finds itself deep in someone else's property, make them the owner of the house. Now they can simply walk to the nearest door of the house and respawn somewhere else far away. This really breaks gameplay though, because it's too easy to trick a horde of chasing zombies into conveniently retreating to the nearest house, never to be seen again. What fun is that?

No, that's unacceptable. I can do something similar though. Rather than picking the current house as their destination, they can at least pick a new destination house that's in a direction that takes them to the front yard of the current property rather than straight through the backyard hedges. Surprisingly, this solution seems to work very well. Sometimes I get lucky.

Intermission: This was all quite a bit of work. Every time I get dragged into fixing pedestrian path finding and navigation leads to many hours of debugging. It never works the first time. This is why I created a whole set of onscreen graphical and textual debug tools just for pedestrians. Here's an example of the debug geometry drawn when a person/zombie is selected. I have a text overlay mode as well that shows many of the internal AI variables, but it's turned off here.

Debug visualization of AI path finding: Cyan boxes are collision object AABBs, the green cube above the zombie indicates <next_plot> state, the orange line indicates an unblocked straight path, the green sphere indicates a safe road crossing point, and the magenta cube in the distance represents the destination house. Car avoidance boxes aren't shown.

Now things appear to be working reasonably well. Sometimes zombies will still get stuck somewhere or clip through an object, but it doesn't happen often enough that I can repeat the failure with debug printouts enabled. And then there's the "dancing" I sometimes see where two people get stuck together and follow each other for a few seconds, spinning in place. I see that maybe every 15 minutes in testing, but when I try to debug I can never force it to happen. Oh well. It may get fixed eventually, similar to how I finally fixed the pedestrian collision prediction repulsive force code that has been broken for over a year.

Sigh. Now that I mentioned the "dancing" problem in this blog, I'm required by law to fix it. I don't want readers to think I'm lazy or don't have the skills for this. I'll have to put off finishing this post for a few days.

Update:

This video shows my latest attempt at having AI pedestrians avoid each other and obstacles while keeping mostly to the sidewalks. This was surprisingly difficult to get right! (Wait, how many times have I said that already?) I managed to fix most of the problems, including people getting stuck, dancing, clipping through each other, and spinning in circles. I even fixed the case where a faster pedestrian came up behind and tried to pass a slower one moving in the same direction. Now they will try to push past each other if they can't move to the side to avoid a collision. This system works almost flawlessly with the default of 8,000 pedestrians. When I double them to 16,000 (as shown in this video), they form larger groups that don't have the space to pass each other cleanly.

I'm not quite sure what caused the "dancing," but I haven't seen it occur since I made these changes. I assume it got fixed in the process.

I still haven't figured out how to correctly handle large groups forming at street corners waiting to cross when cars are enabled and traffic is dense. Right now they will form into a line along the edge of the road. When the space along the road by the crosswalk is full, the pedestrians in the back will walk into the ones in front and either get stuck mid-step against them, or push them into the road. (The outcome depends on who is dominant, which is based on unique IDs.) There's no easy way to tell that they have nowhere to go and must stop because the system only considers the nearest single pedestrian. I may revisit this later.

Retail Spaces

It's time to add something other than offices to 3DWorld's commercial buildings. Someone suggested adding stores, so I'll start there. The easiest way to begin is by adding a retail area to the ground floor of some office buildings with rows of racks/shelves filled with items. This will be a good test of how well my building object management system scales to thousands of individual items in the same room. I've only attempted to add retail areas to rectangular buildings since that case seems much easier than buildings with angled or curved sides.

Rows of racks are first added along the longer dimension of the ground floor rectangle, with aisles in between them. These are broken into shorter segments to allow people (and possibly shopping carts?) to pass between the aisles. Any rack that's too close to an exterior door, stairs, or an elevator is either clipped smaller at one end or removed entirely. In addition, the area between the front door and central stairs/elevator is left clear of racks. Rectangular ceiling lights are placed in the space between the racks above the aisles. I may add some sort of checkout area later.

Each rack contains between 3 and 5 shelves, with optional top and side panels. I made the number of shelves and rack style consistent per-building, though that's not really required. Shelves are white or gray metal, with wooden pegboards separating the front and back sides that face each aisle. Each shelf is then filled with smaller objects that the player can take down and interact with.

I started by adding boxes of various sizes and shades of color, since there was already a function to add boxes to shelves. The player can open these boxes and remove the items.

Racks of shelves filled with boxes of various sizes and shades of color. This looks similar to storage rooms.

This worked without too much trouble. Now it looks like a FedEx warehouse or something. That's a good start, but there's not too much variety. It's time to divide the racks into categories and fill them with some of the other ~140 types of objects that are currently in 3DWorld's buildings. The categories I used are:

• Boxes/boxed items
• Food and Drink
• Household Goods
• Kitchen Items
• Electronics

I originally had a few other categories such as clothing, but they only had a single item type and got merged into one of the other categories.

All shelves in a particular rack are assigned to the same category. However, some items have preferred shelves. For example, boxes of pizza are on the bottom shelf, while food boxes such as crackers and cereal are always on the top shelf. Some of the larger items such as computer monitors, lamps, and fire extinguishers can only be placed on taller shelves (racks with fewer shelves stacked vertically). Items are arranged either in rows, rows + columns, vertical stacks, or randomly.

Retail areas didn't look quite right, so I had to adjust the lighting and materials used. I also added vertical support pillars from floor to ceiling at the end of some racks. These next screenshots show retail areas after the carpet was replaced with tile floor and indirect lighting was enabled.

Retail area with a variety of object types on the shelves, in a brightly lit area with tile floor.

Another view of racks of items, looking down an aisle between two rows of shelves.

The electronics and kitchen sections, with stairs at the far end that lead up to offices and down to the parking garage below.

Another view of the retail area, with household items on shelves.

So how many objects are there? The building from the first few screenshots had 16,599 total objects on the shelves! I'm sure there are buildings with more. Maybe 20,000 objects?

Optimizations

One goal of this addition was to test the performance and scalability of adding a large number of objects in one place. Initially, the performance wasn't all that bad. Of course it really helped that I had bought a new, high end gaming PC while I was in the process of working on this. The CPU and GPU were both around 3x faster than my previous 9 year old PC. I went back and tested this on the old PC and the performance wasn't great. Creating the triangle geometry for this many objects was slow. Updating it when the player took an object (or even approached a shelf) was slow. Even drawing and creating the shadow map was slow.

But the biggest problem was with security monitors. See, I made sure to place cameras at the ends of the retail rooms as well, because why not? We have to catch the shoplifters, right? The problem was that trying to update these cameras with this many objects every frame, on top of everything else, reduced the framerate below 20 FPS. That's terrible. I put some effort into optimizing this. The biggest improvement came from skipping the shadows of all of these shelf objects, since they're difficult to see in the security monitors anyway. Most of the visible shadows are from the simple cube geometry of the shelves themselves.

There were many other optimizations. Profiling the code told me that the majority of the time was spent generating and drawing two of the 32 types of shelf objects: bottles and vases. Bottles were a problem because they have high vertex count smooth surfaces, and there are many of them. So I reduced both their detail and count, limiting the number of rows of bottles per shelf to only 2 rather than 3.

Vases were slow because they're formed from high vertex count, custom procedural curves. (You can see some of these in the third screenshot from the top, second rack back on the right, bottom two shelves.) Simply reducing their vertex density vertically and horizontally from 32x32 to 16x16 made them nearly 4s faster to generate and draw. Visually, they look nearly identical.

The next optimization I made was to improve occlusion culling for 3D models placed on shelves. The occlusion system currently only considered walls, ceilings, and floors as occluders. Since the entire ground floor retail area was one room, there was nothing to occlude the models. This was even worse than the problems I had with occlusion culling in the backrooms rooms. I decided to add the pegboard backs of the shelves as additional occluders. This dramatically improved the culling rate because most objects were completely blocked by the back of at least one rack between the player and the object.

At this point the drawing and shadowing runtime was acceptable, and the framerate was at least 50 FPS even on the old computer. The only major remaining problem was the ~100ms lag encountered the first time the player approached each individual rack of shelves. This is because these 16,599 objects aren't physical objects in the building, they're simply drawn as around 100 batches of triangles that have been merged across many objects. When the player approaches a shelf, the system needs to have a list of the individual objects so that the cursor can turn green to indicate that the player can pick up or interact with an item. This involves "expanding" the particular rack into its component objects, which requires updating various data structures that span the entire building. The worst case is when the player walks down each aisle and forces the racks to be expanded one-by-one. Racks are only expanded once, but there are many of them.

The only fix I was able to come up with was to disable the cursor and interactive content for shelf racks. It's not a big deal. I think the only iterative objects were microwave doors, boxes, and books that the player can open. Most of the electronics are unpowered and can't be interacted with. None of this is required for gameplay anyway. The player can still take an item from a shelf, and this will expand the rack. After that the cursor and interactive content will work on this rack since the objects were expanded. Now the lag only occurs when the player is actively stealing from the shelves, rather than simply browsing them. This seems fine because the player must pause to press the "take item" key, which does a good job hiding the lag. This is far less noticeable then the lag that occurred when simply walking down the aisle as it interrupts the smooth walking animation.

The code for all of this can be found in my GitHub repo. Shelf rack placement code is in the building_t::add_retail_room_objs() function in this file. Shelf expansion/population code is in the building_room_geom_t::get_shelfrack_objects() function in this file.

Procedural Clocks, Digital and Analog

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

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

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

Analog clock above the door on a pool room wall.

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

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

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

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

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

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

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

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

Procedural Buildings: Office Security Rooms

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Pool Rooms and Pool Rooms

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

Pool Tables

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

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

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

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

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

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

Indoor Swimming Pools

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

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

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

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

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

Here is what we have at this point:

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

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

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

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

Brightly lit pool with pool floats and beach ball.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

 

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

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

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

Flooded backrooms with muddy water.

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

Animated Birds in Cities

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Basement Water, Improved

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

Walls Blocking Waves

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

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

Refraction

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

Caustics

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

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

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

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

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

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

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

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

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

Update

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