Procedural Cities: New City and Residential Objects

I've added quite a few smaller features to 3DWorld's procedural cities, in particular to residential neighborhoods. I'll list all of the different types of objects that have recently been added and show at least one representative screenshot of each one. The last two posts were more on the technical side, with few images. This post will contain many images.

City Objects 

First we have the objects added to cities with commercial buildings. Parks were looking too empty since they previously only contained trees, benches, and maybe a flag. Now parks can have one or two winding paved paths crossing through them. These can be treated as either pedestrian or bike paths. (There are no bikes on these paths yet, but there are now static bikes - see below.) The placement algorithm will avoid adding objects such as trees that are too close to paths. People walking through the park don't yet use these paths. Now that I'm thinking of it, maybe I can modify the grid-based pedestrian path finding algorithm of the previous post to assign lower cost to grid cells over park paths.

I also added fountains to some parks. There are currently three 3D models to randomly choose from, but more models can be added to the config file at a later time.

City park with two wavy crossing paved paths and a fountain in the lower left corner.

Fountains can be found inside city blocks as well. They're placed anywhere that has enough open space and is far enough away from buildings. Birds can land on the tops of fountains. Maybe I should add benches or other items around the fountains?

Close-up of one of the three new fountains added to cities. Some are in parks, and others are on the concrete areas between buildings. This fountain has a pigeon on it.

I've added traffic cone objects that can be placed on the ground within cities. They can be used with either commercial cities or residential neighborhoods. These aren't 3D models but are instead formed from simple truncated cones and rectangles for their bases. Traffic cones can be placed anywhere, but initially I only put them in semicircles around the curved roads at the corners of cities. In the future I might add construction areas or closed roads where traffic cones can be used.

Traffic cones are now added to some areas of the city, currently only at the ends of road bends.

Residential Objects

There have been quite a few new additions to residential areas. Most of these are new types of 3D models that have been added, though I've also experimented with trees and plants.

First we have bicycles. These use a single model that's always painted red. Bikes are placed leaning against the exterior walls of houses and sometimes along front yard fences. The only placement rules are that they can't intersect previously placed objects and can't block doors. The same rules apply to the other object types shown later. Bicycles are not yet interactive; maybe some day the player can ride them.

Bicycles can be found leaning against some houses and fences.

I've added small potted plants around the exterior of houses and fences. There are three 3D models to choose from, one type of flower and two types of leafy plants. I'm reusing the same models that I placed on tables inside buildings. Since they're small and low-polygon, they're cheap and can be placed almost anywhere, so I can add several per house.

Oh, I almost forgot to mention that I added downspouts connected to the gutters of houses. You can see two of these in the image below. The small concrete slabs at the base of exterior doors are new as well.

Small potted plants of three varieties have been added around houses and fences.

The next type of vegetation I've added are smaller pine trees placed near houses. I already have deciduous and palm trees added to residential yards and pine trees in parks, but these add a bit more greenery.

I originally wanted to add bushes, but I couldn't quite get them working. The first problem was that trees are instanced all around the world with only 100 unique tree models for performance reasons. If I created bushes specifically for houses, that would have either increased the memory usage of trees or reduced the number of unique trees placed in the rest of the scene. The second problem was that there's little control over the shape of the tree, and sometimes a stray branch clipped through the exterior wall of the house. Pine trees use much simpler models (32 branch quads vs. thousands of leaves) and have a well controlled shape, which avoids both problems.

Small pine trees have been placed around the exterior of houses in residential neighborhoods.

Now it's time to add more sources of outdoor fun and exercise for the city residents. Some back yards have swimming pools. Most of the yards without a pool now have either swing sets or trampolines. These objects have fewer placement restrictions and can be added in situations where pools can't. For example, they can be added to smaller yards that can't easily be fenced in. The only real requirement is that they be in the "back" yard, which really only means they can't be placed between the front of the house and the street.

Here's a swing set placed in a back yard by a balcony. Extra padding has been accounted for in the placement to make sure there's enough space to swing. They're not currently interactive or animated though. I would love to have the seats swing back and forth when pushed by the player, but none of the free 3D swing set models I found have this sort of animation. Birds can land and take off from swing sets. If you look closely, you can see a dark gray bird on the center of the top bar in the screenshot below.

