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.