This screenshot manages to capture many of the new additions: A swing set (with a bird that just landed on it), a bike in the far back right, a pine tree on the left, and potted plants against the house near the center.

And finally we have trampolines. I was only able to find one usable free model with the vertical bars and net, which is similar in style to the trampoline in my own yard. This one has good geometry, though that net has a high vertex count and over 100K triangles. The one downside is that the materials are very dark and have no bright colors for contrast. I believe the normals are wrong on the dark blue ring, which is why it doesn't appear to be properly lit from the sun.

Trampoline placed in the yard next to a house.

Adding all of these new 3D models comes with a performance cost. Some of them have high vertex/triangle counts. Some of them have many individual materials, which leads to a large number of draw calls that hurt performance. I had to add more aggressive LOD and material distance culling to recover some of the framerate. For example, meshes with very small triangles such as the net in the trampoline above are only drawn when close to the player. I applied the same approach to indoor objects such as couches, chairs, and lamps. However, all of these objects together are a fraction of the triangle count that's drawn when people and cars are enabled, as those models are far more detailed.

What else should I add? If you have any suggestions, leave them as a comment.

Procedural Cities: Revisiting Pedestrian AI Navigation

I just wrote that post on colored locks and keys, and I already have two other posts in progress. I guess this makes up for me not posting anything in February. The other post (not this one) is on the topic of new objects I've added to cities. Most of these objects are smaller items placed around houses in residential areas. But wait! Won't all these new objects get in the way of pedestrians and zombies and break my simple path finding system? Yes, yes they will. It's time to rework pedestrian navigation, again.

High level navigation finds a path from the person's current position to a randomly selected destination house or parked car. The path will pass through a number of adjacent city blocks (which I call "plots" in the code) separated by roads. Each next plot is chosen as the one in the direction closest to the destination. Since the city is a uniform grid where all blocks can be traversed, this simple approach will always find the shortest path to the destination. The challenge is finding a valid path within a particular block as the shortest path (straight line) may be blocked by buildings, walls, fences, cars, etc.

The old algorithm constructed paths by starting with a straight line from the center of the person to the destination point, and repeatedly adding detours to split it into two separate segments to avoid obstacles hit by the original line. Only AABBs (axis aligned bounding boxes) of these collision objects are handled. This means that people will treat rounded objects and non-cube buildings as larger colliders than they actually are and will avoid some open areas. At each iteration, the closest intersection point on the current path line segment is found. Then the path is routed around the obstacle by adding points to the corner of the box, moved outward by the radius of the person to avoid collisions. There will always be two choices of direction, to the left and to the right. Path finding uses a recursive branch-and-bound tree-based solver that considers both the left and right options and selects the shortest valid path between the two. This continues, breaking the line into incrementally shorter segments, until the goal is reached. Then the path is simplified by removing vertices that are not needed and connecting the neighbor points directly if the line is unobstructed.

This tends to work well in many cases, but can fail to find paths when a number of adjacent objects block off a large area that can't be walked around by following corners. This can even fail in simple cases where the AABB corners are inside other objects. A second problem is that the path may not be the shortest, in particular in cases where the AI must move away from the destination to get around a large object (or chain of objects) that's in the way. In this situation the path may follow the contour of an object rather than using a straighter line with a backwards detour. I had to find a better solution for these cases.

The common way to solve AI path finding in other game engines to use what's called a navigation mesh, or nav mesh. My original approach was more of a path node system. One common third party library used for creating and evaluating nav meshes is Recast Navigation. But this solution is far more complex than what I need. I'm basically looking for a 2D solution on a flat surface. I don't need support for heightmaps, inclines, stairs, jumping, falling, etc.

There are some difficulties with my world representation as well. The most important one is that I don't have direct access to the walkable area, I only have the blocked area in the form of buildings and other objects. I need to invert these polygons within the city blocks to get the walkable area. A second problem is that some of the collision objects are analytical shapes such as cylinders, spheres, and ellipsoids rather than polygons. This includes items such as lamps, telephone poles, and trees. Sure, I can approximate the curves with polygon sides; in fact this is how I draw them. And there are polygon libraries around that can invert the blockers to get open space, and other libraries that will divide polygons into triangles. Of course this goes against my goal of writing everything myself, so I need to at least attempt to come up with my own solution.

The new algorithm is based on the grid-based path finding solution I used for backrooms as described in this previous blog post. I used this approach for backrooms because a uniform grid seemed like a good fit for these maze-like rooms due to the way they were constructed and the rules applied to their walls. The minimum width of hallways and doorways to fit the people and player ensured grids could be fit into every open area. This mostly generalizes to city blocks. The city object placer is supposed to ensure there's enough space between buildings and prop placements for people to walk between them.

The city query API is a good match for what I need to construct a navigation grid. It provides two functions, a sphere intersection test and a line intersection test. Point intersection queries are also possible using either a zero radius sphere or a zero length line. I first determine which grid cells are "open" for navigation by running a sphere collision query for each grid square at mid-person height level. It wasn't clear whether an inscribed or circumscribed sphere radius would work better, so I used something in between. I had to store the index of buildings in each grid so that these grids can be considered as open rather than blocked when the building is the pedestrian's destination. This query is accurate enough to test the exact building footprint rather than the AABB used in the old navigation system. This means that people can walk in concave areas of the building footprint, which makes path finding more flexible. (It turned out later that these concave ares aren't very useful for navigation unless the person's destination is that building, in which case isn't not considered as a collider anyway.)

Once the grid is constructed it can be used for realtime path finding. This is run for each pedestrian, initially when they enter a new city block. I also update path finding a few times a second, more often when they're near the player. This is needed to adapt to small deviations from the original planned path, which can occur due to restrictions on turn radius and collision avoidance with other pedestrians. Some updates are also needed to adjust to dynamic moving objects such as cars pulling into and out of driveways. And of course the path must be updated frequently when chasing the player in zombie gameplay mode.

If I was to simply find a path from one grid square to the next, it would look unnatural. For example, if the path was diagonal, the actual motion of the person would follow a stair step pattern across the grid with a large number of right angle turns. The solution is to run a "string pulling" algorithm on the raw path. This works by connecting lines between path points and then sequentially removing points, which replaces two line segments with a slightly shorter single straight segment. The result will be a sort of convex hull of the obstacles.

Each simplified path segment must be checked to ensure it doesn't make the person collide with an object. If we didn't do this check, every point other than the start and end would eventually be removed, forming a single straight line. This check employs the ray intersection query function. But testing a single ray from the person's center isn't enough because their arms and other extremities may collide with the edges of objects. Instead I use two ray queries for rays offset by the person's radius to the left and right of the direction of movement. These would correspond to the outer edges of their left and right arms. The shortened path is only valid if neither of these lines intersects an object. This assumes that no objects are smaller than a person's collision radius. In the current system, objects are slightly padded in X and Y to provide a bit of extra clearance, so this size constraint is generally met. Note that I could probably expand objects by the person's radius and test a single line instead, but this won't allow people to pass close to sharp edges such as the corners of cubes. The line query doesn't dominate runtime anyway.

What does dominate runtime is grid generation, specifically the sphere intersection queries. This is because there can be thousands of grids per city block. The minimum size of a grid is a bit larger than the radius of a person, to allow them to fit into narrow gaps such as between parked cars and through the gaps of gates in fences. This leads to grids as large as 100x100 = 10,000 cells. The solution to this problem is to cache grids for each block for reuse across many people over many frames. The grid only needs to be recomputed when something changes, such as a parked car entering or leaving that plot. Technically there must be several cached grids per block to account for different rules for home plots vs. private property, which is different per person. I should probably also have two different grids for male vs. female people since females have a 10% smaller radius and can fit into smaller spaces.

There are some downsides of this new approach. Even with these optimizations, this path finding solution is much slower than the original. Second, path finding in complex areas with many small colliders can result in jagged paths with many turns when string pulling is ineffective. And sometimes we don't want people walking into small spaces between buildings and other objects. Ideally we only want to use this solution in cases where it's needed, cases where the old algorithm fails to find a valid path. This means that both algorithms need to coexist so that the path finder can select the optimal solution. But we can't be switching between them too often or the pedestrian will oscillate between two different paths. This is definitely what happened when I enabled them both! Instead we want to continue to use the current path finding solution until it either fails, or the person crosses the street into a different block. Most of the time the original algorithm works well enough and is cheaper in terms of runtime. The case where the new algorithm is the best one to start with is residential neighborhoods where the person's destination is on the opposite side of fences, walls, or hedges. This case is uncommon, so it's okay to use the slower grid-based solution.

The screenshots below show debug visualizations of pedestrian AI path finding. The AABBs of collision objects are shown in cyan, expanded in X and Y by the radius of the person to represent the regions where the center of the person's bounding cylinder cannot pass. Short objects that end below the person's arms use a smaller expand value based on the extents of their legs. The selected person has a green cube above their head indicating that they can move. The old path finding algorithm paths are shown as either yellow (complete) or orange (incomplete) spheres connected with same color lines. The new algorithm displays walkable grids as red squares, with path nodes shown as purple spheres connected by purple lines.

Pedestrian AI walking through a city block and around the AABB (axis aligned bounding box) of a building using the old navigation algorithm. Note that cars mark the entire parking space as blocked.

Residential areas have more complex geometry due to the walls, fences, and hedges separating the individual plots. Here the new algorithm is selected by default. The three images below show some of the situations that can occur. I've disabled cars to remove the clutter.

The new grid navigation system showing walkable grid tiles of a block as red squares, selected path nodes in purple, and collider AABBs in cyan. The old algorithm path is at the same location as the purple sphere.

Overlay of old (yellow) and new (purple) navigation system path nodes for a straight route through the center of a residential block. Both systems return nearly identical results since the path is unobstructed.

Here the AI paths diverge between the old and new algorithms. The old algorithm (orange) follows the contour of the cyan collider AABBs and is incomplete on the left side with a dead end in the driveway. The new algorithm (purple) forms a complete and minimum length path around the houses by using string pulling.

Here we can see that the algorithms agree when the path is short or straight, but can diverge significantly when the shortest path is complex and weaves around many obstacles. In extreme cases, the old algorithm may not be able to find a complete path. This system isn't perfect, but is definitely an improvement over what I started with.

Procedural Buildings: Colored Locks and Keys

I haven't created a blog post since January, so I'm behind on my monthly posts. I did record a 21 minute YouTube video on my procedural cities and buildings progress last month. That took quite a while to put together, and sort of takes the place of the usual blog post. I didn't add any other major visuals that I can show in that time frame anyway.

The video was created from a list of dozens of features I wanted to show that I kept adding to while working on the recording. One of the reasons it took so long was because I repeatedly found a problem while recording, so I discarded the video, fixed the problem, and started over. I guess I've never tried to visit so many areas in the world and make so many changes at one time before. But some of these were minor issues such as objects clipping through each other. I still wanted to avoid showing any bugs. What was supposed to be the final video was interrupted by a crash (C++ assert) halfway into the recording.

The problem was that I added a step in the recording process where I got a black key and unlocked a black padlock from a door, then flew across the world to some other location to show off. When I came back to the first house with the lock it failed because a step was triggered that added locks to doors, but the door had already been unlocked. The state of the door was saved for that building, so the padlock addition code needed to skip it. To show respect for this bug, today's post will be on the subject of colored locks and keys. I don't have any single big task that I worked on during this time, so I may as well show one of the many smaller tasks.

First, a bit of background. One of the inspirations for these procedural buildings was the game Hello Neighbor, which I played with my daughter in the 2018-2020 time frame. This game had several houses full of locked doors and various objects that could be picked up, used, and thrown. The player had to find specific items and get into the rooms while either hiding or running from the neighbor AI. I liked the general idea very much, but I was always disappointed when I reached the last room and found there was nowhere else to explore. After that I was determined to create my own world full of houses and items that the player could never in their lifetimes fully explore.

But I'm just a single person working part time on this (on weekends and nights), I don't have a team, and I don't have any good 3D modeling skills (or interests). I'm not even sure it's possible to make something like that with thousands of houses in Unreal Engine, which was the game engine used in Hello Neighbor. The only practical way to reach these goals was through procedural generation. And I don't just mean generating everything at preprocessing time or even load time. I mean generating the content incrementally, dynamically, while the player is moving in the world. Everything has to be ready to draw when it comes into view. Objects must be ready to be interacted with when the player enters the building. On top of this, any changes the player makes must be permanent, which means we have to track all of the objects rather than simply discarding them when the player leaves the area and regenerating them when the player comes back.

How many objects are we talking about here? There are over 18,000 buildings, consisting of around 12K houses and 6K office buildings. Houses have hundreds of items, and office buildings can have thousands of items. That's not all though - some of these items are shelves, or boxes, or have drawers that contain other items. In total there are probably close to 100M total objects in the world. Each is unique. The player can take a book off a shelf in one house and drop it onto a desk in an office building a mile away. The book no longer exists in the house, and will always exist in the office building. It's all done with a hierarchical tree of containers: city => block => building => building part => room => object => sub-object. If the player modifies an object, that node and the tree nodes above it must be flagged as persistent and not deleted or regenerated later.

Sorry, I got a bit distracted with object management. I was going to talk about padlocks and keys. Keys have existed for a while now. Each building can have one or more keys, and previously all keys unlocked all locked doors in that particular building. This means the player only needed to find one of the keys to access every room in the building. This may be okay for small houses with a single key, but it's too easy on the player for large buildings with many keys. I changed the keys to have one of eight colors, and added padlocks of these eight colors to doors. I got that idea from Hello Neighbor as well. Padlocks are object type 152 of 159. Yes, there are currently 159 unique types of objects in 3DWorld's buildings!

Keys can be found inside the drawers of desks, dressers, and nightstands. They're not left out in the open. No, the player needs to work to find keys. Opening drawers is risky in gameplay mode because the sound attracts zombies and spiders may jump out of them. There must be risk associated with the reward of opening a locked door ... even if there's nothing of value in the locked room.

Red key hidden in an upstairs bedroom dresser drawer.

At the moment padlocks are only added to houses because office buildings generally have hallways that can be navigated without the player needing to use doors, and stairs and elevators that connect all floors together. Padlocks are added to both sides of the door in cases where the player can approach them from either side. For doors connecting to leaf rooms (rooms with a single door), padlocks are only added to the exterior side of the door. I left some doors in the "locked without padlock" state where the original behavior applies: Any key will open these doors. This makes navigation somewhat easier for the player. Having a single color key will open a bit over half the locked doors (those without padlocks or with matching padlock colors).

Note that locked doors may not actually block the player. In some cases a room may have another door that creates an alternate path. Unlocking the door can still be useful though, as it allows for an escape route when cornered in a dead end room. Or the alternate path may be longer and take the player past a zombie or a snake on the floor.

I did want to make sure all padlocks could be unlocked and all rooms were reachable. I don't have direct control over key placement; they get added as part of the procedural item placement using a tree of random numbers. However, it's possible to iterate over all of the room objects, enumerate all of their drawers and doors, and query the items inside them. This lets the placer know which colors of keys can be found, and what rooms they're found in. The padlock colors to choose from are limited to the subset of the eight key colors that can be found in the house. If there are no keys, there are no locked doors. This isn't enough to guarantee each room is reachable though. For example, what if the only red key is inside a room where the only access door is locked with a red padlock? There's no way for the player to get inside other than clipping through a wall.

There are three cases where a room may be unreachable. For floors above the ground floor, a lock may block the only path from the room with the key to the stairs. This applies to both the stairs going up and the stairs down to the basement. For the ground floor, the lock may either block the path to the room with the key on that floor, or the path to the stairs leading to the floor with the room that has the key. As far as I'm aware, it's not possible for a locked door on any floor other than the ground floor to block the path to a room on a different floor. At least not with the houses 3DWorld can create, assuming stairs connect correctly to all floors. Stairs placed in houses will usually connect through all floors above the ground floor.

When the player uses the action key on a locked door that they have the matching key for, the padlock will fall onto the floor and the door will open. The padlock on the other side of the door just disappears. If they don't have the key, the message "Door is locked with <color> padlock" will be shown to make it more clear what color key the player needs to find to open this door. Once unlocked, the door can never be re-locked with a padlock. However, the door can be locked normally, preventing zombies from passing through it. Zombies can't unlock the door unless they kill the player and take the key. Only doors that were initially locked can be re-locked.

That reminds me of another feature I added. Building AI people and zombies will now open doors over the course of a number of frames before running into the door, and will wait until the door is fully open before passing through. When the door opens toward them, they will stand out of range so that it doesn't hit them when opening.

Here are a pair of images showing a door locked with a red padlock and the same door after it's been unlocked and opened. The key icon in the top right shows that the player is holding a key, and it contains small vertical strips in each of the eight colors that are shown when the player has that color key in their inventory. The red key has a red stripe.

That red key goes to this locked door to a room coming off the kitchen on the ground floor.

The door has been unlocked, and the padlock is left on the floor.

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.